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

判断题得分:24总分:26
1-1

Given 1000 runs and 8 tapes. If simple kk-way merge is used, the minimum number of passes required is 5 (runs generation pass is not counted). (2分)

       

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

1-2

For a leftist heap with NN nodes, the worst-case running time of all operations (insert/delete min/merge) is Θ(N)\Theta(N). (2分)

       

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

1-3

If a data structure supports an operation QI such that a sequence of nn QI’s takes Θ(n2logn)\Theta(n^2\log n) time to perform in the worst case, then the amortized cost of a QI operation is Θ(nlogn)\Theta(n \log n) , while the actual time of a single QI operation could be as high as Θ(n2logn)\Theta(n^2\log n). (2分)

       

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

1-4

Consider a state-flipping algorithm for the Maximum-Cut problem. We say that partitions (A,B)(A, B) and (A,B)(A', B') are neighbors under the kk-flip rule if (A,B)(A', B') can be obtained from (A,B)(A, B) by moving at most kk nodes from one side of the partition to the other. If (A,B)(A, B) is a local optimum under the pp-flip rule, it is also a local optimum under the kk-flip rule for every k<pk < p. (2分)

       

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

1-5

The 4-queen problem has exactly 2 distinct solutions. (2分)

       

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

1-6

A randomized Quicksort algorithm has an O(NlogN)O(N \log N) expected running time, only if all the input permutations are equally likely. (2分)

       

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

1-7

A 2-3 tree with 12 leaves may have at most 11 nonleaf nodes. (2分)

       

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

1-8

The Huffman code is one kind of optimal prefix codes. For a given alphabet and its characters' frequencies,the Huffman codes may not be unique, but the Huffman code length of each character is unique. (2分)

       

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

1-9

If L1pL2L_1 \leq_p L_2 and L1NPL_1 \notin NP, then L2NPL_2 \notin NP. (2分)

       

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

1-10

Givien two n×nn\times n matrices AA and BB, the time complexity of the simple matrix multiplication C=ABC = A \cdot B is O(n3)O(n^3). Now let's consider the following Divide and Conquer idea:

Divide each matrix into four n2×n2\frac{n}{2}\times\frac{n}{2} submatrics as follows:

[C1C2C3C4]\begin{bmatrix} C_1 & C_2 \\ C_3 & C_4 \end{bmatrix} = [A1A2A3A4][B1B2B3B4]\begin{bmatrix} A_1 & A_2 \\ A_3 & A_4 \end{bmatrix} \cdot \begin{bmatrix} B_1 & B_2 \\ B_3 & B_4 \end{bmatrix}

We recursively calculate each block of CC as C1=A1B1+A2B3C_1 = A_1\cdot B_1+A_2\cdot B_3 and so on. This can reduce the time complexity of the simple calculation. (2分)

       

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

1-11

In the bin packing problem, we are asked to pack a list of items LL to the minimum number of bins of capacity 1. For the instance LL, let FF(L)FF(L) denote the number of bins used by the algorithm First Fit. The instance LL' is derived from LL by deleting one item from LL. Then FF(L)FF(L') is at most of FF(L)FF(L). (2分)

       

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

1-12

Recall the discussion about the Maximum Finding Problem (that is, to find the maximum among nn numbers in an array), Common CRCW memory strategy is used to assure T(n)=O(1)T(n) = O(1) for the parallel algorithm. Actually, we can also apply Arbitrary CRCW memory strategy to keep O(1)O(1) time complexity. Now let us consider a new memory strategy, namely the Concurrent Read Owner Write (CROW). It means that each memory has an official "owner". Only the "owner" can write to the corresponding memory. Then there is no parallel algorithm that can solve the problem with T(n)=O(1)T(n) = O(1) using CROW memory strategy. (2分)

       

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

1-13

In a search engine, thresholding for query retrieves the top kk documents according to their weights. (2分)

       

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

单选题得分:57总分:60
2-1

Which of the following binomial trees can represent a binomial queue of size 141? (3分)

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

2-2

Two spam mail detection systems are tested on a dataset with 10000 ordinary mails and 2000 spam mails. System A detects 300 ordinary mails and 1600 spam mails, and system B detects 315 ordinary mails and 1800 spam mails. If our primary concern is to keep the important mails safe, which of the following is correct? (3分)

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

2-3

In the bin packing problem, suppose that the maximum size of the items is bounded from above by α<1\alpha < 1. Now let's apply the Next Fit algorithm to pack a set of items LL into bins with capacity 1. Let NF(L)NF(L) and OPT(L)OPT(L) denote the numbers of bins used by algorithms Next Fit and the optimal solution. Then for all LL, we have NF(L)<ρOPT(L)+1 NF(L) < \rho \cdot OPT(L) + 1 for some ρ \rho. Which one of the following statements is FALSE? (3分)

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

2-4

