Data Structures Data Structures 3

Question 1

A max-heap is stored in an array starting at index 0. Where is the left child of the node at index i?

Accepted Answer

2i + 1

Answer

In a 0-indexed array heap, the left child of index i is at 2i + 1 and the right child at 2i + 2.

Question 2

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

Accepted Answer

Stack

Answer

Undo reverses the most recent action first, matching a stack's LIFO behavior.

Question 3

What is the average-case time complexity of lookup in a well-designed hash table?

Accepted Answer

O(1)

Answer

With a good hash function and low load factor, hash table lookups take constant time on average.

Question 4

Which structure would you use to efficiently find the k-th smallest element repeatedly as elements stream in?

Accepted Answer

A max-heap of size k

Answer

A max-heap of size k keeps the k smallest elements seen, with the k-th smallest always at the root.

Question 5

In a circular queue implemented with an array of size n, what typically indicates the queue is full?

Accepted Answer

The next position of the rear equals the front

Answer

In the common one-slot-empty convention, the queue is full when (rear + 1) mod n equals front.

Data Structures Practice Test