已阅读5页,还剩3页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
第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)。但具体是多少次,则不应当按照公式来计算(即(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, 则哈希表未填满。由此可写出下列形式简明的算法:void PrintWord(Hash Table ht)/按第一个字母的顺序输出哈希表ht中的标识符。哈希函数为表示符的第一个字母在字母表中的序号,处理冲突的方法是线性探测开放定址法。for(i=1; i=
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 全球及中国多焦点人工晶状体行业市场现状供需分析及市场深度研究发展前景及规划可行性分析研究报告(2024-2030)
- 全球及中国外科或手术显微镜行业市场现状供需分析及市场深度研究发展前景及规划可行性分析研究报告(2024-2030)
- 全球及中国壁挂式净水器行业市场现状供需分析及市场深度研究发展前景及规划可行性分析研究报告(2024-2030)
- 全球及中国坐标测量机光学传感器行业市场现状供需分析及市场深度研究发展前景及规划可行性分析研究报告(2024-2030)
- 全球及中国商用船用柴油机行业市场现状供需分析及市场深度研究发展前景及规划可行性分析研究报告(2024-2030)
- 全球及中国哮喘护理设备行业市场现状供需分析及市场深度研究发展前景及规划可行性分析研究报告(2024-2030)
- 全球及中国口袋面膜行业市场现状供需分析及市场深度研究发展前景及规划可行性分析研究报告(2024-2030)
- 全球及中国反射锤行业市场现状供需分析及市场深度研究发展前景及规划可行性分析研究报告(2024-2030)
- 全球及中国原硅酸钠行业市场现状供需分析及市场深度研究发展前景及规划可行性分析研究报告(2024-2030)
- 全球及中国卵巢癌的治疗和诊断行业市场现状供需分析及市场深度研究发展前景及规划可行性分析研究报告(2024-2030)
- GB/T 34625-2017金属及其他无机覆盖层电气、电子和工程用金和金合金电镀层技术规范和试验方法
- 培训机构安全应急预案范文10篇
- 人音版小学音乐五年级下册《田野在召唤》课件
- 博导第6讲 蜿蜒型河道的演变规律课件
- 北京理工大学在线作业之高等数学
- 《病原生物与免疫学》教学教案
- 旋转楼梯拆除施工方案
- 旅行社设立申请书
- 《探究与发现“杨辉三角”中的一些秘密》课件(部级优课)
- 脓毒症脓毒症休克诊治指南
- 施工现场安全检查考核表3
评论
0/150
提交评论