Given a set of activities S={a1,a2,,an}S = \{ a_1, a_2, \cdots , a_n \}. Each ai a_i takes place during a time interval [si,fi) [s_i, f_i). If an instance SS given as the following, the maximum-size of mutually compatible activities is __. (3分)

greedy试题.png

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

2-5

Suppose that the replacement selection is applied to generate longer runs with a priority queue of size 5. Given the sequence of numbers { 17, 2, 6, 57, 51, 86, 5, 94, 43, 54, 39, 87, 29}, the longest run contains __ numbers. (3分)

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

2-6

Which one of the following statements is FALSE? (3分)

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

2-7

The Online Hiring Algorithm ( hire only once ) is described as the following:

int OnlineHiring ( EventType C[ ], int N, int k )
{
    int Best = N;
    int BestQ = -INFINITY ;
    for ( i=1; i<=k; i++ ) {
        Qi = interview( i );
        if ( Qi > BestQ )   BestQ = Qi;
    }
    for ( i=k+1; i<=N; i++ ) {
        Qi = interview( i );
        if ( Qi > BestQ ) {
            Best = i;
            break;
        }
    }
    return Best;
}

Assume that the quality input C[ ] is uniformly random. When NN = 271 and kk = 90, the probability of hiring the NNth candidate is__. (3分)

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

2-8

Givien two n×nn\times n matrices AA and BB. Let's consider the following Divide and Conquer idea to do matrix multiplication C=ABC = A \cdot B.

Divide each matrix into four n2×n2\frac{n}{2}\times\frac{n}{2} submatrics as follows:

[C1C2C3C4]\begin{bmatrix} C_1 & C_2 \\ C_3 & C_4\end{bmatrix} = [A1A2A3A4][B1B2B3B4]\begin{bmatrix} A_1 & A_2 \\ A_3 & A_4 \end{bmatrix} \cdot \begin{bmatrix} B_1 & B_2\\ B_3 & B_4 \end{bmatrix}

We define P1,P2,,P7P_1, P_2, \cdots ,P_7 as follows:

P1=A1(B2B4)P_1 = A_1\cdot(B_2-B_4)

P2=(A1+A2)B4 P_2 = (A_1+A_2)\cdot B_4

P3=(A3+A4)B1 P_3 = (A_3+A_4)\cdot B_1

P4=A4(B3B1) P_4 = A_4\cdot(B_3-B_1)

P5=(A1+A4)(B1+B4) P_5 = (A_1+A_4)\cdot(B_1+B_4)

P6=(A2A4)(B3+B4) P_6 = (A_2-A_4)\cdot(B_3+B_4)

P7=(A1A3)(B1+B2) P_7 = (A_1-A_3)\cdot(B_1+B_2)

Here all the matrix multiplications are done recursively. Then each part of CC can be calculated by simple additions and subtractions among P1,P2,,P7P_1, P_2, \cdots ,P_7.

Which of the following is the closest to the actual time complexity? (3分)

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

2-9

When measure the performance of parallel algorithm, we often use work load (W(n)W(n)) and worst-case running time (T(n)T(n)). How many evaluation metrics are asymptotically equivalent to W(n)W(n) and T(n)T(n)? (3分)

  • P(n)=W(n)/T(n)P(n) = W(n)/T(n) processors and T(n)T(n) time (on a PRAM)
  • W(n)/pW(n)/p time using any number of pW(n)/T(n)p \geq W(n)/T(n) processors (on a PRAM)
  • W(n)/p+T(n)W(n)/p + T(n) time using any number of pp processors (on a PRAM)
评测结果
答案正确(3 分)

2-10

After splaying at node 2 in the given tree, which of the following statements about the resulting tree is FALSE? (3分)

123456(1).jpg

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

2-11

How many of the following sorting methods use(s) Divide and Conquer algorithm? (3分)

  • Heap Sort
  • Insertion Sort
  • Merge Sort
  • Quick Sort
  • Selection Sort
  • Shell Sort
评测结果
答案正确(3 分)

2-12

Insert 28, 23, 54, 61, 98, 37 into an initially empty AVL tree first. Then immediately insert one of the following keys. Which one will cause an RL rotation? (3分)

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

2-13

There are nn jobs, and each job jj has a processing time tjt_j. We will use a local search algorithm to partition the jobs into two groups A and B, where set A is assigned to machine M1M_1 and set B to M2M_2. The time needed to process all of the jobs on the two machines is T1=jAtjT_1 = \sum_{j\in A} t_j, T2=jBtjT_2 = \sum_{j\in B} t_j. The problem is to minimize T1T2|T_1 - T_2|.

Local search: Start by assigning jobs 1,,n/21, \ldots, n/2 to M1M_1, and the rest to M2M_2. The local moves are to move a single job from one machine to the other, and we only move a job if the move decreases the absolute difference in the processing times. Which of the following statement is true? (3分)

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

