15、不同关键字序列，构造的二叉排序树的平均查找长度都相同。
题目
15、不同关键字序列，构造的二叉排序树的平均查找长度都相同。
相似考题
更多“15、不同关键字序列，构造的二叉排序树的平均查找长度都相同。”相关问题
-
第1题：
二叉排序树的形态与关键字的输入序列有关,但平衡二叉排序树是相同的。()此题为判断题(对，错)。
参考答案：错误
-
第2题：
由同一关键字集合构造的各棵二叉排序树 ( )
A．其形态不一定相同，但平均查找长度相同
B．其形态不一定相同，平均查找长度也不一定相同
C．其形态均相同，但平均查找长度不一定相同
D．其形态均相同，平均查找长度也都相同
正确答案：B
-
第3题：
● 用关键字序列10、20、30、40、50构造的二叉排序树（二叉查找树）为 （63） 。
正确答案：C
-
第4题：
已知长度为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。 -
第5题：
设二叉排序树中关键字由1～1000的整数构成，现要查找关键字为363的结点，下列关键字序列不可能是在二叉排序树上查找到的序列是()。A.2，252，401，398，330，344，397，363
B.924，220，911，244，898，258，362，363
C.925，202，911，240，912，245，363
D.2，399，387，219，266，382，381，278，363答案：C解析：把这四个序列各插入到一个初始为空的二叉排序树中，可以发现，C序列形成的不是一条路径，而是有分支的，可见它是不可能在查找过程中访问到的序列。 -
第6题：
设有一个整数序列{50，38，16，82，110，13，64}，依次取出序列中的数，构造一棵二叉排序树。利用上述二叉排序树，为了查找110，经多少次元素间的比较能成功查到？为了查找15，经多少次元素间的比较可知道查找失败？
（1）
（2）三次；四次
略 -
第7题：
在结点数确定的二叉排序树上进行查找的平均查找长度与二叉树的形态有关，最差的情况是二叉排序树为（）树的时候。
正确答案:单支树 -
第8题：
对两棵具有相同关键字集合而形状不同的二叉排序树，（）遍历它们得到的序列的顺序是一样的。
正确答案:中序 -
第9题：
在最坏的情况下，查找成功时二叉排序树的平均查找长度（）
- A、小于顺序表的平均查找长度
- B、大于顺序表的平均查找长度
- C、与顺序表的平均查找长度相同
- D、无法与顺序表的平均查找长度比较
正确答案:C -
第10题：
设关键字序列为（71，12，88，53，11，25，65，27，16），散列函数为H（key）= key % 7，采用链地址法解决冲突。请回答：请求等概率下查找成功的平均查找长度ASL
正确答案:ASL成功=（1*5+2*2+3*1+4*1）=16/9 -
第11题：
填空题在结点数确定的二叉排序树上进行查找的平均查找长度与二叉树的形态有关，最差的情况是二叉排序树为（）树的时候。正确答案： 单支树解析： 暂无解析 -
第12题：
填空题对两棵具有相同关键字集合而形状不同的二叉排序树，（）遍历它们得到的序列的顺序是一样的。正确答案： 中序解析： 暂无解析 -
第13题：
含n个关键字的二叉排序树的平均查找长度主要取决于()A.关键字的个数
B.树的形态
C.关键字的取值范围
D.关键字的数据类型
参考答案：A
-
第14题：
用关键字序列10、20、30、40、50构造的二叉排序树(二叉查找树)为(63)。
A．
B．
C．
D．
正确答案：C
解析：二叉排序树又称二叉查找树，它可以是一棵空树，若非空时具有下述性质：
1．若根结点的左子树非空，则左子树上所有结点的关键字值均小于等于根结点的关键字值。
2．若根结点的右子树非空，则右子树上所有结点的关键字值均大于等于根结点的关键字值。
3．根结点的左、右子树也分别为二叉排序树。
构造二叉排序树过程如下：
首先与根结点比较，如果小于等于则进入左边子树，再与左边子树的根节点比较，直到找到它要放的位置，否则进入右子树，进行上述操作。 -
第15题：
在关键字随机分布的情况下，在二叉排序树上进行查找的平均查找长度与(28)的量级相当。
A．顺序查找
B．二分查找
C．哈希查找
D．逆序查找
正确答案：B
-
第16题：
设二叉排序树中有n个结点，则在二叉排序树的平均查找长度为()。
答案：B解析：
-
第17题：
设有一个整数序列d{40，28，6，72，100，3，54}依次取出序列中的数，构造一棵二叉排序树。并对上述二叉排序树，在等概率条件下，求成功查找的平均查找长度。
（1）
（2）ASL=（1×1+2×2+3×3+4）/7=18/7
略 -
第18题：
设哈希表的地址范围为0～17，哈希函数为：H（key）=key%16。用线性探测法处理冲突，输入关键字序列：（10，24，32，17，31，30，46，47，40，63，49），构造哈希表，试回答下列问题：假定每个关键字的查找概率相等，求查找成功时的平均查找长度。
正确答案:对于黑色数据元素，各比较1次；共6次； 对红色元素则各不相同，要统计移位的位数。“63”需要6次，“49”需要3次，“40”需要2次，“46”需要3次，“47”需要3次，
所以ASL=1/11（6＋2＋3×3+6）＝23/11 -
第19题：
依次取a中各数据，构造一棵二叉排序树。 （1）对该二叉树进行查找，成功查找到38，和46各要进行多少次元素间的比较？ （2）给出按后序遍历该二叉排序树的序列。
正确答案: （1）4次；3次
（2）5，40，38，46，20，64，52 -
第20题：
假定一个顺序表的长度为40，并假定查找每个元素的概率都相同，则在查找成功情况下的平均查找长度（），在查找不成功情况下的平均查找长度（）。
正确答案:20.5；41 -
第21题：
对大小均为n的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查找成功，它们的平均查找长度是相同的，而对于查找失败，它们的平均查找长度是不同的。
正确答案:正确 -
第22题：
单选题在最坏的情况下，查找成功时二叉排序树的平均查找长度（）A小于顺序表的平均查找长度
B大于顺序表的平均查找长度
C与顺序表的平均查找长度相同
D无法与顺序表的平均查找长度比较
正确答案： A解析： 暂无解析 -
第23题：
判断题对大小均为n的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查找成功，它们的平均查找长度是相同的，而对于查找失败，它们的平均查找长度是不同的。A对
B错
正确答案： 对解析： 暂无解析 -
第24题：
填空题假定一个顺序表的长度为40，并假定查找每个元素的概率都相同，则在查找成功情况下的平均查找长度（），在查找不成功情况下的平均查找长度（）。正确答案： 20.5,41解析： 暂无解析
