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

判断题得分:15总分:29
R1-1

In external sorting, a kk-way merging is usually used in order to reduce the number of passes and we will take the kk as large as possible as long as we have enough amount of tapes. ~@

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

Let S be the set of activities in Activity Selection Problem. The greedy rule of "collecting the activity that starts the latest" is correct for finding a maximum-size subset of mutually compatible activities of S. ~@

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

Insert { 1, 2, 5, 3, 8, 4, -1, 10, 128, 34, 15, 63, 18, -24, 186 } into an initially empty binomial queue, the resulting roots are 186, -24, 15 and -1. ~@

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

In the problem of NN Queens, since the game tree contains N!N! leaves, the space complexity for solving the problem is Ω(N!)\Omega (N!). ~@

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

Recall the amortized analysis for Splay Tree and Leftist Heap, from which we can conclude that the amortized cost (time) is never less than the average cost (time). ~@

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

A skew heap is a heap data structure implemented as a binary tree. Skew heaps are advantageous because of their ability to merge more quickly than balanced binary heaps. The worst case time complexities for Merge, Insert, and DeleteMin are all O(N)O(N), while the amorited time complexities for Merge, Insert, and DeleteMin are all O(logN)O(logN). ~@

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

For the recurrence equation T(N)=aT(N/b)+f(N)T(N)=aT(N/b)+f(N), if af(N/b)=Kf(N)af(N/b)=Kf(N) for some constant K>1K>1, then T(N)=Θ(f(N))T(N)=\Theta(f(N)). ~@

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

While comparing a serial algorithm with its parallel counterpart, we just concentrate on reducing the work load. ~@

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

Consider a Knapsack problem with nn items. If no items have a size larger than n3n^3, then it is no longer NP-hard. ~@

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

If the depth of an AVL tree with nodes { 1, 2, 3, 4 } is 3 (the depth of the root is 1), then either node 2 or node 3 must have two children. ~@

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

Consider the online hiring problem, in which we have total kk candidates. First of all, we interview nn candidates but reject them all. Then we hire the first candidate who is better than all of the previous candidates you have interviewed. It is true that the probability of the mmth candidate is the best is nk(m1)\frac{n}{k(m-1)}, where m>nm > n. ~@

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

As we know there is a 2-approximation algorithm for the Vertex Cover problem. Then we must be able to obtain a 2-approximation algorithm for the Clique problem, since the Clique problem can be polynomially reduced to the Vertex Cover problem. ~@

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

Recall is more important than precision when evaluating the explosive detection in airport security. ~@

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

For any red node X in a Red-Black tree, if it has two children, then the children's colors must be the same. ~@

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

We are given a set of sites S={s1,s2,,sn}S=\{ s_1, s_2, \cdots, s_n\} in the plane, and we want to choose a set of kk centers C={c1,c2,,ck}C=\{ c_1, c_2, \cdots, c_k\} so that the maximum distance from a site to the nearest center is minimized. Here cic_i can be an arbitrary point in the plane.

A local search algorithm arbitrarily choose kk points in the plane to be the centers, then

  • (1) divide SS into kk sets, where SiS_i is the set of all sites for which cic_i is the nearest center; and
  • (2) for each SiS_i, compute the central position as a new center for all the sites in SiS_i.

If steps (1) and (2) cause the covering radius to strictly decrease, we perform another iteration, otherwise the algorithm stops.

When the above local search algorithm terminates, the covering radius of its solution is at most 2 times the optimal covering radius.
~@

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

Assume that Problem X is reduced to Problem Y in polynomial time, where Y is NP-hard. Moreover, Y adimts a ρ\rho-approximation algorithm, and there is no (ρϵ)(\rho-\epsilon)-approroximation algorithm unless P=NP. Which one of the following statements is TRUE?

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

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 0.

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

Which node is root 7's child after splaying 4 in the given splay tree?

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

Given a 2-3 tree as shown in the figure, after inserting 18 with splitting strategy, where will the key 15 be?

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

