Virtual Labs

1. What is the worst-case complexity of rebuilding a heap after the root has been replaced?

O(\log n)

Explanation

O(1)

Explanation

O(n)

Explanation

O(n\log n)

Explanation

2. Does the rebuild operation vary for max and min heaps?

a: True Explanation

Explanation

b: False Explanation

Explanation

3. What is the main purpose of the heapify operation in Heap Sort?

a: To reverse the input array Explanation

Explanation

b: To restore the heap property after a change in the heap Explanation

Explanation

c: To remove duplicate elements Explanation

Explanation

d: To search for an element by index Explanation

Explanation

4. In a max-heap represented as an array, which relationship must hold between a parent and each of its children?

a: Parent is always smaller than both children Explanation

Explanation

b: Parent and children must always be equal Explanation

Explanation

c: Parent is greater than or equal to each child Explanation

Explanation

d: Parent has no ordering relationship with its children Explanation

Explanation

5. Which statement about building a heap from an unsorted array is correct when the bottom-up method is used?

a: It always requires

O(n\log n)

time Explanation

Explanation

b: It can be done in

O(n)

time Explanation

Explanation

c: It requires

O(n^2)

time Explanation

Explanation

d: It requires

O(1)

time Explanation

Explanation

6. During Heap Sort with a max-heap, why is the root exchanged with the last element of the unsorted portion?

a: To place the current maximum in its final sorted position Explanation

Explanation

b: To make the root the minimum element Explanation

Explanation

c: To increase the heap size Explanation

Explanation

d: To avoid using heapify Explanation

Explanation

7. What is the space complexity of an in-place implementation of Heap Sort, excluding the input array?

O(n)

Explanation

O(n\log n)

Explanation

O(\log n)

Explanation

O(1)

Explanation

8. Which sequence of steps best describes Heap Sort using a max-heap for ascending order?

a: Build a max-heap, repeatedly move the root to the end of the unsorted portion, reduce the heap size, and restore the heap property Explanation

Explanation

b: Build a min-heap and repeatedly move the root to the beginning without restoring the heap Explanation

Explanation

c: Repeatedly find the minimum by scanning the entire array and place it at the end Explanation

Explanation

d: Build a max-heap once and leave the array unchanged after construction Explanation

Explanation

9. Why does Heap Sort have

O(n\log n)

worst-case time complexity?

a: Because each of the

n

elements is compared with every other element Explanation

Explanation

b: Because heap construction is

O(n^2)

Explanation

c: Because each extraction can require

O(\log n)

adjustment and this is repeated for the elements Explanation

Explanation

d: Because the array is divided into two equal parts at every step Explanation

Explanation