Problem

Week1

Question

If the depth of an AVL tree is 6 (the depth of an empty tree is defined to be -1), then the minimum possible number of nodes in this tree is:

Answer

• 33
• \(n_h = F_{h+3} - 1, for \quad h \leq -1\)
• 斐波那契公式不一定要记忆，数值不大可以现推

Question

Insert 2, 1, 4, 5, 9, 3, 6, 7 into an initially empty AVL tree. Which one of the following statements is FALSE?

A.4 is the root B.3 and 7 are siblings C.2 and 6 are siblings D.9 is the parent of 7

Answer

• B

Question

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

A.Aggregate analysis shows that for all n, a sequence of n operations takes worst-case time \(T(n)\) in total. Then the amortized cost per operation is therefore \(T(n)/n\)

B.For potential method, a good potential function should always assume its maximum at the start of the sequence

C.For accounting method, when an operation's amortized cost exceeds its actual cost, we save the difference as credit to pay for later operations whose amortized cost is less than their actual cost

D.The difference between aggregate analysis and accounting method is that the later one assumes that the amortized costs of the operations may differ from each other

Answer

• B : 应该是minimum，初始势能最低

Question

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 \(k+1\) to make this insertion, where \(k\) is the number of old items. Clearly, if there are \(N\) items, the worst-case cost for one insertion can be \(Ω(N)\). To show that the average cost is \(O(1)\), let us turn to the amortized analysis. To simplify the problem, assume that the buffer is full after all the \(N\) items are placed. Which of the following potential functions works?

A.The number of items currently in the buffer

B.The opposite number of items currently in the buffer

C.The number of available blocks currently in the buffer

D.The opposite number of available blocks in the buffer

Answer

D

Question

For the result of accessing the keys 3, 9, 1, 5 in order in the splay tree in the following figure, which one of the following statements is FALSE?

A.5 is the root

B.1 and 9 are siblings

C.6 and 10 are siblings

D.3 is the parent of 4

Answer

• D

Week 2

Question

In the red-black tree that results after successively inserting the keys 41; 38; 31; 12; 19; 8 into an initially empty red-black tree, which one of the following statements is FALSE?

A.38 is the root B.19 and 41 are siblings, and they are both red C.12 and 31 are siblings, and they are both black D.8 is red

Success

• 按照红黑树规则插入即可

Question

After deleting 15 from the red-black tree given in the figure, which one of the following statements must be FALSE?

A.11 is the parent of 17, and 11 is black B.17 is the parent of 11, and 11 is red C.11 is the parent of 17, and 11 is red D.17 is the parent of 11, and 17 is black

Success

• 顶上去的那个节点要变成黑色, 但值得注意的是，交换键值与改变颜色是分两步进行的

Week 3

Question

While accessing a term, hashing is faster than search trees.

Success

• T
• hash的复杂度为\(O(1)\)，使用搜索树则是\(O(\log n)\)的。但是hash表的储存不灵活有缺点。

Question

In distributed indexing, document-partitioned strategy is to store on each node all the documents that contain the terms in a certain range.

Success

• F
• 磁盘分区索引技术，每个节点存放部分索引，不是所有的

Question

When evaluating the performance of data retrieval, it is important to measure the relevancy of the answer set.

Success

• F
• 召回率与相关性无关

Question

Precision is more important than recall when evaluating the explosive detection in airport security.

Success

• F
• 医疗以及安全追求全部发现，召回率更重要。

Question

While accessing a term by hashing in an inverted file index, range searches are expensive.

Success

• T
• 这个是与B+Tree进行比较

Question

When measuring the relevancy of the answer set, if the precision is high but the recall is low, it means that: A.most of the relevant documents are retrieved, but too many irrelevant documents are returned as well B.most of the retrieved documents are relevant, but still a lot of relevant documents are missed C.most of the relevant documents are retrieved, but the benchmark set is not large enough D.most of the retrieved documents are relevant, but the benchmark set is not large enough

Success

• B

Question

Which of the following is NOT concerned for measuring a search engine? A.How fast does it index B.How fast does it search C.How friendly is the interface D.How relevant is the answer set

Success

• C

Question

There are 28000 documents in the database. The statistic data for one query are shown in the following table. The recall is: __

	Relevant	Irrelevant
Retrieved	4000	12000
Not Retrieved	8000	4000

A.14% B.25% C.33% D.50%

Success

• C
• 套公式

Week 4

Question

The result of inserting keys \(1\) to \(2^k−1\) for any \(k>4\) in order into an initially empty skew heap is always a full binary tree.

Success

• T

Question

The right path of a skew heap can be arbitrarily long.

Success

• T

Question

Merge the two leftist heaps in the following figure. Which one of the following statements is FALSE?

A.2 is the root with 11 being its right child B.the depths of 9 and 12 are the same C.21 is the deepest node with 11 being its parent D.the null path length of 4 is less than that of 2

Success

• D

Question

We can perform BuildHeap for leftist heaps by considering each element as a one-node leftist heap, placing all these heaps on a queue, and performing the following step: Until only one heap is on the queue, dequeue two heaps, merge them, and enqueue the result. Which one of the following statements is FALSE?

