Data Structures Data Structures 5

Question 1

What distinguishes an AVL tree from a plain binary search tree?

Accepted Answer

It self-balances so subtree heights differ by at most one

Answer

An AVL tree performs rotations after updates to keep every node's subtree heights within one of each other.

Question 2

Which data structure is the standard choice for implementing Dijkstra's shortest path algorithm efficiently?

Accepted Answer

Priority queue (min-heap)

Answer

Dijkstra's algorithm repeatedly extracts the vertex with the smallest tentative distance, a min-heap operation.

Question 3

A dynamic array doubles its capacity when full. What is the amortized cost of appending one element?

Accepted Answer

O(1)

Answer

Occasional O(n) resize costs spread across many cheap appends average out to constant time per append.

Question 4

Which property must hold for every node in a binary min-heap?

Accepted Answer

Its value is less than or equal to its children's values

Answer

The min-heap property only requires each parent to be no larger than its children, with no left-right ordering.

Question 5

You must process tasks in the exact order they arrive. Which data structure should you use?

Accepted Answer

Queue

Answer

A queue's first-in-first-out ordering processes items in arrival order.

Data Structures Practice Test