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

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

The best case time complexity of sorting algorithms based only on comparisons is at least O(NlogN)O(NlogN). (2分)

       

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

To sort NN records, heap sort requires at least O(N)O(N) extra space. (2分)

       

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

If a complete binary tree with 137 nodes is stored in an array (root at position 1), then the nodes at positions 127 and 128 are at the same level. (2分)

       

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

If in a directed graph, every vertex is part of some cycle, then the graph must be strongly connected. (2分)

       

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

For the following piece of code

if ( A > B ){     
  for ( i=0; i<N*2; i++ )         
    for ( j=N*N; j>i; j-- )             
      C += A; 
}
else {     
  for ( i=0; i<N*N/2; i++ )         
    for ( j=N; j>i; j-- ) 
      for ( k=0; k<N*100; k++)
        C += B; 
} 

the lowest upper bound of the time complexity is O(N5)O(N^5). (2分)

       

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

Prim's algorithm is to grow the minimum spanning tree by adding one edge, and thus an associated vertex, to the tree in each stage. (2分)

       

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

An algorithm to check for balancing symbols in an expression uses a queue to store the partial expression. (2分)

       

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

If X and Y are both leaf nodes in a binary tree, then there exists a binary tree with preorder traversal sequence ...X...Y... and postorder traversal sequence ...Y...X.... (2分)

       

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

Given a hash table with size 13. If only the positions with odd (奇数) indices are occupied (the index starts from 0), then when the quadratic probing is used, insertion of a new key into this hash table can be successful. (2分)

       

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

Given two sorted lists L1L1 and L2L2, the fastest algorithm for computing L1L2L1\bigcup L2 has time complexity Θ(N2)\Theta(N^2). (2分)

       

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

To sort NN records iteratively by merge sort, the number of runs is: (2分)

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

Insert 6 keys {23, 80, 95, 90, 82, 76} into an initially empty binary search tree. Suppose that the structure of the resulting tree is given in the figure. Which one of the followings is the possible sequence of insertions? (4分)

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

Insert {6, 15, 3, 9, 7, 4, 12, 10, 15, 14, 5, 13} into an initially empty binary min-heap one at a time. After performing three DeleteMin operations, and then inserting 8 and 11 into the heap, the top element of the heap must be __ . (2分)

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

Given a binary tree with 100 leaves and without 1-degree nodes, the number of nodes in the tree is __ . (3分)

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

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? (3分)

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

The array representation of the disjoint sets is given by {2, –4, 2, 3, -3, 5, 6, 9, -2}. Keep in mind that the elements are numbered from 1 to 9. After invoking Union(Find(4), Find(6)) with union-by-size, which elements will be changed in the resulting array? (3分)

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

If a DFS sequence of a graph is {V2, V0, V4, V3, V1}, then which one of the following can NOT possibly be the corresponding graph? (3分)

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

Which of the following statements is TRUE about topological sorting? (3分)

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

How many distinct topological sequences are there in the following DAG?(2分)

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

Let A and B be the two distinct nodes in a binary tree. A will be visited before B in the inorder traversal if __(3分)

Note: Let R be the nearest common ancestor of A and B. "A is on the right (or left) of B" means that A is in the right (or left) subtree of R and B in the left (or right) subtree of R.

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

Given a hash table of size 13 and the hash function h(x)=x mod 13. Assume that quadratic probing is used to solve collisions. After filling in the hash table one by one with input sequence {2, 15, 3, 29, 6, 25, 33, 7}, which number is placed in the position of index 7? (3分)

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

Insert {5, 6, 7, 2, 4, 3} one by one into an initially empty binary search tree. The postorder traversal sequence of the resulting tree is _ (3分)

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

Given the adjacency list of a directed graph as shown by the figure. There is(are) __ strongly connected component(s). (3分)

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

Given an empty stack S and an empty queue Q. Push elements {1, 2, 3, 4, 5, 6, 7} one by one onto S. If each element that is popped from S is enqueued onto Q immediately, and if the dequeue sequence is {3, 2, 6, 5, 7, 4, 1}, then the minimum size of S must be: (3分)

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

The maximum flow in the network of the given Figure is: (4分)

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

Use Dijkstra's algorithm to find the shortest paths from vertex a to other vertices. In which order that the results must be obtained?(4分)

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

