Font size
WorksheetsDSA (QUIZ 6) Hashing, Graphs, Advanced Graph Algorithms, and DP
Total questions: 20
Worksheet time: 13mins
What is the main advantage of using a hash table?
Data encryption
Data compression
Fast access to data
Sequential search
Which data structure is typically used to implement a hash table?
Stack
Array
Queue
Linked List
In a graph, what does a 'directed edge' imply?
Bi-directional connection
One-way connection
Weighted path
No connection
Which graph algorithm is used to find the shortest path from a source to all other vertices in a graph with positive weights?
Prim's
Dijkstra's
Kruskal's
Topological Sort
Which of the following is a property of dynamic programming?
Recursion without memory
Overlapping subproblems
Random selection
Loop unrolling
Which of the following is an example of a greedy algorithm?
Bellman-Ford
Knapsack (DP)
Dijkstra's
Floyd-Warshall
Which graph representation is more space-efficient for sparse graphs?
Adjacency matrix
Adjacency list
Incidence matrix
Edge list
What does the hash function do?
Deletes duplicates
Translates keys into indexes
Randomly shuffles data
Encrypts values
Which algorithm is commonly used to schedule tasks with dependencies?
DFS
Kruskal's
Topological Sort
BFS
Which is not true about Dynamic Programming?
Solves problems optimally
Uses memoization
Only works on graphs
Avoids recomputation
Recursion is a process where a function calls itself.
True
False
In an undirected graph, edges have direction.
True
False
Hash collisions can be resolved using chaining or open addressing.
True
False
Prim's and Kruskal's are used to find shortest paths.
True
False
Dynamic Programming is useful when problems can be broken into independent subproblems.
True
False
What is the output of this code?
int hashFunction(int key) { return key % 10; } cout << hashFunction(25);
(a)
Given a graph with 5 vertices and 4 edges, what is the minimum number of connections needed for it to be connected?
(a)
What is the time complexity of accessing an element in a hash table (average case)?
(a)
What is the base case in this recursive function?
int fact(int n) {
if (n == 0) return 1;
return n * fact(n - 1);
}
(a)
What will be printed by this DP Fibonacci function for fib(5)?
int fib(int n) {
if (n <= 1) return n;
return fib(n-1) + fib(n-2);
}
(a)
