Short answers
1. True or False? Circle your answers. No justification. Wrong answers will receive a penalty of -1.
(a) (2 points) Performing one rotation always preserves the AVL property. A. True B. False
(b) (2 points) In a red-black trees, at most half of the nodes in a path from the root to a leaf are red. A. True B. False
Copyright By PowCoder代写 加微信 powcoder
(c) (2 points) The order of the vertices visited by the depth-first search algorithm (DFS) algorithm is always strictly different than the order of the vertices returned by the breadth-first search algo- rithm (BFS) algorithm.
A. True B. False
(d) (2 points) Let P (n) be a property over a variable n. We want to prove by induction that P (n) is true for all n ≥ n0. Assume the base case P(n0) is true. Then, for the inductive case, only assuming that P (n − 1) is true is always sufficient to prove that P (n) is true too.
A. True B. False
(e) (2 points) If f(n) is O(g(n)) then g(n) is O(f(n)). A. True B. False
(f) (2 points) We implement hash tables using the open addressing technique to solve conflicts. In this implementation, the load factor α cannot exceed 1.
A. True B. False
(g) (2 points) We run the depth-first search algorithm (DFS) on a graph G and identify a back edge. Thus, G has at least one cycle.
A. True B. False
(h) (2 points) Given a partition of the vertices of a weighted undirected graph, the cut has one and only one light edge.
A. True B. False
(i) (2 points) We run the Dijkstra’s algorithm on a graph with a negative-weight cycle. Then, the algorithm could not terminate.
A. True B. False
(j) (2 points) A bipartite graph has no cycle. A. True B. False
COMP 251 – Midterm Page 3 of 10 Fall 2021
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com