第九章 集合

《第九章 集合》由会员分享，可在线阅读，更多相关《第九章 集合（9页珍藏版）》请在装配图网上搜索。

1、第九章 集合一、 选择题1若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一 个记录，其平均查找长度ASL为（）。【北京航空航天大学2000 、8 （2分）】A （n-1）/2B. n/2C. （n+1）/2D. n2. 对 N 个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为（）【南京理工大学1998一、 7（2分）】A（N+1）/2B. N/2 C. N D. （1+N）*N /23顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较次数为 （1）,二分法 查找只适用于查找顺序存储的有序表，平均比较次数为（2）。在此假定N为线性表中 结点数

2、，且每次查找都是成功的。【长沙铁道学院 1997 四、 3 （4分）】A. N+1B.2logNC.logND.N/2E.NlogNF.N24. 下面关于二分查找的叙述正确的是 （） 【南京理工大学 1996 一、 3 （2分）】A. 表必须有序，表可以顺序方式存储，也可以链表方式存储 C. 表必须有序，而且只 能从小到大排列B. 表必须有序且表中数据必须是整型，实型或字符型D. 表必须有序，且表只能以顺序方式存储5. 对线性表进行二分查找时，要求线性表必须（ ）【燕山大学 2001 一、 5 （2分）】A. 以顺序方式存储 B. 以顺序方式存储,且数据元素有序 C. 以链接方式存储 D. 以

3、链接方式存储,且数据元素有序6适用于折半查找的表的存储方式及元素排列要求为（）【南京理工大学 1997 一、6（2分）】A.链接方式存储，元素无序B.链接方式存储，元素有序C. 顺序方式存储，元素无序D.顺序方式存储，元素有序7. 用二分（对半）查找表的元素的速度比用顺序法（） 【南京理工大学 1998 一、 11 （2分）】A 必然快B. 必然慢 C. 相等 D. 不能确定8当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但 前者比后者的查找速度（）A.必定快 B.不一定 C.在大部分情况下要快 D.取决于表递增还是递减 【南京理工大学 1997 一、 7 （2分）

4、】9. 具有12个关键字的有序表，折半查找的平均查找长度（ ）【中山大学 1998 二、10（2 分）】A. 3.1B. 4C. 2.5D. 510. 折半查找的时间复杂性为（ ）【中山大学 1999 一、 15】A. O（ n2）B. O（ n）C. O（ nlogn）D. O（ logn）11当采用分快查找时，数据的组织方式为 （） 【南京理工大学 1996 一、 7（2分）】A. 数据分成若干块，每块内数据有序B. 数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小） 的数据组成索引块C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块D. 数据

5、分成若干块，每块（除最后一块外）中数据个数需相同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. 必须以链式方式

6、存储； C. 既可以以顺序方式存储，也可以链式方式存储；D. 必须以顺序方式存储，且数据已按递增或递减顺序排好；E. 必须以链式方式存储，且数据已按递增或递减的次序排好。（3）（4）：A.nB.n/2 C.n*n D.n*n/2 E.log n F.nlog n G.（n+1）/2H.log （n+1）14. 在等概率情况下，线性表的顺序查找的平均查找长度ASL为（1），有序表的折半查 找的ASL为（2）,对静态树表,在最坏情况下,ASL为（3）,而当它是一棵平衡树时,ASL 为 （4） ），在平衡树上删除一个结点后可以通过旋转使其平衡，在最坏情况下需（5） ） 次旋转。供选择的答案：【上海海

7、运学院 1999 二、3 （5 分）】（ 1 ）（ 2 ）（ 3 ）（ 4）（ 5） :A.O（1）B. O （ log n）C.O（logn）2）D.O （nlog n）E. O（n）15. 对大小均为 n 的有序表和无序表分别进行顺序查找,在等概率查找的情况下,对于查找 失败,它们的平均查找长度是（1） ,对于查找成功,他们的平均查找长度是（2）供选 择的答案: 【上海海运学院 1997 二、4 （3分）】A.相同的B.不同的16. 如果要求一个线性表既能较快的查找，又能适应动态变化的要求，则可采用（）查找法。A. 分快查找B. 顺序查找C. 折半查找D. 基于属性【西安电子科技大学 20

8、01 应用一、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. 在平衡二叉树中插入一个结点后造

9、成了不平衡，设最低的不平衡结点为A,并已知A的左孩子的平衡因子为 0右孩子的平衡因子为 1,则应作（） 型调整以使其平衡。【合肥工业大学 2001 一、4 （2 分）】A. LLB. LRC. RLD. RR20. 下列关于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个关键字；所有叶子在同一

10、层上；当插入一个数据项引起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

11、 （2 分）】D. 1+logA. lognB. 1+logn C. 1+log25. m路B+树是一棵(1)，其结点中关键字最多为(2)个，最少(3)个。【中科 院计算机 1999 一、5】A. m 路平衡查找树 B. m 路平衡索引树 C. m 路 Ptrie 树 D. m 路键树 E. m-1F. m G. m+1H. -1 I. J. +126在一棵m阶的B+树中，每个非叶结点的儿子数S应满足().【武汉交通科技大学 1996 一、3 (4分) 】A.WSWmB.WSWmC. 1WSWD. 1WSW27. 设有一组记录的关键字为19， 14， 23， 1， 68， 20， 84， 27

