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

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

If a leftist heap can be implemented recursively, so can its counterpart skew heap.~@

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

An (1+ϵ)(1+ \epsilon)-approximation scheme of time complexity (n+1/ϵ)3(n+1/\epsilon)^3 is a PTAS but not an FPTAS.~@

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

The following binary search tree is a valid red-black tree.

br-tree.png
~@

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

For the document-partitioned strategy in distributed indexing, each node contains a subset of all documents that have a specific range of index.
~@

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

Average-case bounds are stronger than the equivalent amortized bounds, because there is a guarantee for any single operation.~@

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

In a Turnpike Reconstruction Problem, given distance set D = { 2, 2, 4, 6, 6, 8 }, x1~x4 = ( 0, 2, 6, 8 ) is the only solution provided that x1 = 0.~@

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

In the vertex cover problem, if the given graph is a tree, then we can find the optimal solution in polynomial time.~@

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

In local search, if the optimization function has a constant value in a neighborhood, there will be a problem.~@

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

In general, for a 3-way merge we need 6 input buffers and 2 output buffers for decreasing the number of passes.~@

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

Let a=(a1,a2,,ai,,aj,,an)a = (a_1, a_2, \ldots, a_i, \ldots, a_j, \ldots, a_n) denote the list of elements we want to sort. In the quicksort algorithm, if the pivot is selected uniformly at random. Then any two elements get compared at most once and the probability of aia_i and aja_j being compared is 2/(ji+1)2/(j-i+1) for j>ij > i, given that aia_i or aja_j is selected as the pivot. ~@

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

In order to solve the maximum finding problem by a parallel algorithm with T(n)=O(1)T(n) = O(1) , we need work load W(n)=Ω(n2)W(n) = \Omega ( n^2 ) in return.~@

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

If P = NP then the Shortest-Path (finding the shortest path between a pair of given vertices in a given graph) problem is NP-complete.~@

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

For the recurrence equation T(N)=8T(N/2)+N3logNT(N)=8T(N/2)+N^3logN,we obtain T(N)=O(N3logN)T(N)=O(N^3logN) according to the Master Theorem.

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

Merge the two skew heaps in the following figure. How many of the following statements is/are FALSE?

  • the null path length of 8 is the same as that of 6
  • 35 is the left child of 18
  • the depths of 18 and 33 are the same

heap.png

(3分)
评测结果答案正确(3 分)
R2-2
If X is a problem in class NP, then how many of the following statements is/are TRUE?
  • There is no polynomial time algorithm for X.
  • There is a polynomial time algorithm for X.
  • If X can be solved deterministically in polynomial time, then P = NP.
(3分)
评测结果答案错误(0 分)
R2-3

To solve a problem with input size NN by divide and conquer, algorithm A divides the problem into 7 subproblems with size N/2N/2 and the time recurrences is

T(N)=7T(N/2)+Θ(N2)T(N) = 7T(N/2)+\Theta(N^2).

Now we attempt to design another algorithm B dividing the problem into aa subproblems with size N/4N/4 and the time recurrences is

T(N)=aT(N/4)+Θ(N2)T(N) = aT(N/4)+\Theta(N^2).

In order to beat algorithm A, what is the largest integer value of aa for which algorithm B would be asymptotically faster than algorithm A?

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

Sorting-by-merging is a classic serial algorithm. It can be translated directly into a reasonably efficient parallel algorithm. A recursive description follows.

MERGE−SORT( A(1), A(2), ..., A(n); B(1), B(2), ..., B(n) )

Assume that n=2ln = 2^l for some integer l0l \ge 0

if n = 1 then return B(1) := A(1)

else call, in parallel, MERGE−SORT( A(1), ..., A(n/2); C(1), ..., C(n/2) ) and

  • MERGE−SORT(A(n/2+1), ..., A(n); C(n/2+1), ..., C(n) )

  • Merge (C(1),...C(n/2)) and (C(n/2 + 1),...,C(n)) into (B(1), B(2), ..., B(n)) with time O(n)

Then the MERGE−SORT runs in __ .

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

