Q1. How many nodes does a leftist tree with r nodes must have?.
A. 2r.
B. 2r-1.
C. 2r.
D. 2r-1.
Answer= 2r-1
Q2. Which of the following operations does not destroy the leftist heap property?.
A. insert.
B. merge.
C. delete.
D. swap.
Answer= delete
Q3. What is the fundamental operation on leftist heap?.
A. insertion.
B. merging.
C. deletion.
D. swapping.
Answer= merging
Q4. A leftist heap is also said to be a binary heap..
A. TRUE.
B. FALSE.
C. Nothing can be said.
D. None of the mentioned.
Answer= TRUE
Q5. What is the efficiency of merge used in leftist heaps?.
A. O(N).
B. O(N log N).
C. O(M log N).
D. O(log N).
Answer= O(log N)
Q6. What is the node path length of a node with 0 or 1 child?.
A. 1.
B. -1.
C. 0.
D. null.
Answer= 0
Q7. Why is this heap named leftist heap?.
A. only left subtrees exist.
B. the tree is biased to get deep down the left.
C. it is balanced.
D. right trees are unbalanced.
Answer= the tree is biased to get deep down the left
Q8. In a leftist heap, all the operations should be performed on?.
A. left path.
B. centre path.
C. right path.
D. root.
Answer= right path
Q9. What would be the result if the left subtree of the root has a null path length of 1 and the right subtree has a null path length of 2?.
A. merge occurs without violation.
B. violation at left subtree.
C. violation at right subtree.
D. violation at the root.
Answer= violation at the root
Q10. What happens if the null path length is not updated?.
A. error occurs.
B. all null path lengths will be 0.
C. all null path lengths will be -1.
D. all null path lengths will be 1.
Answer= all null path lengths will be 0
Q11. What is the time taken to delete a minimum element in a leftist heap?.
A. O(N).
B. O(N log N).
C. O(log N).
D. O(M log N).
Answer= O(log N)
Q12. In what time can a leftist heap be built?.
A. O(N).
B. O(N log N).
C. O(log N).
D. O(M log N).
Answer= O(N)
Q13. ___________ is a self-adjusting version of a leftist heap..
A. Rightist heap.
B. Skew heap.
C. d-heap.
D. Binary heap.
Answer= Skew heap
Q14. The worst case running time of all operations in a skew heap is given as?.
A. O(N).
B. O(N log N).
C. O(N2).
D. O(M log N).
Answer= O(N)
Q15. What is the amortized cost per operation of a skew heap?.
A. O(N).
B. O(N log N).
C. O(N2).
D. O(log N).
Answer= O(log N)
Q16. The relationship of skew heaps to leftist heaps is analogous to that of?.
A. Splay tree and AVL tree.
B. Red black tree and AVL tree.
C. Binary tree and Splay tree.
D. Binary tree and Red black tree.
Answer= Splay tree and AVL tree
Q17. What is the fundamental operation performed in skew heaps?.
A. intersection.
B. difference.
C. merging.
D. sorting.
Answer= merging
Q18. What is the time per operation of merging, insertion and deletion operations in a skew heap?.
A. O(N).
B. O(log N).
C. O(N log N).
D. O(N2).
Answer= O(log N)
Q19. Why would a recursive implementation fail in skew heaps?.
A. skew heaps are self adjusting.
B. efficiency gets reduced.
C. lack of stack space.
D. time complexity.
Answer= lack of stack space
Q20. Which of the following is difficult to determine the right path length?.
A. Skew heaps.
B. Binomial tree.
C. Leftist heap.
D. d-heap.
Answer= Skew heaps
Q21. The worst case analysis for a naïve merge is given as?.
A. O(N).
B. O( log N).
C. O( N log N).
D. O(N2).
Answer= O(N)
Q22. How many types of the merge are available in skew heaps?.
A. 1.
B. 2.
C. 3.
D. 4.
Answer= 2
Q23. What is the amortized efficiency of skew merge?.
A. O(N).
B. O( log N).
C. O( N log N).
D. O(N2).
Answer= O( log N)
Q24. In skew heaps, certain constraints are to be met in order to perform swapping..
A. TRUE.
B. FALSE.
C. Nothing can be said.
D. None of the mentioned.
Answer= FALSE
Q25. Descending priority queue can be implemented using ______.
A. max heap.
B. min heap.
C. min-max heap.
D. trie.
Answer= max heap
Q26. Min heap can be used to implement selection sort..
A. TRUE.
B. FALSE.
C. Nothing Can be said.
D. None of the mentioned.
Answer= TRUE
Q27. The ascending heap property is ___________.
A. A[Parent(i)] =A[i] .
B. A[Parent(i)] <= A[i] .
C. A[Parent(i)] >= A[i] .
D. A[Parent(i)] > 2 * A[i] .
Answer= A[Parent(i)] <= A[i]
Q28. The procedure FindMin() to find the minimum element and the procedure DeleteMin() to delete the minimum element in min heap take _________.
A. logarithmic and linear time constant respectively.
B. constant and linear time respectively.
C. constant and quadratic time respectively.
D. constant and logarithmic time respectively.
Answer= constant and logarithmic time respectively
Q29. Which one of the following array elements represents a binary min heap?.
A. 12 10 8 25 14 17.
B. 8 10 12 25 14 17.
C. 25 17 14 12 10 8.
D. 14 17 25 10 12 8.
Answer= 8 10 12 25 14 17
Q30. In a binary min heap containing n elements, the largest element can be found in __________ time..
A. O(n).
B. O(nlogn).
C. O(logn).
D. O(1).
Answer= O(n)
Q31. Min heap is a complete binary tree..
A. TRUE.
B. FALSE.
C. Nothing Can be said.
D. None of the mentioned.
Answer= TRUE
Q32. What will be the position of 5, when a max heap is constructed on the input elements 5, 70, 45, 7, 12, 15, 13, 65, 30, 25?.
A. 5 will be at root.
B. 5 will be at last level.
C. 5 will be at second level.
D. 5 can be anywhere in heap.
Answer= 5 will be at last level
Q33. Trie is also known as _________.
A. Digital Tree.
B. Treap.
C. Binomial Tree.
D. 2-3 Tree.
Answer= Digital Tree
Q34. What traversal over trie gives the lexicographical sorting of the set of the strings?.
A. postorder.
B. preorders.
C. inorder.
D. level order.
Answer= inorder
Q35. Which of the following is the efficient data structure for searching words in dictionaries?.
A. BST.
B. Linked List.
C. Balancded BST.
D. Trie.
Answer= Trie