思凯学习俱乐部
第九章 集合
一、 选择题
1.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为( )。【北京航空航天大学 2000 一、8 （2分）】
A． (n-1)/2 B. n/2 C. (n+1)/2 D. n 2. 对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( ) 【南京理工大学1998一、7（2分）】 A．（N+1）/2 B. N/2 C. N D. [（1+N）*N ]/2 3．顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较次数为（（1））,二分法查找只适用于查找顺序存储的有序表，平均比较次数为（（2））。 在此假定N为线性表中结点数，且每次查找都是成功的。【长沙铁道学院 1997 四、3 (4分)】
A.N+1 B.2log2N C.logN D.N/2 E.Nlog2N F.N2
4. 下面关于二分查找的叙述正确的是 ( ) 【南京理工大学 1996 一、3 （2分）】
A. 表必须有序，表可以顺序方式存储，也可以链表方式存储 C. 表必须有序，而且只能从小到大排列
B. 表必须有序且表中数据必须是整型，实型或字符型 D. 表必须有序，且表只能以顺序方式存储 5. 对线性表进行二分查找时，要求线性表必须（ ）【燕山大学 2001 一、5 （2分）】
A.以顺序方式存储 B.以顺序方式存储,且数据元素有序 C.以链接方式存储 D.以链接方式存储,且数据元素有序
6．适用于折半查找的表的存储方式及元素排列要求为( ) 【南京理工大学 1997 一、6 （2分）】
A．链接方式存储，元素无序 B．链接方式存储，元素有序
C．顺序方式存储，元素无序 D．顺序方式存储，元素有序 7. 用二分（对半）查找表的元素的速度比用顺序法( ) 【南京理工大学 1998 一、11 （2分）】
A． 必然快 B. 必然慢 C. 相等 D. 不能确定
8．当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，
也可用顺序查找，但前者比后者的查找速度( )
A．必定快 B.不一定 C. 在大部分情况下要快 D. 取决于表递增还是递减
中国在职研究生网
www.zzyjs.com
思凯学习俱乐部
【南京理工大学 1997 一、7 （2分）】
9. 具有12个关键字的有序表，折半查找的平均查找长度（ ）【中山大学 1998 二、10 （2分）】
A. 3.1 B. 4 C. 2.5 D. 5 10. 折半查找的时间复杂性为（ ）【中山大学 1999 一、15】
A. O（n2） B. O（n） C. O（nlogn） D. O（logn） 11．当采用分快查找时，数据的组织方式为 ( ) 【南京理工大学 1996 一、7 （2分）】
A．数据分成若干块，每块内数据有序
B．数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块
C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块
D. 数据分成若干块，每块（除最后一块外）中数据个数需相同 12. 二叉查找树的查找效率与二叉树的( （1）)有关, 在 (（2）)时其查找效率最低【武汉交通科技大学1996 一、2(4分)】
(1): A. 高度 B. 结点的多少 C. 树型 D. 结点的位置
(2): A. 结点太多 B. 完全二叉树 C. 呈单枝树 D.
结点太复杂。
13. 要进行顺序查找，则线性表（1）；要进行折半查询，则线性表（2）；若表中元素个数为n,则顺序查找的平均比较次数为（3）；折半查找的平均比较次数为（4）。【北方交通大学 1999 一、2 （4分）】 （1）（2）：A. 必须以顺序方式存储； B. 必须以链式方式存储；C. 既可以以顺序方式存储，也可以链式方式存储；
D. 必须以顺序方式存储，且数据已按递增或递减顺序
排好；
E. 必须以链式方式存储，且数据已按递增或递减的次
序排好。
（3）（4）：A.n B.n/2 C.n*n D.n*n/2 E.log2n F.nlog2n G.(n+1)/2 H.log2(n+1)
14．在等概率情况下,线性表的顺序查找的平均查找长度ASL为( （1） ),有序表的折半查找的ASL为( （2） ),对静态树表,在最坏情况下,ASL为( （3） ),而当它是一棵平衡树时,ASL为 ( （4） ),在平衡树上删除一个结点后可以通过旋转使其平衡,在最坏情况下需( （5） )次旋转。供选择的答案：【上海海运学院 1999 二、3 （5分）】 中国在职研究生网 www.zzyjs.com
思凯学习俱乐部
（1）（2）（3）（4）（5）: A. O(1) B. O( log2n ) C. O((log2n)2) D.O(nlog2n) E. O(n)
15. 对大小均为n的有序表和无序表分别进行顺序查找,在等概率查
找的情况下,对于查找失败,它们的平均查找长度是((1)) ,对于查找成功,他们的平均查找长度是((2))供选择的答案: 【上海海运学院 1997 二、4 （3分）】
A. 相同的 B.不同的 16．如果要求一个线性表既能较快的查找，又能适应动态变化的要求，
则可采用( )查找法。
A. 分快查找 B. 顺序查找 C. 折半查找 D. 基于属性
【西安电子科技大学 2001应用一、8 （2分）】
17. 既希望较快的查找又便于线性表动态变化的查找方法是 ( ) 【北方交通大学 2000 二、4 （2分）】 A．顺序查找 B. 折半查找 C. 索引顺序查找 D. 哈希法查找
18．分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( ) 【合肥工业大学2000一、4（2分）】
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)
19. 在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0右孩子的平衡因子为1,则应作( ) 型调整以使其平衡。【合肥工业大学 2001 一、4 （2分）】
A. LL B. LR C. RL D. RR 20．下列关于m阶B-树的说法错误的是( ) 【南京理工大学 1997 一、9 （2分）】
A．根结点至多有m棵子树 B．所有叶子都在同一层次上 C. 非叶结点至少有m/2 (m为偶数)或m/2+1（m为奇数）棵子树 D. 根结点中的数据是有序的
21. 下面关于m阶B树说法正确的是( ) 【南京理工大学 1999 一、5 （2分）】
①每个结点至少有两棵非空子树； ②树中每个结点至多有m一1个关键字;
③所有叶子在同一层上; ④当插入一个数据项引中国在职研究生网
www.zzyjs.com
思凯学习俱乐部
起B树结点分裂后，树长高一层。
A． ①②③ B. ②③ C. ②③④ D. ③
22. 下面关于B和B+树的叙述中，不正确的是( ) 【北方交通大学 2001 一、17 （2分）】
A. B树和B+树都是平衡的多叉树。 B. B树和B+树都可用于文件的索引结构。
C. B树和B+树都能有效地支持顺序检索。 D. B树和B+树都能有效地支持随机检索。
23. m阶B-树是一棵( ) 【北京邮电大学 2000 二、2 （20/8分）】
A. m叉排序树 B. m叉平衡排序树 C. m-1叉平衡排序树 D. m+1叉平衡排序树
24. 在一棵含有n个关键字的m阶B-树中进行查找，至多读盘( )次。【中科院计算所 2000 一、6 （2分）】
?m??n?1??2??2?nn
? D. A. log2 B. 1+log2 C. 1+log????n??m?1??2??2?? 1+log???25. m路B+树是一棵(（1）) ，其结点中关键字最多为(（2）)个，
最少(（3）)个。【中科院计算机 1999 一、5】
A. m路平衡查找树 B. m路平衡索引树 C. m路Ptrie树 D. m路键树 E. m-1 F. m G. m+1
?m??m??m??????? H. ?2?-1 I. ?2? J. ?2?+1
26在一棵m阶的B+树中, 每个非叶结点的儿子数S 应满足 ( ). 【武汉交通科技大学 1996 一、3 (4分) 】
?m?1??m??m?1????2???22???? ??A.≤S≤m B. ≤S≤m C. 1≤S≤
?m???D. 1≤S≤?2?
27. 设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，
11，10，79}，用链地址法构造散列表，散列函数为H（key）=key MOD 13,散列地址为1的链中有（ ）个记录。【南京理工大学 1997 一、4 （2分）】
A．1 B. 2 C. 3 D. 4
28. 下面关于哈希(Hash，杂凑)查找的说法正确的是( ) 【南京理工大学 1998 一、10 （2分）】
中国在职研究生网
www.zzyjs.com
思凯学习俱乐部
A．哈希函数构造的越复杂越好，因为这样随机性好，冲突小 B．除留余数法是所有哈希函数中最好的
C．不存在特别好与坏的哈希函数，要视情况而定
D．若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可
29. 若采用链地址法构造散列表，散列函数为H（key）=key MOD 17，
则需 (（1）) 个链表。这些链的链首指针构成一个指针数组，数组的下标范围为 (（2）) 【南京理工大学 1999 一、12(13) （4分）】 （1） A．17 B. 13 C. 16 D. 任意
（2） A．0至17 B. 1至17 C. 0至16 D. 1至16
30. 关于杂凑查找说法不正确的有几个( ) 【南京理工大学 2000 一、16 （1.5分）】
（1）采用链地址法解决冲突时，查找一个元素的时间是相同的 （2）采用链地址法解决冲突时，若插入规定总是在链首，则插
入任一个元素的时间是相同的
（3）用链地址法解决冲突易引起聚集现象 （4）再哈希法不易产生聚集
A. 1 B. 2 C. 3 D. 4
31. 设哈希表长为14，哈希函数是H(key)=key,表中已有数据的
关键字为15，38，61，84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是( ) 【南京理工大学 2001 一、15 （1.5分）】
A．8 B．3 C．5 D．9 32. 假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行多少次探测？( )
A．k-1次 B. k次 C. k+1次 D. k（k+1）/2次 【中国科技大学 1998 二、3 （2分）】【中科院计算所1998 二、3 （2分）】
33. 哈希查找中k个关键字具有同一哈希值，若用线性探测法将这k
个关键字对应的记录存入哈希表中，至少要进行( )次探测。【西安电子科技大学 1998 一、8 （2分）】
A． k B. k+1 C. k(k+1)/2 D.1+k(k+1)/2 34. 散列函数有一个共同的性质，即函数值应当以( )取其值域的每个值。
中国在职研究生网
www.zzyjs.com