一、单项选择题 ( 本大题共 15 小题，每小题 2 分，共 30 分 ) 在每小题列出的四个选项中只有一个选项是符合题目要求的，请将其代码填在以下表格内。错选或未选均无分。

（ A  ）1. 下列数据结构中，（    ）是非线性数据结构：

A. 树       B. 字符串     C. 队       D. 栈

（ B  ）2. 一个算法应该是（    ）。

A. 程序                   B. 问题求解步骤的描述 

C. 要满足五个基本特性     D.  A和C

（ B ）3. 下面关于线性表的叙述中，错误的是哪一个？（ ）

A. 线性表采用顺序存储，必须占用一片连续的存储单元。

B. 线性表采用顺序存储，便于进行插入和删除操作。

C. 线性表采用链式存储，不必占用一片连续的存储单元。

D. 线性表采用链式存储，便于插入和删除操作。

（ B ）4. 在循环双链表的p所指节点之后插入s所指节点的操作是(    )。

A. p->right=s；s->left=p；p->right->left=s；s->right=p->right；

B. s->left=p；s->right=p->right；p->right->left=s；p->right=s；

C. s->left=p；s->right=p->right；p->right=s；p->right->left=s；

D.p->right=s；p->right->left=s；s->left=p；s->right=p->right；

解析：

如图所示为一个简单的循环双向链表

要插入一个节点S，则应该修改指针为  s-left>p;   s->right=p->right;  p->right->left->s;  p->right=s; 故选B

（ C ）5. 设栈S 和队列Q 的初始状态为空，元素e1，e2，e3，e4,e5 和e6 依次通过栈S，一个元素出栈后即进队列Q，

若6 个元素出队的序列是e2，e4，e3，e6，e5，e1。则栈S 的容量至少应该是( C)。

      A. 6          B. 4         C. 3             D. 2

（B  ）6. 在循在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取出数据打印。

该缓冲区应该是一个（  ）结构。

A. 栈       B. 队列                C. 数组                D. 线性表

解析：

队列的主要应用为：汽车加油站、模拟打印机缓冲区、CPU分时系统等方面。

（ A ）7. 数组A[0…5,0…6]的每个元素占5个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5,5]的地址是（   ）。

A. 1175             B. 1180        C. 1205          D. 1210

解析：

1000+（5*6+5）*5=1175

（B  ）8. 下列哪一种图的邻接矩阵是对称矩阵？（    ）

A. 有向图          B. 无向图       C. AOV网          D. AOE网

解析：

无向图是没有方向的，所以它的邻接矩阵是对称的。

AOV网是点表示活动的网

AOE网是边表示活动的网

（ B ）9. 有关二叉树下列说法正确的是（    ）

A. 二叉树的度为2                   B. 一棵二叉树的度可以小于2                                                                                

C. 二叉树中至少有一个结点的度为2   D. 二叉树中任何一个结点的度都为2

解析：

二叉树具有如下两个特点：
①非空二叉树只有一个根结点。
②每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。

二叉树中结点的度小于或等于2，A、C选项错误。

度为0的树是一棵单结点树，也是一棵二叉树，D错误

（D  ）10. 设树T的度为4，其中度为1,2,3,4的结点个数分别为4,2,1,1则T中的叶子数为（ ）

A.  5          B.  6          C. 7       D. 8

解析：

（ C ）11. 分别以下列序列构造二叉排序树，跟其他序列所构造的结果不同的是(    )

A．（100，80， 90， 60， 120，110，130） 

B.（100，120，110，130，80， 60， 90）

C.（100，60， 80， 90， 120，110，130） 

D. (100，80， 60， 90， 120，130，110)

解析：

二叉排序数定义： 即右孩子结点>根节点>左孩子结点

二叉排序树或者是一棵空树；或者是具有如下特性的二叉树：
（1）若它的左子树不空，则左子树上
          所有结点的值均小于根结点的值；
（2）若它的右子树不空，则右子树上
          所有结点的值均大于根结点的值；
（3）它的左、右子树也都分别是二叉排序树。

（  ）12. 对右图进行拓扑排序，可以得到不同的拓扑的个数是（  ）

       A：4       

       B：3

       C：2     

       D：1 

（ c  ）13. 有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100},当二分查找值为82的结点时,（   ）次比较后查找成功。

A.  1           B.  2         C.  4       D. 8

解析：

    C

第一次    [1,3,9,12,32,41,45,62,75,77,82,95,100]

第二次     1,3,9,12,32,41,45,[62,75,77,82,95,100]

第三次     1,3,9,12,32,41,45,62,75,77,[82,95,100]

第四次     1,3,9,12,32,41,45,62,75,77,[82],95,100]

（B  ）14. 下列二叉排序树中，满足平衡二叉树定义的是

解析：

什么是平衡二叉树？
   平衡二叉树又称AVL树，它是具有如下性质的二叉树：
   1.)左、右子树都是平衡二叉树；
   2.)所有结点的左、右子树深度之差的绝对值≤ 1

  即 |左子树深度 - 右子树深度| ≤ 1

选项A左子树的深度为2，右子树的深度为0， 即 |左子树深度 - 右子树深度| =2>1不符合平衡二叉树定义。

选项B左子树的深度为2，右子树的深度为2，即|左子树深度 - 右子树深度| =0≤1符合平衡二叉树定义。

选项C左子树的深度为1，右子树的深度为3，即|左子树深度 - 右子树深度| =2>1不符合平衡二叉树定义。

