分数 2

作者陈越

单位浙江大学

For the recurrence equation $T (N) = a T (N / b) + f (N)$ , if $a f (N / b) = f (N)$ , then $T(N)=\Theta (f(N) log_b N)$ .

T

F

答案正确：2 分

1-2

分数 2

作者陈越

单位浙江大学

Making $N$ insertions into an initally empty binomial queue takes $O (N)$ time in the worst case.

T

F

答案正确：2 分

1-3

分数 2

作者陈越

单位浙江大学

The time bound of the FIND operation in a B+ tree containing $N$ numbers is $O(\log N)$ , no matter what the degree of the tree is.

T

F

答案正确：2 分

1-4

分数 2

作者杨洋

单位浙江大学

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

T

F

答案正确：2 分

1-5

分数 2

作者陈昊

单位浙江大学

When retrieving a word, the hash algorithm is faster than the search tree.

T

F

答案正确：2 分

1-6

分数 2

作者陈越

单位浙江大学

A perfectly balanced tree forms if keys 1 to $2^{k} - 1$ are inserted in order into an initally empty skew heap.

T

F

答案正确：2 分

2-1

分数 3

作者陈越

单位浙江大学

Delete the minimum number from the given binomial queue in the following figure. Which one of the following statements is FALSE?

A.

there are three binomial trees after deletion, which are $B_{0}$ , $B_{1}$ and $B_{4}$

B.

11 is the root of a binomial tree

C.

23 is not the root of any resulting binomial tree

D.

29 and 23 are both children of 4

答案正确：3 分

2-2

分数 3

作者杨欣豫

单位浙江大学

Given a recurrence equation $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:

A.

for k in 0 to n: for i in 0 to n: for j in n to 0

B.

for i in 0 to n: for j in 0 to n: for k in 0 to n

C.

for i in 0 to n: for j in n to 0: for k in n to 0

D.

for i in 0 to n: for j in n to 0: for k in 0 to n

答案正确：3 分

2-3

分数 3

作者何钦铭

单位浙江大学

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

A.

in the root alone

B.

in the root with key 20

C.

alone in a node on the second level (the leaves are on the first level)

D.

in a node with key 11 on the second level (the leaves are on the first level)

答案正确：3 分

2-4

分数 3

作者陈越

单位浙江大学

Starting from the red-black tree given in the figure, after successively inserting the keys {75, 70, 50}, which one of the following statements is FALSE?

A.

50 is the deepest red node

B.

70 and 99 are siblings, and they are both black

C.

70 is the parent of 75

D.

there are two red nodes

答案正确：3 分

2-5

分数 3

作者陈昊

单位浙江大学

F-Measure is a comprehensive evaluation of Precision and Recall. The calculation formula is $F_\beta=\frac{(1+\beta^2)\cdot P\cdot R}{\beta^2\cdot P+R}$ (where $P$ and $R$ are Precision and Recall, respectively) . A larger $\beta$ means that recall is more important. Please calculate $F_{2}$ according to the retrieval results in the following table.

	Relevant	Irrelevant
Retrieved	200	200
Not Retrieved	300	300

A.

0.5

B.

0.4

C.

0.4167

D.

0.4761

答案正确：3 分

2-6

分数 3

作者陈越

单位浙江大学

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

A.

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

B.

Skew heaps have $O (l o g N)$ amortized cost per operation

C.

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

D.

Skew heaps have $O (l o g N)$ worst-case cost for merging

答案正确：3 分

5-1

0/1 knapsack

分数 4

作者陈昊

单位浙江大学

There are $n$ ( $1 \leq n \le 5$ ) objects and a knapsack.

The weight and value of the i-th object ( $1\le i \le n$ ) is $w_{i}$ and $v_{i}$ (both $w_{i}$ and $v_{i}$ are integers), respectively, and the capacity of the knapsack is $W$ .

We can select some objects to put in the knapsack, and each object can only be selected once.

Now, you are supposed to calculate the maximum sum of the value of the objects in the knapsack when the sum of weight of selected objects is less than or equal to $W$ . It guarantees that the solution is unique.

We use the backtracking method to solve the problem. Please fill up the blanks in the following functions.

/*
tw: the sum of the weight of the selected objects
tv: the sum of the value of the selected objects
rw: the sum of the value of the remaining objects
x[]: 1/0，whether the object is selected or not corresponding to the current maximum value
op[]: 1/0，whether the object is selected or not corresponding to the current strategy
*/
void dfs(int i,int tw,int tv,int rw,int op[]) 
{
    int j;
    if (i>n)                    
    {    
        if(2 分)     
        {    
            maxv=tv;
            for(j=1;j<=n;j++)    
                x[j]=op[j];
        }
    }
    else                        
    {    
        if(tw+w[i]<=W)        
        {
            op[i]=1;            
            dfs(i+1,tw+w[i],tv+v[i],rw-w[i],op);
        }
        op[i]=0;                
        if (tw+rw>W)           
            dfs(2 分);
    }
}

答案正确：4 分

5-2

Longest Valid Substring

分数 6

作者杨洋

单位浙江大学

The definition of valid parenthesis:

an empty string is a valid parenthesis.
if u is a valid parenthesis, then (u) is a valid parenthesis.
if u and v are both valid parenthesis, then uv is a valid parenthesis.

For example, (()) and (()()) are valid parenthesis while ((() and ))(( are not.

Let t be a substring of s. t is a valid substring of s if t is a valid parenthesis.

Now, given a non-empty string s consists of ( and ), you are supposed to calculate the length of the longest valid substring of s.

We use dynamic programming to solve the problem. Specifically, f[i] denotes the length of the longest valid subtring ended with s[i]. Please fill up the blanks in the following function:

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

int longestValidSubstring(char *s) {
  int n = (int)strlen(s);
  int ans = 0;
  int f[n];
  memset(f, 0, sizeof(f));
  for(int i=1; i<n; i++) {
    if(s[i] == ')') {
      if(s[i-1] == '(') {
        f[i] = 2;
        if(i>=2) f[i] += 2 分;
      } else {
        if(i-f[i-1] > 0 && s[i-f[i-1]-1] == '(') {
          f[i] = f[i-1]+2;
          if(i-f[i-1]-1 > 0) f[i] += 2 分;
        }
      }
    }
    if(f[i] > ans) ans = 2 分;
  }
  return ans;
}

答案正确：6 分