GATE 2019 - P&DS Quiz-10 (Binary Heap )

Attempt now to get your rank among 633 students!

Question 1

Which languages necessarily need heap allocation in the run time environment?

• AThose that support recursion
• BThose that use dynamic scoping
• CThose that use global variables
• DThose that allow dynamic data structures

Question 2

Consider the following “Max-heapify” algorithm.Array has size at least n and 1in.After applying The Max-heapify noded at A[i], the result will be the subtree of A[1,….n] rooted at A[i] is a max-heapify.{ Assume that except root A[i], all its children satisfies heap property]
Max –heapify (int A[ ], int n,int i)
{ int p,m;
p = i;
while (2pn)
{
if(Y && Z)
m = 2p+1;
else m =2p;
if(A[p]<A[m])
[swap (A[p],A[m]);
p=m;
_}
else
return ;
}
}
Find missing statement at Y and Z respectively to apply the heapify for subtree rooted at A[i].

• A(2p+1) n, A[2p+1] > A[2p]
• B(2p+1) n, A[2p+1] > A[2p]
• C(2p+1) n, A[2p+1] < A[2p]
• D(2p+1) n, A[2p+1] < A[2p]

Question 3

Given an array, its size n, and an index I into that array, provided that binary trees rooted at left (i) and right (i) are min-heaps, how much time does it take to have a min heap rooted at i. 

• AO(n)
• BO(log n)
• CO(1)
• DO(nlogn)

Question 4

Consider the following elements in a heap {17, 9, 6, 3, 12, 2, 15, 14, 20, 13, 21}. The minimum number of exchanges to convert it into a minheap is

• A5
• B4
• C6
• D3

Question 5

Assume there are n/logn min heap trees are available, each of size logn. What is the time complexity to find the smallest and greatest element respectively?

• AO(n/logn) and O(n)
• BO(logn) and O(logn)
• CO(n) and O(n)
• DO(n) and O(n/logn)

Question 6

A priority queue is implemented as a Max-Heap. Initially, it has 5 elements. The level-order traversal of the heap is : 10, 8, 5, 3, 2. Two new elements 1 and 7 are inserted into the heap in that order. The level-order traversal of the heap after the insertion of the elements is

• A10, 8, 7, 3, 2, 1, 5
• B10, 8, 7, 2, 3, 1, 5
• C10, 8, 7, 1, 2, 3, 5
• D10, 8, 7, 5, 3, 2, 1

• 633 attempts
• 3 upvotes
• 10 comments