编写对有序表进行顺序查找的算法，并画出对有序表进行顺序查找的判定树。假设每次查找时的给定值为随机值，且查找成功和不成功的概率也相等，试求进行每一次查找时和给定值进行比较的关键字个数的期望值。

admin2019-08-01 39

问题编写对有序表进行顺序查找的算法，并画出对有序表进行顺序查找的判定树。假设每次查找时的给定值为随机值，且查找成功和不成功的概率也相等，试求进行每一次查找时和给定值进行比较的关键字个数的期望值。

选项

答案int Search(rectype R[]，int n，K){ ／／在具有n个元素的有序表R中，顺序查找值为K的结点，查找成功返回其位置，／／否则返回一1表示失败 int i=0： while(i＜n){ if(R[i]==K)return(i)； else if(R[i]＞K)return(一1)； i++： }／／while return一1； } 在等概率的情况下，则查找成功的平均查找长度为(n+1)／2，查找失败的平均查找长度为(n+2)／2(失败位置除小于第一个，还存在大于最后一个)。若查找成功和不成功的概率也相等，则查找成功时和关键字比较的个数的期望值约为(n+1)／4。

解析

转载请注明原文地址:https://jikaoti.com/ti/KWGjFFFM

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

编写对有序表进行顺序查找的算法，并画出对有序表进行顺序查找的判定树。假设每次查找时的给定值为随机值，且查找成功和不成功的概率也相等，试求进行每一次查找时和给定值进行比较的关键字个数的期望值。

计算机408

学硕统考专业

比较文艺复兴时期人文主义思想和宗教改革思想的异同。

系统地阐明道家思想的著作《淮南鸿烈》，也叫《淮南子》，是汉武帝时()集宾客写成的。《淮南子》问世时，黄老思想在政治上已不占支配地位了。

在欧美资产阶级革命时代，最能体现出资产阶级革命要求的文献是()。

洋务运动期间，军事企业主要采取的方式是()。

下列选项中，属于汉武帝时期削弱地方诸侯势力的措施是()。①推恩令②左官律③附益法④酎金夺爵

电子计算机的发展经过了四代，①电子数值积分计算机(ENIAC)；②集成电路计算机；③大规模集成电路计算机；④晶体管计算机；⑤人工智能计算机，其先后顺序是()。

A、1243B、4312C、2134D、3214D图的BFS遍历。D选项，首先访问结点3，与3邻接的结点4、2都未曾访问过，故3后面因该为2、4(或4、2)，故D错。

ICMP在TCP／IP协议集中属于()。

梅毒时恒定出现的细胞是()

奠定脏腑病机和六气病机基础的是()

山梨醇苯扎溴铵

会计信息系统根据其功能和管理层次的高低可以分为()。

随着房价的下跌，一些要求“补偿”甚至“退房”的老业主，因诉求未达，选择了打砸售楼处等过激行为泄愤。你如何看待业主的行为?()

稀缺效应，是指人们因物以稀为贵，而引起的购买行为变化的现象，即当某件事物变得稀缺或者难以得到时，人们会认为此物更有价值，也更想得到。根据上述定义，下列没有体现稀缺效应的是：

In2008,MarkLynas,anenvironmentalactivist,wasunsparinginhiscriticismofgenetically-modified(GM)foodcompanies,call

下列协议中，哪一个是在传输层定义的?()

Ifyoudidn’tknowanybetter,youmightthinkthatStar,Snuppy,CCandANDiwerejustabunchofinterestingnames.You’donly