BSCS Bachelor of Science in Computer Science: Algorithms and Data Structures 2

Question 1

What is the worst-case time complexity of quicksort?

Accepted Answer

O(n²)

Answer

Quicksort degrades to O(n²) when the pivot is always the smallest or largest element, causing maximally unbalanced partitions.

Question 2

Which data structure is used to implement Dijkstra's shortest-path algorithm most efficiently?

Accepted Answer

Min-heap (priority queue)

Answer

A min-heap priority queue allows extracting the minimum-distance unvisited node in O(log n), giving Dijkstra's algorithm O((V + E) log V) overall.

Question 3

What property distinguishes a red-black tree from a standard BST?

Accepted Answer

Each node is colored red or black with rules ensuring O(log n) height

Answer

Red-black trees enforce coloring invariants (e.g., no two consecutive red nodes, equal black-height on all paths) that bound tree height to O(log n).

Question 4

What does the Master Theorem solve?

Accepted Answer

Recurrences of the form T(n) = aT(n/b) + f(n)

Answer

The Master Theorem provides closed-form solutions for divide-and-conquer recurrences T(n) = aT(n/b) + f(n) by comparing f(n) to n^(log_b a).

Question 5

In a min-heap, which node always contains the smallest element?

Accepted Answer

The root

Answer

The heap property guarantees that every parent is ≤ its children, so the minimum element always resides at the root.

BSCS - Bachelor of Science in Computer Science Practice Test