Sail E0 Webinar


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
 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
  1.    O(n*n*logn)
  2.    O(n*logn)
  3.    O(n*n)
  4.    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
  1.    O(n)
  2.    O(1)
  3.    O(logn)
  4.    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
  1.    Last added element to heap
  2.    First element added to heap
  3.    Root of the heap
  4.    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;
  1.    o(n)
  2.    O(logn)
  3.    O(1)
  4.    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¦
  1.    Priority queue
  2.    Stack
  3.    A decreasing order array
  4.    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 }
  1.    n+1
  2.    n+n/2
  3.    nlogn
  4.    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
  1.    Line -11
  2.    Line -3
  3.    Line 9
  4.    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()) }
  1.    O(logn)
  2.    amortized O(1)
  3.    O(n)
  4.    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.
  1.    Yes
  2.    No
  3.    Both I and II
  4.    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.

Latest Videos

Latest Test Papers