在一个n个结点的单链表中查找某个元素,若查找成功,则平均比较次数为( )。

admin2013-05-30  19

问题 在一个n个结点的单链表中查找某个元素,若查找成功,则平均比较次数为(    )。

选项 A、n
B、n/2
C、(n-1)/2
D、(n+1)/2

答案8

解析 对单链表结构的查找,每次比较都必须从头结点开始,因此最好情况为比较一次得到查找的元素,最坏情况为比较到最后一个结点需要n次才找到,平均比较次数为 (1+2+3+...+n)/n次,  即为(n+1)/2次。
转载请注明原文地址:https://kaotiyun.com/show/VaqZ777K
0

最新回复(0)