17. 18. 19. 20. 所谓平衡二叉树是指左右子树的高度差的绝对值不大于1的二叉树。 在一个根最大堆中，最大元素在根，最小元素在最低层。

快速排序算法在每一趟排序中都能找到一个元素放在其最终的位置上。 9阶B树中，除根以外的任一结点中的关键字个数不小于4。

21. 在顺序表中取出第i个元素所花费的时间与i成正比。 22. 在栈为空的情况下，不能做出栈操作，否则产生下溢出。

23. 在循环队列中，若尾指针Rear大于头指针Front，则其元素个数为(Rear – Front)。 24. 若一棵二叉树的任一非叶结点的度为2，则该二叉树为满二叉树。 25. 已知一棵树的先序序列和后序序列，一定能构造出该树。向二叉排序树中插入一个结点，

所需比较的次数可能大于此二叉排序树的高度。 26. 若图G的最小生成树不唯一，则G的边数一定多于n-1，并且权值最小的边有多条。 27. 9阶B树中，除根以外的任一个非叶子结点中的关键字数目均在5～9之间。

28. 二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树非空，则根

结点的值大于其左孩子的值；若它的右子树非空，则根结点的值小于其右孩子的值。 29. 给定结点数的平衡二叉树的高度是唯一的。

30.理想情况下，在散列表中查找一个元素的时间复杂度为O(1)。 31、线性表的长度是线性表所占用的存储空间的大小。 （ ）

32、在带头结点的循环单链表中，任一结点的后继指针均不空。 （） 33、栈和队列都是运算受限的线性表。 （ ）

34、数组（矩阵）是一种没有插入与删除操作的非线性结构。（ ） 35、广义表的长度指广义表中的原子个数。（ ）

36、若某二叉树的叶子结点数为1，则其先序遍历序列和后序遍历序列一定相反。 （） 37、完全二叉树就是满二叉树。（ ）

38、就平均查找长度而言，分块查找最小，二分查找次之，顺序查找最大。（） 39、在m阶B-树中，所有非终端结点至少包含┌m/2┐个结点。（）

40、由于希尔排序的最后一趟与直接插入排序过程相同，因此前者一定比后者花费时间多。 （ ）

41．顺序存储方式只能用于存储线性结构。（ ）

42．数据的逻辑结构与存储结构都是依赖于计算机的。 ( )

43. 非空线性表中任意一个数据元素都有且只有一个直接后继元素。 （ ） 44.在顺序表中取出第i个数据元素所花费的时间与i成正比。 （ ） 45. 二维数组是它的数据元素为线性表的线性表。 （ ） 46.广义表的长度指广义表中的原子个数。（ ） 47. 完全二叉树就是满二叉树。 （ ）

48. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和。 （ ）

49.由于希尔排序的最后一趟与直接插入排序过程相同，因此前者一定比后者花费时间多。 （ ）

50.对一个堆，无论按二叉树层次遍历还是先序遍历，都不一定能得到有序序列。（ ） 51. 线性表的唯一存储方式是链表。（ ）

52. 线性表的长度是线性表所占用存储空间的大小。 （ ） 53. 栈和队列都是运算受限的线性表。 （ ）

54.在栈满的情况下不能作进栈操作，否则产生上溢。 （ ）

55.数组可看成是对线性结构的一种推广，因此可以对它进行插入、删除操作。 （ ） 56. 二叉树只能用二叉链表来存储。 （ ）

- 8 -

57.将一棵树转换成二叉树后，根结点没有左子树。 （ ）

58. 有向图用邻接矩阵表示，顶点i的出度等于第i行中非0且非∞的元素个数。 （ ） 59. 对任意一个图，从它的某顶点出发进行一次深度优先或广度优先搜索，可访问到图的每一个顶点。 （ ）

60. 二叉排序树查找和二分查找的时间性能相同。 （ ）

三、填空题。

1. 数据元素之间存在的相互关系称为 ，分为 和 两大类。

