浙江大学2020-21春夏《高级数据结构与算法分析》期末模拟练习
开始时间2016/01/01 08:00:00
结束时间2038/01/18 08:00:00
答题时长120分钟
考生
得分31
总分100

判断题得分:16总分:26
R1-1

When insert three keys into a non-empty 2-3 tree, and if the tree gains height when the first key is in, then it is possible that the 2-3 tree will gain more height after the insertions of the next two keys.

(2分)
评测结果答案错误(0 分)
R1-2

For an optimization problem, given a neighborhood, if its local optimum is also a global optimum, one can reach an optimal solution with just one step of local improvements.

(2分)
评测结果答案错误(0 分)
R1-3

A word which has high term frequency in each document may be a stop word.

(2分)
评测结果答案正确(2 分)
R1-4

If we build a skip list for nn elements, then we can search or delete any element in O(logn)O(\log n) time in the worst case.

(2分)
评测结果答案错误(0 分)
R1-5

If any NP-complete problem can be solved in polynomial time, then all the problems in NP can be solved in polynomial time.

(2分)
评测结果答案正确(2 分)
R1-6

Revisit the activity selection problem. Given a set of activities S={a1,a2,,an}S=\{a_1, a_2, \cdots, a_n \} that wish to use a resource, each aia_i takes place during a time interval. The goal is to arrange as many compatible activities as possible. Recall that several greedy approaches are introduced in the class, among which the one selecting an activity with the shortest length, denoted by SFSF, is not always optimal. However, we claim that SFSF accepts at least OPT/2|OPT|/2 activities, given that the optimal value is OPT|OPT|, where OPTOPT is an optimal solution. Check if the following is a correct proof.

We use a technique, called the charging scheme, similarly as the amortized analysis. Suppose each accepted activity of OPTOPT holds one dollar, which will be given to the activities accepted by SFSF in the following way. For any activity aia_i of OPTOPT, if aia_i is also accepted by SFSF, give the dolloar to itself. Otherwise, there must be some activity aja_j, accepted by SFSF, is not compatible with aia_i. Then aja_j receives one dollar from aia_i. Along this line, each activity of OPTOPT sends out one dollar to an activity in SFSF, while each activity of SFSF receives at most two dollars. It implies that SFSF accepts as least OPT/2|OPT|/2 activities.

(2分)
评测结果答案正确(2 分)
R1-7

The nn-th Fibonacci number can be computed by divide and conquer method of computing xnx^n, where xx is the matrix
(0111)\left( \begin{array}{l} 0 & 1 \\ 1 & 1 \end{array} \right).

Then the n2n^2-th Fibonacci number Fn2F_{n^2} can be computed in O(logn)O(\log n) time.

(2分)
评测结果答案正确(2 分)
R1-8

A binary tree that is not full cannot correspond to an optimal prefix code.

(2分)
评测结果答案正确(2 分)
R1-9

Managing shared memory for parallel programs is simpler than normal sequential programs.

(2分)
评测结果答案错误(0 分)
R1-10

The number of light nodes along the right path of a skew heap is O(logN)O(\log N).

(2分)
评测结果答案正确(2 分)
R1-11

Suppose that the replacement selection is applied to generate longer runs for N numbers with a priority queue of size M, the possible maximum length of the longest run is N.

(2分)
评测结果答案正确(2 分)
R1-12

What makes the time complexity analysis of a backtracking algorithm very difficult is that the number of solutions that do satisfy the restriction is hard to estimate.

(2分)
评测结果答案正确(2 分)
R1-13

If an operation takes O(1)O(1) expected time, then it takes O(1)O(1) amortized time.

(2分)
评测结果答案错误(0 分)
单选题得分:15总分:60
R2-1

Consider the problem of making change for nn cents using the fewest number of coins. Assume that each coin's value is an integer.
The coins of the lowest denomination(面额) is the cent.

(I) Suppose that the available coins are quarters (25 cents), dimes (10 cents), nickels (5 cents), and pennies (1 cent). The greedy algorithm always yields an optimal solution.

(II) Suppose that the available coins are in the denominations that are powers of c, that is, the denominations are c0c^0, c1c^1, ..., ckc^k for some integers c>1c>1 and k>=1k>=1. The greedy algorithm always yields an optimal solution.

(III) Given any set of kk different coin denominations which includes a penny (1 cent) so that there is a solution for every value of nn, greedy algorithm always yields an optimal solution.

Which of the following is correct?

(3分)
评测结果答案错误(0 分)
R2-2

We have mm balls and mm boxes. Each ball is assigned to one of the mm boxes independently and uniformly at random (i.e., equally likely to each box). Suppose that mm is sufficiently large, and ee is the natural number, which of the following is FALSE?

(3分)
评测结果答案错误(0 分)
R2-3

Merge the two leftist heaps in the following figure. Which one of the following statements is FALSE?

a.jpg

(3分)
评测结果答案正确(3 分)
R2-4

