浙江大学2017-18春夏《高级数据结构与算法分析》期末模拟练习
开始时间2016/01/01 08:00:00
结束时间2038/01/18 08:00:00
答题时长120分钟
考生
得分34
总分100

判断题得分:16总分:30
R1-1

In a Turnpike Reconstruction problem, given the distance set DD = { 1, 2, 2, 3, 3, 4, 5, 6, 6, 8 }, it is impossible to have a point placed at 5. ~@

(2分)
评测结果答案错误(0 分)
R1-2

While accessing a term stored in a B+ tree in an inverted file index, range searches are expensive. ~@

(2分)
评测结果答案错误(0 分)
R1-3

In the Activity Selection problem, consider any non-empty set of activities SS, and let ama_m be an activity in SS with the*** latest start time.*** Then ama_m must be included in some maximum-size subset of mutually compatible activities of SS. ~@

(2分)
评测结果答案正确(2 分)
R1-4

To solve the Maximum Finding problem with parallel Random Sampling method, T(n)=O(1)T(n) = O(1) and W(n)=O(n)W(n) = O(n) can be achieved with O(n)O(n) processors. ~@

(2分)
评测结果答案错误(0 分)
R1-5

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分)
评测结果答案正确(2 分)
R1-6

Local search algorithm can be used to solve lots of classic problems, such as SAT and NN-Queen problems. Define the configuration of SAT to be XX = vector of assignments of NN boolean variables, and that of NN-Queen to be YY = positions of the NN queens in each column. The sizes of the search spaces of SAT and NN-Queen are O(2N)O(2^N) and O(NN)O(N^N), respectively. ~@

(2分)
评测结果答案正确(2 分)
R1-7

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 n/4n/4 elements. However, as the same as the deterministic QuickSort, the worst case running time of the randomized QuickSort is still O(N2)O(N^2). ~@

(2分)
评测结果答案错误(0 分)
R1-8

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 xx coordinates but also by their yy coordinates, it would be impossible to solve it in a time of O(NlogN)O(NlogN), where NN is the number of points. ~@

(2分)
评测结果答案正确(2 分)
R1-9

The set cover problem is one of Karp's 21 NP-complete problems. Given a set of elements U={1,2,...,n}U=\{1,2,...,n\} (called the universe) and a collection SS of kk sets whose union equals the universe, and and a cost function cost:SQ+cost:S\rightarrow Q^+, the weighted set cover problem is to identify the smallest cost of sub-collection of SS 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 PNPP\neq NP, we can't find a constant ρN+\rho\in N^+, so that the approximation ratio of the above algorithm is ρ\rho.

~@

(2分)
评测结果答案正确(2 分)
R1-10

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分)
评测结果答案正确(2 分)
R1-11

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分)
评测结果答案错误(0 分)
R1-12

A leftist heap with the null path length of the root being rr must have at least 2r+112^{r+1}-1 nodes. ~@

(2分)
评测结果答案正确(2 分)
R1-13

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分)
评测结果答案错误(0 分)
R1-14

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分)
评测结果答案错误(0 分)
R1-15

If Φ\Phi is a potential function associated with a data structure SS, then 3Φ3 \Phi is also a potential function that can be associated with SS. Moreover, the amortized running time of each operation with respect to 3Φ3 \Phi is at most triple the amortized running time of the operation with respect to Φ\Phi. ~@

(2分)
评测结果答案正确(2 分)
单选题得分:18总分:60
R2-1

The following psuedo-code is for solving the Profix Sums problem parallely, where the input NN 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)
(3分)
评测结果答案正确(3 分)
R2-2

When doing amortized analysis, which one of the following statements is FALSE?

(3分)
评测结果答案错误(0 分)
R2-3

Let X be a problem that belongs to the class NP. Then which one of the following is TRUE?

(3分)
评测结果答案错误(0 分)
R2-4

In a binomial queue with 150150 nodes, how many nodes have depth 11 (the root has depth 00)?

(3分)
评测结果答案错误(0 分)
R2-5

Which one of the following problems can be best solved by dynamic programming?

(3分)
评测结果答案错误(0 分)
R2-6

