违法和不良信息举报 联系客服
免费注册 登录

在最坏的情况下，查找成功时二叉排序树的平均查找长度（）

题目
单选题
在最坏的情况下，查找成功时二叉排序树的平均查找长度（）
A

小于顺序表的平均查找长度

B

大于顺序表的平均查找长度

C

与顺序表的平均查找长度相同

D

无法与顺序表的平均查找长度比较

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

第1题：

（ 1 ）下列叙述中正确的是

A ）对长度为 n 的有序链表进行查找，最坏清况下需要的比较次数为 n

B ）对长度为 n 的有序链表进行对分查找，最坏情况下需要的比较次数为（ n/2 ）

C ）对长度为 n 的有序链表进行对分查找，最坏情况下需要的比较次数为（ log 2 n ）

D ）对长度为 n 的有序链表进行对分查找，最坏情况下需要的比较次数为（ nlog 2 n ）


正确答案：C

第2题：

在各种查找方法中，平均查找长度与查找表中元素个数无关的是(38)。冒泡排序在最坏情况下时间复杂度为(39)。

A．顺序查找

B．散列查找

C．折半查找

D．动态查找


正确答案：B
解析：选项中除散列查找以外，其他查找方法的查找性能都与表长(即查找表中的元素个数)有关，而散列查找(Hash查找)的平均查找长度直接与装填因子相关。

第3题：

（ 1 ）下列叙述中，正确的是

A ）对长度为 n 的有序链表进行查找，最坏情况下需要的比较次数为 n

B ）对长度为 n 的有序链表进行对分查找，最坏情况下需要的比较次数为（ n/2 ）

C ）对长度为 n 的有序链表进行对分查找，最坏情况下需要的比较次数为（ log 2 n ）

D ）对长度为 n 的有序链表进行对分查找，最坏情况下需要的比较次数为（ n log 2 n ）


正确答案：C

第4题：

在结点数确定的二叉排序树上进行查找的平均查找长度与二叉树的形态有关，最差的情况是二叉排序树为（）树的时候。


正确答案:单支树

第5题：

已知长度为9的表{16、3、7、11、9、26、18、14、15}，建立二叉排序树后进行查找，则等概率情况下查找成功的平均查找长度为(35)。

A．30/9

B．25/9

C．29/9

D．31/9


正确答案：D
解析：本题考查二叉排序树的查找。二叉排序树又称为二叉查找树，其定义为：二叉排序树或者是一棵空树，或者是具有如下性质(BST性质)的二叉树：(1)若它的左子树非空，则左子树上所有结点的值均小于根结点；(2)若它的右子树非空，则右子树上所有结点的值均大于根结点；(3)左、右子树本身又各是一棵二叉排序树。在做该题时，首先将表中的9个元素放进二叉树中构成二叉排序树，在构造二叉排序树时，我们将表中的元素依次按照构造二叉排序树的规则往树中添加元素，在获得二叉排序树后，计算平均长度就变得简单了，为(1+2+2+3+3+4+5+5+6)/9=31/9。

第6题：

若对大小为N的有序顺序表进行顺序查找，当查找不成功时，平均查找长度为(59)；当查找成功且表中仅有一个关键字等于欲查找的元素时，平均查找长度为(60)。

A．N

B．N+1

C．N/2

D．(N+1)/2


正确答案：A
解析：当查找不成功时，会查找至最后一个元素，故平均查找长度为N。

第7题：

在关键字随机分布的情况下，在二叉排序树上进行查找的平均查找长度与(28)的量级相当。

A．顺序查找

B．二分查找

C．哈希查找

D．逆序查找


正确答案：B

第8题：

对长度为100的顺序表,在等概率情况下,查找成功时的平均查找长度为(),在查找不成功时的平均查找长度为()。


参考答案：50.5、100(或101)

第9题：

设有一个整数序列d{40，28，6，72，100，3，54}依次取出序列中的数，构造一棵二叉排序树。并对上述二叉排序树，在等概率条件下，求成功查找的平均查找长度。
（1）

（2）ASL=（1×1+2×2+3×3+4）/7=18/7
略

第10题：

在一个长度为n的线性表中顺序查找值为x的元素时，在等概率情况下，查找成功时的平均查找长度（）

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

正确答案:C

更多相关问题
相关内容