For the recurrence equation T ( N ) = a T ( N / b ) + f ( N ) T(N)=aT(N/b)+f(N) T(N)=aT(N/b)+f(N), if a f ( N / b ) = f ( N ) af(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) T(N)=Θ(f(N)logbN).
Making N N N insertions into an initally empty binomial queue takes O ( N ) O(N) O(N) time in the worst case.
The time bound of the FIND operation in a B+ tree containing N N N numbers is O ( log N ) O(\log N) O(logN), no matter what the degree of the tree is.
The following binary search tree is a valid red-black tree.
When retrieving a word, the hash algorithm is faster than the search tree.
A perfectly balanced tree forms if keys 1 to 2 k − 1 2^k -1 2k−1 are inserted in order into an initally empty skew heap.
Delete the minimum number from the given binomial queue in the following figure. Which one of the following statements is FALSE?
there are three binomial trees after deletion, which are B 0 B_0 B0, B 1 B_1 B1 and B 4 B_4 B4
11 is the root of a binomial tree
23 is not the root of any resulting binomial tree
29 and 23 are both children of 4
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}\} fi,j,k=fi,j+1,k+min0≤l≤k{fi−1,j,l+wj,l}. To solve this equation in an iterative way, we cannot fill up a table as follows:
for k in 0 to n: for i in 0 to n: for j in n to 0
for i in 0 to n: for j in 0 to n: for k in 0 to n
for i in 0 to n: for j in n to 0: for k in n to 0
for i in 0 to n: for j in n to 0: for k in 0 to n
Given a 2-3 tree as shown in the figure, after inserting 18 with splitting strategy, where will the key 15 be?
in the root alone
in the root with key 20
alone in a node on the second level (the leaves are on the first level)
in a node with key 11 on the second level (the leaves are on the first level)
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?
50 is the deepest red node
70 and 99 are siblings, and they are both black
70 is the parent of 75
there are two red nodes
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} Fβ=β2⋅P+R(1+β2)⋅P⋅R(where P P P and R R R are Precision and Recall, respectively) . A larger β \beta β means that recall is more important. Please calculate F 2 F_2 F2 according to the retrieval results in the following table.
0.5
0.4
0.4167
0.4761
Which one of the following statements is FALSE about skew heaps?
Comparing to leftist heaps, skew heaps are always more efficient in space
Skew heaps have O ( l o g N ) O(log N) O(logN) amortized cost per operation
Skew heaps do not need to maintain the null path length of any node
Skew heaps have O ( l o g N ) O(log N) O(logN) worst-case cost for merging
There are n n n ( 1 ≤ n ≤ 5 1 \leq n \le 5 1≤n≤5) objects and a knapsack.
The weight and value of the i-th object ( 1 ≤ i ≤ n 1\le i \le n 1≤i≤n) is w i w_i wi and v i v_i vi (both w i w_i wi and v i v_i vi are integers), respectively, and the capacity of the knapsack is W 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 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 分); } }
The definition of valid parenthesis:
an empty string is a valid parenthesis.
if u is a valid parenthesis, then (u) is a valid parenthesis.
u
(u)
if u and v are both valid parenthesis, then uv is a valid parenthesis.
v
uv
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.
t
s
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:
f[i]
s[i]
#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; }