第九章集合

第九章集合一、选择题1.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为(C)。A．(n-1)/2B.n/2C.(n+1)/2D.n2.对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为(A)A．（N+1）/2B.N/2C.ND.[（1+N）*N]/23．顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较次数为（D）,二分法查找只适用于查找顺序存储的有序表，平均比较次数为（C）。在此假定N为线性表中结点数，且每次查找都是成功的。A.N+1B.2log2NC.logND.N/2E.Nlog2NF.N24.下面关于二分查找的叙述正确的是(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.1B.4C.2.5D.510.折半查找的时间复杂性为（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.nB.n/2C.n*nD.n*n/2E.log2nF.nlog2nG.(n+1)/2H.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)查找法。A.分快查找B.顺序查找C.折半查找D.基于属性17.既希望较快的查找又便于线性表动态变化的查找方法是(C)A．顺序查找B.折半查找C.索引顺序查找D.哈希法查找18．分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是(C)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,则应作(C)型调整以使其平衡。A.LLB.LRC.RLD.RR20．下列关于m阶B-树的说法错误的是(D)A．根结点至多有m棵子树B．所有叶子都在同一层次上C.非叶结点至少有m/2(m为偶数)或m/2+1（m为奇数）棵子树D.根结点中的数据是有序的21.下面关于m阶B树说法正确的是(B)①每个结点至少有两棵非空子树；②树中每个结点至多有m一1个关键字;③所有叶子在同一层上;④当插入一个数据项引起B树结点分裂后，树长高一层。A．①②③B.②③C.②③④D.③22.下面关于B和B+树的叙述中，不正确的是(C)A.B树和B+树都是平衡的多叉树。B.B树和B+树都可用于文件的索引结构。C.B树和B+树都能有效地支持顺序检索。D.B树和B+树都能有效地支持随机检索。23.m阶B-树是一棵(B)A.m叉排序树B.m叉平衡排序树C.m-1叉平衡排序树D.m+1叉平衡排序树24.在一棵含有n个关键字的m阶B-树中进行查找，至多读盘(C)次。A.log2nB.1+log2nC.1+logD.1+log25.m路B+树是一棵(B)，其结点中关键字最多为(F)个，最少(I)个。A.m路平衡查找树B.m路平衡索引树C.m路Ptrie树D.m路键树E.m-1F.mG.m+1H.-1I.J.+126在一棵m阶的B+树中,每个非叶结点的儿子数S应满足(A).A.≤S≤mB.≤S≤mC.1≤S≤D.1≤S≤27.设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链地址法构造散列表，散列函数为H（key）=keyMOD13,散列地址为1的链中有（D）个记录。A．1B.2C.3D.428.下面关于哈希(Hash，杂凑)查找的说法正确的是(C)A．哈希函数构造的越复杂越好，因为这样随机性好，冲突小B．除留余数法是所有哈希函数中最好的C．不存在特别好与坏的哈希函数，要视情况而定D．若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可29.若采用链地址法构造散列表，散列函数为H（key）=keyMOD17，则需(A)个链表。这些链的链首指针构成一个指针数组，数组的下标范围为(C)（1）A．17B.13C.16D.任意（2）A．0至17B.1至17C.0至16D.1至1630.关于杂凑查找说法不正确的有几个(B)（1）采用链地址法解决冲突时，查找一个元素的时间是相同的（2）采用链地址法解决冲突时，若插入规定总是在链首，则插入任一个元素的时间是相同的（3）用链地址法解决冲突易引起聚集现象（4）再哈希法不易产生聚集A.1B.2C.3D.431.设哈希表长为14，哈希函数是H(key)=key%11,表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是(D)A．8B．3C．5D．932.假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行多少次探测？(D)A．k-1次B.k次C.k+1次D.k（k+1）/2次33.哈希查找中k个关键字具有同一哈希值，若用线性探测法将这k个关键字对应的记录存入哈希表中，至少要进行(C)次探测。A．kB.k+1C.k(k+1)/2D.1+k(k+1)/234.散列函数有一个共同的性质，即函数值应当以(D)取其值域的每个值。A.最大概率B.最小概率C.平均概率D.同等概率35.散列表的地址区间为0-17,散列函数为H(K)=Kmod17。采用线性探测法处理冲突，并将关键字序列26，25，72，38，8，18，59依次存储到散列表中。（1）元素59存放在散列表中的地址是（D）。A．8B.9C.10D.11（2）存放元素59需要搜索的次数是（C）。A．2B.3C.4D.536.将10个元素散列到100000个单元的哈希表中，则（C）产生冲突。A.一定会B.一定不会C.仍可能会二、判断题1．采用线性探测法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位置置空，因为这会影响以后的查找。T2．在散列检索中，“比较”操作一般也是不可避免的。T3．散列函数越复杂越好，因为这样随机性好，冲突概率小.F4．哈希函数的选取平方取中法最好。F5．Hash表的平均查找长度与处理冲突的方法无关。F6．负载因子(装填因子)是散列表的一个重要参数，它反映散列表的装满程度。T7.散列法的平均检索长度不随表中结点数目的增加而增加，而是随负载因子的增大而增大。T8.哈希表的结点中只包含数据元素自身的信息，不包含任何指针。F9.若散列表的负载因子α1，则可避免碰撞的产生。F10．查找相同结点的效率折半查找总比顺序查找高。F11．用向量和单链表表示的有序表均可使用折半查找方法来提高查找速度。F12.在索引顺序表中，实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每块中元素个数有关。T13.顺序查找法适用于存储结构为顺序或链接存储的线性表。T14.折半查找法的查找速度一定比顺序查找法快。F15.就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。F16．对无序表用二分法查找比顺序查找快。F17．对大小均为n的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查找成功，它们的平均查找长度是相同的，而对于查找失败，它们的平均查找长度是不同的。T18．任一查找树(二叉分类树)的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间.F19．最佳二叉树是AVL树（平衡二叉树）。T20．在查找树（二叉树排序树）中插入一个新结点，总是插入到叶结点下面。F21．完全二叉树肯定是平衡二叉树。F22．对一棵二叉排序树按前序方法遍历得出的结点序列是从小到大的序列。F23．二叉树中除叶结点外,任一结点X，其左子树根结点的值小于该结点（X）的值；其右子树根结点的值≥该结点（X）的值,则此二叉树一定是二叉排序树。F24．有n个数存放在一维数组A[1..n]中，在进行顺序查找时，这n个数的排列有序或无序其平均查找长度不同。F25.N个结点的二叉排序树有多种，其中树高最小的二叉排序树是最佳的。T26.在任意一棵非空二叉排序树中，删除某结点后又将其插入，则所得二排序叉树与原二排序叉树相同。F27.设T为一棵平衡树，在其中插入一个结点n，然后立即删除该结点后得到T1，则T与T1必定相同。F28.将线性表中的结点信息组织成平衡的二叉树，其优点之一是总能保证任意检索长度均为log2n量级（n为线形表中的结点数目）。T29.B-树中所有结点的平衡因子都为零。T30.在m阶B-树中每个结点上至少有个关键字，最多有m个关键字。F31.虽然信息项序列的顺序不一样，但依次生成的二叉排序树却是一样的。F32.在9阶B-树中，除叶子以外的任意结点的分支数介于5和9之间。T33.B-树的插入算法中，通过结点的向上“分裂”，代替了专门的平衡调整。T34.在平衡二叉树中，向某个平衡因子不为零的结点的树中插入一新结点，必引起平衡旋转。F35.二叉排序树删除一个结点后，仍是二叉排序树。T36.B+树既能索引查找也能顺序查找。T三、填空题1.顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为__N_次；当使用监视哨时，若查找失败，则比较关键字的次数为_n+1_。2.在顺序表（8,11,15,19,25,26,30,33,42,48,50