数据结构

从具有n个结点的二叉排序树中查找一个元素时，在平均情况下的时间复杂度大致为（　）。A、 O（n）B、 O（1）C、 O（log2n）D、 O（n2）

题目

从具有n个结点的二叉排序树中查找一个元素时，在平均情况下的时间复杂度大致为（　）。

  • A、 O（n）
  • B、 O（1）
  • C、 O（log2n）
  • D、 O（n2）
如果没有搜索结果，请直接 联系老师 获取答案。
如果没有搜索结果，请直接 联系老师 获取答案。
相似问题和答案

第1题：

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

A．O(n)

B．O(1)

C．O(log2n)

D．O(n2)


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

第2题：

在具有n个结点的二叉排序树上插入一个新结点时，根据n个数据元素生成一棵二叉排序树时，其时间复杂性大致为______。

A．O(n)

B．O(n2)

C．O(log2n)

D．O(nlog2n)


正确答案：D

第3题：

从n个结点的二叉排序树中查找一个元素,平均时间复杂性大致为()。


参考答案：O(log2n)

第4题：

从一个具有N个结点的单链表中查找其值等于X结点时，查找成功的情况下，需平均比较()结点。

A.N
B.N/2
C.(N-1)/2
D.(N+1)/2

答案：D
解析：

第5题：

设二叉排序树中有n个结点，则在二叉排序树的平均查找长度为()。


答案：B
解析：

第6题：

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

A．n

B．n/2

C．(n-1)/2

D．(n+1)/2


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

第7题：

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

A．n

B．n/2

C．(n-1)/2

D．(n+1)/2


正确答案：D

第8题：

从一个具有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。

第9题：

设二叉排序树上有n个结点，则在二叉排序树上查找结点的平均时间复杂度为()。


答案：D
解析：

第10题：

对于一棵有n个结点、深度为h的二叉排序树，当查找一个指定关键字的元素且查找失败时，最多需进行（）次比较。


正确答案:h

更多相关问题
相关内容