For the result of accessing the keys 1 and 2 in order in the splay tree in the following figure, let's define size(v)=number of nodes in subtree of v\textbf{size}(v) = \text{number of nodes in subtree of } v ( vv included ) and potential ϕ=vlog2size(v)\phi = \sum_v \lfloor \log_2 \textbf{size}(v)\rfloor, where x\lfloor x\rfloor means the greatest interger no larger than xx.

How many of the following statements is/are TRUE?

  • the potential change from the initial tree to the resulted tree is -3
  • 1 is the sibling of 4
  • 5 is the child of 6

图.png

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

After inserting { 3, 4, 5, 6, 1, 2, 7 } into an initially empty red-black tree, which of following is False?

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

Assume that there are 10000 documents in the database, and the statistical data for one query are shown in the following table. One metric for evaluating the relevancy of the query is F-α score, which is defined as ((1+ α)∙(precision*recall))/(α∙precision+recall). Then the F-0.5 (α=0.5) score for this query is:

Relevant Irrelevant
Retrieved 4800 1200
**Not Retrieved ** 3200 800
(3分)
评测结果答案错误(0 分)
R2-8

A replacement selection is applied to generate the max run with a priority queue of 5 records. When the sequence of numbers is { 6, 79, 14, 10, 90, 28, 35, X, …. } and the length of the first run is 7, what is the sufficient condition of X?

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

If P and NP are different, which of the following statements is true?

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

Given the following game tree, if node d is pruned with α-β pruning algorithm, which of the following statements about the value of node a or node b is correct?

a-b剪枝(2)-1.jpg

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

The potential function QQ of a binomial queue is the number of the trees. After merging two binomial queues H1H1 with 22 nodes and H2H2 with 13 nodes,what is the potential change Q(H1+H2)(Q(H1)+Q(H2))Q (H1+H2)-(Q (H1)+Q (H2)) ?

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

** Load balancing problem: **
We have nn jobs j=1,2,,nj=1, 2, \ldots, n each with processing time pjp_j being an integer number.
Our task is to find a schedule assigning nn jobs to 100100 identical machines so as to minimize the makespan (the maximum completion time over all the machines).

We adopt the following local search to solve the above load balancing problem.

**LocalSearch: **

Start with an arbitrary schedule.

Repeat the following until no job can be re-assigned:

  • Let ll be a job that finishes last.
  • If there exists a machine ii such that assigning job ll to ii allows ll finish earlier, then re-assign ll to be the last job on machine ii.
  • If such a machine is not unique, always select the one with the minimum completion time.

We claim the following four statements:

  1. The algorithm LocalSearch finishes within polynomial time.
  2. The Load-balancing problem is NP-hard.
  3. Let OPT be the makespan of an optimal algorithm. Then the algorithm LocalSearch finds a schedule with the makespan at most of 1.95 OPT.
  4. This algorithm finishes within O(n2)O(n^2).

How many statments are correct ?

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

In the maximum satisfiability problem (MAX SAT), the input consists of nn Boolean variables x1,,xnx_1,\ldots,x_n, mm clauses C1,,CmC_1,\ldots,C_m(each of which consists of a disjunction(that is an “or”) of some number of the variables and their negations, e.g. x3xˉ5x11x_3 \vee \bar{x}_5 \vee x_{11}, where xˉi\bar{x}_i is the negation of xix_i), and a nonnegative weight wjw_j for each clause CjC_j. The objective of the problem is to find an assignment of the true/false to the xix_i that maximizes the weight of the satisfied clauses.

A variable or a negated variable is a literal. The number of literals in a clause is called its length. Denote ljl_j to be the length of a clause CjC_j . Clauses of length 1 are called unit clauses.

Randomized algorithm RA: Setting each xix_i to true with probability pp independently.

Which of the following statement is false?

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

To solve a problem with input size NN by divide and conquer, an algorithm divides the problem into 3 subproblems with size N\sqrt N (assuming it is an integer ) and the time recurrences is

T(N)=3T(N)+log(N)T(N) = 3T(\sqrt N)+log(N).

