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

It allows duplicate keys at the root

Answer

It stores data only in leaf nodes

Answer

It uses hashing to place nodes

Question 2

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

Accepted Answer

Priority queue (min-heap)

Answer

Stack

Answer

Plain FIFO queue

Answer

Doubly linked list

Question 3

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

Accepted Answer

O(1)

Answer

O(log n)

Answer

O(n)

Answer

O(n^2)

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

Its left child is smaller than its right child

Answer

All values in its left subtree are smaller than its value

Answer

It has exactly zero or two children

Question 5

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

Accepted Answer

Queue

Answer

Stack

Answer

Max-heap

Answer

Hash set

Question 6

What is the worst-case time complexity of searching a skewed (degenerate) binary search tree with n nodes?

Accepted Answer

O(n)

Answer

O(log n)

Answer

O(1)

Answer

O(n log n)

Question 7

Which data structure best supports checking membership of an element in average O(1) time without storing duplicates?

Accepted Answer

Hash set

Answer

Sorted array

Answer

Linked list

Answer

Binary search tree