![](https://csdnimg.cn/release/download_crawler_static/88125509/bg1.jpg)
第九章 查找
一、 选择题
1.若查找每个记录的概率均等,则在具有 n 个记录的连续顺序文件中采用顺序查找法查找一
个记录,其平均查找长度 ASL 为( )。
A. (n-1)/2 B. n/2 C. (n+1)/2 D. n
2. 下面关于二分查找的叙述正确的是 ( )
A. 表必须有序,表可以顺序方式存储,也可以链表方式存储 C. 表必须有序,而且只
能从小到大排列
B. 表必须有序且表中数据必须是整型,实型或字符型 D. 表必须有序,且表只
能以顺序方式存储
3. 用二分(对半)查找表的元素的速度比用顺序法( )
A.必然快 B. 必然慢 C. 相等 D. 不能确定
4. 具有 12 个关键字的有序表,折半查找的平均查找长度( )
A. 3.1 B. 4 C. 2.5 D. 5
5.当采用分块查找时,数据的组织方式为 ( )
A.数据分成若干块,每块内数据有序
B.数据分成若干块,每块内数据不必有序,但块间必须有序,每块内最大(或最小)
的数据组成索引块
C. 数据分成若干块,每块内数据有序,每块内最大(或最小)的数据组成索引块
D. 数据分成若干块,每块(除最后一块外)中数据个数需相同
6. 二叉查找树的查找效率与二叉树的( (1))有关, 在 ((2))时其查找效率最低
(1): A. 高度 B. 结点的多少 C. 树型 D. 结点的位置
(2): A. 结点太多 B. 完全二叉树 C. 呈单枝树 D. 结点太复杂。
7. 对大小均为 n 的有序表和无序表分别进行顺序查找,在等概率查找的情况下,对于查找失
败,它们的平均查找长度是((1)) ,对于查找成功,他们的平均查找长度是((2))供选择的
答案:
A. 相同的 B.不同的
9.分别以下列序列构造二叉排序树,与用其它三个序列所构造的结果不同的是( )
A.(100,80, 90, 60, 120,110,130) B.(100,120,110,130,80, 60,
90)
C.(100,60, 80, 90, 120,110,130) D. (100,80, 60, 90, 120,130,110)
10. 在平衡二叉树中插入一个结点后造成了不平衡,设最低的不平衡结点为 A,并已知 A 的左
孩子的平衡因子为 0 右孩子的平衡因子为 1,则应作( ) 型调整以使其平衡。
A. LL B. LR C. RL D. RR
11. 下面关于 m 阶 B-树说法正确的是( )
①每个结点至少有两棵非空子树; ②树中每个结点至多有 m 一 1 个关键字;
③所有叶子在同一层上; ④当插入一个数据项引起 B 树结点分裂后,树
长高一层。
A. ①②③ B. ②③ C. ②③④ D. ③
12. m 阶 B-树是一棵( )
A. m 叉排序树 B. m 叉平衡排序树 C. m-1 叉平衡排序树 D. m+1 叉平衡排序树
15. 设有一组记录的关键字为{19,14,23,1,68,20,84,27,55,11,10,79},用链
地址法构造散列表,散列函数为 H(key)=key MOD 13,散列地址为 1 的链中有( )
个记录。
A.1 B. 2 C. 3 D. 4
16. 关于哈希查找说法不正确的有几个( )
(1)采用链地址法解决冲突时,查找一个元素的时间是相同的
(2)采用链地址法解决冲突时,若插入规定总是在链首,则插入任一个元素的时间是
相同的
(3)用链地址法解决冲突易引起聚集现象