What does a hash function produce?
A Array index candidate
B Sorted key list
C Tree height
D Graph path
Answer: A. Array index candidate. A hash function maps a key to a hash value used to find a storage location.
What is a hash collision?
A Two arrays have same length
B A key is missing
C A tree contains duplicate leaves
D Keys share one slot
Answer: D. Keys share one slot. A collision occurs when distinct keys map to the same table location.
How does separate chaining handle collisions?
A Moves every key to root
B Stores a bucket of entries
C Discards the new key
D Sorts the whole table
Answer: B. Stores a bucket of entries. Separate chaining stores colliding entries together in a bucket, often a list.
What does open addressing do after collision?
A Creates a linked list always
B Probes other table slots
C Changes key contents
D Deletes the old entry
Answer: B. Probes other table slots. Open addressing searches for another available slot according to a probe rule.
What does hash table load factor compare?
A Entries to table capacity
B Keys to graph vertices
C Tree height to width
D Bytes to processor speed
Answer: A. Entries to table capacity. Load factor is the number of stored entries relative to table capacity.
Why resize a hash table?
A Make keys immutable
B Sort entries by value
C Keep collisions manageable
D Remove every bucket
Answer: C. Keep collisions manageable. Resizing lowers load factor and can reduce collision costs.
What does a map store?
A Only unique values
B Tree edges only
C Key and value pairs
D Ordered instructions
Answer: C. Key and value pairs. A map associates keys with corresponding values.
What does a set typically guarantee?
A Unique elements
B Sorted elements always
C Fixed element count
D Key value pairs
Answer: A. Unique elements. A set contains no duplicate elements according to its equality rule.
Which graph representation suits sparse graphs?
A Adjacency matrix
B Full binary tree
C Sorted array only
D Adjacency list
Answer: D. Adjacency list. An adjacency list stores existing neighbors without allocating every possible edge.
Which representation has O(V squared) space?
A Adjacency list
B Adjacency matrix
C Edge iterator
D Hash function
Answer: B. Adjacency matrix. An adjacency matrix stores a cell for each possible vertex pair.
What is an edge in a graph?
A A stored array index
B Connection between vertices
C A tree root
D A hash bucket
Answer: B. Connection between vertices. An edge represents a connection between vertices.
What is a directed edge?
A Connection with an orientation
B Connection with no endpoints
C A sorted pair always
D A weight without vertices
Answer: A. Connection with an orientation. A directed edge goes from one endpoint toward another.
What is a weighted graph edge?
A Connection without vertices
B A hash key only
C Connection with an associated cost
D A queue insertion
Answer: C. Connection with an associated cost. A weight can represent distance, cost, or another numeric attribute.
What is a cycle in a graph?
A Path with one vertex
B Tree with no root
C Path returning to its start
D Edge without endpoint
Answer: C. Path returning to its start. A cycle is a path that returns to its starting vertex.
What does connected mean for an undirected graph?
A All vertices mutually reachable
B Every vertex has two edges
C No cycles are present
D All edges have equal weight
Answer: A. All vertices mutually reachable. A connected undirected graph has a path between every vertex pair.
What does DAG stand for?
A Directed acyclic graph
B Data address group
C Double array graph
D Depth aligned grid
Answer: A. Directed acyclic graph. A DAG is directed and contains no directed cycle.
What does topological sorting order?
A Edges by numeric weight
B Keys by hash value
C Vertices respecting dependencies
D Nodes by insertion time
Answer: C. Vertices respecting dependencies. A topological order places every prerequisite before the dependent vertex.
Which search finds shortest paths by edge count in an unweighted graph?
A Depth first search
B Binary search
C Linear probing
D Breadth first search
Answer: D. Breadth first search. Breadth first search explores vertices in increasing distance from the source.
Which traversal explores a branch deeply before backtracking?
A Breadth first search
B Heap extraction
C Topological insertion
D Depth first search
Answer: D. Depth first search. Depth first search follows a path until it cannot continue, then backtracks.
What does disjoint set represent?
A A sorted key sequence
B Graph edge weights
C Groups of nonoverlapping elements
D A priority queue
Answer: C. Groups of nonoverlapping elements. A disjoint set structure tracks a partition into separate groups.
What does union do in disjoint sets?
A Finds a shortest path
B Merges two groups
C Sorts a graph
D Deletes an isolated vertex
Answer: B. Merges two groups. Union combines the groups containing two elements.
What does path compression improve?
A Array insertion order
B Heap root selection
C Graph matrix storage
D Future representative lookups
Answer: D. Future representative lookups. Path compression shortens parent chains during find operations.
What does Kruskal's algorithm find?
A Shortest path with negative edges
B Largest binary heap
C Topological order
D Minimum spanning tree
Answer: D. Minimum spanning tree. Kruskal selects low weight edges that connect components without cycles.
What restriction does Dijkstra's algorithm require?
A Nonnegative edge weights
B A directed acyclic graph
C Equal edge weights
D No more than two vertices
Answer: A. Nonnegative edge weights. Dijkstra's standard algorithm assumes edge weights are nonnegative.
Which algorithm handles negative edges without negative cycles?
A Dijkstra
B Bellman Ford
C Kruskal
D Binary search
Answer: B. Bellman Ford. Bellman Ford can handle negative edge weights and detect reachable negative cycles.