Week 1 Quiz
Use this quiz to test your knowledge and understanding of this week's lectures.
Question 1
The minimum and maximum numbers of comparisons Insertion Sort can require to sort a sequence of \( n \) numbers are respectively
- \( n \log_2 n \) and \( 2 n \log_2 n \)
- \( 0 \) and \( \binom{n}{2} \)
- \( n-1 \) and \( \binom{n}{2} \)
- \( n \log_2 n \) and \( \binom{n}{2} \)
Question 2
Exactly how many comparisons does Mergesort require to sort the sequence \( (4,8,2,7,3,1,5,6) \)?
- \( 12 \)
- \( 15 \)
- \( 24 \)
- \( n \log_2 n \)
Question 3
For a connected graph \( G \) and an initial vertex \( v_0 \),
- the BFS tree is never deeper than the DFS tree
- the BFS tree can sometimes be deeper than the DFS tree
- the DFS tree is always strictly deeper than the BFS tree
- the BFS and DFS trees always have the same depth
Question 4
For a connected graph \( G \) and an initial vertex \( v_0 \), let \( d_D \) and \( d_B \) represent the degrees of \( v_0 \) in the depth-first and breadth-first search trees respectively. Which of the following must be true?
- \( d_D < d_B \)
- \( d_D \le d_B \)
- \( d_D = d_B \)
- \( d_D \ge d_B \)
Question 5
For Kruskal's algorithm to work correctly, the edge weights must
- all be distinct
- all be positive
- all be integers
- none of the above
| Submit | Reset |