从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较（）个元素结点。A、n/2B、nC、（n+1）/2D、（n-1）/2

题目

从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较（）个元素结点。

A、n/2
B、n
C、（n+1）/2
D、（n-1）/2

如果没有搜索结果或未解决您的问题，请直接联系老师获取答案。

相似问题和答案

第1题：

在具有n个结点的单链表上查找值为y的元素时,其时间复杂度为()。

A、O(n)

B、O(1)

C、O(n2)

D、O(n-1)

参考答案：A

第2题：

顺序查找n个元素的顺序表,若查找成功,则比较关键字的次数最多为()次。

A、n/2

B、(n+1)/2

C、(n-1)/2

D、n

参考答案：D

第3题：

●在长度为n的线性表中顺序查找值为x的元素时，查找成功的平均查找长度为 (49) 。

(49) A．n

B．n／2

C．(n+1)／2

D．(n-1)／2

正确答案：C
【解析】假设在每个位置查找的概率相等，即有Pi=1/n；若是从表尾往表头方向查找，则在每个位置上的查找比较次数为Cn=1，Cn-1=2，．．．，C1=n。因此，查找成功的平均查找长度为

第4题：

从具有n个结点的二叉查找树中查找一个元素时，在最坏情况下进行成功查找的时间复杂度为(51)。

A．O(n)

B．O(1)

C．O(log2n)

D．O(n2)

正确答案：A
解析：当二叉查找树严重不平衡时，二叉查找树有n层，最坏情况就是把n个结点都比较一遍才查找成功。

第5题：

从一个具有n个结点的单链表中查找值为x的结点时，在查找成功的情况下，需平均比较(45)个结点。

A．n

B．n/2

C．(n-1)/2

D．(n+1)/2

正确答案：D

第6题：

在一个长度为n的顺序线性表中顺序查找值为x的元素时,查找成功时的平均查找长度(即x与元素的平均比较次数,假定查找每个元素的概率都相等)为().

Bn/2

C(n+1)/2

D(n-1)/2

参考答案：C

第7题：

从一个具有n个结点的单链表中查找其值等于k的结点时，在查找成功的情况下，需平均比较 ______个结点。

A．n

B．n/2

C．(n-1)/2

D．(n+1)/2

正确答案：D
解析：在n个结点的单链表中，查找第i个结点需要比较关键词的次数是i，所以，在查找成功的情况下，需平均比较的结点个数为(1+2+…+n)/n，即(n+1)/2。

第8题：

对n个元素的表做顺序查找时,若查找每个元素的概率相同,则平均查找长度为()。

A.(n-1)/2

B、n/2

C、(n+1)/2

D、n

参考答案：C
解释：总查找次数N=1+2+3+…+n=n(n+1)/2，则平均查找长度为N/n=(n+1)/2。

第9题：

用二分查找法对具有n个结点的线性表查找一个结点，所需的平均比较次数为（）。A．O（n2）B．O（nlog2n）C．O（n）D．O（log2n）

正确答案：D
二分查找的优点是比较次数少，查找速度快，平均检索长度小，经过log₂n次就可以完成查找过程。

第10题：

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

A．n

B．n/2

C．(n-1)/2

D．(n+1)/2

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

从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较（）个元素结点。A、n/2B、nC、（n+1）/2D、（n-1）/2

题目

相似问题和答案

更多相关问题

相关内容