Multiple choices
2. Multiple choice questions. No justification. No negative penalty for wrong answers. A question has at least one correct answer but can also have multiple correct answers. You will receive full credits if and only if you identify all correct answers and do not include wrong ones.
(a) (5points) Wewanttoprovethatf(n)=12¡¤n2+8¡¤¡Ìn+1isO(n2)usingtheformaldefinition introduced in class (i.e., f(n) is O(g(n)) if there are two constants c and n0 such that f(n) ¡Ü c¡¤g(n) for all n ¡Ý n0). Which of the following pairs(s) of constants c and n0 satisfy the definition?
A. c= 21 andn0 =0 2
Copyright By PowCoder代写 加微信 powcoder
B. c = 21 and n0 = 4 C. c= 19 andn0 =1
D. c=10andn0 =1000
(b) (5 points) We are in the middle of the execution of the Kruskal¡¯s algorithm for computing a minimal spanning tree (MST) of the graph below. The bold edges have already been selected to be in the solution found so far by the Kruskal algorithm, and the edge (d, e) has just been added to the MST (i.e. under construction). Which edge will be the next one to be added to the MST? A. (e,g) B. (c,d) C. (d,f) D. (f,h)
a9c2e8g 54
1 10 6 2 b d9f7h
(c) (5 points) What is/are the longest series of activities (i.e. number of activities) that could be returned by a greedy algorithm for solving the scheduling problem (i.e. finding the maximal number of compatible activities) as seen in class?
A. (a7,a5,a2,a6,a3) B. (a7,a5,a2,a6,a9) C. (a4,a5,a2,a6,a3) D. (a4,a5,a2,a6,a9)
a7 a8 a9 a4 a5a6
0 1 2 3 4 5 6 7 8 9 10
COMP 251 – Midterm Page 4 of 10 Fall 2021
(d) (5 points) We use a tree representation to model disjoint sets, and implement unions as union- by-height with path compression. We have the two following trees T1 and T2 representing two distinct disjoint sets.
(A) T1 (B) T2
We perform the union of the set containing 6 with the set containing 1 (i.e. union(6,1)).
Which of the options below is/are possible output(s)?
522143 1656
A. TA B. TB
C. TC D. TD
COMP 251 – Midterm
Page 5 of 10
(e) (8 points) We want to insert a new key with value 20 in the AVL tree below.
11 25 10 15
11 23 11 23 11 23
15 10 25 10 20 25 10 15 25
(B) (C) (D)
11 25 10 15
11 25 10 20
15 25 11 20
Consider now the following trees (A is the input tree from above).
23 20 15 20
23 23 15 23
Which of the following sequences of trees would represent the series of basic operations (i.e. BST insertion, rotation left and rotation right) as they would be executed by the AVL insertion method seen in class?
A. A¡úE¡úH¡úC B. A ¡ú H ¡ú F ¡ú C C. A¡úH¡úD¡úF D. A¡úB¡úG¡úD E. A ¡ú B ¡ú F ¡ú E F. A ¡ú E ¡ú F ¡ú B
COMP 251 – Midterm
Page 6 of 10
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com