第9章查找

第九章集合一、选择题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/2C.ND.[（1+N）*N]/23．顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较次数为（（1））,二分法查找只适用于查找顺序存储的有序表，平均比较次数为（（2））。在此假定N为线性表中结点数，且每次查找都是成功的。【长沙铁道学院1997四、3(4分)】A.N+1B.2log2NC.logND.N/2E.Nlog2NF.N24.下面关于二分查找的叙述正确的是()【南京理工大学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.取决于表递增还是递减【南京理工大学1997一、7（2分）】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.数据分成若干块，每块（除最后一块外）中数据个数需相同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.nB.n/2C.n*nD.n*n/2E.log2nF.nlog2nG.(n+1)/2H.log2(n+1)14．在等概率情况下,线性表的顺序查找的平均查找长度ASL为(（1）),有序表的折半查找的ASL为(（2）),对静态树表,在最坏情况下,ASL为(（3）),而当它是一棵平衡树时,ASL为(（4）),在平衡树上删除一个结点后可以通过旋转使其平衡,在最坏情况下需(（5）)次旋转。供选择的答案：【上海海运学院1999二、3（5分）】（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.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个关键字;③所有叶子在同一层上;④当插入一个数据项引起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分）】A.log2nB.1+log2nC.1+log2m21nD.1+log2n21m25.m路B+树是一棵(（1）)，其结点中关键字最多为(（2）)个，最少(（3）)个。【中科院计算机1999一、5】A.m路平衡查找树B.m路平衡索引树C.m路Ptrie树D.m路键树E.m-1F.mG.m+1H.2m-1I.2mJ.2m+126在一棵m阶的B+树中,每个非叶结点的儿子数S应满足().【武汉交通科技大学1996一、3(4分)】A.21m≤S≤mB.2m≤S≤mC.1≤S≤21mD.1≤S≤2m27.设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链地址法构造散列表，散列函数为H（key）=keyMOD13,散列地址为1的链中有（）个记录。【南京理工大学1997一、4（2分）】A．1B.2C.3D.428.下面关于哈希(Hash，杂凑)查找的说法正确的是()【南京理工大学1998一、10（2分）】A．哈希函数构造的越复杂越好，因为这样随机性好，冲突小B．除留余数法是所有哈希函数中最好的C．不存在特别好与坏的哈希函数，要视情况而定D．若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可29.若采用链地址法构造散列表，散列函数为H（key）=keyMOD17，则需(（1）)个链表。这些链的链首指针构成一个指针数组，数组的下标范围为(（2）)【南京理工大学1999一、12(13)（4分）】（1）A．17B.13C.16D.任意（2）A．0至17B.1至17C.0至16D.1至1630.关于杂凑查找说法不正确的有几个()【南京理工大学2000一、16（1.5分）】（1）采用链地址法解决冲突时，查找一个元素的时间是相同的（2）采用链地址法解决冲突时，若插入规定总是在链首，则插入任一个元素的时间是相同的（3）用链地址法解决冲突易引起聚集现象（4）再哈希法不易产生聚集A.1B.2C.3D.431.设哈希表长为14，哈希函数是H(key)=key%11,表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是()【南京理工大学2001一、15（1.5分）】A．8B．3C．5D．932.假定有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．kB.k+1C.k(k+1)/2D.1+k(k+1)/234.散列函数有一个共同的性质，即函数值应当以()取其值域的每个值。A.最大概率B.最小概率C.平均概率D.同等概率【西安电子科技大学2001应用一、7（2分）】【北京邮电大学1999一、4（2分）】35.散列表的地址区间为0-17,散列函数为H(K)=Kmod17。采用线性探测法处理冲突，并将关键字序列26，25，72，38，8，18，59依次存储到散列表中。（1）元素59存放在散列表中的【北方交通大学2001一、（19，20）（4分）】地址是（）。A．8B.9C.10D.11（2）存放元素59需要搜索的次数是（）。A．2B.3C.4D.536.将10个元素散列到100000个单元的哈希表中，则（）产生冲突。【北京邮电大学2001一、4（2分）】A.一定会B.一定不会C.仍可能会二、判断题1．采用线性探测法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位置置空，因为这会影响以后的查找。【长沙铁道学院1998一、3(1分)】2．在散列检索中，“比较”操作一般也是不可避免的。【华南理工大学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.哈希表的结点中只包含数据元素自身的信息，不包含任何指针。【山东大学2001一、6(1分)】9.若散列表的负载因子α1，则可避免碰撞的产生。【北京大学1994】10．查找相同结点的效率折半查找总比顺序查找高。【北京邮电大学2002一、8（1分）】11．用向量和单链表表示的有序表均可使用折半查找方法来提高查找速度。【中科院软件所1997一、6（1分）】12.在索引顺序表中，实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每块中元素个数有关。