For the recurrence equation ,we obtain according to the Master Theorem.
Merge the two skew heaps in the following figure. How many of the following statements is/are FALSE?
If X is a problem in class NP, then how many of the following statements is/are TRUE?
To solve a problem with input size by divide and conquer, algorithm A divides the problem into 7 subproblems with size and the time recurrences is
.
Now we attempt to design another algorithm B dividing the problem into subproblems with size and the time recurrences is
.
In order to beat algorithm A, what is the largest integer value of for which algorithm B would be asymptotically faster than algorithm A?
Sorting-by-merging is a classic serial algorithm. It can be translated directly into a reasonably efficient parallel algorithm. A recursive description follows.
MERGE−SORT( A(1), A(2), ..., A(n); B(1), B(2), ..., B(n) )
Assume that for some integer
if n = 1 then return B(1) := A(1)
else call, in parallel, MERGE−SORT( A(1), ..., A(n/2); C(1), ..., C(n/2) ) and
MERGE−SORT(A(n/2+1), ..., A(n); C(n/2+1), ..., C(n) )
Merge (C(1),...C(n/2)) and (C(n/2 + 1),...,C(n)) into (B(1), B(2), ..., B(n)) with time O(n)
Then the MERGE−SORT runs in __ .
For the result of accessing the keys 1 and 2 in order in the splay tree in the following figure, let's define ( included ) and potential , where means the greatest interger no larger than .
How many of the following statements is/are TRUE?
After inserting { 3, 4, 5, 6, 1, 2, 7 } into an initially empty red-black tree, which of following is False?
Assume that there are 10000 documents in the database, and the statistical data for one query are shown in the following table. One metric for evaluating the relevancy of the query is F-α score, which is defined as ((1+ α)∙(precision*recall))/(α∙precision+recall). Then the F-0.5 (α=0.5) score for this query is:
Relevant | Irrelevant | |
---|---|---|
Retrieved | 4800 | 1200 |
**Not Retrieved ** | 3200 | 800 |
A replacement selection is applied to generate the max run with a priority queue of 5 records. When the sequence of numbers is { 6, 79, 14, 10, 90, 28, 35, X, …. } and the length of the first run is 7, what is the sufficient condition of X?
If P and NP are different, which of the following statements is true?
Given the following game tree, if node d is pruned with α-β pruning algorithm, which of the following statements about the value of node a or node b is correct?
The potential function of a binomial queue is the number of the trees. After merging two binomial queues with 22 nodes and with 13 nodes,what is the potential change ?
** Load balancing problem: **
We have jobs each with processing time being an integer number.
Our task is to find a schedule assigning jobs to identical machines so as to minimize the makespan (the maximum completion time over all the machines).
We adopt the following local search to solve the above load balancing problem.
**LocalSearch: **
Start with an arbitrary schedule.
Repeat the following until no job can be re-assigned:
We claim the following four statements:
How many statments are correct ?
In the maximum satisfiability problem (MAX SAT), the input consists of Boolean variables , clauses (each of which consists of a disjunction(that is an “or”) of some number of the variables and their negations, e.g. , where is the negation of ), and a nonnegative weight for each clause . The objective of the problem is to find an assignment of the true/false to the that maximizes the weight of the satisfied clauses.
A variable or a negated variable is a literal. The number of literals in a clause is called its length. Denote to be the length of a clause . Clauses of length 1 are called unit clauses.
Randomized algorithm RA: Setting each to true with probability independently.
Which of the following statement is false?
To solve a problem with input size by divide and conquer, an algorithm divides the problem into 3 subproblems with size (assuming it is an integer ) and the time recurrences is
.
What is the overall time complexity of this algorithm?
In Activity Selection Problem, we are given a set of activities that wish to use a resource (e.g. a room). Each takes place during a time interval .
Let us consider the following problem: given the set of activities , we must schedule them all using the minimum
number of rooms.
Greedy1:
Use the optimal algorithm for the Activity Selection Problem to find the max number of activities that can be scheduled in one room. Delete and repeat on the rest, until no activities left.
Greedy2:
Which of the following statement is correct?
After deleting number 14 from a binomial queue of 5 numbers { 12, 13, 14, 23, 24 }, which of the followings is impossible?
To build a leftist heap, we can start from placing all the keys as single-node heaps on a queue, and perform the following until only one heap is on the queue: dequeue two heaps, merge them, and enqueue the result.
Then the best description of the time complexity of this procedure is:
Insert { 9, 8, 7, 2, 3, 5, 6, 4 } one by one into an initially empty AVL tree. How many of the following statements is/are FALSE?
Assume P≠NP, please identify the false statement.
Start from single-node splay trees, let's merge them into one splay tree in the following way: each time we select two splay trees, delete nodes one by one from the smaller tree and insert them into the larger tree. Then which of the following statements is NOT true?
The function FindKey
is to check if a given key
is in a B+ Tree with its root pointed by root
.
Return true
if key
is in the tree, or false
if not. The B+ tree structure is defined as following:
static int order = DEFAULT_ORDER;
typedef struct BpTreeNode BpTreeNode;
struct BpTreeNode {
BpTreeNode** childrens; /* Pointers to childrens. This field is not used by leaf nodes. */
ElementType* keys;
BpTreeNode* parent;
bool isLeaf; /* 1 if this node is a leaf, or 0 if not */
int numKeys; /* This field is used to keep track of the number of valid keys.
In an internal node, the number of valid pointers is always numKeys + 1. */
};
bool FindKey(BpTreeNode * const root, ElementType key){
if (root == NULL) {
return false;
}
int i = 0;
BpTreeNode * node = root;
while ((3分)) {
i = 0;
while (i < node->numKeys) {
if ((3分)) i++;
else break;
}
node = node->childrens[i];
}
for(i = 0; i < node->numKeys; i++){
if(node->keys[i] == key)
return true;
}
return false;
}
序号 | 结果 | 测试点得分 |
---|---|---|
0 | 编译错误 | 0 |
1 | 编译错误 | 0 |
Suppose that a string of English letters is encoded into a string of numbers. To be more specific, A
-Z
are encoded into 0
-25
. Since it is not a prefix code, the decoded result may not be unique. For example, 1213407
can be decoded as BCBDEAH
, MBDEAH
, BCNEAH
, BVDEAH
or MNEAH
. Note that 07
is not 7
, hence cannot be decoded as H
.
Your job is to tell in how many different ways we can decode a numeric string.
int Decode( char NumStr[] );
where NumStr
is a string consisting of only the numbers 0
-9
.
The function Decode
is supposed to return the number of different ways we can decode NumStr
.
Since the answer might be super large, you only need to output the answer modulo 1000000007.
#include <stdio.h>
#include <string.h>
#define MAXN 100
#define BASE 1000000007
int Decode( char NumStr[] );
int main()
{
char NumStr[MAXN];
scanf("%s", NumStr);
printf("%d", Decode(NumStr));
return 0;
}
/* Your function will be put here */
1213407
5