There are 14000 documents in the database. The statistic data for one query are shown in the following table. The recall is: __

Relevant Irrelevant
Retrieved 2000 6000
Not Retrieved 4000 2000
(3分)
评测结果答案正确(3 分)
R2-6

Let us consider the problem of finding a large cut in an undirected graph G=(V,E)G=(V, E) which has nn vertices and mm edges. A cut is a partition of the vertices into two disjoint sets, and the value of a cut is the weight of all edges crossing from one side of the partition to the other. Here we consider the case where all edges in the graph have the same weight 1.

Suppose that a partition of VV into two disjoint sets AA and BB is given by a randomized algorithm, in which each vertex is randomly and independently assigned to one of the two sets.

Which of the following statements is FALSE?

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

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+1k+1 to make this insertion, where kk is the number of old items. Clearly, if there are NN items, the worst-case cost for one insertion can be Ω(N)\Omega (N). To show that the average cost is O(1)O(1), let us turn to the amortized analysis. To simplify the problem, assume that the buffer is full after all the NN items are placed. Which of the following potential functions works?

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

Given a recurrence equation fi,j,k=fi,j+1,k+min0lk{fi1,j,l+wj,l}f_{i,j,k} =f_{i,j+1,k}+\min_{0 \le l \le k}\{f_{i-1,j,l}+w_{j,l}\}. To solve this equation in an iterative way, we cannot fill up a table as follows:

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

In the Red Black tree that results after successively inserting the keys 20, 22, 18, 12, 15, 8, into an initially empty Red Black tree, which nodes will be black?

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

Spanning Tree Problem: Given an undirected graph G=(V,E)G = (V, E), where V=n|V | = n and E=m|E| = m. Let FF be the set of all spanning trees of GG. Define d(u)d(u) to be the degree of a vertex uVu \in V. Define w(e)w(e) to be the weight of an edge eEe \in E.
We have the following three variants of spanning tree problems:

  • (1) Max Leaf Spanning Tree: find a spanning tree TFT \in F with a maximum number of leaves.
  • (2) Minimum Spanning Tree: find a spanning tree TFT \in F with a minimum total weight of all the edges in TT.
  • (3) Minimum Degree Spanning Tree: find a spanning tree TFT \in F such that its maximum degree of all the vertices is the smallest.

For a pair of edges (e,e)(e, e') where eTe \in T and e(GT)e' \in (G-T) such that ee belongs to the unique cycle of TeT\cup e', we define edge-swap(e,e)(e, e') to be (Te)e(T-e)\cup e'.

Here is a local search algorithm:

