浙江大学2015-16春夏《高级数据结构与算法分析》期末模拟练习

开始时间2016/01/01 08:00:00

结束时间2038/01/18 08:00:00

答题时长120分钟

考生

得分22

总分100

判断题得分：11总分：30

R1-1

An AVL tree with the balance factors of all the non-leaf nodes being 0 must be a perfect binary tree. ~@

(2分)

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

R1-2

In the 4-queens problem, ( $x_1$ , $x_2$ , $x_3$ , $x_4$ ) correspond to the 4 queens' column indices. During backtracking, (1, 4, 2, ?) will be checked before (1, 3, 4, ?), and none of them has any solution in their branches. ~@

(2分)

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

R1-3

The worst-case running time is equal to the expected running time within constant factors for any randomized algorithm. ~@

(1分)

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

R1-4

With the same operations, the resulting leftist heap is always more balanced than the skew heap. ~@

(2分)

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

R1-5

In the 4-queens problem, ( $x_1$ , $x_2$ , $x_3$ , $x_4$ ) correspond to the 4 queens' column indices. During backtracking, (1, 4, 2, ?) will be checked before (2, 4, 1, ?), and none of them has any solution in their branches. ~@

(2分)

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

R1-6

If we translate a serial algorithm into a reasonably efficient parallel algorithm, the work load and the worst-case running time are usually reduced. ~@

(1分)

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

R1-7

Let S be the set of activities in Activity Selection Problem. Then there must be some maximum-size subset of mutually compatible activities of S that includes the earliest finish activity $a_m$ . ~@

(2分)

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

R1-8

Recall that the worst-case time complexities of insertions and deletions in a heap of size $N$ are both $O(\log N)$ . Then, without changing the data structure, the amortized time complexity of insertions in a heap is also $O(\log N)$ , and that of deletions is $O(1)$ . ~@

(3分)

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

R1-9

To merge 55 runs using 3 tapes for a 2-way merge, the original distribution (30, 25) is better than (34, 21). ~@

(2分)

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

R1-10

In a red-black tree, if an internal black node is of degree 1, then it must have only 1 descendant node. ~@

(2分)

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

R1-11

Since finding a locally optimal solution is presumably easier than finding an optimal solution, we can claim that for any local search algorithm, one step of searching in neighborhoods can always be done in polynomial time. ~@

(2分)

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

R1-12

Suppose ALG is an $\alpha$ -approximation algorithm for an optimization problem $\Pi$ whose approximation ratio is tight. Then for every $\epsilon > 0$ there is no ( $\alpha - \epsilon$ )-approximation algorithm for $\Pi$ unless P = NP. ~@

(2分)

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

R1-13

The decision problem HALTING returns TRUE, if, for a given input $I$ and a given (deterministic) algorithm $A$ , $A$ terminates, otherwise it loops forever. The HALTING problem is NP-complete. ~@

(1分)

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

R1-14

To solve a problem by dynamic programming instead of recursions, the key approach is to store the results of computations for the subproblems so that we only have to compute each different subproblem once. Those solutions can be stored in an array or a hash table. ~@

(2分)

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

R1-15

When measuring the relevancy of the answer set of a search engine, the precision is low means that most of the relevant documents are not retrieved. ~@

(2分)

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

R1-16

For a binomial queue, merging takes a constant time on average. ~@

(2分)

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

单选题得分：10总分：60

R2-1

Given four characters (a, b, c, d) with distinct frequencies in a text. Suppose that a and b are the two characters having the lowest frequencies. Which of the following sets of code is a possible Huffman code for this text?

(3分)

a: 000, b:001, c:10, d:1

a: 000, b:001, c:01, d:11

a: 010, b:001, c:01, d:1

a: 000, b:001, c:01, d:1

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

R2-2

Which one of the following statements about the Maximum Finding problem is true?

(3分)

Parallel random sampling algorithm can run in $O(1)$ time and $O(N)$ work with very high probability.

There exists a serial algorithm with time complexity being $O(logN)$ .

No parallel algorithm can solve the problem in $O(1)$ time.

When partitioning the problem into sub-problems and solving them in parallel, compared with $\sqrt N$ , choosing $log log N$ as the size of each sub-problem can reduce the work load and the worst-case time complexity.

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

R2-3

For the result of accessing the keys 5 and 8 in order in the splay tree in the following figure, which one of the following statements is FALSE?

(3分)

2 and 7 are siblings

11 is the parent of 7

8 is the root

5 is the parent of 7

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

R2-4

Suppose that the replacement selection technique is used in external sorting to construct the initial runs. A priority queue of size 5 is used by the internal memory. Given input sequence {5, 19, 25, 45, 30, 24, 15, 60, 16, 27, 1}. Which of the following runs will be generated?

