Given a binary search tree with 20 integer keys which include 4, 5, and 6, if 4 and 6 are on the same level, then 5 must be their parent. (2分)

If $N$ numbers are stored in a singly linked list in increasing order, then the average time complexity for binary search is $O(logN)$. (2分)

If the preorder and the postorder traversal sequences of a binary tree have exactly the opposite orders, then none of the nodes in the tree has two subtrees. (2分)

Quadratic probing is equivalent to double hashing with a secondary hash function of $Hash_2(k) = k$. (2分)

For a graph, if each vertex has an even degree, we can find an Euler circuit that visits every vertex exactly once. (2分)

If keys are pushed onto a stack in the order abcde, then it's impossible to obtain the output sequence cedab. (2分)

Let P be the shortest path from S to T. If the weight of every edge in the graph is incremented by 1, P will still be the shortest path from S to T. (2分)

Mergesort is stable. (2分)

To sort $N$ records by quick sort, the worst-case time complexity is $O(NlogN)$. (2分)

$(logN)^3$ is $O(N)$. (2分)

It is known that a 3-heap is a heap whose nodes have 3 children. Suppose that the level-order traversal sequence of a max-3-heap is {88, 76, 65, 82, 68, 46, 52, 44, 62, 33, 75, 28, 55, 60}. Use the linear algorithm to adjust this max-3-heap into a min-3-heap, and then run DeleteMin. As a result, there are __ nodes whose positions are not moved in the process. (3分)

1. 2
2. 3
3. 4
4. 5

Given input { 46, 79, 56, 38, 40, 84 }. Which one of the following is the initial heap built by heap sort? (3分)

1. 79, 46, 56, 38, 40, 80
2. 84, 79, 56, 46, 40, 38
3. 84, 56, 79, 40, 46, 38
4. 84, 79, 56, 38, 40, 46

Suppose that the size of a hash table is 11, and the hash function is H(key)=key%11. The following 4 elements have been inserted into the table as Addr(14)=3, Addr(38)=5, Addr(61)=6, Addr(86)=9. When open addressing with quadratic probing is used to solve collisions, the address of the element with key=60 will be . (3分)

1. 5
2. 7
3. 8
4. 10

Which one of the following is a possible postorder traversal sequence of a binary search tree? (3分)

1. 2 4 1 5 3 7 9 10 8 6
2. 2 4 1 5 3 7 10 9 8 6
3. 2 1 4 5 3 7 10 9 8 6
4. 2 1 4 5 3 10 7 9 8 6

Given the structure of a binary search tree (as shown in the figure), which one of the following insertion sequences is impossible? (3分)

1. 83 67 91 98 20 75
2. 83 67 75 91 20 98
3. 83 91 75 67 20 98
4. 83 91 98 67 75 20

Given a tree of degree 6. Suppose that the numbers of nodes of degrees 1, 2, 3, 4, 5, 6 are 3, 5, 3, 4, 2, 1, respectively. Then the number of leaf nodes must be: (3分)

1. 35
2. 31
3. 33
4. 37

For the quicksort implementation with both the left and the right pointers stop when an element with the same key as the pivot is found during the partitioning, what is the running time when all keys are equal? (3分)

1. $O(logN)$
2. $O(N)$
3. $O(NlogN)$
4. $O(N^2)$

Which one of the following is the expression tree corresponding to the postfix expression aef*+bc*+? (3分)

For an in-order threaded binary tree, if the pre-order and in-order traversal sequences are D A B C F E and B A C D E F respectively, which pair of nodes' right links are both threads? (3分)

1. D and A
2. A and F
3. B and A
4. B and E

The inorder and the postorder traversal sequences of a binary tree are a b c d e f g and a c b g f e d, respectively. Then the preorder traversal sequences is: (3分)

1. d b a c f e g
2. d b a c e f g
3. d a c b f e g
4. d c a b e f g

The maximum flow from v1 to v6 is __: (3分)

1. 11
2. 12
3. 13
4. 0

