浙江大学2018-19秋冬《数据结构基础》期中模拟练习
开始时间1/1/2016, 12:00:00 AM
结束时间1/18/2038, 12:00:00 AM
答题时长90分钟
考生-
得分92
总分100

判断题总分:15得分:15
1-1

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分)

       

评测结果:答案正确(3 分)
1-2

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

       

评测结果:答案正确(3 分)
1-3

NlogN2NlogN^2 and NlogNNlogN have the same speed of growth. (3分)

       

评测结果:答案正确(3 分)
1-4

For a sequentially stored linear list of length NN, the time complexities for deleting the first element and inserting the last element are O(1)O(1) and O(N)O(N), respectively. (3分)

       

评测结果:答案正确(3 分)
1-5

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分)

       

评测结果:答案正确(3 分)
单选题总分:64得分:59
2-1

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

  • P1: T(1)=1T(1)=1, T(N)=T(N/2)+1T(N)=T(N/2)+1;
  • P2: T(1)=1T(1)=1, T(N)=2T(N/2)+1T(N)=2T(N/2)+1;

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

评测结果:答案正确(5 分)
2-2

For the quicksort implementation with neither the left nor the right pointer stops 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? (5分)

评测结果:答案正确(5 分)
2-3

To sort { 8, 3, 9, 11, 2, 1, 4, 7, 5, 10, 6 } by Shell Sort, if we obtain ( 4, 2, 1, 8, 3, 5, 10, 6, 9, 11, 7 ) after the first run, and ( 1, 2, 3, 5, 4, 6, 7, 8, 9, 11, 10 ) after the second run, then the increments of these two runs must be __ , respectively. (5分)

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

To insert s after p in a doubly linked circular list, we must do: (5分)

评测结果:答案正确(5 分)
2-5

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

评测结果:答案正确(5 分)
2-6

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分)

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

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

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

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

Suppose that an array of size m is used to store a circular queue. If the head pointer front and the current size variable size are used to represent the range of the queue instead of front and rear, then the maximum capacity of this queue can be: (5分)

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

Given input { 4321, 56, 57, 46, 289, 17, 331, 33, 234, 63 }. Which one of the following is the result after the 1st run of the Least Signification Digit (LSD) radix sort? (5分)

评测结果:答案正确(5 分)
2-11

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分)

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

How many leaf node does a complete binary tree with 2435 nodes have? (5分)

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

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分)

评测结果:答案正确(5 分)
程序填空题总分:15得分:12
5-1

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]);
      }
   }
} 
评测结果:部分正确(6 分)
序号结果得分
0答案错误0
1答案正确3
2答案正确3
5-2

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

评测结果:答案正确(6 分)
序号结果得分
0答案正确3
1答案正确3
函数题总分:6得分:6
6-1
No Greater Than X in BST

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

Format of function:

void Print_NGT( 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_NGT( Tree T,  int X );

int main()
{
    Tree T;
    int X;

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

    return 0;
}

/* Your function will be put here */

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

91 90 85 81 80 55 End

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

End
代码
/*#include <stdio.h>
#include <stdlib.h>

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

Tree BuildTree(); 
void Output( int X ); 

void Print_NGT( Tree T,  int X );

int main()
{
    Tree T;
    int X;

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

    return 0;
}

 Your function will be put here */

int a[1000] = {0}, st = -1;

int cmp(const void *a, const void *b) {
    return *(int *)b - *(int *)a;
}

void Tr(Tree T, int X) {
    if (T) {
        if (T->Element <= X) {
            a[++st] = T->Element;
        }

        Tr(T->Left, X);
        Tr(T->Right, X);
    }
}

void Print_NGT( Tree T,  int X ) {
    Tr(T, X);
    qsort(a, st+1, sizeof(int), cmp);
    for (int i = 0; i<=st; i++) {
        Output(a[i]);
    }
}
评测结果:答案正确(6 分)
测试点结果得分耗时内存
0答案正确23 ms256 KB
1答案正确14 ms256 KB
2答案正确14 ms256 KB
3答案正确13 ms256 KB
4答案正确14 ms256 KB
a.c: In function ‘BuildTree’:
a.c:33:6: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
      scanf("%d", &n);
      ^~~~~~~~~~~~~~~
a.c:35:10: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
          scanf("%d", &x);
          ^~~~~~~~~~~~~~~
a.c: In function ‘main’:
a.c:52:5: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &X);
     ^~~~~~~~~~~~~~~