单选题
对长度为n的有序单链表，若搜索每个元素的概率相等，则顺序搜索到表中任一元素的平均搜索长度为
A) n/2 B) (n+1)/2 C) (n-1)/2 D) n/4
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。于是，查找成功的平均查找长度为：
假设在每个位置查找概率相等，即P1=P2… =Pn=1/n，若是从表头向表尾方向查找，则每个位置上查找比较次数为C1=1,C2=2,…，Cn=n。于是，查找成功的平均查找长度为：