Engineering Questions with Answers - Multiple Choice Questions

Home » MCQs » Aeronautical Engineering » D-ary Heap Multiple Choice MCQ

# D-ary Heap Multiple Choice MCQ

d-heap is similar to that of a?

a) binary heap

b) fibonacci heap

c) leftist heap

d) treap

**
View Answer**

Answer: a

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.

d-heap is shallower than a binary heap.

a) true

b) false

**
View Answer**

Answer: a

Explanation: d-heap is much shallower than a binary heap with respect to performance efficiency of insert and delete operations.

Which operation cannot be directly performed in a d-heap?

a) insert

b) delete

c) find

d) create

**
View Answer**

Answer: c

Explanation: Find operation in a d-heap cannot be performed as in other heaps. This is the main weakness of d-heap.

Which operation is not efficiently performed in a d-heap?

a) insert

b) delete

c) find

d) merge

**
View Answer**

Answer: d

Explanation: Unlike find operation, which cannot be performed in a d-heap, the task of merging two d-heaps is very difficult.

What is the run time efficiency of an insertion algorithm in d-heap?

a) O(N)

b) O(log N)

c) O(log_{d} N)

d) O(N^{d})

**
View Answer**

Answer: c

Explanation: The run time efficiency of an insertion algorithm in a d-heap is found to be O(log_{d} N) where d is the number of children.

How many comparisons will occur while performing a delete-min operation?

a) d

b) d-1

c) d+1

d) 1

**
View Answer**

Answer: b

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.

How many basic operations can be performed in a d-heap?

a) 1

b) 2

c) 3

d) 4

**
View Answer**

Answer: b

Explanation: The two basic operations performed in a d-heap are insert and delete-min operations.

What is the run time efficiency of delete-min operation?

a) O(log N)

b) O(log_{d} N)

c) O(d log_{d} N)

d) O(d)

**
View Answer**

Answer: c

Explanation: The run time efficiency of a delete-min algorithm using d-1 comparisons is mathematically found to be O(d log_{d} N).

The following figure is an example for

a) d-heap

b) binary heap

c) leftist heap

d) skew heap

**
View Answer**

Answer: a

Explanation: The given heap is a d-heap since it looks like a binary heap with d- children. Here, d=3.

Multiplication and division to find children and parents cannot be implemented in a d-heap.

a) true

b) false

**
View Answer**

Answer: b

Explanation: Multiplication and division for finding children and parents can be implemented in a d-heap but d should be a power of 2.

How many secondary operations are performed in a d-heap?

a) 1

b) 2

c) 3

d) 4

**
View Answer**

Answer: d

Explanation: The other operations that can be performed in a d-heap are increasekey, decreasekey, buildheap and delete.

On which data structure is a d-ary heap based?

a) stack

b) queue

c) linked list

d) priority queue

**
View Answer**

Answer: d

Explanation: d-ary heap is a priority queue based data structure that is a generalization of binary heaps.