Data Structures MCQs (Set-4)

What does amortized analysis estimate?

A One call worst cost
B Only memory capacity
C Average cost over operation sequence
D Compiler parsing time

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

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

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)

What is binary heap delete root time?

A O(log n)
B O(1) always
C O(n)
D O(n squared)

What is time to traverse every node in a tree?

A O(log n)
B O(n)
C O(1)
D O(n squared)

What is adjacency list BFS time?

A O(V plus E)
B O(V squared) always
C O(log V)
D O(E squared)

What is adjacency matrix neighbor scan time?

A O(log V)
B O(1)
C O(E)
D O(V)

What does a skip list use to speed search?

A Multiple linked levels
B Recursive array copies
C Heap priorities
D Graph adjacency matrices

What does a Bloom filter answer probabilistically?

A Exact sorted position
B Shortest graph distance
C Maximum heap value
D Possible membership

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

What does a bitset compactly store?

A Strings as pointers
B Tree edges as lists
C Boolean flags as bits
D Floating point values

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

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

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

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

What is an iterator used for?

A Resize a hash table
B Balance a tree
C Compress graph paths
D Visit collection elements

What does a stable sort preserve?

A Original array length
B Hash function result
C Tree height
D Relative order of equal keys

Which structure supports minimum lookup and efficient insertions?

A Singly linked list
B Unsorted array
C Stack
D Min heap

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

What does an immutable collection prevent?

A Element lookup
B In place modification
C Iteration
D Creating a new version

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

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

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

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