2-14

Which one of the following statements is FALSE? (3分)

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

2-15

Which one of the following statements is FALSE? (3分)

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

2-16

Delete the minimum number from the given leftist heap. Which one of the following statements is TRUE? (3分)

F3.JPG

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

2-17

Given the following game tree, the red node will be pruned with α-β pruning algorithm if and only if __. (3分)

bt.jpg

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

2-18

After inserting 1 into the red-black tree given in the figure, which node(s) will have its/their color(s) changed? (3分)

rbTree1.jpg

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

2-19

After inserting 0 into the 2-3 tree given in the figure, how many of the following statements are FALSE? (3分)

(S1) The tree grows higher;

(S2) 2 and 4 are in the same interior node;

(S3) the root node still contains 9 only;

(S4) the interior node containing 12 keeps unchanged.

2-3tree.jpg

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

2-20

Merge the two given skew heaps. Which one of the following statements is FALSE? (3分)

F2.JPG

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

程序填空题得分:6总分:6
5-1

The function DeleteRoot is to delete the root of a subtree with index Ind from a binomial queue H. The rest of the subtree is then stored as a new binomial queue and returned.

BinQueue DeleteRoot( BinQueue H, int Ind )
{
	BinTree OldRoot, SubTree;
	BinQueue NewBinQ;
	int i;
	
	OldRoot = H->TheTrees[Ind];
	SubTree = OldRoot->LeftChild;
	free(OldRoot);
	NewBinQ = Initialize();
	NewBinQ->CurrentSize = (3分);
	for ( (3分) ) {
		NewBinQ->TheTrees[i] = SubTree;
		SubTree = SubTree->NextSibling;
		NewBinQ->TheTrees[i]->NextSibling = NULL;
	}
	return NewBinQ;
}
评测结果
答案正确(6 分)
测试点得分
序号结果得分
0答案正确3
1答案正确3

函数题得分:6总分:8
6-1
Variable Manipulation (8分)

CYLL has an integer-typed variable XX whose initial value is 1. The variable can be updated in each step by applying either of the two operations:

  1. Multiply the variable by a fixed integer KK: X=X×KX = X \times K

  2. Add an integer TT (1T101 \le T \le 10) to the number: X=X+TX = X + T

Given two integers NN and KK as inputs, can you help CYLL to decide the minimum number of steps required before she obtains the number NN as the variable value?

Format of functions:

int FindMinSteps(int N, int K);

Here NN (1N106 1\le N \le 10^6 ) is the target number and KK (1KN 1 \le K \le N ) is the multiplication factor, which are integers as described in the problem specification.

The function is expected to return the minimum number of steps before the variable XX reaches value NN. (See the sample input/output for a concrete example.)

Sample program of judge:

#include <stdio.h>

int FindMinSteps(int N, int K);

int main()
{
  int N, K;
	
	scanf("%d%d", &N, &K);
	
	printf("%d", FindMinSteps(N, K));
	
	return 0;
}	

/* Implement the 'FindMinSteps' function here */

Sample input:

101 2

Sample output:

6

Sample explanation :

step 1: X=1+10=11 X = 1 + 10 = 11

step 2: X=112=22 X = 11 * 2 = 22

step 3: X=222=44 X = 22 * 2 = 44

step 4: X=44+6=50 X = 44 + 6 = 50

step 5: X=502=100 X = 50 * 2 = 100

step 6: X=100+1=101 X = 100 + 1 = 101

Note that this is not the only way to reach 101 in 6 steps, however, we care about the minumum number of steps, which is unique, rather than how you reach there.

编译器
GCC
代码
int FindMinSteps(int N, int K)
{
    if(N<=1){
        return 0;
    }
    if(N<=11){
        return 1;
    }
    int temp=N/K;
    int a=1;
    int step=0;
    while(a<temp){
        if(step==0&&a+10<=temp){
        a=a+10;
        step++;
        }
        if(step>0&&a*K<=temp){
        a=a*K;
        step++;
        }
        if(step>0&&a*K>temp){
        while(a+10<=temp){
        a=a+10;
        step++;
        }
        if(a!=temp){
        a=temp;
        step++;
        }
        }
    }
    if(a*K<=N){
    a=a*K;
    step++;
    }
    while(a+10<=N){
    a=a+10;
    step++;
    }
    if(a!=N){
    a=N;
    step++;
    }
    return step;
}
评测结果
部分正确(6 分)
编译器输出
a.c: In function ‘main’:
a.c:9:2: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &K);
  ^~~~~~~~~~~~~~~~~~~~~
测试点得分
测试点结果得分耗时内存
0答案正确24.00 ms380 KB
1答案正确24.00 ms360 KB
2答案错误03.00 ms360 KB
3答案正确14.00 ms256 KB
4运行超时00.00 ms0 KB
5答案正确13.00 ms284 KB