浙江大学2015-16春夏《高级数据结构与算法分析》期末模拟练习
开始时间01/01/2025 1:20:00 PM
结束时间01/01/2025 3:20:00 PM
答题时长120分钟
考生庞星磊
试卷总分100
考生得分90
判断题得分 / 总分:28 / 30
R1-41

In the 4-queens problem, (x1x_1, x2x_2, x3x_3, x4x_4) correspond to the 4 queens' column indices. During backtracking, (1, 3, 4, ?) will be checked before (1, 4, 2, ?), and none of them has any solution in their branches.

| 考生作答
答案
T
答案正确
2 / 2
R1-14

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.

| 考生作答
答案
F
答案正确
2 / 2
R1-7

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

| 考生作答
答案
F
答案错误
0 / 2
R1-15

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.

| 考生作答
答案
T
答案正确
2 / 2
R1-10

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

| 考生作答
答案
F
答案正确
1 / 1
R1-40

For a binomial queue, delete-min takes a constant time on average.

| 考生作答
答案
F
答案正确
2 / 2
R1-8

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

| 考生作答
答案
F
答案正确
2 / 2
R1-1

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

| 考生作答
答案
T
答案正确
2 / 2
R1-3

In the 4-queens problem, (x1x_1, x2x_2, x3x_3, x4x_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.

| 考生作答
答案
F
答案正确
2 / 2
R1-5

The decision problem HALTING returns TRUE, if, for a given input II and a given (deterministic) algorithm AA, AA terminates, otherwise it loops forever. The HALTING problem is NP-complete.

| 考生作答
答案
F
答案正确
1 / 1
R1-2

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

| 考生作答
答案
F
答案正确
1 / 1
R1-12

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

| 考生作答
答案
T
答案正确
2 / 2
R1-43

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

| 考生作答
答案
T
答案正确
2 / 2
R1-39

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

| 考生作答
答案
F
答案正确
2 / 2
R1-13

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

| 考生作答
答案
T
答案正确
3 / 3
R1-42

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

| 考生作答
答案
T
答案正确
2 / 2
单选题得分 / 总分:52 / 60
R2-16

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

| 考生作答
答案
C
答案正确
4 / 4
R2-46

When solving a problem with input size NN 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/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?

| 考生作答
答案
A
答案正确
4 / 4
R2-7

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?

| 考生作答
答案
D
答案正确
3 / 3
R2-48

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

| 考生作答
答案
C
答案正确
3 / 3
R2-67

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

| 考生作答
答案
A
答案正确
3 / 3
R2-66

Which one of the following statements is FALSE about skew heaps?

| 考生作答
答案
D
答案正确
3 / 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 {6, 20, 26, 46, 31, 25, 16, 61, 17, 28, 2}. Which of the following runs will be generated?

| 考生作答
答案
B
答案正确
4 / 4
R2-9

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

| 考生作答
答案
A
答案正确
3 / 3
R2-15

To solve the optimal binary search tree problem, we have the recursive equation cij=minilj{wij+ci,l1+cl+1,j}c_{ij} = \min_{i \le l \le j} \{w_{ij} + c_{i,l-1}+c_{l+1,j}\}. To solve this equation in an iterative way, we must fill up a table as follows:

| 考生作答
答案
D
答案正确
3 / 3
R2-68

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

| 考生作答
答案
D
答案正确
3 / 3
R2-8

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

| 考生作答
答案
A
答案正确
3 / 3
R2-50

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

| 考生作答
答案
A
答案正确
2 / 2
R2-13

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?

| 考生作答
答案
A
答案正确
4 / 4
R2-14

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

| 考生作答
答案
C
答案正确
4 / 4
R2-69

Given a 3-SAT formula with kk 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/21/2, independently for each variable. Which of the following statements is FALSE?

| 考生作答
答案
C
答案错误
0 / 4
R2-3

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?

| 考生作答
答案
A
答案正确
3 / 3
R2-53

Which of the following statement is true ?

| 考生作答
答案
B
答案错误
0 / 4
R2-64

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

| 考生作答
答案
D
答案正确
3 / 3
程序填空题得分 / 总分:6 / 6
R5-55

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: 
3分
; break; case 4: H1->TheTrees[i] = Carry; Carry = NULL; break; case 3: Carry = CombineTrees( T1, T2 ); H1->TheTrees[i] = H2->TheTrees[i] = NULL; break; case 5: Carry = CombineTrees( T1, Carry ); H1->TheTrees[i] = NULL; break; case 6: Carry = CombineTrees( T2, Carry ); H2->TheTrees[i] = NULL; break; case 7: H1->TheTrees[i] = Carry;
3分
; H2->TheTrees[i] = NULL; break; } /* end switch */ } /* end for-loop */ return H1; }
| 考生作答
填空#1
H1->TheTrees[i] = T2;H2->TheTrees[i] = NULL
填空#2
Carry = CombineTrees(T1,T2)
| 评测详情
填空详情
序号结果得分
1答案正确3
2答案正确3
答案正确
6 / 6
函数题得分 / 总分:4 / 4
R6-1

The function Power calculates the exponential function NkN^k. But since the exponential function grows rapidly, you are supposed to return (Nk)%10007(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:

8

Sample Input 2:

128 2

Sample Output 2:

6377
| 考生作答
代码
编译器: GCC
int Power(int N, int k) {
    long long result = 1;
    long long base = N;
    
    while(k > 0) {
        if(k & 1) {
            result = (result * base) % MOD;
        }
        base = (base * base) % MOD;
        k >>= 1;
    }
    
    return (int)result;
}
| 评测详情
编译器输出
a.c: In function ‘main’:
a.c:9:5: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
    9 |     scanf("%d%d", &N, &k);
      |     ^~~~~~~~~~~~~~~~~~~~~
测试点详情
测试点结果测试点得分耗时内存
0答案正确12.00 ms172 KB
1答案正确11.00 ms352 KB
2答案正确11.00 ms304 KB
3答案正确12.00 ms308 KB
答案正确
4 / 4