第9章自测卷答案.pdf
1 第 8 章 查找 自测卷答案 一、填空题（每空1 分，共 10 分）1.在数据的存放无规律而言的线性表中进行检索的最佳方法是 顺序查找（线性查找）。2.线性有序表（a1，a2，a3，a256)是从小到大排列的，对一个给定的值 k，用二分法检索表中与 k 相等的元素，在查找不成功的情况下，最多需要检索 8 次。设有 100 个结点，用二分法查找时，最大比较次数是 7 。3.假设在有序线性表 a20上进行折半查找，则比较一次查找成功的结点数为 1；比较两次查找成功的结点数为 2 ；比较四次查找成功的结点数为 8 ；平均查找长度为 3.7 。解：显然，平均查找长度O（log2n）5 次（25）。但具体是多少次，则不应当按照公式)1(log12nnnASL来计算（即（21log221）/204.6 次并不正确！）。因为这是在假设 n2m-1 的情况下推导出来的公式。应当用穷举法罗列：全部元素的查找次数为（122438455）74；ASL74/20=3.7 ！4折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素 20，它将依次与表中元素 28，6，12，20 比较大小。5.在各种查找方法中，平均查找长度与结点个数 n 无关的查找方法是 散列查找 。6.散列法存储的基本思想是由 关键字的值 决定数据的存储地址。7.有一个表长为 m 的散列表，初始状态为空，现将 n（nhigh)return 0;/查找不到时返回 0 mid=(low+high)/2;if(ST.elemmid.key=key)return mid;else if(ST.elemmid.keykey)return Search_Bin_Recursive(ST,key,low,mid-1);else return Search_Bin_Recursive(ST,key,mid+1,high);/Search_Bin_Recursive 2.【严题集 9.31】试写一个判别给定二叉树是否为二叉排序树的算法，设此二叉树以二叉链表作存储结构。且树中结点的关键字均不同。解：注意仔细研究二叉排序树的定义。易犯的典型错误是按下述思路进行判别：“若一棵非空的二叉树其左、右子树均为二叉排序树，且左子树的根的值小于根结点的值，又根结点的值不大于右子树的根的值，则是二叉排序树”（即不能只判断左右孩子的情况，还要判断左右孩子与双亲甚至根结点的比值也要遵循（左小右大）原则）。若要采用递归算法，建议您采用如下的函数首部：bool BisortTree(BiTree T,BiTree&PRE)，其中 PRE 为指向当前访问结点的前驱的指针。（或者直接存储前驱的数值，随时与当前根结点比较）一个漂亮的算法设计如下：int last=0,flag=1;/last 是全局变量，用来记录前驱结点值，只要每个结点都比前驱大就行。int Is_BSTree(Bitree T)/判断二叉树 T 是否二叉排序树，是则返回 1，否则返回 0 if(T-lchild&flag)Is_BSTree(T-lchild);if(T-datadata;if(T-rchild&flag)Is_BSTree(T-rchild);return flag;/Is_BSTree 3.【严题集 9.22】已知一个含有 1000 个记录的表，关键字为中国人姓氏的拼音，请给出此表的一个哈希表设计方案，要求它在等概率情况下查找成功的平均查找长度不超过 3。解：设计哈希表的步骤为：a)根据所选择的处理冲突的方法求出装载因子 a 的上界；b)由 a 值设计哈希表的长度 m；c)根据关键字的特性和表长 m 选定合适的哈希函数。注：要求 ASL3，则 m 必然要尽量长，以减少冲突；4.【严题集 9.44】已知某哈希表的装载因子小于 1，哈希函数 H(key)为关键字（标识符）的第一个字母在字母表中的序号，处理冲突的方法为线性探测开放定址法。试编写一个按第一个字母的顺序输出哈希表中所有关键字的算法。解：注意此题给出的条件：装载因子 a1,则哈希表未填满。由此可写出下列形式简明的算法：8 void PrintWord(Hash Table ht)/按第一个字母的顺序输出哈希表 ht 中的标识符。哈希函数为表示符的第一个字母在字母表中的序号，处理冲突的方法是线性探测开放定址法。for(i=1;i=26;i+)j=i;While(ht.elemj.key)if(Hash(ht.elemj.key=i)printf(ht.elemj.key);j=(j+1)%m;/PrintWord 9 古今名言 敏而好学，不耻下问孔子 业精于勤，荒于嬉；行成于思，毁于随韩愈 兴于诗，立于礼，成于乐孔子 己所不欲，勿施于人孔子 读书破万卷，下笔如有神杜甫 读书有三到，谓心到，眼到，口到朱熹 立身以立学为先，立学以读书为本欧阳修 读万卷书，行万里路刘彝 黑发不知勤学早，白首方悔读书迟颜真卿 书卷多情似故人，晨昏忧乐每相亲于谦 书犹药也，善读之可以医愚刘向 莫等闲，白了少年头，空悲切岳飞 发奋识遍天下字，立志读尽人间书苏轼 鸟欲高飞先振翅，人求上进先读书李苦禅 立志宜思真品格，读书须尽苦功夫阮元 非淡泊无以明志，非宁静无以致远诸葛亮 熟读唐诗三百首，不会作诗也会吟孙洙唐诗三百首序 书到用时方恨少，事非经过不知难陆游 问渠那得清如许，为有源头活水来朱熹 旧书不厌百回读，熟读精思子自知苏轼 书痴者文必工，艺痴者技必良蒲松龄 10 声明 访问者可将本资料提供的内容用于个人学习、研究或欣赏，以及其他非商业性或非盈利性用途，但同时应遵守著作权法及其他相关法律的规定，不得侵犯本文档及相关权利人的合法权利。谢谢合作！
