CS301 Quiz 4 by VU Topper RM

In a perfect binary tree of height h, the total number of nodes N is

A. 2h+1 +1 B. 2h-1 + 1 C. 2h-1 – 1

D. 2h+1 – 1

One requirement to construct a max heap tree is _________. A. The tree must be strictly binary tree B. The tree must be AVL tree C. The tree must be binary search three

D. The tree must be complete binary tree

In heap data structure, the time required for buildHeap() method will be proportional to ___________.

A. N

B. Log2 n C. Nlog2 N D. N2

Consider a max heap, represented by the following array: 40,30,20,10,15,16,17,8,4 Which of the following is the index of the parent of node 15? A. 2 B. 3 C. 0

D. 1

In heap, insertion takes unit time if _________________. A. Insertion is done at level 1 B. Key percolates up to the root

C. Insertion is done at leaf node

D. Insertion is done at level 2 Which of the following statement concerning heaps is NOT true? A. A heap can be used to sort data. B. A heap can be stored in an array. C. A heap can be stored in a binary search tree. D. A heap can be used to implement a priority queue.

Consider a min heap, represented by the following array: 2,5,6,7,8 After calling the function deleteMin().Which of the following is the updated min heap? A. 5,7,8,6 B. 5,8,6,7

C. 5,6,7,8

D. 5,7,6,8

In deletion, ________ method reorganizes the min heap.

A. PercolateDown

B. Percolate_Below C. IncreaseKey D. DecreaseK

A perfect binary tree is constructed using 127 nodes then what will be sum of heights of nodes?

1. 121
2. 118
3. 119
4. 120

Correct answer: 120

Which of the following statement concerning heaps is NOT true?

1. Removing the item at the top provides immediate access to the key value with highest (or lowest) priority.
2. A heap may be stored in an array.
3. Traversing a heap in order provides access to the data in numeric or alphabetical order.
4. Inserting an item is always done at the end of the array, but requires maintaining the heap property

Correct answer: Traversing a heap in order provides access to the data in numeric or alphabetical order.

Which one of the following array elements represents a min heap?

1. 9,11,13,10,15,18
2. 9,7,13,26,15,18
3. 9,11,8,26,15,18
4. 9,11,13,26,15,18

Correct answer: 9,7,13,26,15,18

Q1. Vu-Topper RM (1 marks)

A pair of sets which does not have any ________ element are called disjoint sets

A. Common

B. Different C. Null D. Uncommon

Q2. Vu-Topper RM (1 marks)

Which of the following is NOT true regarding the maze generation?

1. Remove a randomly chosen wall if the cells it separates are already in the same set.
2. Randomly remove walls until the entrance and exit cells are in the same set.
3. Removing a wall is the same as doing a union operation.
4. Do not remove a randomly chosen wall if the cells it separates are already in the same set.

Correct answer: Randomly remove walls until the entrance and exit cells are in the same set.

Q3. Vu-Topper RM (1 marks)

A table consists of several columns, known as