1-1
分数 2
作者 陈越
单位 浙江大学

For the recurrence equation T ( N ) = a T ( N / b ) + f ( N ) T(N)=aT(N/b)+f(N) , if a f ( N / b ) = f ( N ) af(N/b)=f(N) , then T ( N ) = Θ ( f ( N ) l o g b N ) T(N)=\Theta (f(N) log_b N) .


1-2
分数 2
作者 陈越
单位 浙江大学

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


1-3
分数 2
作者 陈越
单位 浙江大学

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


1-4
分数 2
作者 杨洋
单位 浙江大学

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

br-tree.png


1-5
分数 2
作者 陈昊
单位 浙江大学

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


1-6
分数 2
作者 陈越
单位 浙江大学

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


2-1
分数 3
作者 陈越
单位 浙江大学

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


2-2
分数 3
作者 杨欣豫
单位 浙江大学

Given a recurrence equation f i , j , k = f i , j + 1 , k + min 0 l k { f i 1 , j , l + w j , 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:


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?


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?


2-5
分数 3
作者 陈昊
单位 浙江大学

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

Relevant Irrelevant
Retrieved 200 200
Not Retrieved 300 300

2-6
分数 3
作者 陈越
单位 浙江大学

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


5-1
0/1 knapsack
分数 4
作者 陈昊
单位 浙江大学

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

The weight and value of the i-th object ( 1 i n 1\le i \le n ) is w i w_i and v i v_i (both w i w_i and v i v_i are integers), respectively, and the capacity of the knapsack is W 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 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 分
); } }

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; }