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

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

Amortized analysis is a technique to provide an upper bound on the actual cost of a sequence of operations

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

Consider the randomized quicksort. We have proved that it runs in O(nlogn)O(n \log n) time in expectation even for the worst input. Is the following statement true of false?

There exists some good inputs on which the expected running time of randomized quicksort is O(n)O(n) where nn is the input size.
(2分)
评测结果答案错误(0 分)
R1-3

Recall that, to solve the closest pair problem, the first step of the divide-and-conquer algorithm divides the point set into LL and RR according to the x-coordinate. Is the following statement true of false?

In the combine step of this algorithm, it is always able to find the closest pair with one point in LL and the other in RR.
(2分)
评测结果答案错误(0 分)
R1-4

Suppose that the internal memory can handle M=3M =3 records at a time. We use replacement selection algorithm to generate a long run on the following sequence {81, 94, 11, 96, 12, 80, 17, 98, 28, 58, 41, 75, 15}, then 98 belongs to the first run.

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

There exists an on-line algorithm for the bin packing problem that uses at most 3/2 the optimal number of bins for any instance.

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

Starting from the following configuration of a Hopfield Neural Network, the state-filpping algorithm will terminiate at a stable configuration after at most 32 iterations.

fig.jpg

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

For the Activity Selection Problem, we can get the optimal solution by selecting the interval which starts earliest.

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

Stop words should be ignored when creating inverted file indices, since they appear rarely in articles, and are not useful for indexing.

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

For the Turnpike reconstruction algorithm of NN points, assuming that the distance set DD is maintained as an AVL tree, the running time is O(N2logN)O(N^2\log{N}) if no backtracking happens.

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

A problem is NP-complete if and only if it is in NP\mathcal{NP} and there is no polynomial time algorithms for it.

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

When we solve the summation problem via designing the parallel algorithms, we shorten the asymptotic time complexity but take more asymptotic work loads comparing with the sequential algorithms.

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

After deleting 12 from the following red-black tree, 13, 14, 15 and 17 will change its color.

image.png

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

After merging two Leftist Heaps H1 and H2 of different NPL's, the NPL of the resulted Leftist Heap will be no more than max(NPL of H1, NPL of H2)

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

Given a set of 20000 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 precision of this filter is: ___.

Category Actual True Spam Actual False Spam
Retrieved True Spam 3000 6000
Retrieved False Spam 5000 6000
(3分)
评测结果答案错误(0 分)
R2-2

Scheduling Job Problem: There are nn jobs and mm identical machines (running in parallel) to which each job may be assigned. Each job j=1,,nj =1, \cdots, n must be processed on one of these machines for tjt_j time units without interruption. Each machine can process at most one job at a time. The aim is to complete all jobs as soon as possible; that is, if job jj completes at a time CjC_j (the schedule starts at time 00), then we wish to minimize Cmax=maxj=1,,nCjC_{max} = max_{j=1,\cdots, n}C_j. The length of an optimal schedule is denoted as OPT(Cmax)OPT(C_{max}).

Local Search Algorithm: Start with any schedule; consider the job ll that finishes last; check whether or not there exists a machine to which it can be reassigned that would cause this job to finish earlier. If so, transfer job ll to this other machine. The local search algorithm repeats this procedure until the last job to complete cannot be transferred. An illustration of this local move is shown in following figure.

画板 1-100.jpg

Which of the following statement is false?

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

You have 20 identical cores on which you want to schedule some nn jobs. Each job j{1,2,,n}j \in \{1,2, \ldots,n\} has a processing time pj>0p_j > 0. If SiS_i is the set of jobs assigned to core ii, let the load be jSipj\sum_{j\in S_i} p_j. Now, you want to partition the jobs among the cores to minimize the load of the most-loaded core.

We design a greedy algorithm that picks any unassigned job, and assign it to the core with the least current load.
What is the approximation ratio of the greedy algorithm? (Choose the smallest bound that applies.)

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

When deleting node 6 from the following Leftist Heap, which statement is False for the resulted priority queue?

最左堆1.png

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

Delete the minimum number from the binomial queue given in the following figure. Which one of the following statements must be FALSE? (Note that you can merge any two of carry, T1 and T2 when all of them are not none)

