大学MOOC Advanced Data Structures and Algorithm Analysis(Zhejiang University)1460402161 最新慕课完整章节测试答案

Quiz 1.1

1、单选题：
‎Insert 2, 1, 4, 5, 9, 3, 6, 7 into an initially empty AVL tree.  Which one of the following statements is FALSE?‌
选项：
A: 4 is the root
B: 3 and 7 are siblings
C: 2 and 6 are siblings
D: 9 is the parent of 7
答案: 【 3 and 7 are siblings】

2、单选题：
‌If the depth of an AVL tree is 6 (the depth of an empty tree is defined
to be -1), then the minimum possible number of nodes in this tree is:​
选项：
A: 13
B: 17
C: 20
D: 33
答案: 【 33】

Quiz 1.2

1、单选题：

‏For the result of accessing the keys 3, 9, 1, 5 in order in the splay
tree in the following figure, which one of the following statements is
FALSE?

‍

‏

‍选项：
A: 5 is the root
B: 1 and 9 are siblings
C: 6 and 10 are siblings
D: 3 is the parent of 4
答案: 【 3 is the parent of 4】

2、判断题：
‏Finding the maximum key from a splay tree will result in a tree with its root having no right subtree.‎
选项：
A: 正确
B: 错误
答案: 【 正确】

Quiz 1.3

1、单选题：
​Consider the following buffer management problem. Initially the buffer size (the number of blocks) is one. Each block can accommodate exactly one item. As soon as a new item arrives, check if there is an available block. If yes, put the item into the block, induced a cost of one. Otherwise, the buffer size is doubled, and then the item is able to put into. Moreover, the old items have to be moved into the new buffer so it costs k+1 to make this insertion, where k is the number of old items. Clearly, if there are N items, the worst-case cost for one insertion can be Ω(N). To show that the average cost is O(1), let us turn to the amortized analysis. To simplify the problem, assume that the buffer is full after all the N items are placed. Which of the following potential functions works?‌
选项：
A: The number of items currently in the buffer
B: The opposite number of items currently in the buffer
C: The number of available blocks currently in the buffer
D: The opposite number of available blocks in the buffer
答案: 【 The opposite number of available blocks in the buffer】

2、判断题：
‌For one operation, if its amortized time bound is O(logN), then its worst-case time bound must be O(logN).‌
选项：
A: 正确
B: 错误
答案: 【 错误】

Quiz 10.1

1、判断题：
‍All decidable problems are NP problems.‌
选项：
A: 正确
B: 错误
答案: 【 错误】

2、判断题：
‍All NP problems are decidable.‍
选项：
A: 正确
B: 错误
答案: 【 正确】

3、判断题：
‌All NP-complete problems are NP problems.‎
选项：
A: 正确
B: 错误
答案: 【 正确】

4、判断题：
​All NP problems can be solved in polynomial time in a non-deterministic machine.‍
选项：
A: 正确
B: 错误
答案: 【 正确】

Quiz 10.2

1、判断题：
‍The first problem that was proven to be NP-complete was Circuit-SAT.‌
选项：
A: 正确
B: 错误
答案: 【 正确】

Quiz 10.3

1、判断题：
‏All the languages can be decided by a non-deterministic machine.‏
选项：
A: 正确
B: 错误
答案: 【 错误】

2、判断题：

​Let A and B be decision problems in NP, and assume P NP. If A B and B   A, then both A and B are NP-complete.

‍选项：
A: 正确
B: 错误
答案: 【 错误】

3、判断题：
‎A language L belongs to NP iff there exist a two-input polynomial-time algorithm A that verifies language L in polynomial time.‍
选项：
A: 正确
B: 错误
答案: 【 正确】

Quiz 11.1

1、判断题：

‌An approximation scheme that runs in for any fixed is a polynomial-time approximation scheme.

‎

‌

‎选项：
A: 正确
B: 错误
答案: 【 正确】

2、判断题：

‍An -approximation scheme of time complexity is a PTAS but not an FPTAS.

‍

‍

‍选项：
A: 正确
B: 错误
答案: 【 错误】

Quiz 11.2

1、判断题：
​In the bin packing problem, we are asked to pack a list of items L to the minimum number of bins of capacity 1. For the instance L, let FF(L) denote the number of bins used by the algorithm First Fit. The instance L' is derived from L by deleting one item from L. Then FF(L') is at most of FF(L).‍
选项：
A: 正确
B: 错误
答案: 【 错误】

Quiz 11.3

1、判断题：
‏For the 0-1 version of the Knapsack problem, if we are greedy on taking the maximum profit or profit density, then the resulting profit must be bounded below by the optimal solution minus the maximum profit.​
选项：
A: 正确
B: 错误
答案: 【 正确】

Quiz 11.4

1、判断题：
‏The K-center problem can be solved optimally in polynomial time if K is a given constant.​
选项：
A: 正确
B: 错误
答案: 【 正确】

Quiz 12.1

1、判断题：
‌In local search, if the optimization function has a constant value in a neighborhood, there will be a problem.‎
选项：
A: 正确
B: 错误
答案: 【 正确】

2、判断题：
‌Greedy method is a special case of local search. ‏
选项：
A: 正确
B: 错误
答案: 【 错误】

Quiz 12.2

1、判断题：
‍Random restarts can help a local search algorithm to better find global maxima that are surrounded by local maxima.‍
选项：
A: 正确
B: 错误
答案: 【 正确】

2、判断题：
‏In Metropolis Algorithm, the probability of jumping up depends on T, the temperature. When the temperature is high, it'll be close to the original gradiant descent method.​
选项：
A: 正确
B: 错误
答案: 【 错误】

Quiz 12.4

1、单选题：
‎In the Maximum Cut problem, let us define S' be the neighbor of S such that S' can be obtained from S by moving one node from A to B, or one from B to A. We only choose a node which, when flipped, increases the cut value by at least w(A,B)/|V|. Then which of the following is true?‍
选项：
A: Upon the termination of the algorithm, the algorithm returns a cut (A,B) so that 2.5w(A,B)≥w(A*,B*), where (A*,B*) is an optimal partition.
B: The algorithm terminates after at most flips, where is the total weight of edges.
C: Upon the termination of the algorithm, the algorithm returns a cut (A,B) so that 2w(A,B)≥w(A*,B*).
D: The algorithm terminates after at most flips.
答案: 【 Upon the termination of the algorithm, the algorithm returns a cut (A,B) so that 2.5w(A,B)≥w(A*,B*), where (A*,B*) is an optimal partition.】

2、判断题：
‍Since finding a locally optimal solution is presumably easier than finding an optimal solution, we can claim that for any local search algorithm, one step of searching in neighborhoods can always be done in polynomial time.‌
选项：
A: 正确
B: 错误
答案: 【 错误】

Quiz 13.1

1、单选题：
‏If we repeatedly perform independent trials of an experiment, each of which succeeds with probability p>0, then the expected number of trials we need to perform until the first success is:‏
选项：
A: p/(1−p)
B: 1/(1−p)
C: 1/p
D: None of the above
答案: 【