In typical applications of data structures, it is not a single operation that is performed, but rather a sequence of operations, and the relevant complexity measure is not the time taken by one operation but the total time of a sequence. Hence instead of imposing any explicit structural constraint, we allow the data structure to be in an arbitrary state, and we design the access and update algorithms to adjust the structure in a simple, uniform way, so that the efficiency of future operations is improved. We call such a data structure self-adjusting. For example skew heaps and splay trees are such kind of structures.

Which one of the following statements is FALSE about self-adjusting data structures?

(3分)
评测结果答案错误(0 分)
R2-5

In this problem, we would like to find the amortized cost of insertion in a dynamic table TT. Initially the size of the table TT is 1. The cost of insertion is 11 if the table is not full. When an item is inserted into a full table, the table TT is expanded as a new table of size 3 times larger. Then, we copy all the elements of the old table into this new table, and insert the item in the new table.

Let num(T)num(T) be the number of elements in the table TT, and size(T)size(T) be the total number of slots of the table. Clearly, if the table TT is full, the cost of one insertion is num(T)+1num(T) + 1.

Let DiD_i denote the table after applying the iith operation on Di1D_{i-1}.
Which of the following potential function Φ(Di)\Phi(D_i) can help us achieve O(1)O(1) amortized cost per insertion?

(3分)
评测结果答案正确(3 分)
R2-6

Given the following game tree, the red node will be pruned with α-β pruning algorithm if and only if ___.

b.jpg

(3分)
评测结果答案错误(0 分)
R2-7

Which of the asymptotic upper bound for the following recursive T(n)T(n) is correct?

(3分)
评测结果答案错误(0 分)
R2-8

Consider two disjoint sorted arrays A[1m]A[1\ldots m] and B[1n]B[1\ldots n], we would like to compute the kk-th smallest element in the union of the two arrays, where kmin{m,n}k \leq \min\{m, n\}. Please choose the smallest possible running time among the following options.

(3分)
评测结果答案正确(3 分)
R2-9

If there are 28 nodes in an AVL tree, then the maximum depth of the tree is ____. The depth of an empty tree is defined to be -1.

(3分)
评测结果答案错误(0 分)
R2-10

Two red-black trees are said to be different if they have different tree structures or different node colors. How many different red-black trees are there with 3 internal nodes?

(3分)
评测结果答案错误(0 分)
R2-11

Consider the bin packing problem which uses a minimum number of bins to accommodate a given list of items. Recall that Next Fit (NF) and First Fit (FF) are two simple approaches, whose (asymptotic) approximation ratios are 2 and 1.7, respectively. Now we focus on a special class I2I2 of instances in which only two distinct item sizes appear. Check which of the following statements is true by applying NF and FF on I2I2.

(3分)
评测结果答案正确(3 分)
R2-12

The Merging problem is to merge two non-decreasing arrays A(1), A(2), ..., A(nn) and B(1), B(2), ..., B(nn) into another non-decreasing array C(1), C(2), ..., C(2n2n). To solve it in parallel, we turn it into a Ranking problem. That is, to compute RANK(A(ii),B) and RANK(B(ii),A) for every 1in1\le i\le n, where RANK(e,S) is the position of e in S. The following psuedo-code is for solving the Ranking problem parallely.

for Pi, 1<=i<=n  pardo
    RANK(A(i),B) := BS(A(i),B)
    RANK(B(i),A) := BS(B(i),A)

where BS(e,S) is to find the position of e in S by binary search.

Which of the following gives the time and work load of the algorithm?

(3分)
评测结果答案错误(0 分)
R2-13

In a binomial queue, the total number of the nodes at even depth is always ___ than that of the nodes at odd depth (the root is defined to be at the depth 0).

(3分)
评测结果答案正确(3 分)
R2-14

Consider the Minimum Degree Spanning Tree problem: Given a connected undirected graph G(V,E)G(V,E), find a spanning tree TT whose maximum degree over its vertices is minimized over all spanning trees of GG. The problem can be shown to be NP-hard by reduction from the Hamiltonian Path Problem. On the other hand, we can use local search to design approximating algorithms. Denote d(u)d(u) as the degree of vertex uu on a tree TT. Consider the following algorithm:

  1. Find an arbitrary spanning tree TT of GG.
  2. If there's some edge eE(G)\E(T)e \in E(G)\backslash E(T) with endpoints u,vu, v, and there's some other vertex ww on the path between u,vu, v on TT such that max{d(u),d(v)}+1<d(w)max \{d(u), d(v) \}+1 < d(w), then we replace an edge ee^\prime incident to ww on TT with ee, i.e. T:=T{e}\{e}T:= T \cup \{e\} \backslash \{e^\prime\}.
  3. Repeat Step (2) until there's no edge to replace.

