**INDUSTRY AND COMPANY AWARENESS (ICA)**

## MCQs

**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.

**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.

**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.

**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.

**Answer: Option C. ->**O(1)

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

**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.

**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 }**

__Question 7.__**Answer: Option A. ->**n+1

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

**What is wrong with the following code of insertion in fibonacci heap.**

__Question 8.__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

**Answer: Option C. ->**Line 9

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

**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) .

**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.