## MCQs

Total Questions : 10
Question 1. What is the location of parent node for any arbitary node i?
1.    (i/2) position
2.    (i+1)/ position
3.    floor(i/2) position
4.    ceil(i/2) position
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
1.    O(n*n*logn)
2.    O(n*logn)
3.    O(n*n)
4.    O(n *logn *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
1.    O(n)
2.    O(1)
3.    O(logn)
4.    O(nlogn)

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
1.    Last added element to heap
2.    First element added to heap
3.    Root of the heap
4.    Leftmost node of the heap
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;
1.    o(n)
2.    O(logn)
3.    O(1)
4.    O(n logn)

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

Question 6. Heap can be used as¦
1.    Priority queue
2.    Stack
3.    A decreasing order array
4.    None of the mentioned
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 }
1.    n+1
2.    n+n/2
3.    nlogn
4.    2*n

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
1.    Line -11
2.    Line -3
3.    Line 9
4.    Line 7
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()) }
1.    O(logn)
2.    amortized O(1)
3.    O(n)
4.    None of the mentioned
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.
1.    Yes
2.    No
3.    Both I and II
4.    None of these