image.png

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

For the game tree shown below, for which values of xx the dashed branch with the scissors will be pruned by α\alpha-β\beta pruning? (Assume that the nodes are evaluated left to right)

image.png

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

A Huffman tree with 61 nodes is the optimal coding tree for nn characters. What a conclusion can we make for nn?

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

Which one of the following statements about the Maximum Finding is False?

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

Recall that in the merge sort, we divide the input list into two groups of equal size, sort them recursively, and merge them into one sorted list. Now consider a variant of the merge sort. In this variant, we divide the input list into n\sqrt{n} groups of equal size, where nn is the input size. What is the worst case running time of this variant? (You may use the fact that merging kk sorted lists takes O(mlogk)O(m\log k) where mm is the total number of elements in these lists.)

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

Consider the hiring problem. Assume that the nn candidates arrive in random order, and that no two candidates have the same performance. Let kk be some fixed parameter in the range [1,n][1, n]. We use the following algorithm.

interview the first k candidates, but hire none of them
for candidates i = k+1 to n
    if candidate i is better than all the first k candidates
        hire candidate i

How many candidtes will be hired in expectation?

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

Consider the following pseudo-code.

strange(a1,,ana_1, \ldots, a_n):
1.1.\,\,if n2022n \leq 2022 then return
2.2.\,\,strange(a1,,an/2a_{1}, \ldots, a_{\lfloor n/2 \rfloor})
3.3.\,\,strange(an/4+1,,a3n/4a_{\lfloor n/4 + 1 \rfloor}, \ldots, a_{\lfloor 3n/4 \rfloor})
4.4.\,\,for i=1i = 1 to nn:
5.5.\quadfor j=1j = 1 to n\lfloor \sqrt{n} \rfloor:
6.6.\quad\quadprint(ai+aja_i+a_j)
7.7.\,\,strange(an/4+1,,a3n/4a_{\lfloor n/4 + 1 \rfloor}, \ldots, a_{\lfloor 3n/4 \rfloor})
8.8.\,\,strange(an/2+1,,ana_{\lfloor n/2 + 1 \rfloor}, \ldots, a_{n})

What is the running time of this pseudo-code? Your answer should be as tight as possible. (You may assume that nn is a power of 2.)

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

A nn-nodes AVL tree TT performs insertion or deletion in the worst case that costs a0lgn+b0a_0 \lg n + b_0, a1lgn+b1a_1 \lg n + b_1, respectively, where a0,a1,b0,b1a_0, a_1, b_0, b_1 are constants. Now, we start from an empty tree, perform a sequence of nn insertions or deletions in the AVL tree. To analysis the amortized cost per insertion or deletion, we define a potential function Φ(T)=a1i=1nlgi\Phi(T) = a_1 \sum_{i=1}^{n} \lg i. What is the amortized cost per insertion or deletion?

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

How many of the following statements are correct?

  • If some NP-complete problem can be solved in polynomial time, then P=NP\mathcal{P}=\mathcal{NP}.
  • Given enough computational resources, for example time and space, any problem can be solved by a computer,
  • If a problem AA can be reduced to problem BB in polynomial time, then problem BB can also be reduced to problem AA in polynomial time.
(3分)
评测结果答案错误(0 分)
R2-14

To perform Insert on a B+ tree of order M, a node with M+1 keys will be split into 2 nodes.
After inserting 1,2,3,...,9,101, 2, 3, ... , 9, 10 consequentially into an initially empty B+ tree of order 3, how many split operations have occurred in total?

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

After deleting 7 from the given splay tree, which of the following statements about the resulting tree is impossible?

v2.jpg

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

We have 4 tapes for 3-way external merge sorting. How shall we distribute 31 runs into 3 tapes, such that the total number of passes is minimized.

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

After Inserting 12 into the following Skew Heap, which of the following statements is correct for the resulted Skew Heap?

斜堆1.png

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

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

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

Which one of the following statements about the Ranking problem is TRUE? (Assume that both arrays contain NN elements)

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

There are nn(=8) characters whose frequencies are the first nn(=8) Fibonacci numbers. How many of the following statements about the Huffman Coding is/are correct?

