网友您好， 请在下方输入框内输入要搜索的题目：
题目内容
（请给出正确答案）
2、对表长为n的有序表进行折半查找，其判定树的高度为 。
A．lg(n+1)
B．lg(n+1)-1
C．lgn
D．lg(n-1)
参考答案和解析
[log2n]+1
更多 “2、对表长为n的有序表进行折半查找，其判定树的高度为 。A．lg(n+1)B．lg(n+1)-1C．lgnD．lg(n-1)” 相关考题
考题
设查找表为(7,15,21,22,40,58,68,80,88,89,120) ,元素的下标依次为1,2,3,……, 11.(1)画出对上述查找表进行折半查找所对应的判定树(树中结点用下标表示)(2)说明成功查找到元素40需要经过多少次比较?(3)求在等概率条件下,成功查找的平均比较次数?
考题
设查找表为(50,60,75,85,96,98,105,110,120,130)(1)说出进行折半查找成功查找到元素120需要进行多少次元素间的比较?(2)为了折半查找元素95，经过多少次元素间的比较才能确定不能查到?(3)画出对上述有序表进行折半查找所对应的判定树(要求以数据元素作为树结点)。
考题
对n个元素的有序表A[1．．n]进行二分(折半)查找(除2取商时向下取整)，查找元素A[i](1≤i≤n)时，最多与A中的(57)个元素进行比较。A．nB．[log2n]-1C．n／2D．[log2n]+1
考题
在查找算法中，可用平均查找长度(记为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)
考题
对n个元素的有序表A[i,j]进行顺序查找，其成功查找的平均查找长度（即在查找表中找到指定关键码的元素时，所进行比较的表中元素个数的期望值）为（ ）。A.n
B.（n+1）/2
C.log2n
D.n2
考题
设有序表为（13，19，25，36，48，51，63，84，91，116，135，200），元素的下标依次为1，2，……，12。画出对上述有序表进行折半查找所对应的判定树（树结点用下标表示）。
考题
单选题对具有n个元素的有序表采用折半查找，则算法的时间复杂度为（）。A
O（n）B
O（n2）C
O（1）D
O（log2n）
热门标签
最新试卷