# Leftlist, Skew and Min/Max Heap MCQs

Q1. How many nodes does a leftist tree with r nodes must have?.

A. 2r.

B. 2r-1.

C. 2r.

D. 2r-1.

Q2. Which of the following operations does not destroy the leftist heap property?.

A. insert.

B. merge.

C. delete.

D. swap.

Q3. What is the fundamental operation on leftist heap?.

A. insertion.

B. merging.

C. deletion.

D. swapping.

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.

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).

Q6. What is the node path length of a node with 0 or 1 child?.

A. 1.

B. -1.

C. 0.

D. null.

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.

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.

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).

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).

Q13. ___________ is a self-adjusting version of a leftist heap..

A. Rightist heap.

B. Skew heap.

C. d-heap.

D. Binary 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).

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).

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.

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).

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.

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.

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).

Q22. How many types of the merge are available in skew heaps?.

A. 1.

B. 2.

C. 3.

D. 4.

Q23. What is the amortized efficiency of skew merge?.

A. O(N).

B. O( log N).

C. O( N log N).

D. O(N2).

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.

Q25. Descending priority queue can be implemented using ______.

A. max heap.

B. min heap.

C. min-max heap.

D. trie.

Q26. Min heap can be used to implement selection sort..

A. TRUE.

B. FALSE.

C.  Nothing Can be said.

D.  None of the mentioned.

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] .

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).

Q31. Min heap is a complete binary tree..

A. TRUE.

B. FALSE.

C.  Nothing Can be said.

D.  None of the mentioned.

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.

Q34. What traversal over trie gives the lexicographical sorting of the set of the strings?.

A. postorder.

B. preorders.

C. inorder.

D. level order.