28、若从二叉树的根结点到其它任一结点的路径上所经过的结点序列按其关键字递增有序，
则该二叉树是( C )。
A. 二叉排序树 B. 赫夫曼树 C. 堆 D. 平衡二叉树
29、已知一组待排序的记录关键字初始排列如下：56,26,86,35,75,19,77,58,48,42
下列选择中（ D ）是快速排序一趟排序的结果。（ B ）是归并排序 一趟排序的结果。（ A ）是初始堆（大堆顶）。 A）86,75,77,58,42,19,56,35,48,26. B）26,56,35,86, 19, 75, 58, 77, 42, 48. C）35,26,19,42,58,48,56,75,86,77. D）42,26,48,35,19,56,77,58,75,86.
三．填空题
（1-13是线性、树形、图形结构，14-15是查找和排序）
1、数据结构通常有下列4类基本结构：集合、 线性结构 、树型结构、图型结构。
2、线性表的顺序存储结构是以 物理存储地址 来表示数据元素之间的逻辑关系的。
3、递归过程可借助于数据结构 ( 栈 )改写成非递归过程。
4、设循环队列存于一维数组Ｑ[ｍ]中，尾指针rear指示队尾元素在队列中的当前位置，?头指针front指示队列中队头元素的前一个位置，则队列长度＝( （rear-front +m）%m )。
5、在二叉树的第i层上至少有____1_____个结点, 至多有____2i-1_____个结点 , 深度为k的二叉树至多有____2k_-1________个结点.
6、对树的遍历有先序遍历树和后序遍历树。若以二叉链表作树的存储结构, 则树的先序遍历可借用二叉树的 先序 遍历算法来实现, 而树的后序遍历可借用二叉树的 中序 遍历算法来实现。
7、设森林F中有三棵树，第一、第二和第三棵树的结点个数分别为m1、m2和m3， 则与森林F对应的二叉树根结点的左子树上的结点个数是（m1-1 ）， 右子树上的结点个数是（ m2+m3 ）。
8、若某二叉树有n0个叶子结点，有n1个结点仅有一个孩子，则该二叉树的总结点数是（ 2 n0 + n1-1）。
9、如果对完全二叉树中结点从1开始按层进行编号，设最大编号为n；那么，可以断定编号为i (i>1)
的结点的父结点编号为( i/2 )；所有编号（ >n/2 ）的结点为叶子结点。
10、若某二叉树中，有20个结点没有孩子，有20个结点仅有一个孩子，则该二叉树的总结点数是 59 。
11、 n个顶点的连通图至少有 n-1 条边，至多有 n(n-1)/2 条边。
12、对于图的存储结构有（ 邻接表 ）、（ 邻接矩阵 ）等方法。
13、在一个无向图的邻接表中，若表结点的个数是m，则图中边的条数是___m/2_________条。
14、若有序表中关键字序列为：12，22，33，44，55，66，77，88，99，100，101对其进行折半查找，则在等概率情况下，查找成功时的平均查找长度是（ 3 ）。查找99时需进行（ 2 ）次比较。
15、用 中序 遍历对二叉排序树进行访问可得到有序序列。
已知Hash函数为 H（K）=K mod 13 ，散列地址为0 --14，用二次探测再散列 处理冲突，关键字（23，34，56，24，75，12，49, 52，36，92） 的分布如图，则平均成功的查找长度为（ ）。
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 52 36
92 56 34 23 24 75 12 49 图示结构题
（1-4是线性、树形、图形结构，5-6是查找排序）
1. 已知在电文中只出现频率为 ( 5,26,7,23,20,19 )的６个字符，
画出你建的哈夫曼树，并给出其哈夫曼编码。
2.已知某二叉树的后序遍历和中序遍历次序分别为DBFGECA和BDACFEG
请画出该二叉树。
3将图示森林转换为二叉树，并对该二叉树先序遍历。
a d h
b c e f i j
g k l m
4．某二叉树的结点数据采用顺序存储表示如下：
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
A B C D E F G H I （1）试画出此二叉树的图形表示。
（2）将此二叉树看作森林的二叉树表示，试将它还原为森林。
5． 已知Hash函数为 H（K）=K mod 13 ，散列地址为0 --14，用线性探测再散列处理
冲突，给出关键字（56，34，68，23，16，70，48，35，83，12，14，57） 在散列地址的分布。并指出平均成功的查找长度是多少?
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
6．已知待排序序列为：25,12,9,20,7,31,24,35,17,10，试写出： (1). 堆排序初始建堆(大顶堆)的结果；
(2). 以第一个元素为枢轴的快速排序一趟扫描的结果；