CS Algorithms & Data Structures 2

Question 1

What is the worst-case time complexity of quicksort when the pivot is always the smallest element?

Accepted Answer

O(n^2)

Answer

A consistently bad pivot creates maximally unbalanced partitions, degrading quicksort to O(n^2).

Question 2

Which data structure is most appropriate for implementing an undo feature in a text editor?

Accepted Answer

Stack

Answer

Undo requires reversing the most recent action first, which matches a stack's LIFO behavior.

Question 3

In a min-heap with n elements, what is the time complexity of finding the maximum element?

Accepted Answer

O(n)

Answer

The maximum in a min-heap must be a leaf, so roughly half the nodes must be scanned, giving O(n).

Question 4

Which traversal of a binary search tree visits nodes in ascending sorted order?

Accepted Answer

In-order

Answer

In-order traversal visits left subtree, node, then right subtree, yielding sorted order in a BST.

Question 5

A hash table with separate chaining has n keys stored in m buckets. What is the expected time for a successful search assuming uniform hashing?

Accepted Answer

O(1 + n/m)

Answer

Expected search time is proportional to the load factor n/m plus the constant hash computation.

(CS) Computer Science Practice Test