The -th Fibonacci number can be computed by divide and conquer method of computing , where is the matrix
.
Then the -th Fibonacci number can be computed in time.
In a random skip list for a set of size , the operations Search, Insert, and Delete can be performed in expected time .
If an operation takes expected time, then it takes amortized time.
The number of light nodes along the right path of a skew heap is .
Managing shared memory for parallel programs is simpler than normal sequential programs.
What makes the time complexity analysis of a backtracking algorithm very difficult is that the sizes of solution spaces may vary.
A binary tree that is not full cannot correspond to an optimal prefix code.
NP-hard problems and NP-complete problems are the subsets of NP problems.
A word which has high term frequency in the whole document set must be a stop word.
When insert three keys into a non-empty 2-3 tree, and if the tree gains height when the first key is in, then it is possible that the 2-3 tree will gain more height after the insertions of the next two keys.
Suppose that the replacement selection is applied to generate longer runs for N numbers with a priority queue of size M, the possible maximum length of the longest run is N.
For an optimization problem, given a neighborhood, if its local optimum is also a global optimum, one can reach an optimal solution with just one step of local improvements.
Revisit the activity selection problem. Given a set of activities that wish to use a resource, each takes place during a time interval. The goal is to arrange as many compatible activities as possible. Recall that several greedy approaches are introduced in the class, among which the one selecting an activity with the shortest length, denoted by , is not always optimal. However, we claim that accepts at least activities, given that the optimal value is , where is an optimal solution. Check if the following is a correct proof.
We use a technique, called the charging scheme, similarly as the amortized analysis. Suppose each accepted activity of holds one dollar, which will be given to the activities accepted by in the following way. For any activity of , if is also accepted by , give the dolloar to itself. Otherwise, there must be some activity , accepted by , is not compatible with . Then receives one dollar from . Along this line, each activity of sends out one dollar to an activity in , while each activity of receives at most two dollars. It implies that accepts as least activities.
We have balls and boxes. Each ball is assigned to one of the boxes independently and uniformly at random (i.e., equally likely to each box). Suppose that is sufficiently large, and is the natural number, which of the following is FALSE?
Which of the asymptotic upper bound for the following recursive is correct?
Consider two disjoint sorted arrays and , we would like to compute the -th smallest element in the union of the two arrays, where . Please choose the smallest possible running time among the following options.
In this problem, we would like to find the amortized cost of insertion in a dynamic table . Initially the size of the table is 1. The cost of insertion is if the table is not full. When an item is inserted into a full table, the table is expanded as a new table of size 3 times larger. Then, we copy all the elements of the old table into this new table, and insert the item in the new table.
Let be the number of elements in the table , and be the total number of slots of the table. Clearly, if the table is full, the cost of one insertion is .
Let denote the table after applying the th operation on .
Which of the following potential function can help us achieve amortized cost per insertion?
Merge the two leftist heaps in the following figure. Which one of the following statements is FALSE?
In typical applications of data structures, it is not a single operation that is performed, but rather a sequence of operations, and the relevant complexity measure is not the time taken by one operation but the total time of a sequence. Hence instead of imposing any explicit structural constraint, we allow the data structure to be in an arbitrary state, and we design the access and update algorithms to adjust the structure in a simple, uniform way, so that the efficiency of future operations is improved. We call such a data structure self-adjusting. For example skew heaps and splay trees are such kind of structures.
Which one of the following statements is FALSE about self-adjusting data structures?
The Merging problem is to merge two non-decreasing arrays A(1), A(2), ..., A() and B(1), B(2), ..., B() into another non-decreasing array C(1), C(2), ..., C(). To solve it in parallel, we turn it into a Ranking problem. That is, to compute RANK(A(),B) and RANK(B(),A) for every , where RANK(e,S) is the position of e in S. The following psuedo-code is for solving the Ranking problem parallely.
for Pi, 1<=i<=n pardo
RANK(A(i),B) := BS(A(i),B)
RANK(B(i),A) := BS(B(i),A)
where BS(e,S)
is to find the position of e
in S
by binary search.
Which of the following gives the time and work load of the algorithm?
Consider the problem of making change for cents using the fewest number of coins. Assume that each coin's value is an integer.
The coins of the lowest denomination(面额) is the cent.
(I) Suppose that the available coins are quarters (25 cents), dimes (10 cents), nickels (5 cents), and pennies (1 cent). The greedy algorithm always yields an optimal solution.
(II) Suppose that the available coins are in the denominations that are powers of c, that is, the denominations are , , ..., for some integers and . The greedy algorithm always yields an optimal solution.
(III) Given any set of different coin denominations which includes a penny (1 cent) so that there is a solution for every value of , greedy algorithm always yields an optimal solution.
Which of the following is correct?
Given the following game tree, the red node will be pruned with α-β pruning algorithm if and only if ___.
About Vertex Cover problem, which of the following statements is FALSE?
Which of the following statements is FALSE?
Given a set of 10000 emails in the mailbox, our task is to retrieve the spam emails from this set. The statistic data for a spam filter's performance are shown in the following table. The recall of this filter is: ___.
Category | Actual True Spam | Actual False Spam |
---|---|---|
Retrieved True Spam | 2000 | 1000 |
Retrieved False Spam | 2000 | 5000 |
In a binomial queue, the total number of the nodes at even depth is always ___ than that of the nodes at odd depth (the root is defined to be at the depth 0).
Given a 2-3 tree as shown in the following figure. Which of the following pairs of insertions will result in a 2-3 tree with different structures?
Two red-black trees are said to be different if they have different tree structures or different node colors. How many different red-black trees are there with 3 internal nodes?
To sort numbers by external sorting using a -way merge and a -size heap, which statement is TRUE about the total comparison times and ?
Among the following statements about AVL trees and splay trees, how many of them are correct?
(1) AVL tree is a kind of height balanced tree. In a legal AVL tree, each node's balance factor can only be or .
(2) Define a single-node tree's height to be . For an AVL tree of height , there are at most nodes.
(3) Since AVL tree is strictly balanced, if the balance factor of any node changes, this node must be rotated.
(4) In a splay tree, if we only have to find a node without any more operation, it is acceptable that we don't push it to root and hence reduce the operation cost. Otherwise, we must push this node to the root position.
(5) In a splay tree, for any non-root node , its parent and grandparent (guranteed to exist), the correct operation to splay to is to rotate upward twice.
(6) Splaying roughly halves the depth of most nodes on the access path.
Consider the Minimum Degree Spanning Tree problem: Given a connected undirected graph , find a spanning tree whose maximum degree over its vertices is minimized over all spanning trees of . The problem can be shown to be NP-hard by reduction from the Hamiltonian Path Problem. On the other hand, we can use local search to design approximating algorithms. Denote as the degree of vertex on a tree . Consider the following algorithm:
It can be shown that this algorithm will terminate at a solution with maximum vertex degree . To show the algorithm will terminate in finite steps, a useful technique is to define a nonnegative potential function and to show is strictly decreasing after each step. Which of the following potential functions below satisfies the above requirements?
Consider the bin packing problem which uses a minimum number of bins to accommodate a given list of items. Recall that Next Fit (NF) and First Fit (FF) are two simple approaches, whose (asymptotic) approximation ratios are 2 and 1.7, respectively. Now we focus on a special class of instances in which only two distinct item sizes appear. Check which of the following statements is true by applying NF and FF on .
If there are 14 nodes in an AVL tree, then the maximum depth of the tree is ____. The depth of an empty tree is defined to be 0.
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( (3分) ) {
case 0:
case 4: break;
case 3:
case 7:
(3分);
H2->TheTrees[i] = NULL; break;
case 1:
H1->TheTrees[i] = Carry; Carry = NULL; break;
case 2:
H1->TheTrees[i] = T2; H2->TheTrees[i] = NULL; break;
case 5:
Carry = CombineTrees( T1, Carry );
H1->TheTrees[i] = NULL; break;
case 6:
Carry = CombineTrees( T1, T2 );
H1->TheTrees[i] = H2->TheTrees[i] = NULL; break;
} /* end switch */
} /* end for-loop */
return H1;
}
序号 | 结果 | 得分 |
---|---|---|
0 | 段错误 | 0 |
1 | 编译错误 | 0 |
Suppose you are a baker planning to bake some hand-made cream breads.
To bake a cream bread, we need to use one slice of bread and one kind of cream. Each hand-made cream bread has a taste score to describe how delicious it is, which is obtained by multiplying the taste score for bread and the taste score for cream. (The taste scores could be negative, howerver, two negative tast scores can still produce delicious cream bread.)
The bread and cream are stored separately.
The constraint is that you need to examine the breads in a given order, and for each piece of bread, you have to decide immediately (without looking at the remaining breads) whether you would like to take it.
After you are finished with breads, you will take the same amount of cream in the same manner. The breads and creams you take will be paired in the same order as you take them.
Given taste scores for bread and taste scores for cream, you are supposed to calculate the maximum total taste scores for all hand-made cream bread.
Each input file contains one test case. For each case, the first line contains two integers and (), which are the numbers of bread and cream, respectively.
The second line gives taste scores for bread.
The third line gives taste scores for cream.
The taste scores are integers in .
All the numbers in a line are separated by a space.
Print in a line the maximum total taste score.
3 4
-1 10 8
10 8 11 9
188
The maximum total taste score for the sample case is .