A skew heap is a heap data structure implemented as a binary tree. Skew heaps are advantageous because of their ability to merge more quickly than balanced binary heaps. The worst case time complexities for Merge, Insert, and DeleteMin are all , while the amorited time complexities for Merge, Insert, and DeleteMin are all . ~@
Consider the online hiring problem, in which we have total candidates. First of all, we interview candidates but reject them all. Then we hire the first candidate who is better than all of the previous candidates you have interviewed. It is true that the probability of the th candidate is the best is , where . ~@
We are given a set of sites in the plane, and we want to choose a set of centers so that the maximum distance from a site to the nearest center is minimized. Here can be an arbitrary point in the plane.
A local search algorithm arbitrarily choose points in the plane to be the centers, then
If steps (1) and (2) cause the covering radius to strictly decrease, we perform another iteration, otherwise the algorithm stops.
When the above local search algorithm terminates, the covering radius of its solution is at most 2 times the optimal covering radius.
~@
Assume that Problem X is reduced to Problem Y in polynomial time, where Y is NP-hard. Moreover, Y adimts a -approximation algorithm, and there is no -approroximation algorithm unless P=NP. Which one of the following statements is TRUE?
If there are 28 nodes in an AVL tree, then the maximum depth of the tree is __. The depth of an empty tree is defined to be 0.
Which node is root 7's child after splaying 4 in the given splay tree?
Given a 2-3 tree as shown in the figure, after inserting 18 with splitting strategy, where will the key 15 be?
There are 14000 documents in the database. The statistic data for one query are shown in the following table. The recall is: __
Relevant | Irrelevant | |
---|---|---|
Retrieved | 2000 | 6000 |
Not Retrieved | 4000 | 2000 |
Let us consider the problem of finding a large cut in an undirected graph which has vertices and edges. A cut is a partition of the vertices into two disjoint sets, and the value of a cut is the weight of all edges crossing from one side of the partition to the other. Here we consider the case where all edges in the graph have the same weight 1.
Suppose that a partition of into two disjoint sets and is given by a randomized algorithm, in which each vertex is randomly and independently assigned to one of the two sets.
Which of the following statements is FALSE?
Consider the following buffer management problem. Initially the buffer size (the number of blocks) is one. Each block can accommodate exactly one item. As soon as a new item arrives, check if there is an available block. If yes, put the item into the block, induced a cost of one. Otherwise, the buffer size is doubled, and then the item is able to put into. Moreover, the old items have to be moved into the new buffer so it costs to make this insertion, where is the number of old items. Clearly, if there are items, the worst-case cost for one insertion can be . To show that the average cost is , let us turn to the amortized analysis. To simplify the problem, assume that the buffer is full after all the items are placed. Which of the following potential functions works?
Given a recurrence equation . To solve this equation in an iterative way, we cannot fill up a table as follows:
In the Red Black tree that results after successively inserting the keys 20, 22, 18, 12, 15, 8, into an initially empty Red Black tree, which nodes will be black?
Spanning Tree Problem: Given an undirected graph , where and . Let be the set of all spanning trees of . Define to be the degree of a vertex . Define to be the weight of an edge .
We have the following three variants of spanning tree problems:
For a pair of edges where and such that belongs to the unique cycle of , we define edge-swap to be .
Here is a local search algorithm:
T = any spanning tree in F;
while (there is an edge-swap(e, e') which reduces Cost(T)) {
T = T - e + e';
}
return T;
Here Cost(T)
is the number of leaves in T
in Max Leaf Spanning Tree; or is the total weight of T
in Minimum Spanning Tree; or else is the minimum degree of T
in Minimum Degree Spanning Tree.
Which of the following statements is TRUE?
When solving a problem with input size by divide and conquer, if at each step, the problem is divided into 8 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?
-center problem: Given cities with specified distances, one wants to build warehouses in different cities and minimize the maximum distance of a city to a warehouse.
Which of the following is false?
In the Tic-tac-toe game, a "goodness" function of a position is defined as
where is the number of potential wins at position .
In the following figure, O
represents the computer and X
the human. What is the goodness of the position of the figure?
Which one of the following statements about the Ranking problem is true? (Assume that both arrays contain elements.)
Merge the two leftist heaps in the following figure. Which one of the following statements is FALSE?
Which one of the following statements is TRUE about the NP class?
In external sorting, in order to reduce the number of passes, minimizing the initial number of runs (i.e. generating longer runs ) is a good idea. Suppose the input record keys are (25, 74, 56, 34, 21, 11, 29, 80, 38, 53) and the internal memery can hold only 3 records, the minimum number of initial runs obtained by replacement selection is__ 。
When inserting 1, 2, 3, 6, 5, and 4 one by one into an initially empty AVL tree,which kinds of rotations will be encountered?
In proving the amortized bound of a Merge operation in skew heaps, the potential of a skew heap is defined to be the total number of right heavy nodes. Then we can prove that, in an -node skew heap, the amortized cost for a Merge operation is exactly __ .
Hint:
Define the weight of a node, , to be the number of descendants of (including ). A non-root node is said to be heavy if its weight is greater than half the weight of its parent.
Lemma 1: At most one child is heavy, of all children of any node.
Lemma 2: On any path from node down to a descendant , there are at most light nodes, excluding .
Given 4 characters with some frequencies in a text. If the corresponding Huffman codes are : 00, : 010, : 011 and : 1. Which of the following sets of frequencies is a possible one for ?
The functions BinQueue_Find
and Recur_Find
are to find X
in a binomial queue H
. Return the node pointer if found, otherwise return NULL.
BinTree BinQueue_Find( BinQueue H, ElementType X )
{
BinTree T, result = NULL;
int i, j;
for( i=0, j=1; j<=H->CurrentSize; i++, j*=2) { /* for each tree in H */
T= H->TheTrees[i];
if ( X (3分) ){ /* if need to search inside this tree */
result = Recur_Find(T, X);
if ( result != NULL ) return result;
}
}
return result;
}
BinTree Recur_Find( BinTree T, ElementType X )
{
BinTree result = NULL;
if ( X==T->Element ) return T;
if ( T->LeftChild!=NULL ){
result = Recur_Find(T->LeftChild, X);
if ( result!=NULL ) return result;
}
if ( (3分) )
result = Recur_Find(T->NextSibling, X);
return result;
}
序号 | 结果 | 测试点得分 |
---|---|---|
0 | 编译错误 | 0 |
1 | 编译错误 | 0 |
Bob will participate in a programming contest. There are altogether n
problems in the contest. Unlike in PAT (Programming Ability Test), in a programming contest one can not obtain partial scores. For problem i
, Bob will need time[i]
to solve it and obtains the corresponding score[i]
, or he may choose not to solve it at all. Bob will be happy when he obtains a total score no less than happy_score
. You are supposed to find the minimum time needed for Bob to be happy. The function need_time
must return the minimum time, or -1
if it is impossible for Bob to obtain a score no less than happy_score
.
int need_time(const int time[], const int score[], int happy_score, int n);
Here n
(n
MAXN
) is the number of problems;happy_score
( happy_score
MAXS
) is the minimum score for Bob to be happy;time[]
is the array to store time[i]
(time[i]
) which is the time to solve problem i
;score[]
is the array to store score[i]
(score[i]
) which is the score Bob gets for solving problem i
.
#include <stdio.h>
#define MAXN 10
#define MAXS 1000
int need_time(const int time[], const int score[], int happy_score, int n);
int main() {
int n, i, happy_score;
int time[MAXN], score[MAXN];
scanf("%d %d", &n, &happy_score);
for (i = 0; i < n; ++i)
scanf("%d", &time[i]);
for (i = 0; i < n; ++i)
scanf("%d", &score[i]);
printf("%d\n", need_time(time, score, happy_score, n));
return 0;
}
/* Your function will be put here */
6 121
84 87 78 16 94 38
87 93 50 22 63 28
125
int need_time(const int time[], const int score[], int happy_score, int n) { return 1; }
a.c: In function ‘main’: a.c:11:3: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d %d", &n, &happy_score); ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ a.c:13:7: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d", &time[i]); ^~~~~~~~~~~~~~~~~~~~~ a.c:15:7: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d", &score[i]); ^~~~~~~~~~~~~~~~~~~~~~
测试点 | 结果 | 测试点得分 | 耗时 | 内存 |
---|---|---|---|---|
0 | 答案错误 | 0 | 3.00 ms | 180 KB |
1 | 答案错误 | 0 | 3.00 ms | 184 KB |
2 | 答案错误 | 0 | 3.00 ms | 184 KB |
3 | 答案错误 | 0 | 3.00 ms | 312 KB |
4 | 答案正确 | 1 | 3.00 ms | 316 KB |