Heap-Tree

Question 1

Consider the array representation of a binary min-heap containing 1023 elements. The minimum number of comparisons required to find the maximum in the heap is _______.

A
511
Question 1 Explanation: 
The binary heap contains 1023 elements. When it performs minimum comparisons it will take Ceil(n/2)
n=1023
= Ceil(1023/2)
= 512
So, the maximum element is also part of n/2.
So, we have to subtract from the total elements
= 512-1
= 511
Question 2

The minimum number of interchanges needed to convert the array

 89, 19, 40, 17, 12, 10, 2, 5, 7, 11, 6, 9, 70  

into a heap with the maximum element at the root is

A
0
B
1
C
2
D
3
Question 2 Explanation: 
Lets draw first heap from given sequence,

Question 3

Consider any array representation of an n element binary heap where the elements are stored from index 1 to index n of the array. For the element stored at index i of the array (i≤n), the index of the parent is

A
i-1
B
⌊i/2⌋
C
⌈i/2⌉
D
(i+1)/2
Question 3 Explanation: 
Parent Node is at index: ⌊i/2⌋
Left Child is at index: 2i
Right child is at index: 2*i+1
Question 4

In a heap with n elements with the smallest element at the root, the 7th smallest element can be found in time

A
Θ(n log n)
B
Θ(n)
C
Θ(log n)
D
Θ(1)
Question 4 Explanation: 
The 7th smallest elements can be present in any of 7 levels. Then total possible elements can be present is seven levels is
1 + 2 + 4 + 6 + 8 + 16 + 32
Which is constant then we can find the 7th smallest element in Θ(1) time.
Question 5

The elements 32, 15, 20, 30, 12, 25, 16 are inserted one by one in the given order into a Max Heap. The resultant Max Heap is

A
B
C
D
Question 5 Explanation: 
32, 15, 20, 30, 12, 25, 16






Question 6

Which of the following sequences of array elements forms a heap?

A
{23, 17, 14, 6, 13, 10, 1, 12, 7, 5}
B
{23, 17, 14, 6, 13, 10, 1, 5, 7, 12}
C
{23, 17, 14, 7, 13, 10, 1, 5, 6, 12}
D
{23, 17, 14, 7, 13, 10, 1, 12, 5, 7}
Question 6 Explanation: 

In this every children and parent satisfies Max heap properties.
Question 7

Consider the following array of elements. 〈89, 19, 50, 17, 12, 15, 2, 5, 7, 11, 6, 9, 100〉. The minimum number of interchanges needed to convert it into a max-heap is

A
4
B
5
C
2
D
3
Question 7 Explanation: 
Let's first draw heap from the given array,

→ Swap 100 & 15

→ Swap 100 & 50

→ Swap 89 & 100

∴ Total 3 interchanges are needed.
Question 8

Consider a complete binary tree where the left and the right subtrees of the root are max-heaps. The lower bound for the number of operations to convert the tree to a heap is

A
Ω(logn)
B
Ω(n)
C
Ω(nlog n)
D
Ω(n2)
Question 8 Explanation: 
Since left and right subtree is already a heap. So we can apply Heapify (node) which take log n time.
Question 9

A complete binary min-heap is made by including each integer in [1, 1023] exactly once. The depth of a node in the heap is the length of the path from the root of the heap to that node. Thus, the root is at depth 0. The maximum depth at which integer 9 can appear is _________.

A
8
B
9
C
10
D
11
Question 9 Explanation: 

This is not possible because it violates a property of complete binary tree.
We have total [0, 1023] elements. It means that

∴ 20 + 21 + 22 + ⋯ + 2k = 1024
Add if 1(2(k+1)-1)/(2-1) [using formula for sum of k terms k+1 in G.P]
= 2(k+1) - 1 = 1024 - 1 = 1023
∴ The level ‘9’ at the depth of 8.
Actually we have 1023 elements, we can achieve a complete binary min heap of depth 9, which would cover all 1023 elements, but the max depth of node 9 can be only be 8.
There are 9 questions to complete.

Access quiz wise question and answers by becoming as a solutions adda PRO SUBSCRIBER with Ad-Free content

Register Now

If you have registered and made your payment please contact solutionsadda.in@gmail.com to get access