MCQ Questions

Q1: MaxHeap Insert (Heapify Result)

The array [15, 1, 13, 2, 6, 3, 19] is being sorted using heapsort. The max-heapify operation has just completed. What does the array look like now?

• [19, 13, 15, 2, 6, 1, 3]
• [19, 13, 15, 2, 3, 6, 1]
• [19, 6, 15, 1, 2, 3, 13]
• [19, 6, 15, 2, 1, 3, 13]

Explanation: Sift down from the root after replacing it with the largest leaf — the heap property settles to a left-biased layout where the second level is (13, 15) and the leaves preserve insertion order.

Q2: Topological Sort

Which of the following is/are valid topological orders for the graph below?

Edges: 2 → 8, 8 → 7, 8 → 4, 7 → 4, 4 → 9, 5 → 9.

• 245789
• 578249
• 527849
• 257849

Explanation: Any valid order must place 2 before 8, 8 before 7 and 4, 7 before 4, 4 and 5 before 9. 527849 and 257849 are both consistent with those constraints; the other two violate at least one edge.

Q3: Undirected Graph with n − 1 Edges

Given an undirected graph with n nodes and n − 1 edges. Which statement is correct?

• The shortest path between any two pairs of nodes will always be unique.
• There exists a connected component which is a tree.
• Both A and B
• None of the above

Explanation: n − 1 edges does not force connectivity (you can have a cycle plus an isolated node), so the graph isn't necessarily a single tree. But by pigeonhole / acyclic-component counting, at least one connected component is acyclic — i.e. a tree.

Q4: Time Complexity of Recursive Merge

What is the worst-case time complexity of the routine below (merge runs in O(n))?

def func1(arr, start, end):
    ans = 0
    if end > start:
        mid = (start + end) // 2
        ans += func1(arr, start, mid)
        ans += func1(arr, mid + 1, end)
        ans += merge(arr, start, mid, end)  # O(n)
    return ans

• O(n)
• O(log n)
• O(n²)
• O(n log n)

Explanation: This is the merge-sort recurrence T(n) = 2T(n/2) + O(n) → O(n log n) by the Master Theorem.