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

admin2010-11-26  38

问题 对长度为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
0

相关试题推荐
最新回复(0)