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

admin2009-03-15 53

问题对长度为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全国计算机二级

下列入侵检测系统结构中，能够避免单点故障的是()。

在安装和配置无线接入点之前，不需要向网络管理员询问的信息是()。

在一台Cisco路由器的g0／1端口上，封禁所有端口号为1434的UDP数据包，正确的access-list的配置是()。

若某大学分配给计算机系的IP地址块为202．113．16．224／27，分配给自动化系的IP地址块为202．113．16．192／27，那么这两个地址块经过聚合后的地址为()。

在组建一个家庭局域网时，有三台计算机需要上网访问Internet，但ISP只提供一个连接到网络的接口，且只为其分配一个有效的IP地址。那么在组建这个家庭局域网时可选用的网络设备是

IEEE802．3标准规定的以太网物理地址长度为()。

在关系模型中，“关系中不允许出现相同元组”的约束是通过【】实现的。

视图不能单独存在，它必须依赖于______而存在。

安静时，细胞内、外正常Na+和K+浓度差的维持是由于()

既能平肝潜阳，又能清肝明目、镇惊安神的药物是

患者，男。血清CH50升高，血小板聚集，血管出现渗出、水肿。最可能的诊断为

患者，女，52岁。缘于暴怒，突然昏倒，不省人事，牙关紧闭，面赤唇紫，舌红，脉多沉弦。证属

地下工程无论何种防水等级，变形缝均应选用()防水措施。

如果股票价格上升,则该股票的看跌期权价格(),它的看涨期权价格()

耐久年限在5～20年的建筑称为()

幼儿在认识“方”“万”和“日”“月”等形近符号时出现混淆，这是()所致。