编程题每个人都不一样，就不放了。

判断题

1-1 对N个不同的数据采用冒泡排序进行从大到小的排序，当元素基本有序时交换元素次数肯定最多。 (2分)

1-2 在一个有向图中，所有顶点的入度与出度之和等于所有边之和的2倍。 (2分)

1-3 若用平方探测法解决冲突，则插入新元素时，若散列表容量为质数，插入就一定可以成功。 (2分)

1-4NlogN

²

和NlogN具有相同的增长速度。 (2分)

这道题我错了，没看清，应该是T

1-5 若一棵平衡二叉树的所有非叶结点的平衡因子都是0，则其必为完美二叉树。(2分)

单选题

2-1 给定有权无向图的邻接矩阵如下，其最小生成树的总权重是： (4分)

2-2 给定输入序列 {4371, 1323, 6173, 4199, 4344, 9679, 1989} 以及散列函数 h(X)=X%10。如果用大小为10的散列表，并且用分离链接法解决冲突，则输入各项经散列后在表中的下标为：（-1表示相应的插入无法成功）(4分)

2-3 在图中自d点开始进行深度优先遍历算法可能得到的结果为： (2分)

2-4 在并查集问题中，已知集合元素0~8所以对应的父结点编号值分别是{ 1, -4, 1, 1, -3, 4, 4, 8, -2 }（注：−n表示树根且对应集合大小为n），那么将元素6和8所在的集合合并（要求必须将小集合并到大集合）后，该集合对应的树根和父结点编号值分别是多少？ (4分)

2-5 数据结构中Dijkstra算法用来解决哪个问题？ (2分)

2-6 对一组数据{ 2，12，16，88，5，10 }进行排序，若前三趟排序结果如下： 第一趟排序结果：2，12，16，5，10，88 第二趟排序结果：2，12，5，10，16，88 第三趟排序结果：2，5，10，12，16，88 则采用的排序方法可能是： (2分)

2-7 给出关键字序列{ 4321, 56, 57, 46, 28, 7, 331, 33, 234, 63 }，下面哪个选择是按次位优先（LSD）链式基数排序进行了一趟分配和收集的结果？ (2分)

2-8 在一个有权无向图中，如果顶点b到顶点a的最短路径长度是10，顶点c与顶点b之间存在一条长度为3的边。那么下列说法中有几句是正确的？ (4分)

• c与a的最短路径长度就是13
• c与a的最短路径长度就是7
• c与a的最短路径长度不超过13
• c与a的最短路径不小于7

2-9 设一个栈的输入序列是1、2、3、4、5，则下列序列中，是栈的合法输出序列的是？ (4分)

2-10 对于序列{ 49，38，65，97，76，13，27，50 }，按由小到大进行排序，下面哪一个是初始步长为4的希尔排序法第一趟的结果？ (4分)

2-11要判断一个整数N（>10）是否素数，我们需要检查3到



N

\sqrt{N}














N












​














​之间是否存在奇数可以整除N。则这个算法的时间复杂度是：(2分)

2-12 给定一有向图的邻接表如下。若从v1开始利用此邻接表做广度优先搜索得到的顶点序列为：{v1, v3, v2, v4, v5}，则该邻接表中顺序填空的结果应为： (2分)

2-13 将1~6这6个键值插到一棵初始为空的二叉搜索树中。如果插入完成后，搜索树结构如图所示，问：可能的插入序列是什么？ (2分)

2-14 设栈S和队列Q的初始状态均为空，元素{1, 2, 3, 4, 5, 6, 7}依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是{2, 5, 6, 4, 7, 3, 1}，则栈S的容量至少是： (2分)

2-15 将 { 10, 12, 1, 14, 6, 5, 8, 15, 3, 9, 7 } 逐个按顺序插入到初始为空的最小堆中，然后连续执行两次删除最小元素操作（DeleteMin），再插入4，16，此后堆顶的元素是什么？ (4分)

2-16 将 9, 8, 7, 2, 3, 5, 6, 4 顺序插入一棵初始为空的AVL树。下列句子中哪句是错的？ (4分)

2-17给定散列表大小为17，散列函数为H(Key)=Key%17。采用平方探测法处理冲突：h<sub​>i(k)=(H(k)±i

²

)%17将关键字序列{ 23, 22, 7, 26, 9, 6 }依次插入到散列表中。那么元素6存放在散列表中的位置是：(4分)

2-18 如果循环队列用大小为m的数组表示，队头位置为front、队列元素个数为size，那么队尾元素位置rear为： (2分)

2-19 哈夫曼树是n个带权叶子结点构成的所有二叉树中（）最小的二叉树。 (2分)

2-20 给定二叉树如下图所示。设N代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。若遍历后的结点序列为3、1、7、5、6、2、4，则其遍历方式是： (2分)

2-21 在拓扑排序算法中用堆栈和用队列产生的结果会不同吗？(2分)

2-22 设最小堆（小根堆）的层序遍历结果为{5, 18, 15, 28, 22, 42, 40}。用线性时间复杂度的算法将该堆调整为最大堆（大根堆），则该树的中序遍历结果为：(4分)

程序填空题

5-1 本函数的功能是从有N个元素的线性表A中查找第K小的元素。其中函数BuildMaxHeap(H, K)是将元素H[1] … H[K]调整为一个最大堆。请完成下列填空。

1.

H[child+1]>H[child]


2.

H[child]>H[0]


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 && H[child+1]>H[child] ) child++;
                if ( H[child]>H[0] )
                    H[i] = H[child];
                else break;
            }
            H[i] = H[0];
        }
    }
    return H[1];
}

5-2 The function is to do topological sort on a graph G. TopNum[] starts counting from 1.

1.

++counter


2.

--Indegree[W]


void Topsort( Graph G )
{
   Queue Q;
   Vertex V, W;
   NodePtr ptr;
   int counter = 0;

   Q = CreateEmptyQueue(NumVertex);
   for ( V=0; V<G->NumV; V++ )
      if ( Indegree[V] == 0 )
         Enqueue(V, Q);
   while ( !IsEmpty(Q) ){
      V = Dequeue( Q );
      TopNum[V] = ++counter;
      for ( ptr=G->List[V]; ptr; ptr=ptr->Next) {
         W = ptr->Vertex;
         if ( --Indegree[W] == 0 )
            Enqueue(W, Q);
      }
   }
   if ( counter != NumVertex )
      printf("ERROR: Graph has a cycle.\n");
   DisposeQueue(Q);
}