在一个n个结点的单链表中查找某个元素,若查找成功,则平均比较次数为()。A.nB.n／2C.(n－1)／2D.(n＋1)

Question

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

A．n

B．n/2

C．(n-1)/2

D．(n+1)/2

Answer 1

正确答案：D
解析：对单链表结构的查找，每次比较都必须从头结点开始，因此最好情况为比较一次得到查找的元素，最坏情况为比较到最后一个结点需要n次才找到，平均比较次数为 (1+2+3+...+n)/n次， 即为(n+1)/2次。