考生注意：所有答案必须写在答题纸（卷）上，写在本试题上一律不给分。 

一、 单项选择题(每题2分，共30分)   

1. 一个队列的入列序列是1,2,3,4, 则队列的输出序列是（    ）。

A. 4,3,2,1           B. 1,2,3,4        C. 1,4,3,2        D. 3,2,4,1

2. 循环队列用数组A[0..m-1]存放其元素值，已知其头尾指针分别是front和rear, 则当前队列中的元素个数是(      )。

A. (rear-front+m)%m  B. rear-front+1   C. rear-front-1   D. rear-front

3. 平衡二叉树的平均查找长度是(     )。

    A.   O(n2）          B. O(nlog2n）     C.   O(n）      D.  O(log2n）

4. 设F是由T1、T2和T3三棵树组成的森林，与F对应的二叉树为B，T1、T2和T3的结点数分别为N1、N2和N3，则二叉树B的根结点的左子树的结点数为（     ）。

   A. N1-1      B. N2-1        C. N2+N3     D. N1+N3

5. 计算机内部数据处理的基本单元是（     ）。

  A. 数据             B. 数据元素       C. 数据项      D. 数据库

6. 设按照从上到下、从左到右的顺序从1开始对完全二叉树的结点进行顺序编号，则编号为i结点的左孩子结点的编号为（     ）。

 A. 2i+1      B. 2i         C.  i/2         D.  2i-1

7. 设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的入度为（     ）。

 A. 第i行非0元素的个数之和 B. 第i列非0元素的个数之和

 C. 第i行0元素的个数之和 D. 第i列0元素的个数之和

8. 设一组初始记录关键字序列为(16, 25,12, 30,47,11, 23,36, 9,18,31)，则以增量d=5的一趟希尔排序结束后的结果为（     ）。

A. 11, 23,12, 9, 18,16, 25,36,30, 47, 31  B. 11, 23,12, 9, 16, 18, 25,36, 47, 30, 31

C. 16, 23,12, 9, 11,18, 25,36,30, 47, 31  C. 9, 11,12, 16, 18, 23, 25,30, 36, 47, 31

9.  设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有（    ）条有向边。

 A. n B. n-1 C. m D. m-1

10. 设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（      ）个空指针域。

 A. 2m-1 B. 2m C. 2m+1 D. 4m

11. 对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H(K)=K %9作为散列函数，则散列地址为1的元素有（    ）个。

    A． 1         B． 2          C． 3          D． 4

12. 下面程序的时间复杂为（     ）。

for（i=1，s=0； i<=n； i++） { t=1； for(j=1；j<=i；j++) { t=t*j；s=s+t；} }

  A． O(n) B.  O(n2) C.  O(n3) D.  O(n4)

13. 对于一个具有n个顶点的无向连通图，它包含的连通分量的个数为(     )。      

A． 0          B．1          C． n          D． n+1

14. 设无向图G中边的集合E={(a,b)，(a,e)，(a,c)，(b,e)，(e,d)，(d,f)，(f,c)}，则从顶点a出发进行深度优先遍历可以得到的一种顶点序列为（      ）。

A.   aebcfd B.   acfebd C.  aedfcb D.  aedfbc

15.设指针变量p指向双向链表中结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X的操作序列为（     ）。

A.  p->next=s；s->prior=p； p->next->prior=s； s->prior=p->nest；

B. s->prior=p;  s->next = p->next; p->next=s; s->next->prior=s;

  C. p->prior=s；p->nest->prior=s；s->prior=p；s->next=p->prior；

D.  s->prior=p；s->next=p->next；p->next=s；p->next->prior=s；

二．填空题(每空2分，共20分)

1. 采用堆排序、快速排序、冒泡排序，对初态为有序的表，最省时间的是              。

2. 设一组初始记录关键字序列为(49，38，65，97，76，13，27，50)，则第4趟直接选择排序结束后的结果为                                           。

3. 当待排记录序列按关键字顺序有序时，直接插入排序和冒泡排序能达到     的时间复杂度，快速排序的时间性能退化为          (以第一个关键字为枢轴)。

4. 判定顺序栈是否为空的条件是                         ，判定顺序栈是否为满的条件是                                。

5. 当向B-树中插入关键字时,可能引起结点的             ,最终可能导致整个B-树的高度增加           。

6. 设散列表的长度为8，散列函数H(k)=k%7，用线性探测法解决冲突，则根据一组初始关键字序列(8，15，16，22，30，32)构造出的散列表的平均查找长度是             。

7. 设在一棵度数为3的树中，度数为3的结点数有2个，度数为2的结点数有1个，度数为1的结点数有2个，那么度数为0的结点数有              个。

三．判断题（每题1分，共10分，正确的选t，错误的选f）

1. 顺序表查找指的是在顺序存储结构上进行查找。（    ）

2. 循环队列中不存在队列满的问题。（     ）

3. n阶对称矩阵可压缩存储到n/2个单元的空间中。(     )

4. 一个图的邻接表表示法是唯一的。(    )

5. 希尔排序是稳定的。(     )

6. 由树转化成二叉树，该二叉树的右子树不一定为空。（   ）

7. 根据拓扑排序结果可以判断一个有向图中是否存在环路。（  ）

8. 稀疏矩阵的压缩存储可以用一个三元组表来表示稀疏矩阵中的非0元素。（   ）

9. 入栈操作和入队列操作在链式存储结构上实现时不需要考虑栈溢出的情况。(   )

10.数据元素是数据的最小单位。（    ）

四.  简答题（45分）

1. 设有1000个元素组成的无序序列，希望用最快的速度挑选出其中前10个（仅挑前10个）最大元素，以下几种排序方法中哪一种最合适？分析各排序算法, 给出原因？（7分）

  （1）简单选择排序； （2）冒泡排序； （3）堆排序； （4）归并排序

2. 设二叉排序树中关键字由1至1000的整数组成，现要查找关键字为363的结点，下面的关键字序列哪个不可能是在二叉树中查到的序列？说明原因。（5分）

  （1）51, 250, 501, 390, 320, 340,  382, 363

  （2）24，877， 125, 342, 501， 623， 421, 363

3. 针对二叉树，回答以下问题：

 （1）具有n个结点的二叉树的最小深度是多少？最大深度是多少？（4分）

 （2）具有n个结点的完全二叉树中有多少个叶子结点？有多少个度为2的结点？（4分）

 （3）具有n0个叶子结点的完全二叉树中共有多少个结点？（4分）

4. 阅读如下程序，写出此程序的输出结果（其中栈的元素类型为char）。(5分)

void main ( )

    {  Stack S;

        char x, y;

        InitStack(S);

        x='y'; y='s' ;   

        Push(S,x);  Push(S,y);

        Pop(S,x);  Push(S,'k');  Push(S,x);

        while(!StackEmpty(S))  {Pop(S,y); printf(y);}

     }

5. 给定图1所示带权有向图，利用Floyd算法，求每一对顶点之间的最短路径及其路径长度（要求写出求解过程）。（10分）

6. 一个带权无向图的最小生成树是否一定唯一？在什么情况下构造出的最小生成树可能不唯一？（6分）

五．算法填空（共2小题，每空2分，共20分）

1. 下面的算法是在带头结点的单链表L中第 i 个位置之前插入元素e。请在__________处填上适当内容，使其成为一个完整算法。

  typedef  struct  LNode{

       ElemType data;  

struct  LNode  *next;

  }LNode, * LinkList;

     Status ListInsert_L (LinkList & L, int i, ElemType e)

      { p=L; j=  (1)   ; 

          while (p && (j< i-1)) { p=p->next;   (2)      }

          if (!p )  return ERROR;

      s=(LinkList)malloc(sizeof (LNode)); 

      s->date = e;

          (3)         ;

          (4)         

       return Ok ;

       }

2. 下面是一个有向图G采用邻接表存储结构的拓扑排序算法。请在________处填上适当内容，使其成为一个完整算法。

 typedef struct VNode {

    VertexType data;  

    ArcNode  *firstarc;

 } VNode, AdjList[MAX_VERTEX_NUM];

  typedef struct ArcNode { 

    int adjvex;  

    struct ArcNode *nextarc;

    InfoType  *info;  

  } ArcNode;

 typedef struct { 

     AdjList vertices; 

     int  vexnum, arcnum;

     int  kind;        

 } ALGraph;

 Status TopologicalSort(ALGraph G) {

  // 有向图G采用邻接表存储结构。若G无回路,则输出G的顶点的一个拓扑序列并返回   

     OK，否则返回ERROR。

     int indegree[vexnum];

     FindInDegree(G, indegree); //对各顶点求入度indegree [0..vexnum-1]

     InitStack(S);

     for(i=0;  i<G.vexnum; ++i)

    {  if(    (5)  )   Push(S, i);  }

  count=0;

     while(    （6）     ) {

    (7)     ;

 printf(i, G.vertices[i].data);

 ++count;

     for(p=G.vertices[i].firstarc;    (8)  ;  p=p->nextarc)

       {  k=p->adjvex;

        if(!(- -indegree[k]))    （9）   

       }

 }

   if(    (10)      ) return ERROR;

   else return OK;

}//TopologicalSort

六．编写算法（25分）

1.  编写一个算法求二叉树中叶子结点的个数（10分）。 

2. 已知n个顶点的带权图用邻接矩阵表示，试编写算法实现用kruskal算法构造最小生成树。（15分）