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

admin2019-08-15 33

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

选项

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

学硕统考专业

下列法律文件中，规定内阁对君主负责的是()。

乾隆时期，明确规定了驻藏大臣的地位与达赖班禅同等，并实行“金瓶掣签”制度的文件是()。

下列不是春秋时代齐国管仲改革的内容的是()。

简述三十年战争的过程及其结果。

下面哪部经典是我国最早的官方史书?()

在一个长度为n(n>1)的带头结点的单链表h上，设有尾指针r(指向尾结点)，则执行()操作与链表的长度有关。

既考虑作业等待时间又考虑作业执行时间的调度算法是()。

采用散列函数H(k)=3×kMOD13并用线性探测开放地址法处理冲突，在数列地址空间[0．．12]中对关键字序列22，41，53，46，30，13，1，67，51；(1)构造散列表(画示意图)；(2)装填因子；(3)等概

假设有k个关键字互为同义词，若用线性探查法把这k个关键字存入，至少要进行的探查次数是()。

当向一棵m阶的B一树做插入操作时，若一个结点中的关键字个数等于()，则必须分裂成两个结点，当向一棵m阶的B一树做删除操作时，若一个结点中的关键字个数等于()，则可能需要同它的左兄弟或右兄弟结点合并成一个结点。

Z在承包的200亩沙地植树成活后，被当地政府划为沙化土地封禁保护区，禁止一切采伐活动。下列选项错误的是()

正常情况下不能通过肾小球滤过膜的物质是(　　　)

确定监理服务质量高低的标准，就是看工程质量的好坏。()

对它因此受到的损失负责处理。

设α，β，γ1，γ2，γ3都是4维列向量，且｜A｜＝｜α，γ1，γ2，γ3｜＝4，｜B｜＝｜β，2γ1，3γ2，γ3｜＝21，则｜A＋B｜＝_______．

A、连续，但不可偏导B、可偏导，但不连续C、连续、可偏导，但不可微D、可微D

下图所示的网络中，路由器S路由表中到达网络10.0.0.0表项的下一路由器地址应该是

算法的有穷性是指(　　)。

______

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

计算机408

学硕统考专业

下列法律文件中，规定内阁对君主负责的是()。

乾隆时期，明确规定了驻藏大臣的地位与达赖班禅同等，并实行“金瓶掣签”制度的文件是()。

下列不是春秋时代齐国管仲改革的内容的是()。

简述三十年战争的过程及其结果。

下面哪部经典是我国最早的官方史书?()

在一个长度为n(n>1)的带头结点的单链表h上，设有尾指针r(指向尾结点)，则执行()操作与链表的长度有关。

既考虑作业等待时间又考虑作业执行时间的调度算法是()。

采用散列函数H(k)=3×kMOD13并用线性探测开放地址法处理冲突，在数列地址空间[0．．12]中对关键字序列22，41，53，46，30，13，1，67，51；(1)构造散列表(画示意图)；(2)装填因子；(3)等概

假设有k个关键字互为同义词，若用线性探查法把这k个关键字存入，至少要进行的探查次数是()。

当向一棵m阶的B一树做插入操作时，若一个结点中的关键字个数等于()，则必须分裂成两个结点，当向一棵m阶的B一树做删除操作时，若一个结点中的关键字个数等于()，则可能需要同它的左兄弟或右兄弟结点合并成一个结点。

Z在承包的200亩沙地植树成活后，被当地政府划为沙化土地封禁保护区，禁止一切采伐活动。下列选项错误的是()

正常情况下不能通过肾小球滤过膜的物质是( )

确定监理服务质量高低的标准，就是看工程质量的好坏。()

对它因此受到的损失负责处理。

设α，β，γ1，γ2，γ3都是4维列向量，且｜A｜＝｜α，γ1，γ2，γ3｜＝4，｜B｜＝｜β，2γ1，3γ2，γ3｜＝21，则｜A＋B｜＝_______．

A、连续，但不可偏导B、可偏导，但不连续C、连续、可偏导，但不可微D、可微D

下图所示的网络中，路由器S路由表中到达网络10.0.0.0表项的下一路由器地址应该是

算法的有穷性是指( )。

______

正常情况下不能通过肾小球滤过膜的物质是(　　　)

算法的有穷性是指(　　)。