第九章查找
1.若有18个元素的有序表存放在一维数组A[19]中,第一个元素放A[1]中,现进行二分查找,则查找A[ 3]的比较序列的下标依次为()
A. 1 ,2,3
B. 9 ,5,2,3
C. 9 ,5,3
D. 9 ,4,2,3
2.设二叉排序树中有n 个结点,则在二叉排序树的平均平均查找长度为( )。
A. O(1)
B. O(log 2n)
C. O(n)
D. O(n 2)
5?设有序表中有1000个元素,则用二分查找查找元素X最多需要比较()次。
A. 25
B. 10
C. 7
D. 1
6.顺序查找不论在顺序线性表中还是在链式线性表中的时间复杂度为( )。
2 1/2
A. O(n)
B. O(n 2)
C. O(n 1/2)
D. O(1og2n) 8.( )二叉排序树可以得到一个从小到大的有序序列。
A. 先序遍历
B. 中序遍历
C. 后序遍历
D. 层次遍历
9.设一组初始记录关键字序列为(13,18,24,35,47,50,62,83,90,115,134), 则利用二分法查找关键字90 需要比较的关键字个数为( )。A. 1 B. 2 C. 3 D. 4
10?设某散列表的长度为100,散列函数H(k)=k %P,贝U P通常情况下最好选择 ( )。
A. 99
B. 97
C. 91
D. 93
11.在二叉排序树中插入一个关键字值的平均时间复杂度为( )。
A. O(n)
B. O(1og 2n)
C. O(nlog 2n)
D. O(n )
12.设一个顺序有序表A[1:14] 中有14个元素,则采用二分法查找元素A[4] 的过程中比较元素的顺序为( ) 。
A. A[1] ,A[2] ,A[3] ,A[4]
B.A[1] ,A[14] ,A[7] ,A[4]
C.A[7] ,A[3] ,A[5] ,A[4]
D. A[7] ,A[5] ,A[3] ,A[4]
13. 设散列表中有m个存储单元,散列函数H(key)= key %p,则p最好选择()。
A.小于等于m的最大奇数
B.小于等于m的最大素数
C.小于等于m的最大偶数
D. 小于等于m的最大合数
14. 设顺序表的长度为n,则顺序查找的平均比较次数为( )。
A. n
B. n/2
C. (n+1)/2
D. (n-1)/2
15. 设有序表中的元素为(13,18,24,35,47,50,62),则在其中利用二分
法查找值为24的元素需要经过( )次比较。
A. 1
B. 2
C. 3
D. 4
17. 设有一组初始记录关键字序列为(34,76,45,18,26,54,92),则由这
组记录关键字生成的二叉排序树的深度为( )。
A. 4
B. 5
C. 6
D. 7
18. 二叉排序树中左子树上所有结点的值均( )根结点的值。
A. <
B. >
C. =
D. !=
26. 对一棵二叉排序树采用中根遍历进行输出的数据一定是( )
A. 递增或递减序列
B. 递减序列
C. 无序序列
D. 递增
序列
27. 一个有序表为{1 ,3,9,12,32,41 ,45,62,75,77,82,95,100} ,当
二分查找值为82的结点时,查找成功时的比较次数为(
) A.1 B.2 C.4 D.8
28 .若构造一棵具有n 个结点的二叉排序树,最坏的情况下其深度不超过()
30. 在对查找表的查找过程中,若被查找的数据元素不存在,则把该数据元素插 入到集合中。这种方式主要适合于()
A.静态查找表
B.动态查找表
C.静态查找表与动态查找表
D.静态查找表或动态查找表
31. 设一组记录的关键字 key 值为{62,50,14,28,19, 35, 47,56, 83},散 列函数为H (key )=key mod13,则它的开散列表中散列地址为1的链中的结点个 数是()
A. 1
B.2 C . 3 D.4
32. 已知一个有序表为(13,18,24,35,47,50,62,83,90,115,134),
当二分检索值为90的元素时,检索成功需比较的次数是( )
A.1
B.2
C.3
D.4
36. 设有100个元素,用二分法查找时,最大比较次数是(
)。 A. 25 B . 7 C. 10
D . 1 37. 设有1000个元素,用二分法查找时,最小比较次数为(
) A . 0 B . 1 C. 10 D
. 500 40.
在一个有N 个元素的有序单链表中查找具有给定关键字的结点,
平均情况下 的时间复杂性为(B )
A.O (1)
B.O (N )
C.0 (N 2)
D.O (NlogN )
41. 对线性表进行二分查找时,要求线性表必须( )
A.以顺序方式存储
B.以顺序方式存储,且数据元素有序
C.以链接方式存储
D. 以链接方式存储,且数据元素有序
42. 下列二叉排序树中查找效率最高的是()
A.平衡二叉树
B. 二叉查找树
C.没有左子树的二叉排序树
D.没有右子树的二叉排序树
44.分别以下列序列构造二叉排序树,与用其它三个序列所构造的结果不同的是 ()
A.(100,80,90,60,120,110,130)
B.(100,120,110,130,80,60,90)
C.(100,60,80,90, 20,110,130)
D.(100,80,60,90,120,130,110)
50.设哈希表长 M=14哈希函数 H(KEY)=KEY MOD 11表中已有 4个结点:
ADDR(15)=4 ADDR(38)=5, ADDR(61)=6 ADDR(84)=7 其余地址为空,如用二 次探测再散列处理冲突,关键字为 49的结点的地址是()
A. 8
B. 3
C. 5
D. 9 52 .将10个元素散列到100000个单元的哈希表中,则(
)产生冲突
A. 一定会
B. 一定不会
C.仍可能会
55.二叉查找树的查找效率与二叉树的树型有关,在()
A.
B. n
C.
D. n+1
时其查找效率最低。
A.结点太多
B. 完全二叉树
C.呈单枝树
D.结点太复杂
64.对于长度为18的顺序存储的有序表,若采用二分查找,则查找第15个元素的查找长度为()。
A. 3
B. 4
C. 5
D. 6
二、填空题
7 ?根据初始关键字序列(19 , 22, 01 , 38,10)建立的二叉排序树的高度为
12 ?设二叉排序树的高度为h,则在该树中查找关键字key最多需要比较
________ 。
13?设散列表的长度为8,散列函数H(k)=k %7,用线性探测法解决冲突,则根据一组初始关键字序列(8 , 15, 16, 22, 30, 32)构造出的散列表的平均查找长度是。16. ________________________________________ 解决散列表冲突的两种方法是_______________________________________________ 和_____________________ 。
18.从一棵二叉搜索树中查找一个元素时,若元素的值等于根结点的值,则表明,若元素的值小于根结点的值,则继续向找,若元素的大于根结点的值,则继续向找。
20. 二叉搜索树的中序遍历得到的结点序列为_ _ 。
27. ________________________________ 在一棵二叉排序树上按历得到的结点序列是一个有序序列。
28. 实现二分查找的存储结构仅限于顺序存储结构,且其中元素排列必须是—的。
31. __________________________________________________ 一棵平衡二叉树中任一结点的平衡因子只可能是______________________________ 。
32. ______________________________ 二分查找的时间复杂度为。
41.在线性表的_________ 储中,对每一个元素只能采用顺序查找。
48?对于二分查找所对应的判定树,它既是一棵__________ 又是一棵 _________ 。
64. 平衡二叉树又称____________ 其定义是________ 。
69.在含有n个结点的二叉排序树中查找一个关键字,进行关键字比较次数最大值是___________ 。
72.动态查找表和静态查找表的重要区别在于前者包含有______________________ 和__________ 算,而后者不包含这两种运算。
83.在一棵二叉排序树中,每个分支结点的左子树上所有结点的值一定该结点的值,右子树上所有结点的值一定____________________________ 该结点的值。86.向一棵二叉排序树中插入一个元素时,若元素的值小于根结点的值,则接着向根结点的___________ 插入,若元素的值大于根结点的值,贝U接着向根结点的
________ 插入。
89.在一棵平衡二叉排序树中,每个结点的左子树高度与右子树高度之差的绝对值不超过______________ 。
四、简答题
6.对长度为20的有序表进行二分查找,试画出它的一棵判定树
8?—个线性表为B= (12, 23, 45, 57, 20, 03, 78, 31, 15, 36),设散列表为HT[0..12],散列函数为H(key) = key % 13并用线性探查法解决冲突,请画出散列表,并计算等概率情况下查找成功的平均查找长度。
21. 一棵二叉排序树结构如下,各结点的值从小到大依次为1-9,请标出各结点的值。
22. 在查找和排序算法中,监视哨的作用是什么?
23. 输入一个正整数序列(53,17,12,66,58,70,87,25,56,60 ),试完成下列各题。
(1)按次序构造一棵二叉排序树BS (2)依此二叉排序树,如何得到一个从大到小的有序序列?
(2)画出在此二叉排序树中删除“ 66”后的树结构。
五、应用题
3.已知待散列的线性表为(36,15,40,63,22),散列用的一维地址空间为[0.. 6], 假定选用的散列函数是H( K)= K mod7,若发生冲突采用线性探查法处理,试:
(1)计算出每一个元素的散列地址并在下图中填写出散列表:
' 0 1 2 3 4 5 6
(2)求出在查找每一个元素概率相等情况下的平均查找长度。
11 ?依次输入表{ 30, 15, 28, 20, 24, 10, 12, 68, 35, 50, 46, 55 } 中的元素,生成一棵二叉搜索树。
①试画出生成之后的二叉搜索树;
②对该二叉搜索树进行中序遍历,试写出遍历序列。
③假定每个元素的查找概率相等,试计算该二叉搜索树的平均查找长度。
18 ?假定一个待散列存储的线性表为(32,75,29,63,48,94,25,46,18,70) ,散列地址空间为HT[13],若采用除留余数法构造散列函数和线性探查法处理冲突,试求出每一元素的散列地址,画出最后得到的散列表,求出平均查找长度。