Skew Heap Multiple Choice Questions and Answers (MCQs)

«
»

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

1. ___________ is a self-adjusting version of a leftist heap.
a) Rightist heap
b) Skew heap
c) d-heap
d) Binary heap
View Answer

Answer: b
Explanation: A skew heap is a self-adjusting version of a leftist heap and it is simpler to implement.
advertisement

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

Answer: a
Explanation: The worst case running time of all operations in a skew heap is mathematically found to be O(N).

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

Answer: d
Explanation: The amortized cost per operation of a skew heap is O(log N) since the worst case analysis of skew heap is O(N) and splay tree is O(M log N).
advertisement
advertisement

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

Answer: a
Explanation: Splay tree is a self -adjusting version of AVL tree. Similarly, skew heap is a self-adjusting version of leftist heap.

5. What is the fundamental operation performed in skew heaps?
a) intersection
b) difference
c) merging
d) sorting
View Answer

Answer: c
Explanation: The fundamental operation of skew heaps is merging. Hence, it is similar to that of a leftist heap.
advertisement

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

Answer: b
Explanation: Skew heaps support merging, insertion and deletion all effectively in O(log N) time per operation.

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

Answer: c
Explanation: In skew heaps, a recursive implementation could fail because of lack of stack space even though performance is acceptable.
advertisement

8. Which of the following is difficult to determine the right path length?
a) Skew heaps
b) Binomial tree
c) Leftist heap
d) d-heap
View Answer

Answer: a
Explanation: It is an open problem to determine precisely the expected right path length of both leftist and skew heaps and comparatively, the latter is difficult.

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

Answer: a
Explanation: The worst-case analysis for the naïve merge is an insertion in a right heavy tree. So, insertion takes O(N).
advertisement

10. How many types of the merge are available in skew heaps?
a) 1
b) 2
c) 3
d) 4
View Answer

Answer: b
Explanation: Two kinds of the merge are available in skew heaps- naïve merge and skew merge.

11. Naïve merge cannot be done in a skew merge.
a) true
b) false
View Answer

Answer: b
Explanation: One way of doing skew merge is to begin with naïve merge and then swapping the left and right children of the tree.

12. What is the amortized efficiency of skew merge?
a) O(N)
b) O( log N)
c) O( N log N)
d) O(N2)
View Answer

Answer: b
Explanation: The amortized efficiency of a skew heap is mathematically found to be O( log N).

13. In skew heaps, certain constraints are to be met in order to perform swapping.
a) true
b) false
View Answer

Answer: b
Explanation: In skew heaps, swaps are unconditional. It is done with the exception that the largest of all nodes does not have its children swapped.

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.

Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

advertisement
advertisement
Manish Bhojasia - Founder & CTO at Sanfoundry
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 | Youtube | Instagram | Facebook | Twitter