If the preorder and the postorder traversal sequences of a binary tree have exactly the opposite order, which of the followings is TRUE about the tree? (3分)

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

Which of the following statements is FALSE about the shortest path algorithms? (3分)

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

Given the following four algorithms with their runtimes for problem size 100 and their time complexities:

Algorithm Runtime Time Complexity
A 100 O(N)O(N)
B 50 O(N2)O(N^2)
C 25 O(N3)O(N^3)
D 10 O(N4)O(N^4)

Which algorithm is the fastest for problem size 200? (3分)

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

Given a weighted graph as shown by the figure. Which one of the following statements is TRUE about its minimum spanning tree? (3分)

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

The function is to find the K-th largest element in a list A of N elements. The initial function call is Qselect(A, K, 0, N-1). Please complete the following program.

ElementType Qselect( ElementType A[], int K, int Left, int Right )
{
    ElementType Pivot = A[Left];
    int L = Left, R = Right+1;

    while (1) {
        while ( A[++L] > Pivot ) ;
        (3分);
        if ( L < R ) Swap( &A[L], &A[R] );
        else break;
    }
    Swap( &A[Left], &A[R] );
    if ( K < (L-Left) )
        return Qselect(A, K, Left, R-1);
    else if ( K > (L-Left) )
        (3分);
    else
        return Pivot;
}
评测结果:部分正确(3 分)
序号结果得分
0答案正确3
1答案错误0
5-2

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

ElementType FindKthLargest ( 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];
    BuildMinHeap(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];
}

评测结果:部分正确(3 分)
序号结果得分
0答案错误0
1答案正确3
函数题总分:8得分:8
6-1
LCA in BST

The lowest common ancestor (LCA) of two nodes u and v in a tree T is the deepest node that has both u and v as descendants. Given any two nodes in a binary search tree (BST), you are supposed to find their LCA.

Format of function:

int LCA( Tree T, int u, int v );

where Tree is defined as the following:

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

The function LCA is supposed to return the key value of the LCA of u and v in T. In case that either u or v is not found in T, return ERROR instead.

Sample program of judge:

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

#define ERROR -1
typedef struct TreeNode *Tree;
struct TreeNode {
    int   Key;
    Tree  Left;
    Tree  Right;
};

Tree BuildTree(); /* details omitted */
int LCA( Tree T,  int u, int v );

int main()
{
    Tree T;
    int u, v, ans;

    T = BuildTree();
    scanf("%d %d", &u, &v);
    ans = LCA(T, u, v);
    if ( ans == ERROR ) printf("Wrong input\n");
    else printf("LCA = %d\n", ans);

    return 0;
}

/* Your function will be put here */

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

2 7

Sample Output 1:

LCA = 6

Sample Input 2 (for the same tree in Sample 1):

1 9

Sample Output 2:

Wrong input
代码
int a[1000],now=0;
void make(Tree T){
    if(T==NULL)return;
    make(T->Left);
    a[now++]=T->Key;
    make(T->Right);
}
int LCA( Tree T, int u, int v ){
    make(T);
    int i,flag1=0,flag2=0;
    for(i=0;i<now;i++){
        if(a[i]==u)flag1=1;
        if(a[i]==v)flag2=1;
    }
    if(flag1==0||flag2==0)return ERROR;
    if(T==NULL)return ERROR;
    if(u<=T->Key&&v>=T->Key)return T->Key;
    if(u>=T->Key&&v<=T->Key)return T->Key;
    if(u<T->Key&&v<T->Key)return LCA(T->Left,u,v);
    if(u>T->Key&&v>T->Key)return LCA(T->Right,u,v);
    else return ERROR;
}
评测结果:答案正确(8 分)
测试点结果得分耗时内存
0答案正确12 ms256 KB
1答案正确13 ms384 KB
2答案正确12 ms256 KB
3答案正确12 ms256 KB
4答案正确13 ms256 KB
5答案正确13 ms256 KB
6答案正确12 ms256 KB
7答案正确12 ms256 KB
a.c: In function ‘BuildTree’:
a.c:35:6: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
      scanf("%d", &n);
      ^~~~~~~~~~~~~~~
a.c:37: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:51:5: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &u, &v);
     ^~~~~~~~~~~~~~~~~~~~~~