The following is the part of depth-first search tree to find the articulation points, and the Num(v) value has been marked beside each vertex v. The back edges are not shown. Which of the following situation is impossible? (3分)

1. low(v3) is equaled to low(v5)
2. low(v5) is greater than low(v7)
3. low(v7) is 2
4. low(v4) is 1

A graph with 100 vertices and 12 edges must have at most __ connected component(s). (3分)

1. 87
2. 88
3. 94
4. 95

Use Dijkstra algorithm to find the shortest paths from 1 to every other vertices. In which order that the destinations must be obtained? (3分)

1. 2, 5, 3, 4, 6, 7
2. 2, 4, 3, 6, 5, 7
3. 2, 3, 4, 5, 6, 7
4. 5, 2, 6, 3, 4, 7

Insert {18, 23, 4, 26, 31, 33, 17, 39} one by one into an initially empty hash table of size 13 with the hash function $H(Key) = Key\%13$, and linear probing is used to resolve collisions. What is the loading density when the first collision occurs? (3分)

1. 0.54
2. 0.63
3. 0.31
4. 0.62

Following is the C-like pseudo code of a function that takes a Queue as an argument.

void foo(Queue Q)
{
    Stack S = CreateStack();  // create an empty stack

    while (!IsEmpty(Q))
    {
        // dequeue an item from Q and push it into S
        Push(S, Dequeue(Q));
    }

    while (!IsEmpty(S))
    {
        // pop an item from S and enqueue it into Q
        Enqueue(Q, Pop(S));
    }
		
    DisposeStack(S);
}

What does the above function do? (3分)

1. Removes the last item from Q
2. Keeps Q unchanged
3. Makes Q empty
4. Reverses Q

In order to convert the infix expression 4 * 3 + (6 * 3 - 12) to postfix expression using a stack $S$, then the minimum size of $S$ must be: (3分)

1. 2
2. 3
3. 4
4. 5

To find the minimum spanning tree with Prim's algorithm for the following graph, a sequence of vertexes 6, 1, 2, 3 was found during the algorithm's early steps. Which one vertex will be added in the next step? (3分)

1. 0
2. 4
3. 5
4. the vertex serial is incorrect

Let $T$ be a tree of $N$ nodes created by union-by-size without path compression, then the minimum depth of $T$ may be (3分)

1. 1
2. $logN$
3. $N-1$
4. $N/2$

When inserting a new key K into a binary search tree T with 511 nodes, the worst-case number of comparisons between K and the keys already in T is in the range of: (3分)

1. [10, 511]
2. [9, 511]
3. [9, 512]
4. [10, 512]

The function is to find the K-th smallest element in a list A of N elements. The function BuildMaxHeap(H, K) is to arrange elements H[1] ... H[K] into a max-heap. Please complete the following program.

ElementType FindKthSmallest ( int A[], int N, int K )
{   /* it is assumed that K<=N */
    ElementType *H;
    int i, next, child;

    H = (ElementType *)malloc((K+1)*sizeof(ElementType));
    for ( i=1; i<=K; i++ ) H[i] = A[i-1];
    BuildMaxHeap(H, K);

    for ( next=K; next<N; next++ ) {
        H[0] = A[next];
        if ( H[0] < H[1] ) {
            for ( i=1; i*2<=K; i=child ) {
                child = i*2;
                if ( child!=K && (3分) ) child++;
                if ( (3分) )
                    H[i] = H[child];
                else break;
            }
            H[i] = H[0];
        }
    }
    return H[1];
}

Given an array a[]of n integers, the function MissingMin is to find and return the minimum positive integer which is NOT in the array. For example, given { 3, -1, 8, 1, 0 }, 2 is the smallest positive integer which is missing.

int MissingMin( int a[], int n )
{
    int i, j, min, missing=1;
		
    for( i=0; i<n; i++ ){
        min = i;
        for( j = i+1; j < n; j++ )
            if ((3分))  min = j;	
        if ( min != i )  swap(a[i], a[min]);
        if ( a[i] == missing )  missing++;
        else if ( a[i] > missing )  (3分);
    }
    return missing;
}