This page has a set of practice questions that cover most topics in COMP2521 23T3 and will give you a chance to test your knowledge of data structures and algorithms.
Note that the theory questions in the real COMP2521 23T3 exam will not be multiple choice!
Question 1 - Minimum Spanning Tree
Given this graph, what is the total weight of the minimum spanning tree?
14
15
16
18
Question 2 - Graph Traversal Algorithms
Consider the following iterative functions for breadth-first and depth-first traversal on a graph.
Show what would be printed by the following calls to these functions on this graph:
a) breadthFirst(g, 3)
b) depthFirst(g, 0)
a) 3, 2, 0, 6, 5, 4, 1
b) 0, 1, 5, 2, 3, 4, 6
a) 3, 0, 2, 1, 4, 5, 6
b) 0, 1, 5, 2, 3, 6, 4
a) 3, 0, 1, 5, 2, 6, 4
b) 0, 1, 5, 4, 2, 3, 6
a) 0, 1, 5, 2, 4, 6, 3
b) 3, 0, 1, 5, 2, 6, 4
Question 3 - Time complexity
What is the time complexity of the following function?
void print_nums(int nums[]) {
for (int i = 0; i < 100; i++) {
printf(""%d\n"", nums[i]);
}
}
O(1)
O(100)
O(n)
O(n ^ 2)
Question 4 - Euler paths
Does an Euler path exist for this graph?
Yes
No
Question 5 - Sorting
In which of the following sorting algorithms is the performance for both sorted and reverse inputs slower than random inputs?
Bubble sort
Selection sort
Naive quicksort
Merge sort
Question 6 - Time complexity
What is the time complexity of this algorithm?
void function(int n) {
for (int i = 0; i < n; i++) {
int *a = calloc(n, sizeof(int));
printf("Hello!\n");
free(a);
}
}
O(n)
O(n^2)
O(n + m)
O(n * log(n))
Question 7 - Time complexity
What is the time complexity of the following function? You may assume that n is positive.
void halve(int n) {
printf(""called halve(%d)\n"", n);
if (n == 0) {
return;
}
halve(n / 2);
}
O(1)
O(log(n))
O(n)
O(2 ^ n)
Question 8 - Time complexity
What is the time complexity of the following function? You may assume the values of n and m passed in are positive.
int rem(int n, int m) {
while (n >= m) {
n -= m;
}
return n;
}
O(n + m)
O(n - m)
O(n * m)
O(n / m)
Question 9 - AVL Trees
After inserting 45 into this AVL tree, what will the tree look like?
Question 10 - BFS and DFS
What is the difference between the implementation of iterative BFS and iterative DFS and the theoretical difference between the two?
BFS uses a queue, checking all neighbours of a node before moving on to another node, and DFS uses a stack, checking every new node as it is found.
BFS uses a stack, checking all neighbours of a node before moving on to another node, and DFS uses a queue, checking every new node as it is found.
BFS uses a queue, checking every new node as it is found, and DFS uses a stack, checking all neighbours of a node before moving on to another node.
BFS uses a stack, checking every new node as it is found, and DFS uses a queue, checking all neighbours of a node before moving on to another node.
Question 11 - Graph ordering
Which of the following is post order?
-
Traverse the left subtree, i.e., call recursion (left-subtree).
-
Visit the root (i.e., do work on the current node).
-
Traverse the right subtree, i.e., call recursion (right-subtree).
-
Visit the root (i.e., do work on the current node).
-
Traverse the left subtree, i.e., call recursion (left-subtree).
-
Traverse the right subtree, i.e., call recursion (right-subtree).
-
Traverse the left subtree, i.e., call recursion (left-subtree).
-
Traverse the right subtree, i.e., call recursion (right-subtree).
-
Visit the root (i.e., do work on the current node).
None of the above.
Question 12 - Tree Rotations
What sequence of rotations will transform this tree to end up with 7 at the root?
rotate_right(7), rotate_left(8), rotate_right(5)
rotate_left(8), rotate_right(5), rotate_left(10)
rotate_left(5), rotate_right(8), rotate_right(8)
rotate_right(8), rotate_left(5), rotate_right(10)
Question 13 - Kruskal's Algorithm
Using Kruskal's algorithm, find the minimum spanning tree of this fully connected and weighted graph.
During this procedure, how many times do you encounter a cycle before you find the MST?
0
1
2
3
Question 14 - Tree Rotations
Which sequence of transformations will make the following transformation?
rotate_right(1), rotate_left(7)
rotate_right(2), rotate_left(6)
rotate_right(5), rotate_left(3)
rotate_right(6), rotate_left(2)
Question 15 - Dijkstra's Algorithm (Challenge)
Using Dijkstra's algorithm, find the shortest path from A to all other vertices in this fully connected directed and weighted graph.
During this procedure, how many times is an edge relaxed towards vertex E? In other words, on how many occasions do we update our knowledge of the shortest distance from A to E?
0
1
2
3
Question 16 - Time complexity (Challenge)
What is the time complexity of the following function? You may assume the value of n is positive.
void print_pairs(int n) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j += i) {
printf("%d %d\n", i, j);
}
}
}
O(n)
O(n * log(n))
O(n^1.5)
O(n^2)
Good luck for the exam! Remember; you've been preparing for it for the entire term so all that's left is to apply everything you've learned and to do your best :D