12、， 55， 11， 10， 79，用链 地址法构造散列表，散列函数为H (key) =key MOD 13,散列地址为1的链中有()个记录。【南京理工大学 1997 一、4 (2 分)】A1B. 2C. 3D. 428. 下面关于哈希(Hash,杂凑)查找的说法正确的是()【南京理工大学1998 一、10 ( 2 分)】A. 哈希函数构造的越复杂越好，因为这样随机性好，冲突小B. 除留余数法是所有哈希函数中最好的C. 不存在特别好与坏的哈希函数，要视情况而定D. 若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删 去即可29.30.若采用链地址法构造散列表，散列函数为 H

13、(key) =key MOD 17，则需 (1) ) 个链 表。这些链的链首指针构成一个指针数组，数组的下标范围为 (2) ) 【南京理工 大学 1999 一、 12(13)(4分)】( 1 ) A17B. 13(2) A0 至17B. 1 至 17关于杂凑查找说法不正确的有几个(1) 采用链地址法解决冲突时，查找一个元素的时间是相同的(2) 采用链地址法解决冲突时，若插入规定总是在链首，则插入任一个元素的时间是相同的(3) 用链地址法解决冲突易引起聚集现象(4) 再哈希法不易产生聚集A. 1B. 2C. 3C. 16D. 任意C. 0至16D. 1 至 16【南京理工大学 2000 一、 1

14、6 (1.5分)】D. 431. 设哈希表长为14,哈希函数是H(key)=key%11,表中已有数据的关键字为15，38，61，84 共四个，现要将关键字为 49 的结点加到表中，用二次探测再散列法解决冲突， 则放入的位置是() 【南京理工大学 2001 一、 15 (1.5分)】A8B3C5D932. 假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行多少次探测？()A. k-1 次B. k 次 C. k+1 次 D. k (k+1) /2 次【中国科技大学 1998 二、 3 (2分)】【中科院计算所1998 二、 3 (2分)】33哈希查找中k个关键字具有

15、同一哈希值,若用线性探测法将这k个关键字对应的记录存 入哈希表中，至少要进行()次探测。【西安电子科技大学 1998 一、 8 (2分)】A. kB. k+1 C. k(k+1)/2D.1+k(k+1)/234. 散列函数有一个共同的性质，即函数值应当以()取其值域的每个值。A. 最大概率B. 最小概率C. 平均概率D. 同等概率【西安电子科技大学 2001 应用一、 7 (2 分)】 【北京邮电大学 1999 一、 4 (2 分)】35. 散列表的地址区间为0-17,散列函数为 H（K）=K mod 17。采用线性探测法处理冲突，并 将关键字序列 26，25，72，38，8，18，59 依次

16、存储到散列表中。）。1）元素 59 存放在散列表中的【北方交通大学 2001 一、（19，20）（4 分）】地址是（D. 11D. 5）产生冲突【。北京邮电大学 2001A 8B. 9C. 102）存放元素59 需要搜索的次数是（）。A 2B. 3C. 436. 将10 个元素散列到100000个单元的哈希表中，则（、4 （2 分）】A. 一定会 B. 一定不会 C. 仍可能会二、 判断题 1采用线性探测法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所 在位置置空，因为这会影响以后的查找。【长沙铁道学院 1998 一、3 （1 分）】 2在散列检索中，“比较”操作一般也是不可避

17、免的。【华南理工大学 2001 一、4 （1 分）】 3散列函数越复杂越好，因为这样随机性好，冲突概率小. 【南京理工大学 1997 二、5 （2 分）】4哈希函数的选取平方取中法最好。 【青岛大学 2000 四、7 （1 分）】5. Hash表的平均查找长度与处理冲突的方法无关。【南京航空航天大学1997 、9 （1 分）】6. 负载因子 （装填因子）是散列表的一个重要参数，它反映散列表的装满程度。【中科院软 件所 1999 六（1-3）（2 分）】7. 散列法的平均检索长度不随表中结点数目的增加而增加，而是随负载因子的增大而增大。 【中山大学 1994 一、 8 （2 分）】8. 哈希表的

18、结点中只包含数据元素自身的信息，不包含任何指针。 【山东大学 2001 一 、6 （1 分 ） 】9. 若散列表的负载因子a 1，则可避免碰撞的产生。【北京大学1994】10. 查找相同结点的效率折半查找总比顺序查找高。 【北京邮电大学 2002 一、 8 （1分）】11. 用向量和单链表表示的有序表均可使用折半查找方法来提高查找速度。 【中科院软件 所 1997 一、 6 （ 1 分）】12. 在索引顺序表中，实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中元 素个数有关，而且与每块中元素个数有关。【上海交通大学 1998 一、 17】13. 顺序查找法适用于存储结构为顺序或链接存

