Engineering Questions with Answers - Multiple Choice Questions

# Skew Heap MCQ’s

1 - Question

__________ is a self-adjusting version of a leftist heap.
a) Rightist heap
b) Skew heap
c) d-heap
d) Binary heap

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

2 - Question

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)

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

3 - Question

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)

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

4 - Question

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

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

5 - Question

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

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

6 - Question

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)

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

7 - Question

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

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

8 - Question

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

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 - Question

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)

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

10 - Question

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

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

11 - Question

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

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 - Question

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

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

13 - Question

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