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

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

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

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

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分)
评测结果答案错误(0 分)
R1-3

The 4-queen problem has exactly 2 distinct solutions. ~@

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

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分)
评测结果答案错误(0 分)
R1-5

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 分)
R1-6

A 2-3 tree with 12 leaves may have at most 10 nonleaf nodes. ~@

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

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分)
评测结果答案错误(0 分)
R1-8

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分)
评测结果答案错误(0 分)
R1-9

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 分)
R1-10

In a search engine, thresholding for query retrieves the top kk documents according to their weights. ~@

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

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 分)
R1-12

If L1pL2L_1 \leq_p L_2 and L2NPL_2 \in NP, then L1NPL_1 \in NP. ~@

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

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 分)
单选题得分:24总分:60
R2-1

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)+1NF(L) < \rho \cdot OPT(L) + 1 for some ρ\rho. Which one of the following statements is FALSE?

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

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

123456(1).jpg

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

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分)
评测结果答案错误(0 分)
R2-4

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

rbTree1.jpg

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

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分)
评测结果答案错误(0 分)
R2-6

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

bt.jpg

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

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

  • Heap Sort
  • Insertion Sort
  • Merge Sort
  • Quick Sort
  • Selection Sort
  • Shell Sort
(3分)
评测结果答案错误(0 分)
R2-8

Which one of the following statements is FALSE?

(3分)
评测结果答案正确(3 分)
R2-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)?

  • 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分)
评测结果答案正确(3 分)
R2-10

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分)
评测结果答案错误(0 分)
R2-11

Merge the two given skew heaps. Which one of the following statements is FALSE?

F1.JPG

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

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)B4P_2 = (A_1+A_2)\cdot B_4

P3=(A3+A4)B1P_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分)
评测结果答案错误(0 分)
R2-13

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

F3.JPG

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

Which of the following binomial trees can represent a binomial queue of size 78?

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

Which one of the following statements is FALSE?

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

Given a set of activities S={a1,a2,,an}S = \{ a_1, a_2, \cdots , a_n \}. Each aia_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 __.

greedy试题.png

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

Which one of the following statements is FALSE?

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

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

(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分)
评测结果答案正确(3 分)
R2-19

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 分)
R2-20

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分)
评测结果答案错误(0 分)
程序填空题得分:0总分:6
R5-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;
}
评测结果编译错误(0 分)
函数题得分:暂无总分:8
R6-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 (1N1061\le N \le 10^6) is the target number and KK (1KN1 \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=11X = 1 + 10 = 11

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

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

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

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

step 6: X=100+1=101X = 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.