If there are less than 20 inversions in an integer array, then Insertion Sort will be the best method among Quick Sort, Heap Sort and Insertion Sort. (3分)

For a sequentially stored linear list of length $NN$, the time complexities for query and insertion are $O\left(1\right)O(1)$ and $O\left(N\right)O(N)$, respectively. (3分)

In a binary search tree, the keys on the same level from left to right must be in sorted (non-decreasing) order. (3分)

$N^{2}logNN^2\; logN$ and $Nlog{N}^{2}N\; logN^2$ have the same speed of growth. (3分)

If keys are pushed onto a stack in the order {1, 2, 3, 4, 5}, then it is impossible to obtain the output sequence {3, 4, 1, 2, 5}. (3分)

For the quicksort implementation with the left pointer stops at an element with the same key as the pivot during the partitioning, but the right pointer does not stop in a similar case, what is the running time when all keys are equal? (5分)

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

Given a quadtree(四叉树) with 3 nodes of degree 2, 2 nodes of degree 3, 4 nodes of degree 4. The number of leaf nodes in this tree is __. (5分)

1. 10
2. 12
3. 20
4. 21

The result of performing three DeleteMin operations in the min-heap {1,3,2,6,7,5,4,15,14,12,9,10,11,13,8} is: (5分)

1. 4,5,6,7,8,9,10,11,12,13,14,15
2. 4,6,5,13,7,10,8,15,14,12,9,11
3. 4,6,5,12,7,10,8,15,14,9,13,11
4. 4,5,6,12,7,10,8,15,14,13,9,11

Given input { 110, 119, 7, 911, 114, 120, 122 }. Which one of the following is the result after the 2nd run of the Least Signification Digit (LSD) radix sort? (5分)

1. 7, 110, 119, 114, 911, 120, 122
2. 7, 110, 119, 114, 911, 122, 120
3. 7, 110, 911, 114, 119, 120, 122
4. 110, 120, 911, 122, 114, 7, 119

The recurrent equations for the time complexities of programs P1 and P2 are:

• P1: $T\left(1\right)=1T(1)=1$, $T\left(N\right)=T\left(N\mathrm{/}2\right)+1T(N)=T(N/2)+1$;
• P2: $T\left(1\right)=1T(1)=1$, $T\left(N\right)=2T\left(N\mathrm{/}2\right)+1T(N)=2T(N/2)+1$;

Then the correct conclusion about their time complexities is: (5分)

1. they are both $O\left(logN\right)O(logN)$
2. $O\left(logN\right)O(logN)$ for P1, and $O\left(N\right)O(N)$ for P2
3. they are both $O\left(N\right)O(N)$
4. $O\left(logN\right)O(logN)$ for P1, and $O\left(NlogN\right)O(NlogN)$ for P2

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

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

Suppose that an array of size m is used to store a circular queue. If the front position is front and the current size is size, then the rear element must be at: (5分)

1. front+size
2. front+size-1
3. (front+size)%m
4. (front+size-1)%m

To sort { 49, 38, 65, 97, 76, 13, 27, 50 } in increasing order, which of the following is the result after the 1st run of Shell sort with the initial increment 4? (5分)

1. 13,27,38,49,50,65,76,97
2. 49,13,27,50,76,38,65,97
3. 49,76,65,13,27,50,97,38
4. 97,76,65,50,49,38,27,13

Insert { 3, 8, 9, 1, 2, 6 } one by one into an initially empty binary search tree. The post-order traversal sequence of the resulting tree is: (5分)

1. 2, 1, 3, 6, 9, 8
2. 1, 2, 8, 6, 9, 3
3. 2, 1, 6, 9, 8, 3
4. 1, 2, 3, 6, 9, 8

In-order traversal of a binary tree can be done iteratively. Given the stack operation sequence as the following:

push(1), push(2), push(3), pop(), push(4), pop(), pop(), push(5), pop(), pop(), push(6), pop()

Which one of the following statements is TRUE? (5分)

1. 6 is the root
2. 2 is the parent of 4
3. 2 and 6 are siblings
4. None of the above

Among the following sorting methods, which ones will be slowed down if we store the elements in a linked structure instead of a sequential structure? (5分)

1. Insertion sort; 2. Selection Sort; 3. Bubble sort; 4. Shell sort; 5. Heap sort

1. 1 and 2 only
2. 2 and 3 only
3. 3 and 4 only
4. 4 and 5 only

In a complete binary tree with 1102 nodes, there must be __ leaf nodes. (5分)

1. 79
2. 551
3. 1063
4. cannot be determined

To delete p from a doubly linked list, we must do: (5分)

1. p->prior=p->prior->prior; p->prior->next=p;
2. p->next->prior=p; p->next=p->next->next;
3. p->prior->next=p->next; p->next->prior=p->prior;
4. p->next=p->prior->prior; p->prior=p->next->next;

The function is to sort the list { r[1] … r[n] } in non-decreasing order. Unlike selection sort which places only the minimum unsorted element in its correct position, this algorithm finds both the minimum and the maximum unsorted elements and places them into their final positions.

void  sort( list r[], int n )  
{
   int i, j, mini, maxi;

   for (i=1; i<n-i+1; i++) {
      mini = maxi = i;
      for( j=i+1; (3分); ++j ){
         if( (3分) ) mini = j; 
         else if(r[j]->key > r[maxi]->key) maxi = j;
      }
      if( mini != i ) swap(&r[mini], &r[i]);
      if( maxi != n-i+1 ){
         if( (3分) ) swap(&r[mini], &r[n-i+1]);
         else swap(&r[maxi], &r[n-i+1]);
      }
   }
} 

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];
}

You are supposed to output, in decreasing order, all the elements no less than X in a binary search tree T.

Format of function:

void Print_NLT( Tree T,  int X );

where Tree is defined as the following:

typedef struct TreeNode *Tree;
struct TreeNode {
    int Element;
    Tree  Left;
    Tree  Right;
};

The function is supposed to use Output(X) to print X.

Sample program of judge:

#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode *Tree;
struct TreeNode {
    int Element;
    Tree  Left;
    Tree  Right;
};

Tree BuildTree(); /* details omitted */
void Output( int X ); /* details omitted */

void Print_NLT( Tree T,  int X );

int main()
{
    Tree T;
    int X;

    T = BuildTree();
    scanf("%d", &X);
    Print_NLT( T, X );
    printf("End\n");

    return 0;
}

/* Your function will be put here */

Sample Output 1 (for the tree shown in Figure 1):

92 91 90 85 81 80 End

Figure 1

Sample Output 2 (for the tree shown in Figure 2):

End

Figure 2