What does amortized analysis estimate?
A One call worst cost
B Only memory capacity
C Average cost over operation sequence
D Compiler parsing time
Answer: C. Average cost over operation sequence. Amortized analysis averages costly operations across a sequence using an aggregate argument.
Why might dynamic array append be amortized O(1)?
A Every append sorts the array
B Resizing cost spread across appends
C Capacity never changes
D Each append scans all values
Answer: B. Resizing cost spread across appends. Geometric growth makes occasional copying inexpensive when averaged over many appends.
What is the worst case lookup time in a hash table?
A O(1) always
B O(log n)
C O(n)
D O(n squared) always
Answer: C. O(n). In the worst case, many keys can collide and require linear inspection.
What is typical hash table lookup with good hashing?
A Worst case O(1)
B Always O(log n)
C Expected O(1)
D Always O(n squared)
Answer: C. Expected O(1). With a controlled load factor and good hashing, expected lookup is constant time.
What is binary heap delete root time?
A O(log n)
B O(1) always
C O(n)
D O(n squared)
Answer: A. O(log n). After root removal, heap repair follows a path of logarithmic height.
What is time to traverse every node in a tree?
A O(log n)
B O(n)
C O(1)
D O(n squared)
Answer: B. O(n). A complete traversal visits each of the n nodes a constant number of times.
What is adjacency list BFS time?
A O(V plus E)
B O(V squared) always
C O(log V)
D O(E squared)
Answer: A. O(V plus E). With adjacency lists, BFS visits vertices and examines each edge a constant number of times.
What is adjacency matrix neighbor scan time?
A O(log V)
B O(1)
C O(E)
D O(V)
Answer: D. O(V). Finding all neighbors in a matrix may inspect every possible destination vertex.
What does a skip list use to speed search?
A Multiple linked levels
B Recursive array copies
C Heap priorities
D Graph adjacency matrices
Answer: A. Multiple linked levels. Skip lists add express lanes across linked levels for expected logarithmic search.
What does a Bloom filter answer probabilistically?
A Exact sorted position
B Shortest graph distance
C Maximum heap value
D Possible membership
Answer: D. Possible membership. A Bloom filter can say possibly present or definitely absent with a false positive risk.
What is false positive in Bloom filter?
A Present item reported absent
B Absent item reported possibly present
C Key mapped to two slots
D Item stored twice in array
Answer: B. Absent item reported possibly present. Bloom filters may report possible membership for an item that was never inserted.
What does a bitset compactly store?
A Strings as pointers
B Tree edges as lists
C Boolean flags as bits
D Floating point values
Answer: C. Boolean flags as bits. A bitset stores many Boolean flags using individual bits.
What is a sparse matrix?
A Matrix with sorted rows only
B Matrix with one column
C Matrix stored as a heap
D Matrix with mostly zero entries
Answer: D. Matrix with mostly zero entries. Sparse matrix formats avoid storing most zero entries explicitly.
Which structures commonly support an LRU cache?
A Stack and binary tree
B Queue and adjacency matrix
C Hash map plus doubly list
D Trie and disjoint set
Answer: C. Hash map plus doubly list. A hash map gives lookup while a doubly linked list maintains recent-use order.
What does an LRU policy evict?
A Least recently used item
B Largest numeric item
C Newest inserted item always
D Item with shortest key
Answer: A. Least recently used item. LRU removes the item whose last access occurred longest ago.
What is a union find optimization called union by rank?
A Sort every set by rank
B Attach shorter tree below taller
C Delete empty sets
D Hash every representative
Answer: B. Attach shorter tree below taller. Union by rank limits the height by attaching the shallower tree to the deeper one.
What is an iterator used for?
A Resize a hash table
B Balance a tree
C Compress graph paths
D Visit collection elements
Answer: D. Visit collection elements. An iterator provides a way to traverse a collection's elements.
What does a stable sort preserve?
A Original array length
B Hash function result
C Tree height
D Relative order of equal keys
Answer: D. Relative order of equal keys. Stable sorting leaves equal keyed items in their original relative order.
Which structure supports minimum lookup and efficient insertions?
A Singly linked list
B Unsorted array
C Stack
D Min heap
Answer: D. Min heap. A min heap exposes the minimum while supporting logarithmic insertion.
What does a persistent data structure preserve?
A Earlier versions after updates
B Only the newest element
C Fixed memory address
D Sorted insertion order
Answer: A. Earlier versions after updates. Persistent structures keep previous versions available after creating an updated one.
What does an immutable collection prevent?
A Element lookup
B In place modification
C Iteration
D Creating a new version
Answer: B. In place modification. An immutable collection is not modified after creation; updates create another value.
Why use an adjacency list for a sparse graph?
A Makes all pairs adjacent
B Guarantees O(1) path search
C Stores only present neighbors
D Removes edge weights
Answer: C. Stores only present neighbors. For sparse graphs it avoids space for the many absent edges.
What is the main purpose of a sentinel node?
A Store the smallest key
B Simplify boundary handling
C Represent every graph vertex
D Measure tree balance
Answer: B. Simplify boundary handling. A sentinel can reduce special cases at collection boundaries.
What does a circular buffer use?
A Fixed array with wrapped indices
B Linked tree with rotations
C Hash slots with chaining
D Sorted list of priorities
Answer: A. Fixed array with wrapped indices. A circular buffer advances indexes modulo its capacity to reuse slots.
What does a persistent queue typically enable?
A Access to previous queue versions
B Constant time arbitrary sorting
C Only one enqueue operation
D Automatic graph traversal
Answer: A. Access to previous queue versions. Persistent queues retain older versions when updates create new queue states.