CS Algorithms & Data Structures 3

Question 1

Dijkstra's shortest path algorithm fails to produce correct results when the graph contains what?

Accepted Answer

Negative edge weights

Answer

Dijkstra assumes settled vertices are final, an invariant that negative edges can violate.

Question 2

Which sorting algorithm is stable and runs in O(n log n) time in the worst case?

Accepted Answer

Merge sort

Answer

Merge sort preserves the relative order of equal keys and guarantees O(n log n) in all cases.

Question 3

A programmer needs constant-time insertion and deletion at both ends of a sequence. Which structure fits best?

Accepted Answer

Doubly linked list (deque)

Answer

A doubly linked list or deque supports O(1) insertion and removal at both head and tail.

Question 4

What is the primary advantage of an AVL tree over a plain binary search tree?

Accepted Answer

Guaranteed O(log n) operations via balancing

Answer

AVL rotations keep the tree height logarithmic, preventing the O(n) degeneration of an unbalanced BST.

Question 5

The recurrence T(n) = 2T(n/2) + O(n) solves to which complexity?

Accepted Answer

O(n log n)

Answer

By the master theorem, splitting into two half-size problems with linear combine work gives O(n log n).

(CS) Computer Science Practice Test