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

admin2019-08-15 30

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

选项

答案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://jikaoti.com/ti/01GjFFFM

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

下列关于民族大迁徙的说法不正确的是()。

关于一战后构筑的凡尔赛体系，说法不正确的是()。

日本三个月亡华计划破产的标志是()。

某系统中n个相互独立的生产者进程为一个消费者进程提供数据，假设每个生产者提供的数据写入各不相同的缓冲区，且生产者写缓冲区的速度比消费者读缓冲区的速度快，则缓冲区个数的最优值应为()。

一棵：BS’r树共7个结点，值分别为1、2、3、4、5、6、7，形态为满二叉树，()不是插入序列。

已知散列函数为H(key)=key％11，处理冲突的方法为二次探测法，探测的序列为：1，-1，4，-4，…，j2，-j2(j＜=m／2)。当di＞0时，Hi=(H(key)+di)％m当di＜0时，Hi=(H(key)+di+m)％m散列

若二叉树的前序序列为DABCEFG，中序序列为BACDFGE，则其层次序列为()。

在一个双链表中，在p结点之前插入q结点的操作是()。

在下列查找的方法中，平均查找长度与结点个数n无关的查找方法是()。

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

下列食物中富含最理想的天然优质蛋白质的是

A．目B．舌C．口D．鼻E．耳肺在窍为

转铁蛋白增多说明

10kV或6kV固定式配电装置的出线侧，在架空出线回路或有反馈可能的电缆出线回路中，应装设断路器。()

设z=z(x,y)由F(az-by,bx-cz,cy-ax)=0确定,其中函数F连续可偏导且aF’1-cF’2≠0,则=__________。

下列设备中，属于输入设备的是(　　)。

Withtheworld’spopulationestimatedtogrowfromsixtoninebillionby2050,researchers,businessesandgovernmentsarealre

Itwas6:40inthemorningandnearlyallofthedoctorsattendingthemedicalconferencehadassembledforthefirstsessionof

A、Taiwan’sNationalistParty.B、PeopleFirstParty.C、DemocraticProgressiveParty.D、TheNewParty.A

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

计算机408

学硕统考专业

下列关于民族大迁徙的说法不正确的是()。

关于一战后构筑的凡尔赛体系，说法不正确的是()。

日本三个月亡华计划破产的标志是()。

某系统中n个相互独立的生产者进程为一个消费者进程提供数据，假设每个生产者提供的数据写入各不相同的缓冲区，且生产者写缓冲区的速度比消费者读缓冲区的速度快，则缓冲区个数的最优值应为()。

一棵：BS’r树共7个结点，值分别为1、2、3、4、5、6、7，形态为满二叉树，()不是插入序列。

已知散列函数为H(key)=key％11，处理冲突的方法为二次探测法，探测的序列为：1，-1，4，-4，…，j2，-j2(j＜=m／2)。当di＞0时，Hi=(H(key)+di)％m当di＜0时，Hi=(H(key)+di+m)％m散列

若二叉树的前序序列为DABCEFG，中序序列为BACDFGE，则其层次序列为()。

在一个双链表中，在*p结点之前插入*q结点的操作是()。

在下列查找的方法中，平均查找长度与结点个数n无关的查找方法是()。

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

下列食物中富含最理想的天然优质蛋白质的是

A．目B．舌C．口D．鼻E．耳肺在窍为

转铁蛋白增多说明

10kV或6kV固定式配电装置的出线侧，在架空出线回路或有反馈可能的电缆出线回路中，应装设断路器。()

设z=z(x,y)由F(az-by,bx-cz,cy-ax)=0确定,其中函数F连续可偏导且aF’1-cF’2≠0,则=__________。

下列设备中，属于输入设备的是( )。

Withtheworld’spopulationestimatedtogrowfromsixtoninebillionby2050,researchers,businessesandgovernmentsarealre

Itwas6:40inthemorningandnearlyallofthedoctorsattendingthemedicalconferencehadassembledforthefirstsessionof

A、Taiwan’sNationalistParty.B、PeopleFirstParty.C、DemocraticProgressiveParty.D、TheNewParty.A

在一个双链表中，在p结点之前插入q结点的操作是()。

下列设备中，属于输入设备的是(　　)。