In the Activity Selection problem, consider any non-empty set of activities , and let be an activity in with the shortest lasting time. Then must be included in some maximum-size subset of mutually compatible activities of . (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分)
In a Red-Black tree, the path from the root to the farthest leaf is no more than twice as long as the path from the root to the nearest leaf. (2分)
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分)
A leftist heap with the null path length of the root being must have at least nodes. (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分)
While accessing a term by hashing in an inverted file index, range searches are expensive. (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分)
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分)
Inserting a number into a binomial heap with 15 nodes costs less time than inserting a number into a binomial heap with 19 nodes. (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分)
To solve the Maximum Finding problem with parallel Random Sampling method, and can be achieved with processors. (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. However, as the same as the deterministic QuickSort, the worst case running time of the randomized QuickSort is still . (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分)
If there are 81 runs to be merged using 4 taps for 3-way merges, then distributing the runs unevenly as (12, 24, 45) will require less number of passes than the even distribution (27, 27, 27). (2分)
Suppose that the replacement selection is applied to generate longer runs with a priority queue of size 4. Given the sequence of numbers { 11, 81, 17, 12, 94, 96, 30, 28, 35, 41, 58, 99, 15 }. Which of the following gives the second output run? (3分)
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分)
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分)
Let X be a problem that belongs to the class NP. Then which one of the following is 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分)
Which one of the following statements is TRUE? (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分)
How many of the following statements is/are TRUE? (3分)
In a binomial queue with nodes, how many nodes have depth (the root has depth )? (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分)
When doing amortized analysis, which one of the following statements is FALSE? (3分)
Which one of the following problems can be best solved by dynamic programming? (3分)
Which of the following is TRUE about NP-Complete and NP-Hard problems? (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分)
There are 8000 documents in the database. The statistic data for one query are shown in the following table. The precision is: __ (3分)
Relevant | Irrelevant | |
---|---|---|
Retrieved | 1000 | 1000 |
Not Retrieved | 2000 | 4000 |
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分)
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分)
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)
Delete the minimum number from the binomial queue given in the following figure. Which one of the following statements must be FALSE? (3分)
Given the following game tree, which node in the right subtree is the first node to be pruned with α-β pruning algorithm? (3分)
IsRBTree (3)
The functions IsRBTree
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 BH; /* black height */
colors Color;
};
typedef PtrToRBNode RBTree;
Please fill in the blanks.
bool IsRBTree( RBTree T )
{
int LeftBH, RightBH;
if ( !T ) return true;
if ( T->Color == black ) T->BH = 1;
else {
if ( T->Left && (T->Left->Color == red)) return false;
if ( T->Right && (2分) ) return false;
}
if ( !T->Left && !T->Right ) return true;
if ( (2分)) {
if ( T->Left ) LeftBH = T->Left->BH;
else LeftBH = 0;
if ( T->Right ) RightBH = T->Right->BH;
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 | 3.00 ms | 296 KB |
1 | 答案正确 | 1 | 3.00 ms | 296 KB |
2 | 答案正确 | 1 | 3.00 ms | 356 KB |