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

admin2009-02-13 65

问题对长度为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://www.kaotiyun.com/show/qz1p777K

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

二级VB

NCRE全国计算机二级

相关试题推荐

随机试题

最新回复(0)

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

二级VB

NCRE全国计算机二级

ava程序与数据库的连接机制是

将较长的数据类型转换为较短的整数类型，要进行()。

一棵二叉树第六层(根结点为第一层)的结点数最多为【】个。

在switch(expression)语句中，expression的数据类型不能是

下列数据结构中，能用二分法进行查找的是

数据库系统中实现各种数据管理功能的核心软件称为【】。

如果进栈序列为e1，e2，e3，e4，则可能的出栈序列是()

ODL转换关系时，若为原子类型属性，类的每个属性对应关系的一个属性；若为结构类型，其每个元素为关系的一个属性；若为数组，则按元素的个数即可扩展为______，也可扩展为多个属性。

2.设某循环队列的容量为50，如果头指针front=45(指向队头元素的前一位置)，尾指针rear=10(指向队尾元素)，则该循环队列中共有______个元素。(作图)

一个队列的进队列顺序是1、2、3、4，则出队列顺序为()。

下列属于地理自然环境的有()

路中心的双黄实线属于哪一类标线？

经济、政治、法律、伦理等人际关系是()

孤立性心肌炎时，心肌间质的肉芽肿不含有下列哪一种成分

下列有关糖皮质激素治疗特发性血小板减少性紫癜的叙述，正确的是

在诊断尚未明确的腹部闭合性外伤观察期做法错误的是

TheJapaneseareexpectinghouseguests.Thesevisitorswillstayforalongtime,servingtea,cleaninghouse,makingConversat