questions for discussion Cs iiitdm kancheepuram

Engineering mechanics

1. What is the worst-case time complexity of inserting n elements into an empty linked list, if the linked list needs to be maintained in sorted order? More than one answer may be correct.

2. Θ( n 2 )

3. What is the worst-case time complexity of inserting n 2 elements into an AVL tree with n elements initially?

4. Θ( n 2 log n)

5. The result evaluating the postfix expression 10 5 + 60 6/ * 8 –

6. The postorder traversal of a binary tree is 8,9,6,7,4,5,2,3,1 . The inorder traversal of the same tree is 8,6,9,4,7,2,5,1,3 . The height of a tree is the length of the longest path from the root to any leaf. Then the height of the binary tree is ________

7. An array [ 82,101,90, 11,111,75,33, 131,44,93] is heapified . What are the first three elements in the heapified array?

8. ​​​​​Let H be a binary min-heap consisting of n elements implemented as an array. What is the worst case time complexity of an optimal algorithm to find the maximum element in H?

9. Θ( n)

10. Given a binary-max heap. The elements are stored in an arrays as 25, 14, 16, 13, 10, 8, 12. What is the content of the array after two delete operations?

11. A queue is implemented using array, What is the time complexity of enqueue and dequeue operation ?

12. Θ( 1)

13. The queue data structure is to be realized using stack. The number of stacks required is

14. While inserting the elements 71, 65, 84, 69,67, 83 in an empty binary search tree (BST) in the sequence shown, the element in the lowest level is