Data Structures Data Structures 3 — Questions and Answers
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?
- 2i + 1 (Correct answer)
- 2i
- i / 2
- i + 1
Correct answer: 2i + 1
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?
- Stack (Correct answer)
- Queue
- Binary search tree
- Hash table
Correct answer: Stack
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?
- O(1) (Correct answer)
- O(log n)
- O(n)
- O(n log n)
Correct answer: O(1)
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?
- A max-heap of size k (Correct answer)
- An unsorted array
- A queue
- A singly linked list
Correct answer: A max-heap of size k
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?
- The next position of the rear equals the front (Correct answer)
- The rear index equals n
- The front index is 0
- The rear index equals the front index
Correct answer: The next position of the rear equals the front
In the common one-slot-empty convention, the queue is full when (rear + 1) mod n equals front.
Question 6: Which of these is a key advantage of a doubly linked list over a singly linked list?
- Deletion of a given node without traversing from the head (Correct answer)
- Lower memory usage per node
- Faster random access by index
- Simpler pointer management
Correct answer: Deletion of a given node without traversing from the head
A doubly linked list node stores a previous pointer, allowing O(1) deletion when you already hold the node.
Question 7: What is the height of a complete binary tree containing n nodes?
- Approximately log2(n) (Correct answer)
- Approximately n / 2
- Exactly n - 1
- Approximately sqrt(n)
Correct answer: Approximately log2(n)
A complete binary tree fills each level before starting the next, so its height is floor(log2 n).
Data Structures Data Structures 3
A max-heap is stored in an array starting at index 0.
Where is the left child of the node at index i?