对表长为n的有序表进行折半查找,其判定树的高度为 。
A.lg(n+1)
B.lg(n+1)-1
C.lgn
D.lg(n-1)
第1题:
A.O(n2)
B.O(nlogn)
C.O(n)
D.O(logn)
第2题:
对长度为n的顺序存储的有序表进行二分查找时,其对应的判定树的高度为(40)。
A.n
B.[log2n]
C.[log2(n+1)]
D.[log2n+1]
第3题:
● 对 n 个元素的有序表 A[1..n]进行二分(折半)查找,则成功查找到表中的任意一个元素时,最多与A 中的 (39) 个元素进行比较。
(39)
第4题:
在n个记录的有序顺序表中进行折半查找,最大的比较次数是(27)。
A.
B.
C.
D.
第5题:
设有序表为(13,19,25,36,48,51,63,84,91,116,135,200),元素的下标依次为1,2,……,12。画出对上述有序表进行折半查找所对应的判定树(树结点用下标表示)。
略
第6题:
画出对长度为10的有序表进行折半查找的判定树(以序号1,2,……10表示树结点),并对上述序列进行折半查找,求等概率条件下,成功查找的平均查找长度。
(1)
(2)ASL=(1x1+2x2+3x4+4x3)/10=29/10
略
第7题:
长度为20的有序表采用折半查找,共有()个元素的查找长度为3。
第8题:
对具有n个元素的有序表采用折半查找,则算法的时间复杂度为()。
第9题:
假定对长度n=50的有序表进行二分查找,则对应的判定树高度为(),判定树中前5层的结点数为(),最后一层的结点数为()。
第10题:
第11题:
第12题:
第13题:
A.O(n2)
B.O(nlogn)
C.O(n)
D.O(logn)
第14题:
在查找算法中,可用平均查找长度(记为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)
第15题:
对长度为10的有序表进行折半查找,设在等概率时查找成功的平均查找长度是(46)。
A.2.9
B.3.1
C.3.4
D.2.6
第16题:
线性表只要以()方式存储就能进行折半查找。
A链接
B顺序
C关键字有序的顺序
D二叉树
第17题:
设查找表为(20,19,24,57,68,11)在排序后的有序表的基础上,画出对其进行折半查找所对应的判定树。(要求以数据元素作为树结点)
略
第18题:
设有序列{10,12,15,19,22,25,100,130,150,200}画出对上述序列进行折半查找的判定树(以序列中的元素作为树的结点)。为了成功查找到100需要进行多少次元素间的比较?为了查找9,经过多少次元素间的比较可知道查找失败?
(1)
(2)4次;3次
略
第19题:
假定对长度n=50的有序表进行折半查找,则对应的判定树高度为(),最后一层的结点数为()。
第20题:
进行折半查找的表必须是顺序存储的有序表。
第21题:
线性表以()方式存储,能进行折半查找。
第22题:
O(n)
O(n2)
O(log2n)
O(1)
第23题:
关键字有序的顺序
顺序
链接
二叉树
第24题:
O(n)
O(n2)
O(1)
O(log2n)