对含n个记录的有序表进行折半查找,设每个记录的查找概率相等,则平均查找长度的数量级为()。
第1题:
A、50
B、25
C、10
D、7
第2题:
在查找算法中,可用平均查找长度(记为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)
第3题:
A、35/12
B、37/12
C、39/12
D、43/12
第4题:
在n个记录的有序顺序表中进行折半查找,最大的比较次数是(27)。
A.
B.
C.
D.
第5题:
● 对 n 个元素的有序表 A[1..n]进行二分(折半)查找,则成功查找到表中的任意一个元素时,最多与A 中的 (39) 个元素进行比较。
(39)
第6题:
A.15/7
B.17/7
C.18/7
D.19/7
第7题:
对长度为n的单链有序表,若查找每个元素的概率相等,则查找任一元素的平均查找长度为
A.n/2
B. (n+1) /2
C. (n-1) /2
D. n/4
第8题:
对22个记录的有序表作折半查找,当查找失败时,至少需要比较()次关键字。
A. 3
B. 4
C. 5
D. 6
第9题:
对长度为10的有序表进行折半查找,设在等概率时查找成功的平均查找长度是(46)。
A.2.9
B.3.1
C.3.4
D.2.6
第10题:
画出对长度为10的有序表进行折半查找的判定树(以序号1,2,……10表示树结点),并对上述序列进行折半查找,求等概率条件下,成功查找的平均查找长度。
(1)
(2)ASL=(1x1+2x2+3x4+4x3)/10=29/10
略