Virtual Labs

1. Which of the following sorting algorithms, in its typical implementation, gives the best performance when applied to an array that is sorted or almost sorted (with at most 1 or 2 elements misplaced)?

a: Quick Sort Explanation

Explanation

b: Heap Sort Explanation

Explanation

c: Merge Sort Explanation

Explanation

d: Insertion Sort Explanation

Explanation

2. Consider a full binary min-heap containing

n

elements with distinct keys. What is the probability that the largest element is at the last level?

1/2

Explanation

b: 1 Explanation

Explanation

1/n

Explanation

1/2^n

Explanation

3. In a max-heap, the element with the greatest key is always in which node?

a: Leaf node Explanation

Explanation

b: First node of left subtree Explanation

Explanation

c: Root node Explanation

Explanation

d: First node of right subtree Explanation

Explanation

4. Heap can also be used as _______.

a: Priority queue Explanation

Explanation

b: Stack Explanation

Explanation

c: A decreasing order array Explanation

Explanation

d: None of these Explanation

Explanation

5. An array consists of

n

elements. We want to create a heap using these elements. The time complexity of building a heap will be in the order of ________.

O(n^2\log n)

Explanation

O(n)

Explanation

O(n^2)

Explanation

O(n(\log n)^2)

Explanation

6. Which of the following is the main reason Heap Sort has

O(n\log n)

worst-case time complexity?

a: It performs a linear search for every element Explanation

Explanation

b: It repeatedly partitions the array into equal halves Explanation

Explanation

c: It compares every pair of elements Explanation

Explanation

d: It performs a linear number of heap adjustments, each taking up to

O(\log n)

time Explanation

Explanation

7. Which of the following statements about Heap Sort is correct?

a: Heap Sort always requires

O(n^2)

time Explanation

Explanation

b: Heap Sort can be implemented in-place with

O(1)

auxiliary space Explanation

Explanation

c: Heap Sort requires a second array of size

n

Explanation

d: Heap Sort is stable in its standard in-place implementation Explanation

Explanation

8. For ascending-order Heap Sort, why is a max-heap commonly used?

a: Because the maximum element can be placed at the end of the unsorted portion after each extraction Explanation

Explanation

b: Because a max-heap automatically sorts the array without extraction Explanation

Explanation

c: Because a max-heap always contains the minimum element at the root Explanation

Explanation

d: Because max-heaps require no comparisons during sorting Explanation

Explanation

9. If the input array contains

n

elements, what is the worst-case time complexity of Heap Sort?

O(n)

Explanation

O(\log n)

Explanation

O(n\log n)

Explanation

O(n^2)

Explanation