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. ~@
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 .
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.
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?
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)
When doing amortized analysis, which one of the following statements is FALSE?
Let X be a problem that belongs to the class NP. Then which one of the following is TRUE?
In a binomial queue with nodes, how many nodes have depth (the root has depth )?
Which one of the following problems can be best solved by dynamic programming?
To delete X from a splay tree, the operations are: (1) Find X; (2) Remove X; (3) FindMax(); and the last operation is:
How many of the following statements is/are TRUE?
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?
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 ____.
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?
Given the following game tree, which node is the first one to be pruned with α-β pruning algorithm?
Which of the following is TRUE about NP-Complete and NP-Hard problems?
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?
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?
Which one of the following statements is TRUE?
Delete the minimum number from the binomial queue given in the following figure. Which one of the following statements must be FALSE?
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?
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.
There are 8000 documents in the database. The statistic data for one query are shown in the following table. The recall is: __
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?
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 | 编译错误 | 0 |
1 | 编译错误 | 0 |
2 | 编译错误 | 0 |
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
AVLTree Insert ( int Key, AVLTree T ) { return NULL; }
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 | 答案错误 | 0 | 4.00 ms | 468 KB |
1 | 答案错误 | 0 | 3.00 ms | 328 KB |
2 | 答案错误 | 0 | 3.00 ms | 480 KB |