设二叉排序树的高度为h，则在该树中查找关键字key最多需要比较()次。
题目
设二叉排序树的高度为h，则在该树中查找关键字key最多需要比较()次。
相似考题
更多“设二叉排序树的高度为h,则在该树中查找关键字key最多需要比较()次。 ”相关问题
-
第1题：
结点数目为n的二叉查找树(二叉排序树)的最小高度为(56)、最大高度为(57)。A.AB.B结点数目为n的二叉查找树（二叉排序树）的最小高度为（56）、最大高度为（57）。
A.A
B.B
C.C
D.D
正确答案：D
本题考查二叉排序树的基本构造特点。若二叉树中有n个结点，则结点分布均匀、且高度最小的树的特点是除了最后一层，其余各层的结点数目都达到最大值（第i层上有2i-1个结点），此时树的高度为[log2(n+1)]。若每层只有一个结点，则树的高度为n。具有三个结点的二叉树的所有形态如下所示，每层只有一个结点时称为单枝树。二叉排序树是根据输入序列构造的，当序列呈现有序的特点时，就构造出一棵单枝树。 -
第2题：
● 用关键字序列10、20、30、40、50构造的二叉排序树（二叉查找树）为 （63） 。
正确答案：C
-
第3题：
设二叉排序树中有n个结点，则在二叉排序树的平均查找长度为()。
答案：B解析：
-
第4题：
设二叉排序树上有n个结点，则在二叉排序树上查找结点的平均时间复杂度为()。
答案：D解析：
-
第5题：
设哈希表的地址范围为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 -
第6题：
依次取a中各数据，构造一棵二叉排序树。 （1）对该二叉树进行查找，成功查找到38，和46各要进行多少次元素间的比较？ （2）给出按后序遍历该二叉排序树的序列。
正确答案: （1）4次；3次
（2）5，40，38，46，20，64，52 -
第7题：
设哈希表的地址范围为0～17，哈希函数为：H（key）=key%16。用线性探测法处理冲突，输入关键字序列：（10，24，32，17，31，30，46，47，40，63，49），构造哈希表，试回答下列问题：若查找关键字63，需要依次与哪些关键字进行比较？
正确答案:查找63,首先要与H(63)=63%16=15号单元内容比较，即63与31比较 ,不匹配; 然后顺移，与46,47,32,17,63相比，一共比较了6次！ -
第8题：
将关键字（45，87，30，33，63，27，51，76）依次插入到一棵初始为空的二叉排序树中。请回答：若在二叉排序树中插入新的关键字60，则为寻找插入位置，分别与哪些关键字进行比较。
正确答案:若在二叉排序树中插入新的关键字60，则为寻找插入位置，分别与关键字45,87,63,51进行比较。 -
第9题：
问答题设哈希表的地址范围为0～17，哈希函数为：H（key）=key%16。用线性探测法处理冲突，输入关键字序列：（10，24，32，17，31，30，46，47，40，63，49），构造哈希表，试回答下列问题：若查找关键字60，需要依次与哪些关键字比较？正确答案： 查找60,首先要与H(60)=60%16=12号单元内容比较，但因为12号单元为空（应当有空标记），所以应当只比较这一次即可。解析： 暂无解析 -
第10题：
填空题对于一棵有n个结点、深度为h的二叉排序树，当查找一个指定关键字的元素且查找失败时，最多需进行（）次比较。正确答案： h解析： 暂无解析 -
第11题：
单选题设二叉排序树中有n个结点，则在二叉排序树的平均平均查找长度为（）。AO（1）
BO（log2n）
CO（n4）
DO（n2）
正确答案： C解析： 暂无解析 -
第12题：
问答题依次取a中各数据，构造一棵二叉排序树。 （1）对该二叉树进行查找，成功查找到38，和46各要进行多少次元素间的比较？ （2）给出按后序遍历该二叉排序树的序列。正确答案： （1）4次；3次
（2）5，40，38，46，20，64，52解析： 暂无解析 -
第13题：
用关键字序列10、20、30、40、50构造的二叉排序树(二叉查找树)为(63)。
A．
B．
C．
D．
正确答案：C
解析：二叉排序树又称二叉查找树，它可以是一棵空树，若非空时具有下述性质：
1．若根结点的左子树非空，则左子树上所有结点的关键字值均小于等于根结点的关键字值。
2．若根结点的右子树非空，则右子树上所有结点的关键字值均大于等于根结点的关键字值。
3．根结点的左、右子树也分别为二叉排序树。
构造二叉排序树过程如下：
首先与根结点比较，如果小于等于则进入左边子树，再与左边子树的根节点比较，直到找到它要放的位置，否则进入右子树，进行上述操作。 -
第14题：
以下关于二叉排序树(或二叉查找树、二叉搜索树)的叙述中，正确的是( )
A.对二叉排序树进行先序、中序和后序遍历，都得到结点关键字的有序序列
B.含有N个结点的二叉排序树高度为【log2n】+1
C.从根到任意二个叶子结点的路径上，结点的关键字呈现有序排列的特点
D.从左到右排列同层次的结点，’其关键字呈现有序排列的特点
正确答案：D
-
第15题：
以下关于二叉排序树的说法正确的是()。Ⅰ.在二叉排序树中，每个结点的关键字都比左孩子关键字大，比右孩子关键字小Ⅱ.每个结点的关键字都比左孩子关键字大，比右孩子关键字小，这样的二叉树都是二叉排序树Ⅲ，在二叉排序树中，新插入的关键字总是处于最底层Ⅳ.在二叉排序树中，新结点总是作为叶子结点来插入的Ⅴ.二叉排序树的查找效率和二叉排序树的高度有关A.Ⅰ、Ⅱ、Ⅳ、Ⅴ
B.Ⅱ、Ⅲ、Ⅳ
C.Ⅰ、Ⅲ、Ⅴ
D.Ⅰ、Ⅳ、Ⅴ答案：D解析：在二叉排序树中，新插入的关键字总是作为叶子结点来插入的，但是叶子结点不一定总是处于最底层。对于二叉排序树，左子树上所有记录的关键字均小于根记录的关键字；右子树上所有记录的关键字均大于根记录的关键字。而不是仅仅与左、右孩子的关键字进行比较。 -
第16题：
设二叉排序树中关键字由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序列形成的不是一条路径，而是有分支的，可见它是不可能在查找过程中访问到的序列。 -
第17题：
对于一棵有n个结点、深度为h的二叉排序树，当查找一个指定关键字的元素且查找失败时，最多需进行（）次比较。
正确答案:h -
第18题：
依次插入关键字（51， 37，60，54，49，32，79，27，36）生成二叉排序树，则查找关键字值54（查找成功），需做的关键字比较次数为（）；查找关键字值22（查找失败），需做的关键字比较次数为（）
正确答案:3；4 -
第19题：
设关键字序列为（71，12，88，53，11，25，65，27，16），散列函数为H（key）= key % 7，采用链地址法解决冲突。请回答：查找关键字88时，需要依次与哪些关键字比较。
正确答案:查找关键字88时，分别与25,11,53,88比较。 -
第20题：
设关键字序列为（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 -
第21题：
问答题设关键字序列为（71，12，88，53，11，25，65，27，16），散列函数为H（key）= key % 7，采用链地址法解决冲突。请回答：查找关键字88时，需要依次与哪些关键字比较。正确答案： 查找关键字88时，分别与25,11,53,88比较。解析： 暂无解析 -
第22题：
填空题依次插入关键字（51， 37，60，54，49，32，79，27，36）生成二叉排序树，则查找关键字值54（查找成功），需做的关键字比较次数为（）；查找关键字值22（查找失败），需做的关键字比较次数为（）正确答案： 3,4解析： 暂无解析 -
第23题：
判断题向二叉排序树中插入一个结点需要比较的次数可能大于该二叉树的高度。( )A对
B错
正确答案： 对解析：