Data Structures Data Structures 4 — Questions and Answers
Question 1: You need to check whether a string of brackets like "{[()]}" is balanced. Which data structure fits best?
- Stack (Correct answer)
- Queue
- Hash table
- Binary heap
Correct answer: Stack
Push opening brackets and pop to match each closing bracket, which is exactly LIFO stack behavior.
Question 2: Which data structure does breadth-first search (BFS) of a graph rely on?
- Queue (Correct answer)
- Stack
- Priority queue
- Binary search tree
Correct answer: Queue
BFS explores vertices level by level, using a FIFO queue to process nodes in discovery order.
Question 3: What is the primary drawback of open addressing with linear probing in hash tables?
- Primary clustering degrades performance as the table fills (Correct answer)
- It requires extra memory for pointers
- It cannot handle deletions at all
- It only works with string keys
Correct answer: Primary clustering degrades performance as the table fills
Linear probing causes runs of occupied slots (primary clustering), lengthening probe sequences as load increases.
Question 4: Inserting a new element into a binary min-heap of n elements takes how long in the worst case?
- O(log n) (Correct answer)
- O(1)
- O(n)
- O(n log n)
Correct answer: O(log n)
The new element is placed at the bottom and bubbles up at most the height of the heap, which is O(log n).
Question 5: Which scenario is a classic use case for a trie (prefix tree)?
- Autocomplete suggestions for typed prefixes (Correct answer)
- Scheduling tasks by priority
- Detecting cycles in a graph
- Sorting integers in linear time
Correct answer: Autocomplete suggestions for typed prefixes
A trie stores strings by shared prefixes, making prefix-based lookups like autocomplete very efficient.
Question 6: An adjacency matrix representation of a graph with V vertices uses how much space?
- O(V^2) (Correct answer)
- O(V + E)
- O(E)
- O(V log V)
Correct answer: O(V^2)
An adjacency matrix stores one entry for every ordered pair of vertices, requiring V-squared space regardless of edge count.
Question 7: Which operation is NOT efficiently supported by a standard singly linked list?
- Accessing the middle element by index in O(1) (Correct answer)
- Inserting at the head in O(1)
- Deleting the head in O(1)
- Traversing all elements in O(n)
Correct answer: Accessing the middle element by index in O(1)
Reaching an arbitrary index in a linked list requires traversing from the head, taking O(n) time.
Data Structures Data Structures 4
You need to check whether a string of brackets like "{[()]}" is balanced.
Which data structure fits best?