Since finding a locally optimal solution is presumably easier than finding an optimal solution, we can claim that for any local search algorithm, one step of searching in neighborhoods can always be done in polynomial time. (2分)
When measuring the relevancy of the answer set of a search engine, the precision is low means that most of the retrieved documents are irrelevant. (2分)
The worst-case running time is equal to the expected running time within constant factors for any randomized algorithm. (1分)
The decision problem HALTING returns TRUE, if, for a given input and a given (deterministic) algorithm , terminates, otherwise it loops forever. The HALTING problem is NP-complete. (1分)
Let S be the set of activities in Activity Selection Problem. Then the earliest finish activity must be included in all the maximum-size subset of mutually compatible activities of S. (2分)
To merge 55 runs using 3 tapes for a 2-way merge, the original distribution (34, 21) is better than (30, 25). (2分)
In a red-black tree, if an internal black node is of degree 1, then it must have only 1 descendant node. (2分)
For a binomial queue, merging takes a constant time on average. (2分)
In the 4-queens problem, (, , , ) correspond to the 4 queens' column indices. During backtracking, (1, 3, 4, ?) will be checked before (1, 4, 2, ?), and none of them has any solution in their branches. (2分)
For an AVL tree, the balance factors of all the non-leaf nodes are 0 iff the tree is a complete binary tree. (2分)
Suppose ALG is an -approximation algorithm for an optimization problem whose approximation ratio is tight. Then for every there is no ()-approximation algorithm for unless P = NP. (2分)
In the 4-queens problem, (, , , ) correspond to the 4 queens' column indices. During backtracking, (1, 4, 2, ?) will be checked before (1, 3, 4, ?), and none of them has any solution in their branches. (2分)
If we translate a serial algorithm into a reasonably efficient parallel algorithm, the work load and the worst-case running time are usually reduced. (1分)
With the same operations, the resulting skew heap is always more balanced than the leftist heap. (2分)
To solve a problem by dynamic programming instead of recursions, the key approach is to store the results of computations for the subproblems so that we only have to compute each different subproblem once. Those solutions can be stored in an array or a hash table. (2分)
Recall that the worst-case time complexities of insertions and deletions in a heap of size are both . Then, without changing the data structure, the amortized time complexity of insertions in a heap is also , and that of deletions is . (3分)
Suppose that the replacement selection technique is used in external sorting to construct the initial runs. A priority queue of size 5 is used by the internal memory. Given input sequence {5, 19, 25, 45, 30, 24, 15, 60, 16, 27, 1}. Which of the following runs will be generated? (4分)
After deleting 10 from the red-black tree given in the figure, which one of the following statements must be FALSE? (3分)
Which one of the following statements about the Maximum Finding problem is true? (3分)
Max-cut problem: Given an undirected graph with positive integer edge weights , find a node partition such that , the total weight of edges crossing the cut, is maximized. Let us define be the neighbor of such that can be obtained from by moving one node from to , or one from to . We only choose a node which, when flipped, increases the cut value by at least . Then which of the following is true? (4分)
Given a 3-SAT formula with clauses, in which each clause has three variables, the MAX-3SAT problem is to find a truth assignment that satisfies as many clauses as possible. A simple randomized algorithm is to flip a coin, and to set each variable true with probability , independently for each variable. Which of the following statements is FALSE? (4分)
You are to maintain a collection of lists and to support the following operations.
(i) insert(item, list)
: insert item
into list
(cost = 1).
(ii) sum(list)
: sum the items in list
, and replace the list
with a list containing one item that is the sum (cost = length of list
).
We show that the amortized cost of an insert operation is O(1) and the amortized cost of a sum operation is O(1). If we assume the potential function to be the number of elements in the list, which of the following is FALSE? (4分)
Delete the minimum number from the given leftist heap. Which one of the following statements is TRUE? (3分)
Given four characters (a, b, c, d) with distinct frequencies in a text. Suppose that a and b are the two characters having the lowest frequencies. Which of the following sets of code is a possible Huffman code for this text? (3分)
Given the distance set D={1,1,2,2,2,2,3,3,3,4,5,5,6,6,8} in a Turnpike Reconstruction problem, first it can be sure that x1=0 and x6=8. Which of the following possible solutions will be checked next? (3分)
Suppose Q is a problem in NP, but not necessarily NP-complete. Which of the following is FALSE? (4分)
A B+ tree of order 3 with 21 numbers has at least __ nodes of degree 2. (3分)
For the result of accessing the keys 5 and 8 in order in the splay tree in the following figure, which one of the following statements is FALSE? (3分)
Insert {8, 9, 7, 2, 3, 5, 6, 4} into an initially empty AVL tree. Which one of the following statements is FALSE? (3分)
Which of the following statement is true ? (4分)
Among the following groups of concepts, which group is not totally relevant to a search engine? (2分)
In dynamic programming, we derive a recurrence relation for the solution to one subproblem in terms of solutions to other subproblems. To turn this relation into a bottom up dynamic programming algorithm, we need an order to fill in the solution cells in a table, such that all needed subproblems are solved before solving a subproblem. Among the following relations, which one is impossible to be computed? (3分)
When solving a problem with input size by divide and conquer, if at each step, the problem is divided into 16 sub-problems and each size of these sub-problems is , and they are conquered in . Which one of the following is the closest to the overall time complexity? (4分)
Which one of the following statements is FALSE about a skew heap? (3分)
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( 4*!!Carry + 2*!!T2 + !!T1 ) {
case 0:
case 1: break;
case 2: (3分); break;
case 4: H1->TheTrees[i] = Carry; Carry = NULL; break;
case 3: Carry = CombineTrees( T1, T2 );
H1->TheTrees[i] = H2->TheTrees[i] = NULL; break;
case 5: Carry = CombineTrees( T1, Carry );
H1->TheTrees[i] = NULL; break;
case 6: Carry = CombineTrees( T2, Carry );
H2->TheTrees[i] = NULL; break;
case 7: H1->TheTrees[i] = Carry;
(3分);
H2->TheTrees[i] = NULL; break;
} /* end switch */
} /* end for-loop */
return H1;
}
序号 | 结果 | 得分 |
---|---|---|
0 | 答案正确 | 3 |
1 | 答案正确 | 3 |
The function Power
calculates the exponential function . But since the exponential function grows rapidly, you are supposed to return instead.
int Power(int N, int k);
Both N
and k
are integers, which are no more than 2147483647.
#include <stdio.h>
int Power(int, int);
const int MOD = 10007;
int main()
{
int N, k;
scanf("%d%d", &N, &k);
printf("%d\n", Power(N, k));
return 0;
}
/* Your function will be put here */
2 3
8
128 2
6377
int Power(int N, int k){ if(k==0) return 1; unsigned K = k; unsigned n = N; unsigned int result = 1; while(K>0){ if(K%2){ result = result*n%10007; } K /= 2; n = ((n%10007)*(n%10007))%10007; } return result%10007; }
a.c: In function ‘main’: a.c:9:5: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d%d", &N, &k); ^~~~~~~~~~~~~~~~~~~~~
测试点 | 结果 | 得分 | 耗时 | 内存 |
---|---|---|---|---|
0 | 答案正确 | 1 | 3.00 ms | 256 KB |
1 | 答案正确 | 1 | 3.00 ms | 296 KB |
2 | 答案正确 | 1 | 3.00 ms | 256 KB |
3 | 答案正确 | 1 | 3.00 ms | 360 KB |