第九章集合.doc

第九章 集合 一、 选择题 1.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为( C )。 A． (n-1)/2 B. n/2 C. (n+1)/2 D. n 2. 对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( A ) A．（N+1）/2 B. N/2 C. N D. [（1+N）*N]/2 3．顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较次数为（D）,二分法查找只适用于查找顺序存储的有序表，平均比较次数为（C）。 在此假定N为线性表中结点数，且每次查找都是成功的。 A.N+1 B.2log2N C.logN D.N/2 E.Nlog2N F.N2 4.下面关于二分查找的叙述正确的是 ( D ) A.表必须有序，表可以顺序方式存储，也可以链表方式存储 C.表必须有序，而且只能从小到大排列 B.表必须有序且表中数据必须是整型，实型或字符型 D.表必须有序，且表只能以顺序方式存储 5.对线性表进行二分查找时，要求线性表必须（ B ） A.以顺序方式存储 B.以顺序方式存储,且数据元素有序 C.以链接方式存储 D.以链接方式存储,且数据元素有序 6．适用于折半查找的表的存储方式及元素排列要求为( D ) A．链接方式存储，元素无序 B．链接方式存储，元素有序 C．顺序方式存储，元素无序 D．顺序方式存储，元素有序 7. 用二分（对半）查找表的元素的速度比用顺序法( D ) A． 必然快 B.必然慢 C.相等 D.不能确定 8．当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度(C ) A．必定快 B.不一定 C.在大部分情况下要快 D.取决于表递增还是递减 9.具有12个关键字的有序表，折半查找的平均查找长度（ A ） A. 3.1 B. 4 C. 2.5 D. 5 10.折半查找的时间复杂性为（D ） A. O（n2） B. O（n） C. O（nlogn） D. O（logn） 11．当采用分快查找时，数据的组织方式为 ( B ) A．数据分成若干块，每块内数据有序 B．数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块 C.数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块 D.数据分成若干块，每块（除最后一块外）中数据个数需相同 12.二叉查找树的查找效率与二叉树的(C)有关,在 (C)时其查找效率最低 (1): A.高度 B.结点的多少 C.树型 D.结点的位置 (2): A.结点太多 B.完全二叉树 C.呈单枝树 D.结点太复杂。 13.要进行顺序查找，则线性表（C）；要进行折半查询，则线性表（D）；若表中元素个数为n,则顺序查找的平均比较次数为（G）；折半查找的平均比较次数为（H）。 （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为(E ),有序表的折半查找的ASL为(B),对静态树表,在最坏情况下,ASL为(E ),而当它是一棵平衡树时,ASL为 (B ),在平衡树上删除一个结点后可以通过旋转使其平衡,在最坏情况下需(B)次旋转。供选择的答案： （1）（2）（3）（4）（5）: A. O(1) B. O( log2n ) C. O((log2n)2) D.O(nlog2n) E. O(n) 15.对大小均为n的有序表和无序表分别进行顺序查找,在等概率查找的情况下,对于查找失败,它们的平均查找长度是(B) ,对于查找成功,他们的平均查找长度是(A)供选择的答案: A.相同的 B.不同的 16．如果要求一个线性表既能较快的查找，又能适应动态变化的要求，则可采用( A )查找法。