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

admin2019-08-01 38

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

选项

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

我国第一部系统的史学理论著作是（）。

公元9～13世纪是西欧封建庄园的兴盛时期，典型的庄园采用()的剥削方式。

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

1956年，苏共二十大后，匈牙利大党员和群众强烈要求克服个人崇拜，扩大民主，实行经济改革，一些由知识分子、大学生和干部组成的社团组织纷纷成立，其中最有影响者是()。

二月革命后，为俄国无产阶级革命奠定思想基础的文献是()。

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

序列的“中值记录”指的是：如果将此序列排序后，它是第n／2个记录。试写出一个求中值记录的算法。

已知在二叉树中，T为根结点，p和q为二叉树中两个结点，试编写求距离它们最近的共同祖先的算法。

在一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶结点个数是____。

Thefriendsofhisroommateweresonoisythathecouldn’t________themanymore.

A、5°B、30°C、45°D、90°E、135°金瓷冠基底冠的金瓷衔接处的角度为

根据《建设项目竣工环境保护验收技术规范一生态影响类》，水利工生态影响的环境保护措施调查的内容有（）。

施工质量控制应贯彻全面、全员、全过程质量管理的思想，运用动态控制原理，进行质量的()等。

根据现行《企业会计准则》，下列交易事项中，应计入当期利润表的是()。

员工福利属于()行为。

在个人住房贷款中，政策风险是非系统风险。()

银行风险管理是一项复杂的系统工程，必须建立在稳健扎实的基础之上。以下不属于风险管理基础的是()。

国务院依据法定程序和条件制定的关予国家行政管理活动方面的规范性文件是()

所谓“超流水线”技术的含义是________。

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

计算机408

学硕统考专业

我国第一部系统的史学理论著作是（）。

公元9～13世纪是西欧封建庄园的兴盛时期，典型的庄园采用()的剥削方式。

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

1956年，苏共二十大后，匈牙利大党员和群众强烈要求克服个人崇拜，扩大民主，实行经济改革，一些由知识分子、大学生和干部组成的社团组织纷纷成立，其中最有影响者是()。

二月革命后，为俄国无产阶级革命奠定思想基础的文献是()。

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

序列的“中值记录”指的是：如果将此序列排序后，它是第n／2个记录。试写出一个求中值记录的算法。

已知在二叉树中，T为根结点，*p和*q为二叉树中两个结点，试编写求距离它们最近的共同祖先的算法。

在一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶结点个数是____。

Thefriendsofhisroommateweresonoisythathecouldn’t________themanymore.

A、5°B、30°C、45°D、90°E、135°金瓷冠基底冠的金瓷衔接处的角度为

根据《建设项目竣工环境保护验收技术规范一生态影响类》，水利工生态影响的环境保护措施调查的内容有（）。

施工质量控制应贯彻全面、全员、全过程质量管理的思想，运用动态控制原理，进行质量的()等。

根据现行《企业会计准则》，下列交易事项中，应计入当期利润表的是()。

员工福利属于()行为。

在个人住房贷款中，政策风险是非系统风险。()

银行风险管理是一项复杂的系统工程，必须建立在稳健扎实的基础之上。以下不属于风险管理基础的是()。

国务院依据法定程序和条件制定的关予国家行政管理活动方面的规范性文件是()

所谓“超流水线”技术的含义是________。

已知在二叉树中，T为根结点，p和q为二叉树中两个结点，试编写求距离它们最近的共同祖先的算法。