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

admin2019-08-15 61

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

选项

答案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://kaotiyun.com/show/pMCi777K

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

在1875年宪法中关于法国立法权的叙述，不正确的是()。

20世纪30年代，美国推行“中立”的外交政策。对这一政策的正确表达是()。①适应国内外形势，维护自身利益②反映国际形势走向缓和③维护凡尔赛一华盛顿体系④不利于地区冲突的缓和与解决⑤不关心美洲地区以外的事务

1936年，张学良和杨虎城发动的西安事变()。①是一次具有爱国意义的兵变②民族矛盾激化的结果③检验了中国社会各阶级的抗日态度④促成了抗日民族统一战线初步形成

支持多道程序的操作系统，区别于其他操作系统的主要特征为()。

某定点机字长8位(含1位符号位)，现该机中一个寄存器的内容为43H，则将其算术左移一位、算术右移一位的结果分别为()。

真值0在原码、反码和补码机器数形式下()。

对于一个长度为n的任意表进行排序，至少需要进行的比较次数是()。

“一源而三歧”的奇经是指

A．抗组胺药B．糖皮质激素C．雄激素D．羟基脲E．白消安治疗慢性再生障碍性贫血宜首选

狭义的资产评估程序是()。

“吃大锅饭”容易导致消极怠工，这属于()现象。

学生主体性的形成，既是教育的目的，也是教育成功的条件。

夫妻个人财产是指依法或依当事人约定，夫妻婚后各自保留的一定范围内的个人所有财产。一般包括法定个人财产与约定个人财产，具体而言，包括婚前财产与婚后财产。下列财产中哪一项属于夫妻个人财产?()

发展社会主义市场经济，必须建立主要由市场形成的价格机制。价格形成机制有助于：

患者，女性，24岁，诊断为逆行性牙髓炎，决定其预后的最关键因素为()。