设记录R1，R2，…，Rn按关键字值从小到大顺序存储在数组r[1．．n]中，在r[n+1]处设立一个监督哨，其关键字值为+∞。试写一查找给定关键字k的算法，并画出此查找过程的判定树，求出在等概率情况下查找成功时的平均查找长度。

admin2017-01-04 49

问题设记录R₁，R₂，…，R_n按关键字值从小到大顺序存储在数组r[1．．n]中，在r[n+1]处设立一个监督哨，其关键字值为+∞。试写一查找给定关键字k的算法，并画出此查找过程的判定树，求出在等概率情况下查找成功时的平均查找长度。

选项

答案intSearch(rectype r[]，int n，keytype k){ ／／在n个关键字从小到大排列的顺序表中，查找关键字为k的结点 r[n+1]．key=MAXINT；／／在高端设置监视哨 int i=1： while(r[i]．key＜k)i++； if(r[n+1]．key==k)return(i％(n+1))； else return(0)； } 查找过程的判定树是单枝树。本题中虽然表按关键字有序，但进行顺序查找，查找成功的平均查找长度亦为(n+1)／2。

解析

转载请注明原文地址:https://www.kaotiyun.com/show/iQRi777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

西汉初年，在刘邦翦灭异姓诸侯王的过程中，被保留下来的异姓诸侯王是()

简述士族的源流和在西晋的发展过程。

简述从十月革命胜利到第二次世界大战爆发前夕苏俄(苏联)与主要资本主义国家关系演变的基本情况。

比较工业革命和第二次工业革命，分析英、法、德、美工业革命的过程和特点。

中国第一个资产阶级革命团体兴中会建立的时间是()。

诸侯国的国君如何用人呢?有人主张：“左右皆曰不可，勿听；诸大夫皆曰不可，勿听；国人皆曰不可，然后察之，见不可焉，然后去之。”这种主张最终可能出自下列哪位思想家之口()。

1628年出版了《心血运动论》一书，论证了血液在全身的循环运动，使生理学发展为科学的是()。

(1)页面长度为1KB=210B，因此页内偏移地址占10位。主存大小为16KB=214B，所以物理地址占14位。0AC5H=0000101011000101B，除去后10位，得到页号为2，则查找页表可知物理块号为4，所以物理地址是0100101100

一组记录的关键字为{25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序表，用归并排序方法对该序列进行一趟归并后的结果是()。

一个使用选择性重传协议的数据链路层协议，如果采用了5位的帧序列号，那么可以选用的最大窗口是()。

在Web开发过程中，需要开发小组进行多次循环的阶段有

十二指肠球部溃疡并发症一般不包括

A．心电图B．超声心电图C．胸部X线检查D．中心静脉压E．CT缩窄型心包炎，应选检查项目是

张某是一起抢劫案的犯罪嫌疑人，公安机关将案件移送到检察机关审查起诉，人民检察院将其拘传到人民检察院接受了两天的讯问。张某对此提出了申诉，认为检察院违法。对此，他提出的哪些理由是没有根据的?()

Chronicinsomniaisamajorpublichealthproblem.Andtoomanypeopleareusing【C1】______therapies,evenwhilethereareafew

甲收到一份来自乙的电子订单后，将订单中的货物送达到乙时，乙否认自己曾经发送过这份订单，为了解除这种纷争，采用的安全技术是()。

(36)不是单元测试主要检查的内容。

TheearliestinstitutionofhigherlearningsetupinAmericawas