Questions and answers for exam Preparation

MCQs

Total Questions : 10

Question 1. What is the location of parent node for any arbitary node i?

(i/2) position
(i+1)/ position
floor(i/2) position
ceil(i/2) position

Discuss Question

Answer: Option C. -> floor(i/2) position

For any node child nodes are located at either 2*i , 2*i +1 So the parent node could be found by taking the floor of the half of child node.

Question 2. An array consist of n elements.We want to create a heap using the elements.The time complexity of building a heap will be in order of

O(n*n*logn)
O(n*logn)
O(n*n)
O(n *logn *logn)

Discuss Question

Answer: Option B. -> O(n*logn)

The total time taken will be N times the complexity of adding a single element to the heap .And adding a single element takes logN time,so That is equal to N*logN.

Question 3. Time taken in decreasing the node value in a binomial heap is

O(n)
O(1)
O(logn)
O(nlogn)

Discuss Question

Answer: Option C. -> O(logn)

Decreasing a node value may result in violating the min property. As a result be there would be exchange in the value of parent and child which at max goes up to height of the heap.

Question 4. What does this pseudo_code return ?int myfun(heap_arr[]) { int mini=INF; for(int i=0;i

Last added element to heap
First element added to heap
Root of the heap
Leftmost node of the heap

Discuss Question

Answer: Option C. -> Root of the heap

The function return minimum value in the heap_Array which is equal to the root value of the heap.

Question 5. State the complexity of algorithm given belowint function(vector arr) int len=arr.length(); if(len==0) return; temp=arr[len-1]; arr.pop_back(); return temp;

o(n)
O(logn)
O(1)
O(n logn)

Discuss Question

Answer: Option C. -> O(1)

Deletion in a min-heap is in O(1) time.

Question 6. Heap can be used as¦

Priority queue
Stack
A decreasing order array
None of the mentioned

Discuss Question

Answer: Option A. -> Priority queue

The property of heap that the value of root must be either greater or less than both of its children makes it work like a priority queue.

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

n+1
n+n/2
nlogn
2*n

Discuss Question

Answer: Option A. -> n+1

Union of two trees increase the order of the resultant by atmost value 1.

Question 8. What is wrong with the following code of insertion in fibonacci heap.
Choose the correct optionFIB-INSERT(H, x) degree[x]= 0 p[x]= NIL child[x] =NIL left[x] =x right[x] =x mark[x] =FALSE concatenate the root list containing x with root list H if min[H] = NIL or key[x] > key[min[H]] then min[H]= x n[H]= n[H] + 1

Line -11
Line -3
Line 9
Line 7

Discuss Question

Answer: Option C. -> Line 9

The main characteristics of a Fibonacci heap is violated since min[H] must contain one with smallest value.

Question 9. What is the complexity of given function of insertion.
insert(int n) { if(buffer_size()< maxi_biffer_size()) buffer_aar[ind]==n; else move_to_heap(buffer,buffer+maxi_buffer_size()) }

O(logn)
amortized O(1)
O(n)
None of the mentioned

Discuss Question

Answer: Option B. -> amortized O(1)

e use a buffer array to store a fixed number of elements when the buffer is full the content of buffer is moved to heap.As a result the complexity is amotized O(1) .

Question 10. Does there exist a heap with seven distinct elements so that the In order traversal gives the element in sorted order.

Yes
No
Both I and II
None of these

Discuss Question

Answer: Option B. -> No

No, The inorder traversal will not give elements in sorted order. As heap is implemented as either min-heap or max-heap ,the root
will be have highest or lowest value than remaining values of the nodes .So this traversal will not give a sorted list.