Engineering Questions with Answers - Multiple Choice Questions

# Data Structure MCQ – Binary Heap

1 - Question

What is the space complexity of searching in a heap?
a) O(logn)
b) O(n)
c) O(1)
d) O(nlogn)

Explanation: The space complexity of searching an element in heap is O (n). Heap consists of n elements and we need to compare every element. Here no addition or deletion of elements takes place. Hence space complexity is O (n).

2 - Question

What is the best case complexity in building a heap?
a) O(nlogn)
b) O(n2)
c) O(n*longn *logn)
d) O(n)

Explanation: The best case complexity occurs in bottom-up construction when we have a sortes array given.

3 - Question

Given the code, choose the correct option that is consistent with the code. (Here A is the heap)

```	build(A,i)
left-> 2*i
right->2*i +1
temp- > i
if(left<= heap_length[A] ans A[left] >A[temp])
temp -> left
if (right = heap_length[A] and A[right] > A[temp])
temp->right
if temp!= i
swap(A[i],A[temp])
build(A,temp)```

a) It is the build function of max heap
b) It is the build function of min heap
c) It is general build function of any heap
d) It is used to search element in any heap

Explanation: Since in every condition we are comparing the current value is less than the parent of that node. So this is build function of Max heap.

4 - Question

What is the location of a parent node for any arbitary node i?
a) (i/2) position
b) (i+1)/ position
c) floor(i/2) position
d) ceil(i/2) position

Explanation: 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.

5 - Question

State the complexity of algorithm given below.

```	int function(vector<int> arr)
int len=arr.length();
if(len==0)
return;
temp=arr[len-1];
arr.pop_back();
return temp;```

a) o(n)
b) O(logn)
c) O(1)
d) O(n logn)

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

6 - Question

Given an array of element 5, 7, 9, 1, 3, 10, 8, 4. Which of the following are the correct sequences of elements after inserting all the elements in a min-heap?
a) 1,3,4,5,7,8,9,10
b) 1,4,3,9,8,5,7,10
c) 1,3,4,5,8,7,9,10
d) 1,3,7,4,8,5,9,10

Explanation: Building a min-heap the result will a sorted array so the 1, 3, 4, 5, 7, 8, 9, 10 is correct. If we change the implementation strategy 1, 4, 3, 8, 9, 5, 7, 10 is also correct. (First filling the right child rather than left child first).

7 - Question

For construction of a binary heap with property that parent node has value less than child node. In reference to that which line is incorrect. Line indexed from 1.

```1. add(int k)
2. {
3.     heap_size++;
4.     int i = heap_size - 1;
5.     harr[i] = k;
6.     while (i != 0 && harr[parent(i)] < harr[i])
7.     {
8.             swap(&harr[i], &harr[parent(i)]);
9.             i = parent(i);
10.    }
11. }```

a) Line – 3
b) Line – 5
c) Line – 6
d) Line – 7