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

admin2009-03-15 31

问题对长度为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服务器的描述中，错误的是()。

下列关于路由信息协议RIP的描述中，错误的是()。

如图(A)所示，在某DHCP客户机上捕获了5条报文，表中对第5条报文进行了解析，图(B)是在该客户机捕获上述报文后执行ipconfig／all命令后得到的信息。分析捕获的报文，并补全图中【11】到【15】的信息。

下图是网络地址转换NAT的一个实例，根据图中信息，数据包2的方格中的内容就为()。

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

在某Cisco路由器上使用命令“snmp-serverhost202．113．77．5system”进行SNMP设置，如果在管理站202．113．77．5上能够正常接收来自该路由器的通知，那么下列描述中错误的是()。

已知IP地址172．2．14．33和172．2．14．34、172．2．14．65和172．2．14．66预留给RG与其它路由器互联，请根据下图所示网络结构回答下列问题。填写路由器RG的路由表项

常用数据备份方式包括完全备份、增量备份和差异备份，三种方式在数据恢复速度方面由快到慢的顺序为()。

基于网络的入侵检测系统采用的识别技术主要有：事件的相关性、统计意义上的非正常现象检测、模式匹配，以及()。

数据库(DB)、数据库系统(DBS)、数据库管理系统(DBMS)三者之间的关系是

法洛四联症缺氧发作时有效的抢救措施应除外

中外合资经营企业合营各方必须按合同规定的出资期限缴清各自的出资。合同规定一次缴清的，合营各方应当

牙龈瘤的起因多为()

[2009年第150题，2007年第151题]居住建筑中通过轮椅的走道净宽不应小于：

某项目的招标人具有编制招标文件和组织评标的能力，则招标人()。

Womenhavelongbeenmoreinnumberthanmenoncollegecampuses.Theyalsoholdmoreadvanceddegreesthantheirmale【C1】______

使用VC6打开考生文件夹下的源程序文件modi2．cpp。阅读下列函数说明和代码，补充空出的代码。程序的功能是寻找1～500以内的亲和数并显示出来，函数amicableNum(intm，intn)判定两个数是否是亲和数。亲和数的定义为：两个数