在含有n个节点的二叉排序树中查找一个关键码，最多进行次比较 。A．n/2B．lgnC．lgn+1D．n
题目
在含有n个节点的二叉排序树中查找一个关键码，最多进行次比较 。
A．n/2
B．lgn
C．lgn+1
D．n
相似考题
更多“在含有n个节点的二叉排序树中查找一个关键码，最多进行次比较 。”相关问题
-
第1题：
从19个记录中查找其中的某个记录,最多进行4次关键字的比较,则采用的查找方法只可能是()。A、顺序查找
B、折半查找
C、哈希查找
D、二叉排序树查找
答案：C
-
第2题：
在包含1000个元素的线性表中实现如下各运算，哪一个所需的执行时间最短?
A．线性表按顺序方式存储，查找关键码值为666的节点
B．线性表按链接方式存储，查找关键码值为666的节点
C．线性表按顺序方式存储，查找线性表中第900个节点
D．线性表按链接方式存储，查找线性表中第900个节点
正确答案：C
解析：由顺序存储结构的特点，对于顺序表，可能通过计算直接确定第1个元素的存储地址。无论I多大，找顺序表中第I个元素所需的时间是相等的。所以C) 选项的操作执行的时间最短。 -
第3题：
下列问题是基于下图所示的二叉树：
在该二叉树中查找关键码值600，需要进行多少次关键码值比较? ( )
A．1
B．2
C．3
D．4
正确答案：D
-
第4题：
对n个元素的有序表A[1．．n]进行二分(折半)查找(除2取商时向下取整)，查找元素A[i](1≤i≤n)时，最多与A中的(57)个元素进行比较。
A．n
B．[log2n]-1
C．n／2
D．[log2n]+1
正确答案：D
解析：折半查找不成功时候需要比较次数最多，且最多不超过[log2n]+1次。 -
第5题：
在查找算法中，可用平均查找长度(记为ASL)来衡量一个查找算法的优劣，其定义为：
此处Pi为表中第i个记录被查找的概率，Ci为查找第i个记录时同关键字比较的次数，n为表中记录数。
以下叙述中均假定每一个记录被查找的概率相等，即Pi=//n(i=1，2，…，n)。当表中的记录连续存储在一个一维数组中时，可采用顺序查找与折半查找方法(折半查找要求表是按关键字有序排列的)。顺序查找时的ASL为(19)，折半查找时的ASL为(20)。记录的关键字有序时，用二叉排序树查找记录，在最坏的情况下，ASL为(21)。当二叉排序树是一棵平衡树时，ASL为(22)。在平衡树上删除一个结点后可以通过旋转使其平衡，最坏的情形下需(23)次旋转。
A．O(1)
B．O(log2n)
C．O(log2n2)
D．O(nlog2n)
E．O(n)
正确答案：E
-
第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题：
下图所示二叉树中查找关键码值200，需要进行多少次关键码值比较?
A．1
B．2
C．3
D．4
正确答案：C
解析：二叉排序树的特点是：每个结点上的左子树中所有的结点的关键码值都小于该结点的关键码值，而右子树中所有的关键码值都大于该结点的关键码值。二叉排序树的查找方法是，将待查关键码值与树根的关键码比较，若相等则查到，否则比较结果确定进入左子树或右子树，继续查找，如此进行下去，直到找到待查的关键码值，或确定二叉树中没有这样的关键码。在本题中对关键码200的查找如下：第一次：200236，进入左子树；第二次：200＞75，进入右子树；第三次：200＞100，而100没有右子树，查找完毕，此二叉树中没有这样的关键码。所以经过三次关键码值比较后，确定不含200这样的关键码，本题正确选项为C。 -
第8题：
在一棵非空的二叉排序树（二叉查找树)中，进行__ (41)遍历运算并输出所访问 结点的关键码后，可得到一个有序序列。
A.先序
B.中序
C.后序
D.层序
正确答案：B
本题考查数据结构基础知识。根据二叉排序树的定义，对于树中的每个结点，其左子树中的关键字均小于根结点的关键字，其右子树中的关键字均大于根结点的关键字，而中序遍历的次序是左子树、根结点、右子树，因此，对一个非空的二叉排序树进行中序遍历，所输出的关键码序列是递增有序序列。 -
第9题：
对n个元素的有序表A[i,j]进行顺序查找，其成功查找的平均查找长度（即在查找表中找到指定关键码的元素时，所进行比较的表中元素个数的期望值）为（ ）。A.n
B.（n+1）/2
C.log2n
D.n2答案：B解析：本题考查顺序查找方法。假设从前往后找，则所找元素为第1个元素时，与表中的1个元素作了比较，所找元素为第2个元素时，与表中的2个元素作了比较，……，所找元素为第n个元素时，与表中的n个元素作了比较，因此，平均查找长度等于（1+2+…+n）/n。 -
第10题：
对n个元素的有序表A［1..n］进行二分（折半）查找，则成功查找到表中的任意一个元素时，最多与A中的（）元素进行比较。
- A、n-1
- B、n/2
- C、（log2n）-1
- D、（log2n）+1
正确答案:D -
第11题：
从具有n个结点的二叉排序树中查找一个元素时，在平均情况下的时间复杂度大致为（ ）。
- A、 O（n）
- B、 O（1）
- C、 O（log2n）
- D、 O（n2）
正确答案:C -
第12题：
单选题从具有n个结点的二叉排序树中查找一个元素时，在最坏情况下的时间复杂度为（）。AO（n）
BO（1）
CO（log2n）
DO（n2）
正确答案： A解析： 暂无解析 -
第13题：
顺序查找n个元素的顺序表,若查找成功,则比较关键字的次数最多为()次。A、n/2
B、(n+1)/2
C、(n-1)/2
D、n
参考答案：D
-
第14题：
有二叉树如下图：
在该二叉树中查找关键码值200，需要进行 ______ 次关键码值比较。
A．1
B．2
C．3
D．4
正确答案：C
解析：从根开始：由于200比236小，搜索左子树；而200比75大，搜索右子树；而200比100大，搜索右子树，但结点100没有右子树，搜索结束。关键码比较次数为3。 -
第15题：
在该二叉树中查找关键码值200，需要进行多少次关键码值比较? ( )
A．1
B．2
C．3
D．4
正确答案：C
-
第16题：
●对n 个元素的有序表A[1．．n]进行顺序查找，其成功查找的平均查找长度（即在查找表中找到指定关键码的元素时，所进行比较的表中元素个数的期望值）为__(58)。
(58)
A． n
B． (n+1)／2
C． lOg2 n
D． n2
正确答案：B
-
第17题：
● 对 n 个元素的有序表 A[1..n]进行二分（折半）查找，则成功查找到表中的任意一个元素时，最多与A 中的 （39） 个元素进行比较。
（39）
正确答案：D
-
第18题：
在顺序表(6，10，16，18，25，28，30，48，50，52)中，用二分查找法查找关键码值20，则需要进行关键码比较次数为多少次?
A．2
B．3
C．4
D．不确定
正确答案：C
解析：第一次与25比较，第二次与10比较，第三次与16比较，第四次与 18比较，所以应比较4次。 -
第19题：
下列问题是基于如图所示的二叉树。
在该二叉树中查找关键码值502，需要进行多少次关键码值比较? ( )。
A．1
B．2
C．3
D．4
正确答案：C
解析：该二叉树是二叉搜索树(所有层次上，左子树的所有节点小于树根节点，右子树所有节点大于树根节点)，因此在图13-4扩充二叉树查找502，需依次同236、385、502三个关键码相比较。 -
第20题：
设二叉排序树的高度为h，则在该树中查找关键字key最多需要比较()次。
正确答案：n
-
第21题：
设有一个整数序列{50，38，16，82，110，13，64}，依次取出序列中的数，构造一棵二叉排序树。利用上述二叉排序树，为了查找110，经多少次元素间的比较能成功查到？为了查找15，经多少次元素间的比较可知道查找失败？
（1）
（2）三次；四次
略 -
第22题：
对于一棵有n个结点、深度为h的二叉排序树，当查找一个指定关键字的元素且查找失败时，最多需进行（）次比较。
正确答案:h -
第23题：
填空题对于一棵有n个结点、深度为h的二叉排序树，当查找一个指定关键字的元素且查找失败时，最多需进行（）次比较。正确答案： h解析： 暂无解析 -
第24题：
单选题从具有n个结点的二叉排序树中查找一个元素时，在平均情况下的时间复杂度大致为（ ）。AO（n）
BO（1）
CO（log2n）
DO（n2）
正确答案： D解析： 暂无解析
