Leftlist Heap Multiple Choice Questions and Answers (MCQs)

«
»

This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Leftlist Heap”.

1. Pointer manipulation is generally more time-consuming than multiplication and division.
a) true
b) false
View Answer

Answer: a
Explanation: Use of pointers for merging reduces the speed of other operations. This is the main drawback of all advanced data structures.
advertisement

2. How many properties does a leftist heap support?
a) 1
b) 2
c) 3
d) 4
View Answer

Answer: c
Explanation: A leftist heap supports two properties- structural property, ordering property and a heap order property.

3. In a leftist heap, the null path length of a null node is defined as?
a) 0
b) 1
c) null
d) -1
View Answer

Answer: d
Explanation: In a leftist heap tree, the null path length of a null node with no children is defined as -1.

4. How many nodes does a leftist tree with r nodes must have?
a) 2r
b) 2r-1
c) 2r
d) 2r-1
View Answer

Answer: b
Explanation: A leftist tree with r nodes on the right path is proved to have at least 2r-1 nodes. This theorem is proved by induction.

5. Which of the following operations does not destroy the leftist heap property?
a) insert
b) merge
c) delete
d) swap
View Answer

Answer: c
Explanation: Performing insert and merge operations on the right path could destroy the leftist heap property. It is extremely easy to restore that property.
advertisement

6. What is the fundamental operation on leftist heap?
a) insertion
b) merging
c) deletion
d) swapping
View Answer

Answer: b
Explanation: The fundamental operations on leftist heaps is merge. Insertion operation is a merge of a one-node heap with a larger heap.

7. A leftist heap is also said to be a binary heap.
a) true
b) false
View Answer

Answer: a
Explanation: A leftist heap has a structural property and an ordering property which is similar to that of a binary heap. Hence, leftist heap is also said to be binary heap.

8. 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)
View Answer

Answer: d
Explanation: The efficiency of merge operations in leftist heap is mathematically found to be O( log N) which is the same in binary heaps.

9. What is the node path length of a node with 0 or 1 child?
a) 1
b) -1
c) 0
d) null
View Answer

Answer: c
Explanation: The length of the shortest path from a node to a node without two children is defined as 0.
advertisement

10. 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
View Answer

Answer: b
Explanation: The heap is named as leftist heap because it tends to have deep left paths. It follows that the right path ought to be short.

11. In a leftist heap, all the operations should be performed on?
a) left path
b) centre path
c) right path
d) root
View Answer

Answer: c
Explanation: All the operations are performed on the right path because right paths are short. However, insertion and merges cannot be performed on the right path.

12. 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
View Answer

Answer: d
Explanation: When two leftist heaps are merged, 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, leftist property is violated at the root.

13. 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
View Answer

Answer: b
Explanation: While performing insertion via merge operation in a leftist heap, if the null path length is not updated, all null path lengths will be 0.
advertisement

14. 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)
View Answer

Answer: c
Explanation: The time taken to delete a minimum element in a leftist heap is mathematically found to be O(log N).

15. 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)
View Answer

Answer: a
Explanation: The mathematical calculation yields a result that, a leftist heap can be built in O(N) time by building a binary heap.

Sanfoundry Global Education & Learning Series – Data Structure.

To practice all areas of Data Structure, here is complete set of 1000+ Multiple Choice Questions and Answers.

advertisement
advertisement
advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn