数据结构与c语言程序设计答案 .是非题(2,×10) (×)1、队列逻辑上是一个表头和表尾既能插入又能删除 的线性表 (v)2、任何一个递归过程都可以转换成非递归过程 (x)3、与n个键值的集合{k1,k2,…,kn相对应的堆是唯 的 (x)4、在索引顺序表上实现分块查找,在等概率查找情 况下,其查找长度只与表中元素个数有关,而与 每块中元素个数无关 (x)5、所谓加权无向图G的最小生成树T就是将G中各 结点间的最短路径作为边所构造出来的G的子图 (x)6、在10万个随机排列的数据中,要选出5个最小的 数,采用快速排序比采用 Shell排序、堆排序及 各种直接排序法都快。 (x)7、B树查找算法的时间复杂性为0(n)。 (×)8、哈希表查找无需进行关键字的比较 (x)9、在执行某个排序过程中,出现排序码朝着最终位 置相反方向移动,则该算法是不稳定的。 (×)10、任何有向图的顶点都可以按拓扑序排序 填空题(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,按先序遍历所得到的结点序列为 ABCDGEIHFK 3.设哈希表长度为11,哈希函数H(k)=kMD11,若输 入顺序为(18,10,21,9,6,3,16,25,7),处理冲突方法为 线性探测再散列,请构造哈希表 012345678910 21 325166187910 4.给出 0,7),要求从小到大进行排序,试给出快速排序(选第 个记录为枢轴)第一趙排序结果 74,2,5,16,1820,29,33,40,34 5.已知模式匹配的KP算法中模式串t= adabbadada’,其 next函数的值为0112112343 6.在置换选择排序中,假设工作区的容量为w,若不计输 入、输出的时间,则对n个记录的文件而言,生成所有1 数据结构与 C 语言程序设计答案 一. 是非题（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’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 个记录的文件而言，生成所有