数据结构与C语言程序设计答案
1. 是非题（2’′10）
（′）1、_____________ 队列逻辑上是一个表头和表尾既能插入又能删除的线性表。
（√）2、任何一个递归过程都可以转换成非递归过程。
（′）3、 与n个键值的集合{k1,k2,…,kn}相对应的堆是唯一的。
（′）4、_____________ 在索引顺序表上实现分块查找，在等概率查找情况下，其查找长度只与表中元素个数有关，而与每块中元素个数无关。
（′）5、_____________ 所谓加权无向图G的最小生成树T就是将G中各结点间的最短路径作为边所构造出来的G的子图。
（′）6、_____________ 在10万个随机排列的数据中，要选出5个最小的数，采用快速排序比采用Shell排序、堆排序及各种直接排序法都快。
（′）7、_____________ B树查找算法的时间复杂性为O（n）。
（′）8、_____________ 哈希表查找无需进行关键字的比较。
（′）9、_____________ 在执行某个排序过程中，出现排序码朝着最终位置相反方向移动，则该算法是不稳定的。
（′）10、任何有向图的顶点都可以按拓扑序排序。
2. 填空题（2’′6）
1． 假设用于通信的电文由8个字母组成，其频率分别为0.07，0.19,0.02,0.06, 0.32,0.03,0.21,0.10, 为这8个字母设计哈夫曼编码，其中编码长度最大的字母的编码是_ 5__ 位。
2．已知二叉树按中序遍历所得到的结点序列为DCBGEAHFIJK， 按后序遍历所得到的结点序列为DCEGBFHKJIA， 按先序遍历所得到的结点序列为_ ABCDGEIHFJK___ 。
3. 设哈希表长度为11， 哈希函数 H(k)=k MOD 11, 若输入顺序为（18,10,21,9,6,3,16,25,7）,处理冲突方法为线性探测再散列，请构造哈希表 ____________ 。
__ 0_ 1_ 2_ 3_ 4_ 5_ 6_ 7_ 8_ 9_ 10
__ 21____ _ 3_ 25 16 6_ 18 7_ 9_ 10
4．给出一组关键字 T=(20，4，34，5，16，33，18，29，2，40，7)，要求从小到大进行排序，试给出快速排序(选第一个记录为枢轴)第一趟排序结果 7,4,2,5,16,18,20,29,33,40,34____ 。
5．已知模式匹配的KMP算法中模式串t=’adabbadada’，其next函数的值为_ 0112112343___________ 。
6．在置换-选择排序中，假设工作区的容量为w，若不计输入、输出的时间，则对n个记录的文件而言，生成所有初始归并段所需时间为_ O(n log w)__________ 。
3. 简答题（6’′5）
1． 有n个不同的英文单词，它们的长度相等，均为m，若n>>50，m<5，试问采用什么排序方法时间复杂度最佳？为什么？
采用基数排序方法最佳。
因单词长度相等，而只有26个字母组成，符合基数排序的条件。
因m<<n，故时间复杂性由O(m(n+rm))变成O(n)。
2． 对于一个栈，给出输入序列A，B，C，试给出全部可能的输出序列。若输入序列的长度为n，则可能的输出序列有多少？
ABC，ACB，BAC，BCA，CBA
C2nn/（n+1）
3． 求2-3树的结点数和叶子数的范围并证明之。
2h+1-1 ~ （3h+1-1）/2
2h ~ 3h
h为树的高度
用数学归纳法证明。