What is the overall time complexity of this algorithm?

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

In Activity Selection Problem, we are given a set of activities S={a1,a2,,an}S=\{a_1, a_2, \ldots, a_n \} that wish to use a resource (e.g. a room). Each aia_i takes place during a time interval [si,fi)[s_i, f_i).

Let us consider the following problem: given the set of activities SS, we must schedule them all using the minimum
number of rooms.

Greedy1:
Use the optimal algorithm for the Activity Selection Problem to find the max number of activities that can be scheduled in one room. Delete and repeat on the rest, until no activities left.

Greedy2:

  • Sort activities by start time. Open room 1 for a1a_1.
  • for i=2i = 2 to nn
    if aia_i can fit in any open room, schedule it in that room;
    otherwise open a new room for aia_i.

Which of the following statement is correct?

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

After deleting number 14 from a binomial queue of 5 numbers { 12, 13, 14, 23, 24 }, which of the followings is impossible?

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

To build a leftist heap, we can start from placing all the keys as single-node heaps on a queue, and perform the following until only one heap is on the queue: dequeue two heaps, merge them, and enqueue the result.

Then the best description of the time complexity of this procedure is:

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

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

  • the total number of rotations made is 4 (Note: double rotation counts 2 and single rotation counts 1)
  • the expectation (round to 0.01) of access time is 2.75
  • there are 1 nodes with a balance factor of -1
(3分)
评测结果答案错误(0 分)
R2-19

Assume P≠NP, please identify the false statement.

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

Start from NN single-node splay trees, let's merge them into one splay tree in the following way: each time we select two splay trees, delete nodes one by one from the smaller tree and insert them into the larger tree. Then which of the following statements is NOT true?

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

The function FindKey is to check if a given key is in a B+ Tree with its root pointed by root.

Return true if key is in the tree, or false if not. The B+ tree structure is defined as following:

static int order = DEFAULT_ORDER;
typedef struct BpTreeNode BpTreeNode;
struct BpTreeNode {
    BpTreeNode** childrens;  /* Pointers to childrens. This field is not used by leaf nodes. */
    ElementType* keys;
    BpTreeNode* parent;
    bool isLeaf;  /* 1 if this node is a leaf, or 0 if not */
    int numKeys;  /* This field is used to keep track of the number of valid keys. 
    In an internal node, the number of valid pointers is always numKeys + 1. */
};


bool FindKey(BpTreeNode * const root, ElementType key){
    if (root == NULL) {
            return false;
    }
    int i = 0;
    BpTreeNode * node = root;
    while ((3分)) {
        i = 0;
        while (i < node->numKeys) {
            if ((3分)) i++;
            else break;
        }
        node = node->childrens[i];
    }
    for(i = 0; i < node->numKeys; i++){
        if(node->keys[i] == key)
            return true;
    }
    return false;
}
序号结果测试点得分
0编译错误0
1编译错误0
评测结果编译错误(0 分)
函数题得分:暂无总分:8
R6-1
Decode
(8分)

Suppose that a string of English letters is encoded into a string of numbers. To be more specific, A-Z are encoded into 0-25. Since it is not a prefix code, the decoded result may not be unique. For example, 1213407 can be decoded as BCBDEAH, MBDEAH, BCNEAH, BVDEAH or MNEAH. Note that 07 is not 7, hence cannot be decoded as H.

Your job is to tell in how many different ways we can decode a numeric string.

Format of function:

int Decode( char NumStr[] );

where NumStr is a string consisting of only the numbers 0-9.

The function Decode is supposed to return the number of different ways we can decode NumStr.

Since the answer might be super large, you only need to output the answer modulo 1000000007.

Sample program of judge:

#include <stdio.h>
#include <string.h>

#define MAXN 100
#define BASE 1000000007

int Decode( char NumStr[] );

int main()
{
    char NumStr[MAXN];

    scanf("%s", NumStr);
    printf("%d", Decode(NumStr));

    return 0;
}

/* Your function will be put here */

Sample Input:

1213407

Sample Output:

5