1. d-heap is similar to that of a?
a) binary heap
b) fibonacci heap
c) leftist heap
d) treap
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.
2. d-heap is shallower than a binary heap.
a) true
b) false
Answer: a
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?
a) insert
b) delete
c) find
d) create
Answer: c
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?
a) insert
b) delete
c) find
d) merge
Answer: d
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?
a) O(N)
b) O(log N)
c) O(logd N)
d) O(Nd)
Answer: c
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?
a) d
b) d-1
c) d+1
d) 1
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.
7. How many basic operations can be performed in a d-heap?
a) 1
b) 2
c) 3
d) 4
Answer: b
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)
d) O(d)
Answer: c
Explanation:
The run time efficiency of a delete-min algorithm using d-1 comparisons is mathematically found to be O(d logd N).
9. The Statement “Fibonacci heap has better amortized running time in compare to a binomial heap”.
a) True
b) False
Answer: a
Explanation:
Overall complexity of insertion, merging, deleting is in order of O((a+b)logn) For Fibonacci the complexity reduces to O(a+ blogn).
10. Multiplication and division to find children and parents cannot be implemented in a d-heap.
a) true
b) false
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.
11. How many secondary operations are performed in a d-heap?
a) 1
b) 2
c) 3
d) 4
Answer: d
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?
a) stack
b) queue
c) linked list
d) priority queue
Answer: d
Explanation:
d-ary heap is a priority queue based data structure that is a generalization of binary heaps.
13. What will be the order of new heap created after union of heap H1 and H2 when created by the following code.Initially both are of the order n.
FIB_UNION(H1,H2)
{
H =MAKE_HEAP()
min[H]= min[H1]
concatenate the root list of H2 with the root list of H
if (min[H1] = NIL) or (min[H2]!= NIL and min[H2] < min[H1])
then min[H] = min[H2]
n[H]= n[H1] + n[H2]
free the objects H1 and H2
return H
}
a) n+1
b) n+n/2
c) nlogn
d) 2*n
Answer: a
Explanation:
Union of two trees increase the order of the resultant by atmost value 1.
14. Who invented k-d trees?
a) Arne Andersson
b) Jon Bentley
c) Jon Von Newmann
d) Rudolf Bayer
Answer: b
Explanation:
Jon Bentley found k-d trees. Rudolf Bayer found red black trees. Arne Andersson found AA- trees.
15. What is the condition for an equivalence relation if two cities are related within a country?
a) the two cities should have a one-way connection
b) the two cities should have a two-way connection
c) the two cities should be in different countries
d) no equivalence relation will exist between two cities
Answer: b
Explanation:
If the two towns are in the same country and have a two-way road connection between them, it satisfies equivalence property.
16. Reversal algorithm and juggling algorithm for array rotation have the same time complexity.
a) True
b) False
Answer: a
Explanation:
Time complexity of juggling algorithm is O(n) which like that of reversal algorithm. They also have the same space complexity
