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

admin2019-08-15 55

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

选项

答案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

学硕统考专业

列宁称马克思、恩格斯是“19世纪人类三个最先进国家中三种主要思潮的继承人和天才的完成者”。这里“三个最先进国家”指的是()。

下列长征事件的正确顺序是()。 ①四渡赤水②召开遵义会议③吴起镇会师④飞夺泸定桥

三国时期，魏、蜀、吴三国灭亡的历史顺序是()。

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

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

对下列4个序列用快速排序方法进行排序，以序列的第1个元素为基准进行划分。在第1趟划分过程中，元素移动次数最多的是()。

—棵二叉树的后序遍历序列为DABEC，中序遍历序列为DFBAC，则先序遍历序列为()。

荷兰国旗问题：设有一个仅红、白、蓝三种颜色的条块组成的条块序列，请编写一个时间复杂度为O(n)的算法，使得这些条块按红、白、蓝的顺序排好，即排成荷兰国旗图案。

以下说法中错误的是()。

人民代表大会制度的基础是()

无名条款是指合同中有些条款()。

侧方位排牙时，平衡侧不接触工作侧接触，应

不适合用煮沸消毒法消毒的是()。

玻璃应力检测是指用偏振片确定玻璃是否经(　　)处理。

下列各项中，属于志愿者参与社会服务以利他和社会为中心的动机的有()。

Whichofthefollowingactivitiescanbeusedtogetthemainideaofapassage?

观察下列各式：a+b+1=2，a2+b2+2=5，a2+b2+3=7，a4+b4+4=11，a5+b5+5=16，…，则a10+b10+10=__________．

抚养比就是需要经济供养的少年与老年人口之和与劳动年龄人口数量之比，反映了劳动力的抚养负担程度。根据上述定义，以下现象不会增加抚养比的是()。

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

计算机408

学硕统考专业

列宁称马克思、恩格斯是“19世纪人类三个最先进国家中三种主要思潮的继承人和天才的完成者”。这里“三个最先进国家”指的是()。

下列长征事件的正确顺序是()。 ①四渡赤水②召开遵义会议③吴起镇会师④飞夺泸定桥

三国时期，魏、蜀、吴三国灭亡的历史顺序是()。

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

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

对下列4个序列用快速排序方法进行排序，以序列的第1个元素为基准进行划分。在第1趟划分过程中，元素移动次数最多的是()。

—棵二叉树的后序遍历序列为DABEC，中序遍历序列为DFBAC，则先序遍历序列为()。

荷兰国旗问题：设有一个仅红、白、蓝三种颜色的条块组成的条块序列，请编写一个时间复杂度为O(n)的算法，使得这些条块按红、白、蓝的顺序排好，即排成荷兰国旗图案。

以下说法中错误的是()。

人民代表大会制度的基础是()

无名条款是指合同中有些条款()。

侧方位排牙时，平衡侧不接触工作侧接触，应

不适合用煮沸消毒法消毒的是()。

玻璃应力检测是指用偏振片确定玻璃是否经( )处理。

下列各项中，属于志愿者参与社会服务以利他和社会为中心的动机的有()。

Whichofthefollowingactivitiescanbeusedtogetthemainideaofapassage?

观察下列各式：a+b+1=2，a2+b2+2=5，a2+b2+3=7，a4+b4+4=11，a5+b5+5=16，…，则a10+b10+10=__________．

抚养比就是需要经济供养的少年与老年人口之和与劳动年龄人口数量之比，反映了劳动力的抚养负担程度。根据上述定义，以下现象不会增加抚养比的是()。

玻璃应力检测是指用偏振片确定玻璃是否经(　　)处理。