(1) No more than 2 characters have the same code length.
(2) For any nn (n>2n>2), the maximum length of the codes is n1n-1.
(3) The minimum length of codes is 2.

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

You have NN items and a knapsack with a capacity of WW. The weight of the ii-th item is wiw_i and the value is viv_i. Suppose the number of each item is infinite, calculate the maximum sum of value if the total weight of the items does not exceed the capacity of the knapsack. All numbers are in the range of [1,1000][1, 1000].

#include<bits/stdc++.h>
using namespace std;
int f[1010],w[1010],v[1010],n,W;
int main()
{
    scanf("%d%d",&n,&W);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&w[i],&v[i]);
    for(int i=1;i<=n;i++)
        for(int j=w[i];j<=W;j++)
            (3分)
    printf("%d\n",(3分));
    return 0;
}
评测结果编译错误(0 分)
函数题得分:0总分:8
R6-1
Structure of AVL Tree
(8分)

An AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. Figures 1-4 illustrate the rotation rules.

F1.jpg

F2.jpg

F3.jpg

F4.jpg

Now given a sequence of insertions, you are supposed to build the AVL tree. Then given a sequence of statements about the structure of the resulting tree, you are supposed to tell if they are correct or not. A statment is one of the following:

(1) A is the root
(2) A and B are siblings
(3) A is the parent of B
(4) A is the left child of B
(5) A is the right child of B

Format of functions:

Tree Build_AVL ( int input[ ], int n );
int Judge ( Tree T, int type, int A, int B );

The function Build_AVL is supposed to build an AVL tree according to the input sequence.

Here Tree is defined as the following:

typedef struct TNode *Tree;
struct TNode {
    int key;    //key of the node
    int height; //height of the subtree with this node as the root
    Tree left, right; //pointing to the left and right children of this node
};

The array input contains n (a positive integer) distinct keys to be inserted in order into an initially empty AVL tree. The root pointer of the resulting tree is supposed to be returned by Build_AVL.

The function Judge is supposed to test if a given statement for an AVL tree T is correct or not, and return 1 if the result is true, or 0 otherwise. The parameter type is an integer in [1, 5], which gives the index of a statement, as listed in the problem description; and A and B are the corresponging key values. For type 1, the value of B can be ignored. It is guaranteed that both A and B in the statements are in the tree.

Sample program of judge:

#include <stdio.h>
#include <stdlib.h>

typedef struct TNode *Tree;
struct TNode {
    int key;    //key of the node
    int height; //height of the subtree with this node as the root
    Tree left, right; //pointing to the left and right children of this node
};

Tree Build_AVL ( int input[ ], int n );
int Judge ( Tree T, int type, int A, int B );

int main()
{
    int n, *input;
    int m, type, A, B, i;
    Tree T;

    scanf("%d", &n);
    input = (int *)malloc(sizeof(int) * n);
    for (i=0; i<n; i++) scanf("%d", &input[i]);
    T = Build_AVL(input, n);
    scanf("%d", &m);
    for (i=0; i<m; i++) {
        scanf("%d %d", &type, &A);
        if (type != 1) scanf("%d", &B);
        if (Judge(T, type, A, B)) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

/* Your function will be put here */

Sample Input 1 (Figure 1):

3
88 70 61
8
1 70
1 61
2 61 88
2 88 70
3 88 70
3 70 61
4 88 70
5 88 70

Sample Output 1:

Yes
No
Yes
No
No
Yes
No
Yes

Sample Input 2 (Figure 2):

5
88 70 61 96 120
7
1 70
2 96 88
3 96 120
4 88 70
4 88 96
5 120 96
5 88 70

Sample Output 2:

Yes
No
Yes
No
Yes
Yes
No

Sample Input 3 (Figure 3):

6
88 70 61 96 120 90
8
1 70
1 88
2 90 61
3 70 61
3 96 70
4 90 96
5 90 88
5 96 88

Sample Output 3:

No
Yes
No
Yes
No
Yes
No
Yes

Sample Input 4 (Figure 4):

7
88 70 61 96 120 90 65
7
1 88
2 96 70
2 61 70
3 61 65
4 65 88
4 70 88
5 70 65

Sample Output 4:

Yes
No
Yes
No
Yes
No
Yes
评测结果编译错误(0 分)