19、储的线性表。【山东大学 2001 一、 1 （1 分）】14. 折半查找法的查找速度一定比顺序查找法快 。【山东大学 2001 一、 8 （1 分）】15. 就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。【西安交通大学 1996 二、 3 （3 分 ）】16. 对无序表用二分法查找比顺序查找快。【青岛大学 2002 一、 8 （1 分）】17. 对大小均为n的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查找 成功，它们的平均查找长度是相同的，而对于查找失败，它们的平均查找长度是不同的。【上海海运学院 1995 一、 11（1 分） 1998 一、 12 （1 分）

20、】18. 任一查找树（二叉分类树）的平均查找时间都小于用顺序查找法查找同样结点的线性表 的平均查找时间.【上海海运学院 1997 一、 10 （1 分）】19. 最佳二叉树是AVL树（平衡二叉树）。【北京大学1994】20. 在查找树（二叉树排序树）中插入一个新结点，总是插入到叶结点下面。 【上海海运 学院 1999 一、 8 （1 分）】21. 完全二叉树肯定是平衡二叉树。 【南京航空航天大学 1996 六、 5 （1 分）】22. 对一棵二叉排序树按前序方法遍历得出的结点序列是从小到大的序列。 【南京航空航 天大学 1995 五、 4 （ 1 分）】23. 二叉树中除叶结点外，任一结点X,

21、其左子树根结点的值小于该结点（X）的值；其右 子树根结点的值三该结点（X）的值，则此二叉树一定是二叉排序树。【北京邮电大学1998一、4 （2 分）】24有n个数存放在一维数组Al.n中，在进行顺序查找时，这n个数的排列有序或无序 其平均查找长度不同。【北京邮电大学 1998 一、6 （2 分）】25. N 个结点的二叉排序树有多种，其中树高最小的二叉排序树是最佳的。 【上海交通大 学 1998 一、9】26. 在任意一棵非空二叉排序树中，删除某结点后又将其插入，则所得二排序叉树与原二排 序叉树相同。【中科院软件所 1997 】27. 设T为一棵平衡树，在其中插入一个结点n,然后立即删除该结点

22、后得到人，则T与人 必定相同。【上海交通大学 1998 一、11】28. 将线性表中的结点信息组织成平衡的二叉树，其优点之一是总能保证任意检索长度均为 log2n量级（n为线形表中的结点数目）。【中山大学1994 一、9 （2分）】29. B-树中所有结点的平衡因子都为零。【大连海事大学2001 一、（1, 17）（1分）】30. 在m阶B-树中每个结点上至少有个关键字，最多有m个关键字。【东北大学1997二、 4 （2 分）】31. 虽然信息项序列的顺序不一样，但依次生成的二叉排序树却是一样的【。长沙铁道学院 1998 一、9（1分）】32. 在9阶B-树中，除叶子以外的任意结点的分支数介于

23、5和9之间。【合肥工业大学2001二、9 （1分）】33. B-树的插入算法中，通过结点的向上“分裂”代替了专门的平衡调整。【华南理工大学2001 一、3 （1 分）】34. 在平衡二叉树中，向某个平衡因子不为零的结点的树中插入一新结点，必引起平衡旋转。【南京理工大学 1997 二、 3 （2分）】35. 二叉排序树删除一个结点后，仍是二叉排序树。【青岛大学 2000 四、 4 （1 分）】36. B+树既能索引查找也能顺序查找。【青岛大学2002 一、10 （1分）】第 9 章 集合选择题1.C2.A3.1D3.2C4.D5.B6.D7.D&C9.A10.D11.B12.1C12.2C13.

24、1C13.2D13.3G13.4H14.1E14.2B14.3E14.4B14.5B15.1B15.2A16.A17.C18.C19.C20.D21.B22.C23.B24.C25.1B25.2F25.3I26.A27.D28.C29.1A29.2C30.B31.D32.D33.C34.D35.1D35.2C36.C判断题1. V2. V3. X4. X5. X6. V7. V& X9. X10.X11.X12.V13.V14.X15.X16.X17.V18.X19.V20.X21.X22.X23.X24.X25.V26.X27.X28.V29.V30.X31.X32.V33.V34.X35.

25、V36.V部分答案解释如下。4不能说哪种哈希函数的选取方法最好，各种选取方法有自己的适用范围。 8哈希表的结点中可以包括指针，指向其元素。11单链表不能使用折半查找方法。20按插入后中序遍历是递增序列的原则，若某结点只有右子树，而插入元素的关键字小于 该结点的关键字，则会插入到该结点的左侧，成为其左孩子。这种插入就不是插入到叶子下 面。21从平衡因子定义看，完全二叉树任一结点的平衡因子的绝对值确实是小于等于1。但是， 平衡二叉树本质上是二叉排序树，完全二叉树不一定是排序树。故不能说完全二叉树是平衡 二叉树。23某结点的左子树根结点不一定是它的中序前驱，其右子树根结点也不一定是它的中序后 继。24在等概率下，查找成功时的平均查找长度相同，查找失败时的平均查找长度不相同。 26只有被删除结点是叶子结点时命题才正确。