To delete X from a splay tree, the operations are: (1) Find X; (2) Remove X; (3) FindMax(TLT_L); and the last operation is:

(3分)
评测结果答案错误(0 分)
R2-7

How many of the following statements is/are TRUE?

  • The 0-1 knapsack problem cannot be solved by any local search algorithm.
  • The metropolis algorithm always improves the gradient descent algorithm.
  • In some cases, the state-flipping algorithm cannot terminate.
  • Unless P=NPP=NP, there is no ρ\rho-approximation for the maximum cut problem for any ρ<2\rho<2.
(3分)
评测结果答案错误(0 分)
R2-8

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分)
评测结果答案正确(3 分)
R2-9

Suppose that the devide-and-conquer strategy is used to find the maximum and the minimum of NN positive numbers. At each step, the problem is divided into 2 sub-problems of size N/2N/2. Then the time recurrences is T(N)=2T(N/2)+f(N)T(N) = 2T(N/2)+f(N), where f(N)f(N) is ____.

(3分)
评测结果答案错误(0 分)
R2-10

The potential of a skew heap is defined to be the total number of right heavy nodes. The weight of a node, w(x)w(x), is defined to be the number of descendants of xx (including xx). 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 xx down to a descendant yy, there are at most log2w(x)w(y)\lfloor log_2 \frac{w(x)}{w(y)} \rfloor light nodes, excluding xx. In particular, any path in an nn-node tree contains at most log2n\lfloor log_2 n \rfloor light nodes.

Define the following functions:

  • makeheap : create a new, empty heap
  • findmin : return the minimum key in the heap
  • insert : insert a key in the heap
  • deletemin : delete the minimum key from the heap
  • merge : merge two heaps

Then for any nn-node skew heaps, which of the following is FALSE?

(3分)
评测结果答案错误(0 分)
R2-11

Given the following game tree, which node is the first one to be pruned with α-β pruning algorithm?

abtree1.png

(3分)
评测结果答案正确(3 分)
R2-12

Which of the following is TRUE about NP-Complete and NP-Hard problems?

(3分)
评测结果答案错误(0 分)
R2-13

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分)
评测结果答案错误(0 分)
R2-14

Given a linked list containg NN 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分)
评测结果答案错误(0 分)
R2-15

Which one of the following statements is TRUE?

(3分)
评测结果答案正确(3 分)
R2-16

Delete the minimum number from the binomial queue given in the following figure. Which one of the following statements must be FALSE?

binomial_heap.png

(3分)
评测结果答案错误(0 分)
R2-17

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 NN positions pi(xi,yi)p_i(x_i,y_i) 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.jpg
("Bamboo copter & Hopter", japan12.com/bamboo-copter-hopter)

However, reviewing the knowledge in the ADS course, it is an NPCNPC problem! Wasting too much time in finding the shortest path is unwise, so you decide to design a 2approximation2-approximation 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 PNPP\neq NP, how many methods of traversal listed below can fulfill the requirement?

  • Level-Order Traversal
  • Pre-Order Traversal
  • Post-Order Traversal
(3分)
评测结果答案错误(0 分)
R2-18

When solving a problem with input size NN by divide and conquer, if at each step, the problem is divided into 4 sub-problems of size N\sqrt N, and they are conquered in O(logN)O(logN). Which one of the following is the closest to the overall time complexity T(N)T(N)? Suppose that T(2)=O(1)T(2) = O(1) and all related root values are integers.

(3分)
评测结果答案正确(3 分)
R2-19

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
(3分)
评测结果答案错误(0 分)
R2-20

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?

  • (1) 1 1 2 4
  • (2) 1 2 3 4
  • (3) 2 2 3 3
  • (4) 2 2 3 4
(3分)
评测结果答案正确(3 分)
程序填空题得分:0总分:6
R5-1

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总分:4
R6-1
AVL Tree Insertion
(4分)

You are supposed to implement the Insert function, which inserts an integer Key into an AVL tree T. The resulting tree must be returned.

Format of function:

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;

Sample program of judge:

#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 */

Sample Input:

7
31 27 6 67 88 53 15

Sample Output:

Post-order: 6 27 15 53 88 67 31
In-order: 6 15 27 31 53 67 88
评测结果答案错误(0 分)