(4分)

run1: 5, 19, 24, 25, 30, 45, 60; **run2:**1, 15, 16, 27

run1: 5, 19, 25, 30, 45; ** run2**:1, 15, 16, 24, 27, 60

run1: 5, 19, 24, 25, 30, 45; run2: 1, 15, 16, 27, 60

run1: 5, 19, 25, 30, 45; **run2: **15, 16, 24, 27, 60; ** run3: **1

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

R2-5

Which one of the following statements is FALSE about a skew heap?

(3分)

Skew heaps have $O(log N)$ amortized cost per operation

Skew heaps have $O(log N)$ worst-case cost for merging

Comparing to leftist heaps, skew heaps are always more efficient in space

Skew heaps do not need to maintain the null path length of any node

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

R2-6

Max-cut problem: Given an undirected graph $G = (V, E)$ with positive integer edge weights $w_e$ , find a node partition $(A, B)$ such that $w(A, B)$ , the total weight of edges crossing the cut, is maximized. Let us define $S'$ be the neighbor of $S$ such that $S'$ can be obtained from $S$ by moving one node from $A$ to $B$ , or one from $B$ to $A$ . We only choose a node which, when flipped, increases the cut value by at least $w(A,B)/|V|$ . Then which of the following is true?

(4分)

The algorithm terminates after at most $O(\log |V| \log W)$ flips, where $W$ is the total weight of edges.

The algorithm terminates after at most $O(|V|^2)$ flips.

Upon the termination of the algorithm, the algorithm returns a cut $(A, B)$ so that $2.5 w(A, B) \ge w(A^*, B^*)$ , where $(A^*, B^*)$ is an optimal partition.

Upon the termination of the algorithm, the algorithm returns a cut $(A, B)$ so that $2 w(A, B) \ge w(A^*, B^*)$ .

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

R2-7

Among the following groups of concepts, which group is not totally relevant to a search engine?

(2分)

word stemming, compression, recall

thresholding, dynamic programming, precision

distributed index, hashing, inverted file index

stop words, posting list, dynamic indexing

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

R2-8

A B+ tree of order 3 with 21 numbers has at most __ nodes of degree 2.

(3分)

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

R2-9

You are to maintain a collection of lists and to support the following operations.

(i) insert(item, list): insert item into list (cost = 1).

(ii) sum(list): sum the items in list, and replace the list with a list containing one item that is the sum (cost = length of list).

We show that the amortized cost of an insert operation is O(1) and the amortized cost of a sum operation is O(1).
If we assume the potential function to be the number of elements in the list, which of the following is FALSE?

(4分)

For sum, the change cost is 2-k. The amortized cost is 2.

For insert, the actual cost is 1.

For sum, the actual cost is k.

For insert, the change in potential is 1. The amortized cost is 2.

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

R2-10

After deleting 10 from the red-black tree given in the figure, which one of the following statements must be FALSE?

(3分)

8 is the parent of 15, and there are 2 red nodes in the tree

11 is the parent of 6, and 14 is red

8 is the parent of 15, and 7 is black

11 is the parent of 15, and there are 2 red nodes in the tree

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

R2-11

Given the distance set D={1,1,2,2,2,2,3,3,3,4,5,5,6,6,8} in a Turnpike Reconstruction problem, first it can be sure that x1=0 and x6=8. Which of the following possible solutions will be checked next?

(3分)

x2=2, x5=6

x2=1, x5=6

x2=1, x5=5

x3=3, x5=6

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

R2-12

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

(3分)

12 is the right child of 9

37 is the left child of 23

23 is the left child of 14

9 is NOT the root

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

R2-13

Given a 3-SAT formula with $k$ clauses, in which each clause has three variables, the MAX-3SAT problem is to find a truth assignment that satisfies as many clauses as possible. A simple randomized algorithm is to flip a coin, and to set each variable true with probability $1/2$ , independently for each variable. Which of the following statements is FALSE?

(4分)

The probability that a random assignment satisfies at least $7k/8$ clauses is at most $1/(8k)$ .

If we repeatedly generate random truth assignments until one of them satisfies $\ge 7k/8$ clauses, then this algorithm is a $8/7$ -approximation algorithm.

The expected number of clauses satisfied by this random assignment is $7k/8$ .

For every instance of 3-SAT, there is a truth assignment that satisfies at least a $7/8$ fraction of all clauses.

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

R2-14

Insert { 9, 8, 7, 2, 3, 5, 6, 4} into an initially empty AVL tree. Which one of the following statements is FALSE?

(3分)

5 is the root

