对长度为n的有序单链表，若搜索每个元素的概率相等，则顺序搜索到表中任一元素的平均搜索长度为

admin2009-03-15 22

问题对长度为n的有序单链表，若搜索每个元素的概率相等，则顺序搜索到表中任一元素的平均搜索长度为

选项 A、n/2
B、(n+1)/2
C、(n-1)/2
D、n/4

答案2

解析由于链表不能随机访问，要访问某个结点，必须从它的直接前趋指针域出发才能找到。因此，链式存储的线性表，即使是有序表，也只能使用顺序查找。顺序查找时，从表中的第一个元素开始，将给定的值与表中逐个元素的关键字进行比较，直到两者相符，查到所要找的元素为止。
假设在每个位置查找概率相等，即P1=P2… =Pn=1/n，若是从表头向表尾方向查找，则每个位置上查找比较次数为C1=1,C2=2,…，Cn=n。于是，查找成功的平均查找长度为：

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

本试题收录于：二级VF题库NCRE全国计算机二级分类

二级VF

NCRE全国计算机二级

相关试题推荐

随机试题

最新回复(0)

对长度为n的有序单链表，若搜索每个元素的概率相等，则顺序搜索到表中任一元素的平均搜索长度为

二级VF

NCRE全国计算机二级

下列关于Windows2003系统下DHCP服务器的描述中，错误的是()。

下列关于配置OSPF的描述中，错误的是()。

在Windows命令窗口中输入()命令，可见到下图所示的操作系统返回结果。

下列Windows命令中，可以显示主机路由表内容的命令是()。

如下图所示，某校园网用10Gbps的POS技术与CERNET相连，POS接口的帧格式是SDH，下列R1的POS3／0接口配置，正确的是()。

R1、R2是一个自治系统中采用：RIP路由协议的两个相邻路由器，R1的路由表如下图(A)所示，当R1收到R2发送的如下图(B)的[V，D]报文后，R1更新的4个路由表项中距离值从上到下依次为0、2、3、2。那么，①②③④不可能的取值序列为(

在某DHCP客户机执行ipconfig／all命令后得到的部分信息如图(a)所示。图(b)是在该客户机上依次执行ipconfig／release和ipconfig／renew时捕获的报文，并对其中第5条报文进行了解析。分析图中的信息并补全图中空白处的信息。

DNS正向搜索的功能是将域名解析为IP地址，Windows系统中可测试该功能的命令是（）。

栈和队列的共同点是

下列关于合规管理的目标，说法正确的是()。

以“工作分析”作为其课程开发方法的是()

A．肺炎链球菌B．流感嗜血杆菌C．大肠埃希菌D．金黄色葡萄球菌E．隐球菌引起年长儿化脓性脑膜炎最常见的致病菌是()

因含有雄黄，过量服用可致肝肾功能损害的中成药是()。

下列关于《招标投标法》适用范围的说法中，不正确的有()。

银行在提供个人理财服务时，往往需要广泛利用各种金融产品和投资工具，综合分析和权衡各种产品和工具的风险、收益和流动性。()

首先提出支持面I甸对象数据模型的SQL标准是(62)。

A、Pretendtobeinbettershape.B、Havemorephysicalexercise.C、Turnmoreoftentofriendsforhelp.D、Paymoreattentiontob