Data Structure Quiz
Questions: 16 · 10 minutes
1. What is a collision in a hash table?
Two different keys are assigned to the same bucket or index
A key is inserted more than once with the same value
The table's keys are stored in sorted order
A lookup examines every bucket before returning
2. An application needs fast average-case membership checks for unique user IDs and does not need to preserve their order. Which structure is the most direct fit?
Dynamic array
User ID queue
Hash-based set
Binary min-heap
3. Which ordering relationship defines a min-heap?
Every left child is smaller than its right sibling
Nodes are ordered by their insertion time
All keys in the left subtree are smaller than the root key
Every parent has a key no greater than the keys of its children
4. An autocomplete system must efficiently retrieve words that begin with a supplied character sequence. Which data structure is especially suited to this task?
Character stack
Word disjoint-set structure
Prefix trie
Suggestion min-heap
5. A graph has millions of possible vertices but relatively few edges. Why is an adjacency list usually preferred to an adjacency matrix?
It automatically keeps every vertex sorted
It guarantees constant-time lookup for every possible edge
It removes the need to store vertex identifiers
Its storage is proportional to the vertices and existing edges rather than every possible pair
6. Which stack operation removes and returns the item added most recently?
Pop
Dequeue
Peek
Enqueue
7. A printer must process jobs in the same order they arrive. Which data structure most directly supports this behavior?
Stack
Set
Queue
Binary search tree
8. A scheduler frequently adds tasks with numeric priorities and repeatedly removes the task with the smallest priority value. Which structure is typically appropriate?
Min-heap
FIFO queue
Hash set
Singly linked list
9. A dynamic array occasionally allocates a larger block and copies its elements, but most appends place an item directly at the end. What is the typical amortized time per append?
Logarithmic amortized time: O(log n)
Constant amortized time: O(1)
Linear amortized time: O(n)
Quadratic amortized time: O(n squared)
10. You need to detect whether a singly linked list contains a cycle while using O(1) extra space. Which technique fits this requirement?
Move one pointer by one step and another by two steps
Copy every node into a second linked list
Sort the nodes by their stored values
Run binary search over the node positions
11. For a valid binary search tree containing distinct keys, which traversal visits the keys in ascending order?
Pre-order traversal
In-order traversal
Post-order traversal
Level-order traversal
12. You want to find a path with the fewest edges from a starting vertex in an unweighted graph. Which traversal and supporting structure should you use?
Depth-first search with a stack
Depth-first search with a min-heap
In-order traversal with a stack
Breadth-first search with a queue
13. A network application repeatedly merges groups of connected devices and asks whether two devices currently belong to the same group. Which structure is designed for these operations?
Prefix trie
Circular task queue
Disjoint-set union
Ordered binary search tree
14. You already have a reference to a node in a singly linked list and want to insert a new node immediately after it. What is the usual time complexity of updating the links?
Linearithmic time, O(n log n)
Constant time, O(1)
Logarithmic time, O(log n)
Linear time, O(n)
15. You need to repeatedly search a large array by discarding half of the remaining elements at each step. What condition must the array satisfy?
It must contain no duplicate values
It must have a fixed capacity
It must store elements in insertion order
It must be sorted according to the search order
16. Which data structure is normally used by a program to track active function calls during recursion?
Call queue
Call stack
Function hash table
Call graph