This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “D-ary Heap”.
1. d-heap is similar to that of a?
a) binary heap
b) fibonacci heap
c) leftist heap
Explanation: A d-heap is similar to that of a binary heap except that binary heaps have two children and d-heaps have d children.
2. d-heap is shallower than a binary heap.
Explanation: d-heap is much shallower than a binary heap with respect to performance efficiency of insert and delete operations.
3. Which operation cannot be directly performed in a d-heap?
Explanation: Find operation in a d-heap cannot be performed as in other heaps. This is the main weakness of d-heap.
4. Which operation is not efficiently performed in a d-heap?
Explanation: Unlike find operation, which cannot be performed in a d-heap, the task of merging two d-heaps is very difficult.
5. What is the run time efficiency of an insertion algorithm in d-heap?
b) O(log N)
c) O(logd N)
Explanation: The run time efficiency of an insertion algorithm in a d-heap is found to be O(logd N) where d is the number of children.
6. How many comparisons will occur while performing a delete-min operation?
Explanation: Since, the delete-min operation is more expensive and the heap is shallow, the minimum of d elements can be found using d-1 comparisons.
7. How many basic operations can be performed in a d-heap?
Explanation: The two basic operations performed in a d-heap are insert and delete-min operations.
8. What is the run time efficiency of delete-min operation?
a) O(log N)
b) O(logd N)
c) O(d logd N)
Explanation: The run time efficiency of a delete-min algorithm using d-1 comparisons is mathematically found to be O(d logd N).
Explanation: The given heap is a d-heap since it looks like a binary heap with d- children. Here, d=3.
10. Multiplication and division to find children and parents cannot be implemented in a d-heap.
Explanation: Multiplication and division for finding children and parents can be implemented in a d-heap but d should be a power of 2.
11. How many secondary operations are performed in a d-heap?
Explanation: The other operations that can be performed in a d-heap are increasekey, decreasekey, buildheap and delete.
12. On which data structure is a d-ary heap based?
c) linked list
d) priority queue
Explanation: d-ary heap is a priority queue based data structure that is a generalization of binary heaps.
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!