第八章自测题答案

第八章自测题答案

ID:6737452

大小:503.00 KB

页数:8页

时间:2018-01-24

第八章自测题答案_第1页
第八章自测题答案_第2页
第八章自测题答案_第3页
第八章自测题答案_第4页
第八章自测题答案_第5页
资源描述:

《第八章自测题答案》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、第8章查找自测卷答案姓名班级A题号一二三四五总分题分1027162423100得分一、填空题(每空1分,共10分)1.在数据的存放无规律而言的线性表中进行检索的最佳方法是顺序查找(线性查找)。2.线性有序表(a1,a2,a3,…,a256)是从小到大排列的,对一个给定的值k,用二分法检索表中与k相等的元素,在查找不成功的情况下,最多需要检索9次。设有100个结点,用二分法查找时,最大比较次数是7。3.假设在有序线性表a[20]上进行折半查找,则比较一次查找成功的结点数为1;比较两次查找成功的结点数为2;比较四次查找成功的结点数为8;平均查找长度为3.7。解:显然,平均查

2、找长度=O(log2n)<5次(25)。但具体是多少次,则不应当按照公式来计算(即(21×log221)/20=4.6次并不正确!)。因为这是在假设n=2m-1的情况下推导出来的公式。应当用穷举法罗列:全部元素的查找次数为=(1+2×2+4×3+8×4+5×5)=74;ASL=74/20=3.7!!!4.【计研题2000】折半查找有序表(4,6,12,20,28,38,50,70,88,100),若查找表中元素20,它将依次与表中元素28,6,12,20比较大小。5.在各种查找方法中,平均查找长度与结点个数n无关的查找方法是散列查找。6.散列法存储的基本思想是由关键字的

3、值决定数据的存储地址。7.有一个表长为m的散列表,初始状态为空,现将n(n

4、8,则它将依次与表中比较大小,查找结果是失败。A.20,70,30,50B.30,88,70,50C.20,50D.30,88,50(B)3.【计研题2001】对22个记录的有序表作折半查找,当查找失败时,至少需要比较次关键字。A.3B.4C.5D.6(A)4.链表适用于查找A.顺序B.二分法C.顺序,也能二分法D.随机86.【91程P3】从供选择的答案中,选出应填入下面叙述?内的最确切的解答,把相应编号写在答卷的对应栏内。要进行线性查找,则线性表A;要进行二分查找,则线性表B;要进行散列查找,则线性表C。某顺序存储的表格,其中有90000个元素,已按关键项的值的上升顺

5、序排列。现假定对各个元素进行查找的概率是相同的,并且各个元素的关键项的值皆不相同。当用顺序查找法查找时,平均比较次数约为D,最大比较次数为E。供选择的答案:A~C:①必须以顺序方式存储②必须以链表方式存储③必须以散列方式存储④既可以以顺序方式,也可以以链表方式存储⑤必须以顺序方式存储且数据元素已按值递增或递减的次序排好⑥必须以链表方式存储且数据元素已按值递增或递减的次序排好D,E:①25000②30000③45000④90000答案:A=④B=⑤C=③D=③E=④7.(96初程P73)从供选择的答案中,选出应填入下面叙述?内的最确切的解答,把相应编号写在答卷的对应栏内。

6、数据结构反映了数据元素之间的结构关系。链表是一种A,它对于数据元素的插入和删除B。通常查找线性表数据元素的方法有C和D两种方法,其中C是一种只适合于顺序存储结构但E的方法;而D是一种对顺序和链式存储结构均适用的方法。供选择的答案:A:①顺序存储线性表②非顺序存储非线性表③顺序存储非线性表④非顺序存储线性表B:①不需要移动结点,不需改变结点指针②不需要移动结点,只需改变结点指针③只需移动结点,不需改变结点指针④既需移动结点,又需改变结点指针C:①顺序查找②循环查找③条件查找④二分法查找D:①顺序查找②随机查找③二分法查找④分块查找E:①效率较低的线性查找②效率较低的非线性

7、查找③效率较高的非线性查找④效率较高的线性查找答案:A=④B=②C=④D=①E=③8.【97程P18】从供选择的答案中,选出应填入下面叙述?内的最确切的解答,把相应编号写在答卷的对应栏内。在二叉排序树中,每个结点的关键码值A,B一棵二叉排序,即可得到排序序列。同一个结点集合,可用不同的二叉排序树表示,人们把平均检索长度最短的二叉排序树称作最佳二叉排序,最佳二叉排序树在结构上的特点是C。供选择的答案A:①比左子树所有结点的关键码值大,比右子树所有结点的关键码值小②比左子树所有结点的关键码值小,比右子树所有结点的关键码值大③比左右子树的所有结

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。