Free Printable HEAP TREE

Worksheets

HEAP TREE

Total questions: 20

Worksheet time: 10mins

Name

Class

Date

Which of the following is a max-heap?

Consider a binary max-heap implemented using an array. Which one of the following array represents a binary max-heap?

25,12,16,13,10,8,14

25,12,16,10,13,8,14

25,14,16,13,10,8,12

25,14,12,13,10,8,16

In a binary max heap containing n numbers, the smallest element can be found in time ?

O(n)

O( Log(n) )

O( Log(Log(n)) )

O(1)

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.

Consider a max heap, represented by the array: 40, 30, 20, 10, 15, 16, 17, 8, 4. Now consider that a value 35 is inserted into this heap. After insertion, the new heap is

40, 30, 20, 10, 15, 16, 17, 8, 4, 35

40, 35, 20, 10, 30, 16, 17, 8, 4, 15

40, 30, 20, 10, 35, 16, 17, 8, 4, 15

40, 35, 20, 10, 15, 16, 17, 8, 4, 30

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

The number of nodes of height h in any complete n - element binary heap is

$h$

$2^h$

$\lceil\frac{n}{2^h}\rceil$ ( Ceiling function )

$\lceil\frac{n}{2^{h+1}}\rceil$ ( Ceiling Function )

Given a binary-max heap. The elements are stored in an arrays as 25, 14, 16, 13, 10, 8, 12. What is the content of the array after two delete operations?

14,13,8,12,10

14,12,13,10,8

14,13,12,8,10

14,13,12,10,8

What is the best case Time Complexity of Heap Sort?

$O\left(n\ \cdot\ \log n\right)$

$O\left(n^2\right)$

$O\left(n\right)$

$O\left(\log\left(\log n\right)\right)$

10.

On which algorithm is heap sort based on?

Fibonacci heap

Binary tree

Priority queue

FIFO

11.

Identify the wrong statement

All BST are binary trees

Max-Heap is a complete binary tree

All binary trees are BST

AVL tree is a height balanced BST

12.

What is the time complexity of inserting an element into a binary max-heap?

O(1)

O(log n)

O(n)

O(n log n)

13.

In a binary max-heap, if the root node is removed, what is the next step to maintain the heap property?

Replace it with the last element and heapify down

Replace it with the first element and heapify up

Replace it with the smallest child

Do nothing, the heap is already valid

14.

What is the time complexity of deleting the maximum element from a binary max-heap?

O(1)

O(log n)

O(n)

O(n log n)

15.

In a binary max-heap, if the last element is removed, what happens to the structure of the heap?

The heap remains unchanged

The heap must be re-heapified

The last element becomes the new root

All elements are shifted to the left

16.

Which of the following is a property of a binary max-heap?

Every parent node is less than or equal to its children

The height of the tree is minimized

The maximum element is always at the root

All leaves are at the same level

17.

In a binary max-heap, what is the maximum number of nodes at level l?

2^l

2^{l+1}-1

2^l-1

2^{l+1}

18.

Which of the following operations is not typically supported by a binary max-heap?

Insert

Delete Max

Find Min

Heapify

19.

What is the space complexity of a binary max-heap?

O(1)

O(n)

O(log n)

O(n log n)

20.

In a binary max-heap, how is the parent node's index calculated from its child node's index?

index/2

index*2

$(\lfloor index\ -\ 1\rfloor)/2$

$(\lfloor index+1\rfloor)/2$

100 %

HEAP TREE

Total questions: 20

Worksheet time: 10mins

Similar Resources on Wayground