NEW
Font size
WorksheetsPUTANGINA MO
Total questions: 38
Worksheet time: 24mins
Given the following tentative distances just before extraction: d[a] = 0, d[b] = 3, d[c] = 2, d[d] = 5. Which node is extracted next?
a
b
c
d
Consider building a min-heap (where parent ≤ children) from the elements inserted in that order into an array-based heap starting empty at index 1. After all insertions and heapifications, what is the array content (indices 1 to 6), and which property holds?
Root is minimum, last level filled left-to-right.
Heapify swaps only with larger child in min-heap.
Smallest element always at a leaf after insert.
Complete binary tree shape preserved.
Which traversal guarantees discovering all vertices reachable from a source using a queue and explores by layers of distance?
Dijkstra’s algorithm
Breadth-first search (BFS)
Depth-first search (DFS)
Kruskal’s algorithm
Suppose we extract vertex u with d[u] = 7. It has neighbors v, w, x, y, z, and a with edge weights w(u,v) = 2, w(u,w) = 4, w(u,x) = 3, w(u,y) = 5, w(u,z) = 1, and w(u,a) = 6. Current distances: d[v] = 10, d[w] = 13, d[x] = 11, d[y] = 14, d[z] = 9, d[a] = 15. After relaxing all edges from u, which statement is true?
d[v] = 10, d[w] = 13, d[x] = 11, d[y] = 14, d[z] = 9, d[a] = 15
d[v] = 9, d[w] = 11, d[x] = 10, d[y] = 12, d[z] = 8, d[a] = 15
d[v] = 8, d[w] = 12, d[x] = 9, d[y] = 10, d[z] = 8
d[v] = 9, d[w] = 11, d[x] = 10, d[y] = 12, d[z] = 8, d[a] = 13
In open addressing with linear probing, what happens after a collision at an index?
A new bucket is allocated and appended to the array
A new hash function is sampled for the collided key
Keys are moved into a linked list at that index
The next index is probed sequentially until an empty slot is found
What does entry A_ij represent in the adjacency matrix A of a simple, unweighted directed graph?
Whether there is an edge from j to i
The degree of vertex j
The number of vertices adjacent to vertex i
Whether there is an edge from i to j
A hash table has size 10. The String "MANGO" has a hashCode of ____. What bucket does it go to?
0
5
1
9
What is a collision in a hash table?
When a key is deleted from the table
When two keys map to the same bucket index
When a key maps outside the bucket array bounds
When two keys produce different hash codes
You perform a DFS traversal starting from vertex s in a directed graph. During traversal, you reach vertex u and then vertex v via an edge (u,v). Later, you find another edge (v,u) that was not used during traversal. What is true about the DFS tree?
The edge (v,u) will be part of the DFS tree
The edge (v,u) will be a forward edge
The edge (v,u) will be a cross edge
The edge (v,u) will be a back edge
Which operation breaks the heap-order property in a min-heap and thus must be followed by a sift-down?
Decreasing a key of an internal node
Replacing the root with the last element after extract-min
Swapping two sibling leaves
Inserting a new key at the end and sifting up
Given d[u] = 9, neighbors v and z have weights w(u,v) = 1 and w(u,z) = 4, while d[v] = 11 and d[z] = 12. After relaxation, what is true?
d[v] = 9, d[z] = 12
d[v] = 10, d[z] = 12
d[v] = 11, d[z] = 13
d[v] = 10, d[z] = 9
Suppose you perform a BFS traversal starting from vertex s in an undirected graph. During traversal, you visit vertex u before vertex v. Later, you find that there is a direct edge (u,v) with weight 2, but v was discovered earlier than u in the BFS tree. What is the most likely reason?
BFS does not guarantee shortest paths in weighted graphs
The edge (u,v) was not considered during BFS
The graph contains a cycle that affected the order
BFS always visits vertices in increasing order of their distance from s
Which statement best characterizes a minimum spanning tree (MST) in a connected, undirected, weighted graph?
It maximizes the sum of edge weights.
It contains all edges of minimum weight in the graph.
It minimizes the number of edges.
It connects all vertices with no cycles and minimum total weight.
Which approach efficiently updates an MST when a single edge weight decreases?
Add the edge, and if it creates a cycle with the current MST, remove the heaviest edge on that cycle
Switch to shortest path trees since they update faster
Recompute the MST from scratch using Kruskal’s algorithm
Remove all edges adjacent to the changed edge and rebuild locally
Suppose we extract vertex u with d[u] = 7. It has neighbors v and x with edge weights w(u,v)=2 and w(u,x)=5. The current distances are d[v]=11 and d[x]=12. After relaxing edges from u to v and x, what happens?
d[v] remains 11 and d[x] becomes 10
d[v] becomes 9; d[x] becomes 12
d[v] becomes 9; d[x] becomes 10
d[v] becomes 11 and d[x] becomes 12
What is the primary goal of a hash function in a hash table?
To sort keys in ascending order.
To compress data to a smaller size.
To encrypt data for confidentiality.
To map keys uniformly to indices.
Which component directly stores the key–value pairs in a separate chaining hash table?
Universal hash family
Load factor controller
Open addressing probe sequence
Bucket array entries that hold linked lists or dynamic arrays
Which condition breaks Dijkstra’s correctness about finalized nodes having the lowest cumulative cost?
Use of adjacency lists instead of matrices
Multiple edges between the same pair of nodes
Presence of zero-weight edges
Presence of negative edge weights
In linear probing:
A hash table has size 10. Which of the following is the correct hash index for the key 65?
7
3
9
5
You are using Prim’s algorithm to build an MST starting from vertex s. At some point, you add edge (u,v) with weight 4 to the MST. Later, you find another edge (u,w) with weight 3 that connects u to a vertex not yet in the MST. What happens next?
The edge (u,w) is skipped because u is already in the MST
The edge (u,w) is added to the MST
The algorithm stops and reports an error
The edge (u,w) replaces (u,v) in the MST
In a hash table using separate chaining, what happens when two keys collide?
Both keys are stored in a bucket structure.
Keys are merged into a single entry.
One key is discarded
The table is rehashed immediately.
Which statement best defines a simple undirected graph?
A graph where every edge has a direction
A graph in which every vertex has the same degree
A graph in which multiple edges between the same pair of vertices are allowed
A graph with no parallel edges and no self-loops
In Dijkstra’s algorithm, what is the first invariant maintained at every iteration?
All neighbors of the current node already have finalized distances
The current node has the globally minimal tentative distance among all unvisited nodes
The sum of all tentative distances strictly decreases each iteration
All edges incident to finalized nodes are removed from the graph
A graph is represented using an adjacency list. You notice that vertex u has a list containing vertices v, w, and x, but vertex v’s list does not contain u. What does this imply about the graph?
The graph is undirected and the lists should be symmetric
The graph is directed and there is an edge from u to v, but not from v to u
The adjacency list representation is incomplete
The graph is weighted and the lists only show outgoing edges
Which of the following lists contains all the edges in the graph?
A→B, B→C, C→D, D→A
A→C, B→D, C→B, D→A
A→B, A→D, B→C, C→D, D→B
A→B, A→C, B→D, C→D, D→A
A hash table has a capacity of 10. The String "BAT" has a computed hashCode of ____. What is its index?
0
5
7
2
What is the role of the modulus operation in computing a bucket index from a hash code?
It ensures the index stays within the bucket array bounds
It eliminates all collisions
It randomizes the hash code
It sorts the indices
Which property of linear probing helps ensure that previously unused table slots are eventually utilized?
Primary clustering
Double hashing step sizes
Separate chaining with lists
Sequential slot exploration
Which of the following is NOT a typical application of a weighted graph?
Cost of traveling between nodes
Distance between cities
Time to complete tasks
Color of the vertices
Which statement best defines a minimum spanning tree (MST)?
A subgraph with the fewest edges regardless of connectivity
A tree that connects all vertices with no cycles and minimum total edge weight
A directed acyclic graph with minimum in-degree
A path that visits every vertex exactly once with minimum cost
Why do clusters in linear probing tend to grow?
Deletions automatically break clusters into smaller parts
Resizing immediately removes all clusters
The hash function prevents consecutive occupied cells
More insertions probe into existing clusters and are likely to stop at their ends
Suppose we are running Dijkstra’s algorithm and extract vertex u with d[u] = 8. It has neighbors v, w, x, y, z, and a with edge weights w(u,v) = 3, w(u,w) = 2, w(u,x) = 4, w(u,y) = 1, w(u,z) = 5, and w(u,a) = 6. Current distances: d[v] = 12, d[w] = 11, d[x] = 10, d[y] = 10, d[z] = 15, d[a] = 14. However, after relaxing all edges from u, we notice that d[y] remains unchanged. What is the most likely reason?
The relaxation process skipped y due to a programming error
The edge (u,y) has a negative weight
d[u] + w(u,y) is not less than d[y]
Vertex y was already processed and removed from the queue
Which of the following lists contains all the edges in the graph?
A→B, A→E, B→C, C→D, D→A, E→C
A→B, B→C, C→D, D→E, E→A
A→C, B→D, C→E, D→B, E→A
A→B, A→C, B→E, C→D, D→A
Suppose a graph has 5 vertices and is represented using an adjacency matrix. You notice that the entry at row 2, column 4 is 1, but the entry at row 4, column 2 is 0. What is the most likely explanation?
The adjacency matrix is incorrectly filled
The graph is directed and there is an edge from vertex 2 to vertex 4 only
The graph is undirected and the matrix is symmetric
The graph is weighted and the values represent weights
In a sparsely populated hash table, what advantage does linear probing offer in terms of index utilization?
It compacts keys, minimizing unused slots between them
It leaves gaps to reduce clustering
It uses a secondary structure to reuse empty slots
It requires rehashing after each insertion
In a min-heap with array (indices 1-6), after extract-min (remove root 10, move 30 to root, heapify-down), what is the final array, assuming heapify swaps with the smaller child?
Swapped down right path.
Swapped with left child only.
No swap needed post-move.Links to an external site.
Heapify skips comparisons.
What is the primary purpose of the hash code produced by a hash function?
To compress the key for serialization
To sort keys in ascending order
To index into a bucket array.
To encrypt the key for secure storage
What does Dijkstra’s algorithm compute when all edge weights are nonnegative?
A maximum flow
A minimum spanning tree
Single source shortest path distance
All-pairs shortest paths
