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

admin2010-11-26 31

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

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

答案B

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

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

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

二级VF

NCRE全国计算机二级

相关试题推荐

随机试题

最新回复(0)

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

二级VF

NCRE全国计算机二级

请根据图中所示网络结构回答问题。填写路由器RG的路由表项①至⑥。

某网络中DHCP服务器地址为10．0．0．1，MAC地址为00-12-34-56-78-90，可分配IP地址范围为10．0．0．50～10．0．0．100，其中10．0．0．50保留给MAC地址是00-11-22-33-44-55的主机。网络中某客户机从该

下图所示是校园网中一台主机在命令行模式下执行某个命令时用Sniffer捕获的数据包。请根据图中信息回答下列问题。当需要回放捕获的数据包时，可以使用Sniffer内置的【20】。

某客户机使用DHCP获取IP地址等信息，其获取IP地址过程中捕获的4条报文及对第2条报文分析如下图所示。请分析其中的信息，补全内容。

将Catalyst6500交换机的设备管理地址设置为203．29．166．9／24，缺省网关的IP地址为203．29．166．1，正确的语句是()。

下列关于交换机的描述中，错误的是()。

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

若两台服务器系统可用性分别达到99．99％和99．999％，那么下面关于两台服务器每年停机时间的描述中正确的是()。

常用的数据备份方式包括完全备份、增量备份和差异备份，恢复时三种方式在时间使用方面由少到多的顺序为()。

调整DHCP客户的地址租用时间为3小时30分，Cisco路由器的正确配置语句是（）。

亚硝酸盐中毒即食入含有大量亚硝酸盐的食物而引起的中毒。()

Theoldmangotintothe______ofstoringmoneyunderthebed.

下列对诊断早期原发性肝癌最有价值的检查是()。

建设工程招标工程量清单应当依法由()编制。

个人贷款业务可以为银行带来相关的服务费收入。()

根据《营业税暂行条例》规定,纳税人从事运输业务,应当向()主管税务机关申报缴纳营业税。

旅行社是从事()旅游者等活动的企业法人。

(15年)设函数f(x)连续．φ(x)=。若φ(1)=1．φ’(1)=5，则f(1)=_______．

Computersmayonedayturnnightintoday—withgoodold,naturalsunlight.Giantcomputer-controlledmirrors,thousandsoff

Allthefollowingparticiples(分词)functionsasanattributiveEXCEPT