The set cover problem is one of Karp's 21 NP-complete problems. Given a set of elements (called the universe) and a collection of sets whose union equals the universe, and and a cost function , the weighted set cover problem is to identify the smallest cost of sub-collection of whose union equals the universe. Consider an approximation algorithm as follows:
C = null
while ( C!=U ) {
for each S[i], calculate the cost-effectiveness a[i] = cost(S[i]) / |S[i]-C|
find the best cost-effective set, say S[j]
pick S[j]
C = C union S[j]
}
output the picked sets
If , we can't find a constant , so that the approximation ratio of the above algorithm is .
(2分)
Local search algorithm can be used to solve lots of classic problems, such as SAT and -Queen problems. Define the configuration of SAT to be = vector of assignments of boolean variables, and that of -Queen to be = positions of the queens in each column. The sizes of the search spaces of SAT and -Queen are and , respectively. (2分)
To solve the Maximum Finding problem with parallel Random Sampling method, processors are required to get and with very high probability. (2分)
A leftist heap with the null path length of the root being must have at least nodes. (2分)
Reviewing the randomized QuickSort in our course, we always select a central splitter as a pivot before recursions, make sure that each side contains at least elements. Hence, differing from the deterministic QuickSort, the worst case expected running time of the randomized QuickSort is . (2分)
In a Turnpike Reconstruction problem, given the distance set = { 1, 2, 2, 3, 3, 4, 5, 6, 6, 8 }, it is impossible to have a point placed at 3. (2分)
If there are 105 runs to be merged using 4 taps for 3-way merges, then distributing the runs unevenly as (17, 32, 56) will require less number of passes than the even distribution (35, 35, 35). (2分)
In a Red-Black tree, the path from the root to the nearest leaf is no more than half as long as the path from the root to the farthest leaf. (2分)
If devide-and-conquer strategy is used to find the closest pair of points in a plane, unless the points are sorted not only by their coordinates but also by their coordinates, it would be impossible to solve it in a time of , where is the number of points. (2分)
If is a potential function associated with a data structure , then is also a potential function that can be associated with . Moreover, the amortized running time of each operation with respect to is at most triple the amortized running time of the operation with respect to . (2分)
The weighted Activity Selection problem with weights in the set {1, 2} can be solved optimally by the same greedy algorithm used for the unweighted case. (2分)
In the Activity Selection problem, consider any non-empty set of activities , and let be an activity in with the latest start time. Then must be included in some maximum-size subset of mutually compatible activities of . (2分)
Inserting a number into a binomial heap with 11 nodes costs more time than inserting a number into a binomial heap with 17 nodes. (2分)
While accessing a term stored in a B+ tree in an inverted file index, range searches are expensive. (2分)
A boolean formula is in disjunctive normal form (DNF) if it is a disjunction (OR) of one or more conjunctions (AND) of one or more literals. A literal is a variable or its negation. For example, the formula (x ∧ ¬y ∧ z) ∨ (¬x ∧ z) ∨ (w ∧ y ∧ ¬z) is a DNF formula. In DNF-Sat you are given a DNF formula, and the goal is to tell whether that formula is satisfiable.
We claim that the problem DNF-Sat is in P. (2分)
Let X be a problem that belongs to the class NP. Then which one of the following is TRUE? (3分)
When solving a problem with input size by divide and conquer, if at each step, the problem is divided into 4 sub-problems of size , and they are conquered in . Which one of the following is the closest to the overall time complexity ? Suppose that and all related root values are integers. (3分)
Given a linked list containg nodes. Our task is to remove all the nodes. At each step, we randomly choose one node in the current list, then delete the selected node together with all the nodes after it. Here we assume that each time we choose one node uniformly among all the remaining nodes. What is the expected number of steps to remove all the nodes? (3分)
Insert { 5, 1, 7, 8, 21, 2, 12, 19, 13, 0 } into an initially empty 2-3 tree (with splitting). Which one of the following statements is FALSE? (3分)
Which one of the following problems can be best solved by dynamic programming? (3分)
In a binomial queue with nodes, how many nodes have depth (the root has depth )? (3分)
To delete X from a splay tree, the operations are: (1) Find X; (2)Remove X; (3) FindMin(); and the last operation is: (3分)
Given 4 cases of frequences of four characters. In which case(s) that the total bits taken by Huffman codes are the same as that of the ordinary equal length codes? (3分)
Which one of the following statements is TRUE? (3分)
Which of the following is TRUE about NP-Complete and NP-Hard problems? (3分)
Given the following game tree, which node is the first one to be pruned with α-β pruning algorithm? (3分)
When doing amortized analysis, which one of the following statements is FALSE? (3分)
Delete the minimum number from the binomial queue given in the following figure. Which one of the following statements must be FALSE? (3分)
Suppose that the replacement selection is applied to generate longer runs with a priority queue of size 4. Given the sequence of numbers { 9, 75, 17, 12, 88, 91, 25, 22, 35, 41, 58, 96, 15 }. Which of the following gives the second output run? (3分)
How many of the following statements is/are TRUE? (3分)
The potential of a skew heap is defined to be the total number of right heavy nodes. The weight of a node, , is defined 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 . In particular, any path in an -node tree contains at most light nodes.
Define the following functions:
Then for any -node skew heaps, which of the following is FALSE? (3分)
Assume that you are a real world Chinese postman, which have learned an awesome course "Advanced Data Structures and Algorithm Analysis" (ADS). Given a 2-dimensional map indicating positions of your post office and all the addresses you must visit, you'd like to find a shortest path starting and finishing both at your post office, and visit all the addresses at least once in the circuit. Fortunately, you have a magic item "Bamboo copter & Hopter" from "Doraemon", which makes sure that you can fly between two positions using the directed distance (or displacement).
("Bamboo copter & Hopter", japan12.com/bamboo-copter-hopter)
However, reviewing the knowledge in the ADS course, it is an problem! Wasting too much time in finding the shortest path is unwise, so you decide to design a algorithm as follows, to achieve an acceptable solution.
Compute a minimum spanning tree T connecting all the addresses.
Regard the post office as the root of T.
Start at the post office.
Visit the addresses in order of a _____ of T.
Finish at the post office.
There are several methods of traversal which can be filled in the blank of the above algorithm. Assume that , how many methods of traversal listed below can fulfill the requirement? (3分)
The following psuedo-code is for solving the Profix Sums problem parallely, where the input numbers are stored in the array A
. Which of the following gives the time and work load of the algorithm? (3分)
for Pi , 1 <= i <= n pardo
B(0, i) := A(i)
for h = 1 to log(n)
for i, 1 <= i<= n/(2^h) pardo
B(h, i) := B(h-1, 2*i-1) + B(h-1, 2*i)
for h = log(n) to 0
for i even, 1 <= i<= n/(2^h) pardo
C(h, i) := C(h+1, i/2)
for i = 1 pardo
C(h, 1) := B(h, 1)
for i odd, 3 <= i <= n/(2^h) pardo
C(h, i) := C(h+1, (i-1)/2) + B(h, i)
for Pi , 1 <= i<= n pardo
Output C(0, i)
There are 8000 documents in the database. The statistic data for one query are shown in the following table. The recall is: __ (3分)
Relevant | Irrelevant | |
---|---|---|
Retrieved | 1000 | 1000 |
Not Retrieved | 2000 | 4000 |
Suppose that the devide-and-conquer strategy is used to find the maximum and the minimum of positive numbers. At each step, the problem is divided into 2 sub-problems of size . Then the time recurrences is , where is __. (3分)
The functions IsRBT
is to check if a given binary search tree T
is a red-black tree. Return true
if T
is, or false
if not.
The red-black tree structure is defined as the following:
typedef enum { red, black } colors;
typedef struct RBNode *PtrToRBNode;
struct RBNode{
int Data;
PtrToRBNode Left, Right, Parent;
int BlackHeight;
colors Color;
};
typedef PtrToRBNode RBTree;
Please fill in the blanks.
bool IsRBT( RBTree T )
{
int LeftBH, RightBH;
if ( !T ) return true;
if ( T->Color == black ) T->BlackHeight = 1;
else {
if ( T->Left && (2分)) return false;
if ( T->Right && (T->Right->Color == red) ) return false;
}
if ( !T->Left && !T->Right ) return true;
if ( (2分)) {
if ( T->Left ) LeftBH = T->Left->BlackHeight;
else LeftBH = 0;
if ( T->Right ) RightBH = T->Right->BlackHeight;
else RightBH = 0;
if ( LeftBH == RightBH ) {
(2分);
return true;
}
else return false;
}
else return false;
}
序号 | 结果 | 得分 |
---|---|---|
0 | 答案正确 | 2 |
1 | 答案错误 | 0 |
2 | 答案正确 | 2 |
You are supposed to implement the Insert
function, which inserts an integer Key
into an AVL tree T
. The resulting tree must be returned.
AVLTree Insert ( int Key, AVLTree T );
where AVLTree
is defined as the following:
typedef struct AVLNode *PtrToAVLNode;
struct AVLNode{
int Data;
PtrToAVLNode Left;
PtrToAVLNode Right;
int Height;
};
typedef PtrToAVLNode AVLTree;
#include <stdio.h>
#include <stdlib.h>
typedef struct AVLNode *PtrToAVLNode;
struct AVLNode{
int Data;
PtrToAVLNode Left;
PtrToAVLNode Right;
int Height;
};
typedef PtrToAVLNode AVLTree;
AVLTree Insert ( int Key, AVLTree T );
void PostOrderPrint( AVLTree T ); /* details omitted */
void InOrderPrint( AVLTree T ); /* details omitted */
int main()
{
int N, Key, i;
AVLTree T = NULL;
scanf("%d", &N);
for ( i=0; i<N; i++ ) {
scanf("%d", &Key);
T = Insert( Key, T );
}
PostOrderPrint( T );
InOrderPrint( T );
return 0;
}
/* Your function will be put here */
7
31 27 6 67 88 53 15
Post-order: 6 27 15 53 88 67 31
In-order: 6 15 27 31 53 67 88
int Max(int x, int y){ if(x>y) return x; return y; } int CalHeight(AVLTree T){ if(!T){ return -1; }else{ return T->Height; } } int IsRotate(AVLTree T){ if((CalHeight(T->Left)-CalHeight(T->Right))==2 || (CalHeight(T->Left)-CalHeight(T->Right))== -2){ return 1; } return 0; } AVLTree RRRotation(AVLTree T){ AVLTree TempNode = T; T = T->Right; TempNode->Right = T->Left; TempNode->Height = Max(CalHeight(TempNode->Left),CalHeight(TempNode->Right))+1; T->Left = TempNode; T->Height = Max(CalHeight(T->Left),CalHeight(T->Right))+1; return T; } AVLTree LLRotation(AVLTree T){ AVLTree TempNode = T; T = T->Left; TempNode->Left = T->Right; TempNode->Height = Max(CalHeight(TempNode->Left),CalHeight(TempNode->Right))+1; T->Right = TempNode; T->Height = Max(CalHeight(T->Left),CalHeight(T->Right))+1; return T; } AVLTree LRRotation(AVLTree T){ T->Left =RRRotation(T->Left); T = LLRotation(T); return T; } AVLTree RLRotation(AVLTree T){ T->Right =LLRotation(T->Right); T = RRRotation(T); return T; } AVLTree RotateTree(AVLTree T, int Key){ if(Key < T->Data){ if(Key < T->Left->Data){ T = LLRotation(T); }else{ T = LRRotation(T); } }else if(Key > T->Data){ if(Key < T->Right->Data){ T = RLRotation(T); }else{ T = RRRotation(T); } } return T; } AVLTree InitialTree(AVLTree T, int Key){ T = (struct AVLNode*)malloc(sizeof(struct AVLNode)); T->Left = NULL; T->Right = NULL; T->Height = 0; T->Data = Key; return T; } AVLTree Insert ( int Key, AVLTree T ){ if(!T){ T = InitialTree(T, Key); }else if(Key < T->Data){ T -> Left =Insert(Key, T->Left); if(IsRotate(T)){ T = RotateTree(T, Key); } }else if(Key > T->Data){ T -> Right =Insert(Key, T->Right); if(IsRotate(T)){ T = RotateTree(T, Key); } } T->Height = Max(CalHeight(T->Right),CalHeight(T->Left))+1; return T; }
a.c: In function ‘main’: a.c:48:5: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d", &N); ^~~~~~~~~~~~~~~ a.c:50:9: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d", &Key); ^~~~~~~~~~~~~~~~~
测试点 | 结果 | 得分 | 耗时 | 内存 |
---|---|---|---|---|
0 | 答案正确 | 2 | 4.00 ms | 384 KB |
1 | 答案正确 | 1 | 4.00 ms | 296 KB |
2 | 答案正确 | 1 | 5.00 ms | 256 KB |