T = any spanning tree in F;
while (there is an edge-swap(e, e') which reduces Cost(T)) {
    T = T - e + e';
}
return T;

Here Cost(T) is the number of leaves in T in Max Leaf Spanning Tree; or is the total weight of T in Minimum Spanning Tree; or else is the minimum degree of T in Minimum Degree Spanning Tree.

Which of the following statements is TRUE?

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

When solving a problem with input size NN by divide and conquer, if at each step, the problem is divided into 8 sub-problems and each size of these sub-problems is N/3N/3, and they are conquered in O(N2logN)O(N^2logN). Which one of the following is the closest to the overall time complexity?

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

KK-center problem: Given NN cities with specified distances, one wants to build KK warehouses in different cities and minimize the maximum distance of a city to a warehouse.

Which of the following is false?

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

In the Tic-tac-toe game, a "goodness" function of a position is defined as f(P)=WcomputerWhumanf(P) = W_{computer} - W_{human}
where WW is the number of potential wins at position PP.
In the following figure, O represents the computer and X the human. What is the goodness of the position of the figure?

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

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

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

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

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

Which one of the following statements is TRUE about the NP class?

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

In external sorting, in order to reduce the number of passes, minimizing the initial number of runs (i.e. generating longer runs ) is a good idea. Suppose the input record keys are (25, 74, 56, 34, 21, 11, 29, 80, 38, 53) and the internal memery can hold only 3 records, the minimum number of initial runs obtained by replacement selection is__ 。

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

When inserting 1, 2, 3, 6, 5, and 4 one by one into an initially empty AVL tree,which kinds of rotations will be encountered?

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

In proving the amortized bound of a Merge operation in skew heaps, the potential of a skew heap is defined to be the total number of right heavy nodes. Then we can prove that, in an NN-node skew heap, the amortized cost for a Merge operation is exactly __ .

Hint:

Define the weight of a node, w(x)w(x), to be the number of descendants of xx (including xx). A non-root node is said to be heavy if its weight is greater than half the weight of its parent.

  • Lemma 1: At most one child is heavy, of all children of any node.

  • Lemma 2: On any path from node xx down to a descendant yy, there are at most log2w(x)w(y)\lfloor log_2 \frac{w(x)}{w(y)} \rfloor light nodes, excluding xx.

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

Given 4 characters (u,v,w,x)(u, v, w, x) with some frequencies (fu,fv,fw,fx)(f_u, f_v, f_w, f_x) in a text. If the corresponding Huffman codes are uu: 00, vv: 010, ww: 011 and xx: 1. Which of the following sets of frequencies is a possible one for (fu,fv,fw,fx)(f_u, f_v, f_w, f_x) ?

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

The functions BinQueue_Find and Recur_Find are to find X in a binomial queue H. Return the node pointer if found, otherwise return NULL.

BinTree BinQueue_Find( BinQueue H, ElementType X )
{
    BinTree T, result = NULL;
    int i, j; 

    for( i=0, j=1; j<=H->CurrentSize; i++, j*=2) {  /* for each tree in H */
        T= H->TheTrees[i];
        if ( X (3分) ){  /* if need to search inside this tree */
            result = Recur_Find(T, X);
            if ( result != NULL ) return result;
        } 
    }
    return result;
}

BinTree Recur_Find( BinTree T, ElementType X )
{
    BinTree result = NULL;
    if ( X==T->Element ) return T;
    if ( T->LeftChild!=NULL ){
        result = Recur_Find(T->LeftChild, X);
        if ( result!=NULL ) return result;
    } 
    if ( (3分) )
        result = Recur_Find(T->NextSibling, X);
    return result;
}
评测结果编译错误(0 分)
函数题得分:1总分:5
R6-1
Programming Contest
(5分)

Bob will participate in a programming contest. There are altogether n problems in the contest. Unlike in PAT (Programming Ability Test), in a programming contest one can not obtain partial scores. For problem i, Bob will need time[i] to solve it and obtains the corresponding score[i], or he may choose not to solve it at all. Bob will be happy when he obtains a total score no less than happy_score. You are supposed to find the minimum time needed for Bob to be happy. The function need_time must return the minimum time, or -1 if it is impossible for Bob to obtain a score no less than happy_score.

Format of function:

int need_time(const int time[], const int score[], int happy_score, int n);

Here n (1{1\le }n\le MAXN) is the number of problems;
happy_score (1{1 \le} happy_score \le MAXS) is the minimum score for Bob to be happy;
time[] is the array to store time[i] (1{1 \le}time[i]100{\le 100}) which is the time to solve problem i;
score[] is the array to store score[i] (1{1 \le}score[i]100{\le 100}) which is the score Bob gets for solving problem i.

Sample program of judge:

#include <stdio.h>

#define MAXN 10
#define MAXS 1000

int need_time(const int time[], const int score[], int happy_score, int n);

int main() {
  int n, i, happy_score;
  int time[MAXN], score[MAXN];
  scanf("%d %d", &n, &happy_score);
  for (i = 0; i < n; ++i)
      scanf("%d", &time[i]);
  for (i = 0; i < n; ++i)
      scanf("%d", &score[i]);
  printf("%d\n", need_time(time, score, happy_score, n));
  return 0;
}

/* Your function will be put here */

Sample Input:

6 121

84 87 78 16 94 38
87 93 50 22 63 28

Sample Output:

125
评测结果部分正确(1 分)