A. in the \(k\)-th run, \(⌈N/2^k⌉\) leftist heaps are formed, each contains \(2^k\) nodes B.the worst case is when \(N=2^K\) for some integer \(K\) C.the time complexity \(T(N)=O(\frac{N}{2}\log 2^0 + \frac{N}{2^2}\log 2^1 + \frac{N}{2^3} \log 2^2 +⋯+ \frac{N}{2^K}\log 2 ^{K−1})\) for some integer \(K\) so that \(N=2^K\) D.the worst case time complexity of this algorithm is \(Θ(N\log N)\)

Success

• D
• \(N = 2^k\)是多跑一轮的临界点。

Question

Insert keys 1 to 15 in order into an initially empty skew heap. Which one of the following statements is FALSE?

A.the resulting tree is a complete binary tree B.there are 6 leaf nodes C.6 is the left child of 2 D.11 is the right child of 7

Success

• B

Question

Merge the two skew heaps in the following figure. Which one of the following statements is FALSE?

A.15 is the right child of 8 B.14 is the right child of 6 C.1 is the root D.9 is the right child of 3

Success

• A

程序填空

    PriorityQueue Merge( PriorityQueue H1, PriorityQueue H2 ){ 
        if (H1==NULL) return H2;
        if (H2==NULL) return H1;
        if (
        H1->Element > H2->Element
        )
            swap(H1, H2);  //swap H1 and H2
        if ( H1->Left == NULL )
            H1->Left = H2;
        else {
            H1->Right = Merge( H1->Right, H2 );
            if ( H1->Left->Npl < H1->Right->Npl )
            SwapChildren( H1 );  //swap the left child and right child of H1                
            H1->Npl = H1->Right->Npl+1;
        }
        return H1;
    }

Week 5

Question

To implement a binomial queue, the subtrees of a binomial tree are linked in increasing sizes.

Success

• F
• decreasing order

Question

To implement a binomial queue, left-child-next-sibling structure is used to represent each binomial tree.

Success

• T

Question

Which of the following binomial trees can represent a binomial queue of size 42?

Success

• \(2^1 + 2^3 + 2^5 = 42\)

Question

For a binomial queue, __ takes a constant time on average.

A.merging B.find-max C.delete-min D.insertion

Success

• D

Question

Success

• 如果2是4的parent，则说明\(H_1\)的\(B_2\)未参与运算

Question

Question

        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 ( T && X |>=T->Element| ){  /* 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 ( |T->NextSibling| )
            result = Recur_Find(T->NextSibling, X);
        return result;
    }

Week 6

Question

In the Tic-tac-toe game, a "goodness" function of a position is defined as \(f(P)=W_{computer}−W_{human}\)where W is the number of potential wins at position P. In the following figure, O represents the computer and X the human. What is the goodness of the position of the figure?

A. -1 B. 0 C. 4 D. 5

X	O	X
X	X	X
O	X	X

O	O	O
O	X	X
O	O	O

Success

• B
• 把空的都填上，看有几种赢法

Question

Given the following game tree, the red node will be pruned with \(α-β\) pruning algorithm if and only if __.

Week 7

Question

When solving a problem with input size \(N\) by divide and conquer, if at each stage the problem is divided into \(8\) sub-problems of equal size \(N/3\), and the conquer step takes \(O(N^ 2 \log N)\) to form the solution from the sub-solutions, then the overall time complexity is __

Success

• \(O(N^2 \log N)\)

Week 8

Minterm summary

Question

Success

• 应该是\(O(\log N)\)

Question

Success

• 还真有

Question

一道考察对ppt熟悉程度的程序填空

    BinQueue DeleteRoot( BinQueue H, int Ind )
    {
        BinTree OldRoot, SubTree;
        BinQueue NewBinQ;
        int i;

        OldRoot = H->TheTrees[Ind];
        SubTree = OldRoot->LeftChild;
        free(OldRoot);
        NewBinQ = Initialize();
        NewBinQ->CurrentSize = |2^Ind - 1| ;
        for (|i = Ind-1; i >= 0; i--|) {
            NewBinQ->TheTrees[i] = SubTree;
            SubTree = SubTree->NextSibling;
            NewBinQ->TheTrees[i]->NextSibling = NULL;
        }
        return NewBinQ;
    }

Question

    static int order = DEFAULT_ORDER;
    typedef struct BpTreeNode BpTreeNode;
    struct BpTreeNode {
        BpTreeNode** childrens;  /* Pointers to childrens. This field is not used by leaf nodes. */
        ElementType* keys;
        BpTreeNode* parent;
        bool isLeaf;  /* 1 if this node is a leaf, or 0 if not */
        int numKeys;  /* This field is used to keep track of the number of valid keys. 
        In an internal node, the number of valid pointers is always numKeys + 1. */
    };

bool FindKey(BpTreeNode * const root, ElementType key){
    if (root == NULL) {
            return false;
    }
    int i = 0;
    BpTreeNode * node = root;
    while (|!node->isLeaf|) {
        i = 0;
        while (i < node->numKeys) {
            if (|key>=node->keys[i]|) i++;
            else break;
        }
        node = node->childrens[i];
    }
    for(i = 0; i < node->numKeys; i++){
        if(node->keys[i] == key)
            return true;
    }
    return false;
}

```

Question

Question

​

评论