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

admin2016-03-29 71

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

选项

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

解析

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

评述抗战的三个阶段。

分析战后美国经济发展出现黄金时期的原因。(厦门大学2015年历史学基础真题)

下列哪一项不是凯末尔世俗化改革的内容?()。

世界天文史上最早实地测量子午线的记录是由谁进行的?()

1901年6月，发表《立宪法议》，首先提出君主立宪要求的是()。

“瓜步之战”发生在下列哪两个政权之间?()

唐顺宗时，以王叔文、王侄为首的朝臣与宦官之间发生的冲突，称为()。

下列科技文化成就，产生于3世纪的是()。①刘徽提出计算圆周率的正确方法②贾思勰著《齐民要术》③钟繇把隶书转化为楷书④马钧发明翻车

某计算机的Cache共有16块，采用2路组相联映射方式(即每组2块)。每个主存块大小为32字节，按字节编址。主存129号单元所在主存块应装入到的Cache组号是()。

属于高血压治疗的药物是()

强酸性阳离子交换树脂的离子交换基团是强碱性阴离子交换树脂的离子交换基团是

许多国家的政府债券只允许在证券交易所上市交易。()

关注学生的创造精神、批判思维，适合以学生活动为主安排课程的目标是()。

采用雪崩光电二极管(APD)的要求是有较高的偏置电压和复杂的温度补偿电路。()

以“赢在课堂”为题目，写一篇记叙文或议论文。要求：字数不少于600字，文中不得出现考生的任何信息。

以下说法正确的是（）。