2. 计算机之内的数据关系称为 结构，基本方法为 方法、 方法、 方法和 方法。 3.与后缀表达式3 5 2-7*+等价的中缀表达式为 。 4.树转换成的二叉树，其根结点的 子树一定为空。

5、评价算法的优劣，首先应该是算法的 ；此外除要求算法易于理解、编码、调试外，是以算法的 和 来衡量算法的优劣的。 6、为了能有效地应用散列查找技术，必须解决的两个问题是 和 。

7、多维数组一般采用 存储方法存储数据；广义表一般采用 方式存储。

8设顺序循环队列Q[0：m-1]的队头指针和队尾指针分别为F和R，其中队头指针F指向当前队头元素的前一个位置，队尾指针R指向当前队尾元素所在的位置，则出队列的语句为F =____________;。

9.设线性表中有n个数据元素，则在顺序存储结构上实现顺序查找的平均时间复杂度为___________，在链式存储结构上实现顺序查找的平均时间复杂度为___________。

10设一棵二叉树中有n个结点，则当用二叉链表作为其存储结构时，该二叉链表中共有________个指针域，__________个空指针域。

11设指针变量p指向单链表中结点A，指针变量s指向被插入的结点B，则在结点A的后面插入结点B的操作序列为______________________________________。

12设无向图G中有n个顶点和e条边，则其对应的邻接表中有_________个表头结点和_________个表结点。

13设无向图G中有n个顶点e条边，所有顶点的度数之和为m，则e和m有______关系。 14设一棵二叉树的前序遍历序列和中序遍历序列均为ABC，则该二叉树的后序遍历序列为__________。

15设一棵完全二叉树中有21个结点，如果按照从上到下、从左到右的顺序从1开始顺序编号，则编号为8的双亲结点的编号是___________，编号为8的左孩子结点的编号是_____________。

16中序遍历二叉排序树所得到的序列是___________序列（填有序或无序）。 17快速排序的最坏时间复杂度为___________，平均时间复杂度为__________。 18设某棵二叉树中度数为0的结点数为N0，度数为1的结点数为N1，则该二叉树中度数为2的结点数为_________；若采用二叉链表作为该二叉树的存储结构，则该二叉树中共有_______个空指针域。

19设某无向图中顶点数和边数分别为n和e，所有顶点的度数之和为d，则e=_______。 20设一组初始记录关键字序列为(55，63，44，38，75，80，31，56)，则利用筛选法建立的初始堆为___________________________。

- 9 -

四、综合题 1.

已知一棵二叉树的前根序列和中根序列分别为ABDGHECFIJ及GDHBEACIJF，请画出这棵二叉树,并写出后根序列。

2. 给定权值7，18，3，22，5，25，12，8，构造相应的哈夫曼树，并求这棵哈夫曼树

的带权路径长度WPL。

3. 已知散列函数为H(K)=K mod 13,关键码序列为25，37，52，43，84，99，120，15，

26，11，70，82，1，采用拉链法处理冲突，画出构造的散列表，并计算查找成功的平均查找长度。

4. 设有无向图G（如右图所示），

i、写出采用邻接矩阵存储的表现形式；

ii、按照其存储结构给出用普里姆算法构造最小生成树的过程 iii、写出该图的深度优先和广度优先遍历的序列。

5. 已知一棵二叉树的前序遍历的结果序列是ABDGEHCFI，中

序遍历的结果是GDBHEAFIC，试写出这棵二叉树的后序遍历结果。(要求分析过程)

6. 已知某系统在通信联络中只可能出现9种字符，其频率分别为0.05，0.20，0.07，0.08，

0.14，0.23，0.02，0.11，0.10设它的权值w＝（5，20，7，8，14，23，2，11，10），试设计哈夫曼编码。

7. 已知一组记录的排序码为（46，79，56，38，40，80, 95，24），写出对其进行快

速排序的每一次划分结果。 8. 已知一个散列表如下图所示： 35 20 33 48 59 0 1 2 3 4 5 6 7 8 9 10 11 12

