Given 1000 runs and 8 tapes. If simple -way merge is used, the minimum number of passes required is 5 (runs generation pass is not counted). (2分)
For a leftist heap with nodes, the worst-case running time of all operations (insert/delete min/merge) is . (2分)
If a data structure supports an operation QI such that a sequence of QI’s takes time to perform in the worst case, then the amortized cost of a QI operation is , while the actual time of a single QI operation could be as high as . (2分)
Consider a state-flipping algorithm for the Maximum-Cut problem. We say that partitions and are neighbors under the -flip rule if can be obtained from by moving at most nodes from one side of the partition to the other. If is a local optimum under the -flip rule, it is also a local optimum under the -flip rule for every . (2分)
The 4-queen problem has exactly 2 distinct solutions. (2分)
A randomized Quicksort algorithm has an expected running time, only if all the input permutations are equally likely. (2分)
A 2-3 tree with 12 leaves may have at most 11 nonleaf nodes. (2分)
The Huffman code is one kind of optimal prefix codes. For a given alphabet and its characters' frequencies,the Huffman codes may not be unique, but the Huffman code length of each character is unique. (2分)
If and , then . (2分)
Givien two matrices and , the time complexity of the simple matrix multiplication is . Now let's consider the following Divide and Conquer idea:
Divide each matrix into four submatrics as follows:
=
We recursively calculate each block of as and so on. This can reduce the time complexity of the simple calculation. (2分)
In the bin packing problem, we are asked to pack a list of items to the minimum number of bins of capacity 1. For the instance , let denote the number of bins used by the algorithm First Fit. The instance is derived from by deleting one item from . Then is at most of . (2分)
Recall the discussion about the Maximum Finding Problem (that is, to find the maximum among numbers in an array), Common CRCW memory strategy is used to assure for the parallel algorithm. Actually, we can also apply Arbitrary CRCW memory strategy to keep time complexity. Now let us consider a new memory strategy, namely the Concurrent Read Owner Write (CROW). It means that each memory has an official "owner". Only the "owner" can write to the corresponding memory. Then there is no parallel algorithm that can solve the problem with using CROW memory strategy. (2分)
In a search engine, thresholding for query retrieves the top documents according to their weights. (2分)
Which of the following binomial trees can represent a binomial queue of size 141? (3分)
Two spam mail detection systems are tested on a dataset with 10000 ordinary mails and 2000 spam mails. System A detects 300 ordinary mails and 1600 spam mails, and system B detects 315 ordinary mails and 1800 spam mails. If our primary concern is to keep the important mails safe, which of the following is correct? (3分)
In the bin packing problem, suppose that the maximum size of the items is bounded from above by . Now let's apply the Next Fit algorithm to pack a set of items into bins with capacity 1. Let and denote the numbers of bins used by algorithms Next Fit and the optimal solution. Then for all , we have for some . Which one of the following statements is FALSE? (3分)
Given a set of activities . Each takes place during a time interval . If an instance given as the following, the maximum-size of mutually compatible activities is __. (3分)
Suppose that the replacement selection is applied to generate longer runs with a priority queue of size 5. Given the sequence of numbers { 17, 2, 6, 57, 51, 86, 5, 94, 43, 54, 39, 87, 29}, the longest run contains __ numbers. (3分)
Which one of the following statements is FALSE? (3分)
The Online Hiring Algorithm ( hire only once ) is described as the following:
int OnlineHiring ( EventType C[ ], int N, int k )
{
int Best = N;
int BestQ = -INFINITY ;
for ( i=1; i<=k; i++ ) {
Qi = interview( i );
if ( Qi > BestQ ) BestQ = Qi;
}
for ( i=k+1; i<=N; i++ ) {
Qi = interview( i );
if ( Qi > BestQ ) {
Best = i;
break;
}
}
return Best;
}
Assume that the quality input C[ ] is uniformly random. When = 271 and = 90, the probability of hiring the th candidate is__. (3分)
Givien two matrices and . Let's consider the following Divide and Conquer idea to do matrix multiplication .
Divide each matrix into four submatrics as follows:
=
We define as follows:
Here all the matrix multiplications are done recursively. Then each part of can be calculated by simple additions and subtractions among .
Which of the following is the closest to the actual time complexity? (3分)
When measure the performance of parallel algorithm, we often use work load () and worst-case running time (). How many evaluation metrics are asymptotically equivalent to and ? (3分)
After splaying at node 2 in the given tree, which of the following statements about the resulting tree is FALSE? (3分)
How many of the following sorting methods use(s) Divide and Conquer algorithm? (3分)
Insert 28, 23, 54, 61, 98, 37 into an initially empty AVL tree first. Then immediately insert one of the following keys. Which one will cause an RL rotation? (3分)
There are jobs, and each job has a processing time . We will use a local search algorithm to partition the jobs into two groups A and B, where set A is assigned to machine and set B to . The time needed to process all of the jobs on the two machines is , . The problem is to minimize .
Local search: Start by assigning jobs to , and the rest to . The local moves are to move a single job from one machine to the other, and we only move a job if the move decreases the absolute difference in the processing times. Which of the following statement is true? (3分)
Which one of the following statements is FALSE? (3分)
Which one of the following statements is FALSE? (3分)
Delete the minimum number from the given leftist heap. Which one of the following statements is TRUE? (3分)
Given the following game tree, the red node will be pruned with α-β pruning algorithm if and only if __. (3分)
After inserting 1 into the red-black tree given in the figure, which node(s) will have its/their color(s) changed? (3分)
After inserting 0 into the 2-3 tree given in the figure, how many of the following statements are FALSE? (3分)
(S1) The tree grows higher;
(S2) 2 and 4 are in the same interior node;
(S3) the root node still contains 9 only;
(S4) the interior node containing 12 keeps unchanged.
Merge the two given skew heaps. Which one of the following statements is FALSE? (3分)
The function DeleteRoot
is to delete the root of a subtree with index Ind
from a binomial queue H
. The rest of the subtree is then stored as a new binomial queue and returned.
BinQueue DeleteRoot( BinQueue H, int Ind )
{
BinTree OldRoot, SubTree;
BinQueue NewBinQ;
int i;
OldRoot = H->TheTrees[Ind];
SubTree = OldRoot->LeftChild;
free(OldRoot);
NewBinQ = Initialize();
NewBinQ->CurrentSize = (3分);
for ( (3分) ) {
NewBinQ->TheTrees[i] = SubTree;
SubTree = SubTree->NextSibling;
NewBinQ->TheTrees[i]->NextSibling = NULL;
}
return NewBinQ;
}
序号 | 结果 | 得分 |
---|---|---|
0 | 答案正确 | 3 |
1 | 答案正确 | 3 |
CYLL has an integer-typed variable whose initial value is 1. The variable can be updated in each step by applying either of the two operations:
Multiply the variable by a fixed integer :
Add an integer () to the number:
Given two integers and as inputs, can you help CYLL to decide the minimum number of steps required before she obtains the number as the variable value?
int FindMinSteps(int N, int K);
Here () is the target number and () is the multiplication factor, which are integers as described in the problem specification.
The function is expected to return the minimum number of steps before the variable reaches value . (See the sample input/output for a concrete example.)
#include <stdio.h>
int FindMinSteps(int N, int K);
int main()
{
int N, K;
scanf("%d%d", &N, &K);
printf("%d", FindMinSteps(N, K));
return 0;
}
/* Implement the 'FindMinSteps' function here */
101 2
6
step 1:
step 2:
step 3:
step 4:
step 5:
step 6:
Note that this is not the only way to reach 101 in 6 steps, however, we care about the minumum number of steps, which is unique, rather than how you reach there.
int FindMinSteps(int N, int K) { if(N<=1){ return 0; } if(N<=11){ return 1; } int temp=N/K; int a=1; int step=0; while(a<temp){ if(step==0&&a+10<=temp){ a=a+10; step++; } if(step>0&&a*K<=temp){ a=a*K; step++; } if(step>0&&a*K>temp){ while(a+10<=temp){ a=a+10; step++; } if(a!=temp){ a=temp; step++; } } } if(a*K<=N){ a=a*K; step++; } while(a+10<=N){ a=a+10; step++; } if(a!=N){ a=N; step++; } return step; }
a.c: In function ‘main’: a.c:9:2: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d%d", &N, &K); ^~~~~~~~~~~~~~~~~~~~~
测试点 | 结果 | 得分 | 耗时 | 内存 |
---|---|---|---|---|
0 | 答案正确 | 2 | 4.00 ms | 380 KB |
1 | 答案正确 | 2 | 4.00 ms | 360 KB |
2 | 答案错误 | 0 | 3.00 ms | 360 KB |
3 | 答案正确 | 1 | 4.00 ms | 256 KB |
4 | 运行超时 | 0 | 0.00 ms | 0 KB |
5 | 答案正确 | 1 | 3.00 ms | 284 KB |