It can be shown that this algorithm will terminate at a solution with maximum vertex degree OPT+O(logV)OPT+O(\log |V|). To show the algorithm will terminate in finite steps, a useful technique is to define a nonnegative potential function ϕ(T)\phi(T) and to show ϕ(T)\phi(T) is strictly decreasing after each step. Which of the following potential functions below satisfies the above requirements?

(3分)
评测结果答案错误(0 分)
R2-15

To sort NN numbers by external sorting using a kk-way merge and a kk-size heap, which statement is TRUE about the total comparison times T(N,k)T(N,k) and kk?

(3分)
评测结果答案错误(0 分)
R2-16

Among the following 66 statements about AVL trees and splay trees, how many of them are correct?

(1) AVL tree is a kind of height balanced tree. In a legal AVL tree, each node's balance factor can only be 00 or 11.

(2) Define a single-node tree's height to be 11. For an AVL tree of height hh, there are at most 2h12^h - 1 nodes.

(3) Since AVL tree is strictly balanced, if the balance factor of any node changes, this node must be rotated.

(4) In a splay tree, if we only have to find a node without any more operation, it is acceptable that we don't push it to root and hence reduce the operation cost. Otherwise, we must push this node to the root position.

(5) In a splay tree, for any non-root node XX, its parent PP and grandparent GG (guranteed to exist), the correct operation to splay XX to GG is to rotate XX upward twice.

(6) Splaying roughly halves the depth of most nodes on the access path.

(3分)
评测结果答案错误(0 分)
R2-17

Given a 2-3 tree as shown in the following figure. Which of the following pairs of insertions will result in a 2-3 tree with different structures?

ADS1.jpg

(3分)
评测结果答案错误(0 分)
R2-18

Given a set of 10000 emails in the mailbox, our task is to retrieve the spam emails from this set. The statistic data for a spam filter's performance are shown in the following table. The recall of this filter is: ___.

Category Actual True Spam Actual False Spam
Retrieved True Spam 2000 1000
Retrieved False Spam 2000 5000
(3分)
评测结果答案错误(0 分)
R2-19

Which of the following statements is FALSE?

(3分)
评测结果答案错误(0 分)
R2-20

About Vertex Cover problem, which of the following statements is FALSE?

(3分)
评测结果答案错误(0 分)
程序填空题得分:0总分:6
R5-1

The function BinQueue_Merge is to merge two binomial queues H1 and H2, and return H1 as the resulting queue.

BinQueue BinQueue_Merge( BinQueue H1, BinQueue H2 ) { 
    BinTree T1, T2, Carry = NULL;     
    int i, j;
    H1->CurrentSize += H2-> CurrentSize;
    for ( i=0, j=1; j<= H1->CurrentSize; i++, j*=2 ) {
        T1 = H1->TheTrees[i]; T2 = H2->TheTrees[i];
        switch( (3分) ) { 
        case 0:
        case 4: break;
        case 3: 
        case 7: 
                (3分);
                H2->TheTrees[i] = NULL; break;
        case 1: 
                H1->TheTrees[i] = Carry; Carry = NULL; break;  
        case 2: 
                H1->TheTrees[i] = T2; H2->TheTrees[i] = NULL; break;
        case 5: 
                Carry = CombineTrees( T1, Carry );
                H1->TheTrees[i] = NULL; break;
        case 6: 
                Carry = CombineTrees( T1, T2 );
                H1->TheTrees[i] = H2->TheTrees[i] = NULL; break;
        } /* end switch */
    } /* end for-loop */
    return H1;
}
评测结果编译错误(0 分)
编程题得分:暂无总分:8
R7-1
Hand-made Cream
(8分)

Suppose you are a baker planning to bake some hand-made cream breads.

To bake a cream bread, we need to use one slice of bread and one kind of cream. Each hand-made cream bread has a taste score to describe how delicious it is, which is obtained by multiplying the taste score for bread and the taste score for cream. (The taste scores could be negative, howerver, two negative tast scores can still produce delicious cream bread.)

The bread and cream are stored separately.

The constraint is that you need to examine the breads in a given order, and for each piece of bread, you have to decide immediately (without looking at the remaining breads) whether you would like to take it.

After you are finished with breads, you will take the same amount of cream in the same manner. The breads and creams you take will be paired in the same order as you take them.

Given NN taste scores for bread and MM taste scores for cream, you are supposed to calculate the maximum total taste scores for all hand-made cream bread.

Input Specification:

Each input file contains one test case. For each case, the first line contains two integers NN and MM (1N,M1031\le N,M\le 10^3), which are the numbers of bread and cream, respectively.

The second line gives NN taste scores for bread.

The third line gives MM taste scores for cream.

The taste scores are integers in [103,103][-10^3, 10^3].

All the numbers in a line are separated by a space.

Output Specification:

Print in a line the maximum total taste score.

Sample Input:

3 4
-1 10 8
10 8 11 9

Sample Output:

188

Hint:

The maximum total taste score for the sample case is 10×10+8×11=18810\times 10 + 8\times 11 = 188.

hint.png