## 1. ___________ is a self-adjusting version of a leftist heap.

**a) Rightist heap****b) Skew heap****c) d-heap****d) Binary heap**

**Answer: b**

**Explanation: **

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

## 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)**

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

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

## 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 treea**

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

**Answer: c**

**Explanation:**

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

## 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)**

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

**Answer: c**

**Explanation:**

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

## 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**

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

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

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

**a) 1****b) 2****c) 3****d) 4**

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

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

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

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

## 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)**

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

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

## 16. What is the time complexity for creating a ternary heap using swapping?

**a) O (log n/ log 3)****b) O (n!)****c) O (n)****d) O (1)**

**Answer: c**

**Explanation:**

** Ternary Heap can be formed by two swapping operations. Therefore, the time complexity for creating a ternary heap using two swapping operation is found to be O (n).**

- Know About Most Powerful Jagannath Temple, Puri
- Top Story About Ghatgan Tarini Temple, Keonjhar District
- Positive / Negative Impacts of Social Media on Students
- TOP 20+ MCQs on Data Structure with Answers
- TOP MCQs on Data Structure with Answers
- TOP MCQs on Rotation Array Operation Data Structure with Answers
- TOP MCQs on Preorder Traversal Data Structure with Answers
- TOP MCQs on Postorder Traversal Data Structure with Answers