选项D左子树的深度为4，右子树的深度为1，即|左子树深度 - 右子树深度| =3>1不符合平衡二叉树定义。

（ C ）15. 下列四个序列中，哪一个是堆（    ）

A. 75,65,30,15,25,45,20,10      B. 75,65,45,10,30,25,20,15

C. 75,45,65,30,15,25,20,10      D. 75,45,65,10,25,30,20,15

解析：

判断一个序列是不是堆的具体方法：

    堆把这个序列看成数组型的二叉树，如果根结点是i，左子树是2*i，右子树是2*i+1，

   每个根结点都比左子树和右子树大，就是大根堆，或者根结点比左子树和右子树都小，那就是小根堆。

选项A，75>65>30,15<25,15<45故选项A不是堆。

选项B，76>65>45,10<25<30,故选项B不是堆。

选项C，75>65>45,30>25>15,25>20>10，故选项C为大顶堆

选项D，75>65>45,10<25<30，故选项D不是堆。

二、填空题( 本大题共 10 小题，每小题 1分，共 10 分 )

1、数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的  关系      和操作等的学科。

2、数据元素之间的关系在计算机中有两种不同的表示方法，由此得到两种不同的存储结构：   顺序结构  和链式结构。

3、在有n个元素的顺序表中删除一个元素，所需要移动元素的平均个数是   (n-1)/2 ，具体移动元素的个数与元素位置有关。

4、队列是限制插入只能在表的一端，而删除在表的另一端进行的线性表，其特点是  先进先出  。

5、____栈_   _是限定仅在表尾进行插入或删除操作的线性表。

6、迪杰斯特拉（Dijkstra）最短路径算法从源点到其余各顶点的最短路径的路径长度按__最短路径递增_    _次序依次产生各条路径。

解析：

问题描述：对于一个带权的有向图，如何求得从源点到其余各顶点的最短路径？
解决此问题的算法：迪杰斯特拉(Dijkstra)提出了一个按路径长度递增的次序产生最短路径的长度。

7、设给定权值总数有n个，其哈夫曼树的结点总数为_____2n-1_________个。

8、设无向图的顶点个数为n，则该图最多有____n（n-1）/2___________条边

9、若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为____(n+1)/2______。

10、对n(n>0)个记录进行冒泡排序，最少要交换______0___次记录。

三、综合应用题(共 40分 )

1、设一棵二叉树的先序、中序遍历序列分别为（共8分）

      先序遍历序列： H D A C B G F E 

      中序遍历序列： A D C B H F E G

（1）画出这棵二叉树。（本小题3分）

解析：

先序遍历为H D A C B G F E 推测出H为根结点。

中序遍历为A D C B H F E G 推测出以H为界，A D C B 为左子树，F E G 为右子树。

然后结合先序遍历和中序遍历的规则来推测，即可推测出该二叉树。

（2）写出后序遍历序列。（本小题3分）

由图可知后序遍历规则，左-右-根，可知后序遍历序列为：A B C D E F G H

（3）将这棵二叉树转换成对应的树（或森林）。（本小题2分）

2、某电文共使用5种字符：A,B,C,D,E,它们的出现概率依次为0.05、0.15、0.4、0.3、0.1。(共8分)

(1)试画出对应的赫夫曼树。（请按照同层结点权值由小到大的次序构造，不需要写出构造过程，只画出最后树形结果即可)。 (本小题3分)

(2)求出每个字符的赫夫曼编码。(本小题5分)

 A:1000  B:100  C:0  D:11  E:1001

3、下图为一个连通网。(共8分)

(1)写出从v1出发对该网的广度优先遍历序列。(本小题3分)

从v1出发对该网的广度优先遍历序列：v1、v2、v3 v4、v5、v6

解析：

网的深度优先遍历类似于树的按先根遍历的过程，因此该序列为v1、v2、v3 v4、v5、v6

网的广度优先遍历类似于树的按层次遍历的过程，因此该序列为v1、v2、v3 v4、v5、v6

(2)从v1开始，用Prim算法构造该网的最小生成树(直接写出构造好的结果，不必写过程)，并求出最小生成树上各边权值之和。(本小题5分)

权值之和为:1+4+2+5+3=15 

解析：

生成树：
    是连通图的一个极小连通子图，它含有全部顶点，但只有n-1条边。

最小生成树：
   在 e 条带权的边中选取 n-1 条边（不构成回路），使“权值之和”为最小。

算法一：（普里姆算法）

普里姆算法的基本思想:
    取图中任意一个顶点 v 作为生成树的根，之后往生成树上添加新的顶点 w。在添加的顶点 w 和已经在生成树上的顶点v 之间必定存在一条边，并且该边的权值在所有连通顶点 v 和 w 之间的边中权值最小。之后继续往生成树上添加顶点，直至生成树上含有 n 个顶点为止。
   普里姆算法构造最小生成树的过程是从一个顶点U={u0}作初态，不断寻找与U中顶点相邻且代价最小的边的另一个顶点，扩充到U集合直至U=V为止
算法二：（克鲁斯卡尔算法）

 根据Prim算法可知如图所示：

因此权值之和为:1+4+2+5+3=15

4、设一组数据为{1,14,27,29,55,68,10,11,23}，现采用的哈希函数是H(key)=key MOD 13，冲突用链地址法解决，设哈希表的大小为13(0..12)要求如下。（共8分）

（1）构造哈希表（画示意图）（4分）；

（2）计算装填因子（2分）；

             装填因子： 9/13=0.69

数据结构试题