其散列函数为h(key)=key, 处理冲突的方法为双重散列法，探查序列为： hi=(h(key)+i*h1(key))%m i=0,1,…，m－1 其中 h1(key)=key+1 回答下列问题：

（1）对表中关键字35，20，33和48进行查找时，所需进行的比较次数各为多少？ （2）该散列表在等概率查找时查找成功的平均查找长度为多少？

9. 已知一棵二叉树的前序遍历的结果序列是ABDEGIKCFHJL，中序遍历的结果是DBEIKGACFJLH，试写出这棵二叉树的后序遍历结果。

10. 设一组初始记录关键字序列为(45，80，48，40，22，78)，则分别给出第4趟简单

选择排序和第4趟直接插入排序后的结果。

11. 设散列表的长度为8，散列函数H(k)=k mod 7，初始记录关键字序列为(25，31，8，

27，13，68)，要求分别计算出用线性探测法和链地址法作为解决冲突方法的平均查找长度。 12. 已知一个图的顶点集V和边集E分别为：V={1,2,3,4,5,6,7};

- 10 -

E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25};用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。

13. 多维数组、广义表一般采用什么存储方式？为什么？

14. 队列可以用循环单链表来实现，故可以只设置一个头指针或尾指针。请分析对于循环单链表实现的队列，用哪种方案更合适。

15、存储结构的设计与什么因素有关，请举例说明。

16、说明任意三个结点可构造多少种形态的树，多少种形态的二叉树，图示之。 17、二叉树与树在概念上是相同的吗？为什么？

18、什么是散列表？实际上其查找时间性能为O(1)吗？为什么？

19.已知二叉树的中序遍历序列为CDBAEGF,后序遍历序列为DCBGFEA,请画出该二叉树。 20. 若一篇文档有以下字符：A、B、C、D、E、F，各字符在文档中出现的概率依次为4,5,6,7,10,12。请构建以各字符为叶子结点的Huffman树，并写出各字符的Huffman编码。（构建时按左小右大、左0右1的规则进行）

21. 一组待排序的记录关键字为(68,45,21,82,34,16,56), 则 (1) 利用直接插入排序第一、第二趟的变化序列。 (2) 利用快速排序第一趟的变化序列。

22. 已知如下无向网络的邻接矩阵（其权值为整型数据）

(1)写出从顶点4出发的深度优先搜索序列、从顶点1出发的广度优先搜索序列。 (2) 用prim算法思想求最小生成树，要求画出生成过程。 1 2 3 4 5 6

1 ∞ 3 1 ∞ ∞ ∞ 2 3 ∞ 2 4 ∞ ∞ 3 1 2 ∞ 2 ∞ ∞ 4 ∞ 4 2 ∞ 3 4 5 ∞ ∞ ∞ 3 ∞ 1 6 ∞ ∞ ∞ 4 1 ∞

23、给定叶子结点（1,3,5,6,7,8），构造哈夫曼树。 24、已知如下有向图的邻接矩阵：

0 10 ∞ 30 100 ∞ 0 50 ∞ ∞ ∞ ∞ 0 ∞ 10 ∞ ∞ 20 0 60 ∞ ∞ ∞ ∞ 0 （1）写出从顶点1出发的DFS、BFS序列。 （2）求顶点1到其余顶点的最短路径。

25、已知一组初始的关键字序列为（46,79,56,38,40,84）,则写出利用快速排序得到的第一趟的变化序列。

26、已知关键字序列为(75,33,52,41,12,88,66,27),哈希表长为10，哈希函数为：

H(K)=K%7，解决冲突用线性探测再散列法，构造哈希表，求等概率条件下查找成功的平均查找长度。

27、一棵二叉树的先序遍历序列为abdefcg，中序遍历序列为dfebagc，试画出该二叉树。 28、若一篇文档有以下字符：A、B、C、D、E、F,各字符在文档中出现的概率依次为4,5,7,8,10,12，

- 11 -