there are 2 nodes with their balance factors being -1

the height of the resulting AVL tree is 3

2 and 5 are siblings

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

R2-15

Suppose Q is a problem in NP, but not necessarily NP-complete. Which of the following is FALSE?

(4分)

If Q is NP-hard, then Q is NP-complete.

If Q $\notin P$ , then $P \neq NP$ .

A polynomial-time algorithm for Q would sufficiently imply a polynomial-time algorithm for SAT.

A polynomial-time algorithm for SAT would sufficiently imply a polynomial-time algorithm for Q.

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

R2-16

Which of the following statement is true ?

(4分)

Let $A$ and $B$ be optimization problems where it is known that $A$ reduces to $B$ in polynomial time. Additionally, suppose that there exists a polynomial-time 2-approximation for $B$ . Then there must exist a polynomial time 2-approximation for $A$ .

There exists a polynomial-time 2-approximation algorithm for the general Traveling Salesman Problem.

A randomized algorithm for a decision problem with one-sided-error and correctness probability 1/3 (that is, if the answer is YES, it will always output YES, while if the answer is NO, it will output NO with probability 1/3) can always be amplified（放大） to a correctness probability of 99%.

Suppose that you have two deterministic online algorithms, $A_1$ and $A_2$ , with competitive ratios (the approximation ratio for an online algorithm is called competitive ratio) $c_1$ and $c_2$ respectively. Consider the randomized algorithm $A^*$ that flips a fair coin once at the beginning; if the coin comes up heads, it runs $A_1$ from then on; if the coin comes up tails, it runs $A_2$ from then on. Then the expected competitive ratio of $A^*$ is at least $\min\{c_1, c_2\}$ .

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

R2-17

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

(4分)

$O(N^2log^2N)$

$O(N^2)$

$O(N^3logN)$

$O(N^2logN)$

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

R2-18

In dynamic programming, we derive a recurrence relation for the solution to one subproblem in terms of solutions to other subproblems. To turn this relation into a bottom up dynamic programming algorithm, we need an order to fill in the solution cells in a table, such that all needed subproblems are solved before solving a subproblem. Among the following relations, which one is impossible to be computed?

(3分)

$A(i, j) = F(A(i, j -1), A(i - 1, j - 1), A(i - 1, j + 1))$

$A(i,j) = F(A(i-2, j-2), A(i+2,j+2))$

$A(i, j) = min (A(i-1,j), A(i,j-1), A(i-1,j-1))$

$A(i, j) = F(A(min\{i, j\} - 1, min\{i, j\} - 1), A(max\{i, j\} - 1, max\{i, j\} -1))$

评测结果答案错误(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( 4*!!Carry + 2*!!T2 + !!T1 ) { 
        case 0:
        case 1: break;    
        case 2: H1->TheTrees[i] = T2; H2->TheTrees[i] = NULL; break;
        case 4: H1->TheTrees[i] = Carry; Carry = NULL; break;
        case 3: Carry = CombineTrees( T1, T2 );
                (3分); break;
        case 5: Carry = CombineTrees( T1, Carry );
                H1->TheTrees[i] = NULL; break;
        case 6: (3分);
                H2->TheTrees[i] = NULL; break;
        case 7: H1->TheTrees[i] = Carry; 
                Carry = CombineTrees( T1, T2 ); 
                H2->TheTrees[i] = NULL; break;
        } /* end switch */
    } /* end for-loop */
    return H1;
}

序号	结果	测试点得分
0	编译错误	0
1	编译错误	0

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

函数题得分：1总分：4

R6-1

Quick Power

(4分)

The function Power calculates the exponential function $N^k$ . But since the exponential function grows rapidly, you are supposed to return $(N^k)\%10007$ instead.

Format of function:

int Power(int N, int k);

Both N and k are integers, which are no more than 2147483647.

Sample program of judge:

#include <stdio.h>

int Power(int, int);

const int MOD = 10007;
int main()
{
    int N, k;
    scanf("%d%d", &N, &k);
    printf("%d\n", Power(N, k));        
    return 0;
}

/* Your function will be put here */

Sample Input 1:

2 3

Sample Output 1:

Sample Input 2:

128 2

Sample Output 2:

编译器

GCC

代码

int Power(int N, int k)
{
    return 1;
}

编译器输出

a.c: In function ‘main’:
a.c:9:5: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &N, &k);
     ^~~~~~~~~~~~~~~~~~~~~

测试点	结果	测试点得分	耗时	内存
0	答案正确	1	3.00 ms	308 KB
1	答案错误	0	3.00 ms	324 KB
2	答案错误	0	2.00 ms	316 KB
3	答案错误	0	2.00 ms	504 KB

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