第6课查找

第六课查找一、选择题1．若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为（）。A．(n-1)/2B．n/2C．(n+1)/2D．n2．对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为（）。A．（N+1）/2B．N/2C．ND．[（1+N）*N]/23．顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较次数为（）。在此假定N为线性表中结点数，且每次查找都是成功的。A．N+1B．2log2NC．log2ND．N/2E．Nlog2NF．N24．二分法查找只适用于查找顺序存储的有序表，平均比较次数为（）。在此假定N为线性表中结点数，且每次查找都是成功的。A．N+1B．2log2NC．log2ND．N/2E．Nlog2NF．N25．对线性表进行二分查找时，要求线性表必须（）。A．以顺序方式存储B．以顺序方式存储,且数据元素有序C．以链接方式存储D．以链接方式存储,且数据元素有序6．适用于折半查找的表的存储方式及元素排列要求为（）。A．链接方式存储，元素无序B．链接方式存储，元素有序C．顺序方式存储，元素无序D．顺序方式存储，元素有序7．用二分（对半）查找表的元素的速度比用顺序法（）。A．必然快B．必然慢C．相等D．不能确定8．当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度（）。A．必定快B．不一定C．在大部分情况下要快D．取决于表递增还是递减9．具有12个关键字的有序表，折半查找的平均查找长度（）。A．3.1B．4C．2.5D．510．折半查找的时间复杂性为（）。A．O（n2）B．O（n）C．O（nlog2n）D．O（log2n）11．当采用分块查找时，数据的组织方式为（）。A．数据分成若干块，每块内数据有序B．数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块C．数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块D．数据分成若干块，每块（除最后一块外）中数据个数需相同12．二叉查找树的查找效率与二叉树的（）有关。A．高度B．结点的多少C．树型D．结点的位置13．二叉查找树在（）时其查找效率最低。A．结点太多B．完全二叉树C．呈单枝树D．结点太复杂14．在平衡树上删除一个结点后可以通过旋转使其平衡，在最坏情况下需（）次旋转。A．O(1)B．O(log2n)C．O((log2n)2)D．O(nlog2n)E．O(n)15．下面关于二分查找的叙述正确的是（）。A．表必须有序，表可以顺序方式存储，也可以链表方式存储B．表必须有序且表中数据必须是整型，实型或字符型C．表必须有序，而且只能从小到大排列D．表必须有序，且表只能以顺序方式存储16．如果要求一个线性表既能较快的查找，又能适应动态变化的要求，则可采用（）查找法。A．分块查找B．顺序查找C．折半查找D．基于属性17．既希望较快的查找又便于线性表动态变化的查找方法是（）。A．顺序查找B．折半查找C．索引顺序查找D．哈希法查找18．分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是（）。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，则应作（）型调整以使其平衡。A．LLB．LRC．RLD．RR20．下列关于m阶B-树的说法错误的是（）。A．根结点至多有m棵子树B．所有叶子都在同一层次上C．非叶结点至少有m/2(m为偶数)或m/2+1（m为奇数）棵子树D．根结点中的数据是有序的21．下面关于m阶B树说法正确的是（）。①每个结点至少有两棵非空子树②树中每个结点至多有m-1个关键字③所有叶子在同一层上④当插入一个数据项引起B树结点分裂后，树长高一层A．①②③B．②③C．②③④D．③22．m阶B-树是一棵（）。A．m叉排序树B．m叉平衡排序树C．m-1叉平衡排序树D．m+1叉平衡排序树23．在一棵含有n个关键字的m阶B-树中进行查找，至多读盘（）次。A．log2nB．1+log2nC．1+log2m21nD．1+log2n21m24．将10个元素散列到100000个单元的哈希表中，则（）产生冲突。A．一定会B．一定不会C．仍可能会25．设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链地址法构造散列表，散列函数为H（key）=keyMOD13，散列地址为1的链中有（）个记录。A．1B．2C．3D．426．下面关于哈希(Hash，杂凑)查找的说法正确的是（）。A．哈希函数构造的越复杂越好，因为这样随机性好，冲突小B．除留余数法是所有哈希函数中最好的C．不存在特别好与坏的哈希函数，要视情况而定D．若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可27．关于哈希查找，下列说法中不正确的有（）个。（1）采用链地址法解决冲突时，查找一个元素的时间是相同的（2）采用链地址法解决冲突时，若插入规定总是在链首，则插入任一个元素的时间是相同（3）用链地址法解决冲突易引起聚集现象（4）再哈希法不易产生聚集A．1B．2C．3D．428．设哈希表长为14，哈希函数是H(key)=key%11,表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是（）。A．8B．3C．5D．929．假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行（）次探测。A．k-1次B．k次C．k+1次D．k（k+1）/2次30．散列表的地址区间为0-17,散列函数为H(K)=Kmod17。采用线性探测法处理冲突，并将关键字序列26，25，72，38，8，18，59依次存储到散列表中，则元素59存放在散列表中的地址是（）。A．8B．9C．10D．11二、应用题1．回答问题并填空（1）散列表存储的基本思想是什么？（2）散列表存储中解决碰撞的基本方法有哪些？其基本思想是什么？（3）用线性探查法解决碰撞时，如何处理被删除的结点？为什么？（4）散列法的平均检索长度不随（）的增加而增加，而是随（）的增大而增加。2．如何衡量hash函数的优劣？hash方法的平均查找路长决定于什么？是否与结点个数N有关？3．在采用线性探测法处理冲突的散列表中，所有同义词在表中是否一定相邻？4．设有一组关键字{9,01,23,14,55,20,84,27}，采用哈希函数：H（key）=keymod7，表长为10，用开放地址法的二次探测再散列方法Hi=(H(key)+di)mod10(di=12,22,32,…,)解决冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。5．对下面的关键字集{30,15,21,40,25,26,36,37}，若查找表的装填因子为0.8，采用线性探测再散列方法解决冲突，试：（1）设计哈希函数；（2）画出哈希表；（3）计算查找成功和查找失败的平均查找长度；（4）写出将哈希表中某个数据元素删除的算法。6．设哈希表a、b分别用向量a[0..9],b[0..9]表示，哈希函数均为H（key）=keyMOD7，处理冲突使用开放定址法，Hi=[H(key)+Di]MOD10,在哈希表a中Di用线性探测再散列法，在哈希表b中Di用二次探测再散列法,试将关键字{19,24,10,17,15,38,18,40}分别填入哈希表a,b中,并分别计算出它们的平均查找长度ASL。7．采用哈希函数Ｈ（k）=3*kmod13并用线性探测开放地址法处理冲突，在数列地址空间［0..12］中对关键字序列22,41,53,46,30,13,1,67,51执行（1）构造哈希表（画示意图）；（2）计算装填因子；（3）计算等概率下成功的平均查找长度；（4）计算不成功的平均查找长度。8．设一组数据为{1,14,27,29,55,68,10,11,23}，现采用的哈希函数是H(key)=keyMOD13，即关键字对13取模，冲突用链地址法解决，设哈希表的大小为13(0..12)，试画出插入上述数据后的哈希表。9．设散列表长度为14，散列函数h(x)=2i，其中i为键值中第一个字母在字母表中的序号，若键值的输入顺序为Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec，用拉链法处理冲突，要求：（1）构造散列表；（2）求出在等概率情况下，查找成功的平均查找长度。10．若在哈希表中删除一个记录，应如何操作？为什么？已知一组关键字为（19,14,23,01,68,20,84,27,55,11,10,79）按哈希函数H(Key)=KeyMOD13和线性探测再散列处理冲突的方法在地址空间A[0..15]中构造哈希表。11．设哈希函数H（k）=3Kmod11，散列地址空间为0～10，对关键字序列（32,13,49,24,38,21,4,12）按下述两种解决冲突的方法构造哈希表：（1）线性探测再散列（2）链地址法，并分别求出等概率下查找成功时和查找失败时的平均查找长度ASLsucc和ASLunsucc。12．使用散列函数hashf(x)=xmod11,把一个整数值转换成散列表下标，现要把数据：1,13,12,34,38,33,27,22插入到散列表中。要求：（1）使用线性探查再散列法来构造散列表；（2）使用链地址法构造散列表。（3）针对这两种情况，确定其装填因子，查找成功所需的平均探查次数，以及查找不成功所需的平均探查次数。13．已知长度为12的表(Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec)，要求：（1）试按表中元素的顺序依次插入一棵初始为空的分类二叉树，试画出插入完成之后的分类二叉树并计算其在等概率查找情况下，查找成功的平均查找长度；（2）试用以下两种方法构造两个Hash表，Hash函数H(K)=[i/2],其中i为关键字K中第一个字母在字母表中的序号，[x]表示取整数。a．用线性探测开放定址法处理冲突(散列地址空间为0～16)；b．用链地址法处理,然后分别求出这两个Hash表在等概率查找情况下，查找成功的平均查找长度。14．设散列函数为H（K）=KMOD13，给定的键值序列为13,41,15,44,06,68,12,25,38,64,19,49，画出用链地址法处理冲突构造得的哈希表。15．设散列函数H(k)=Kmod7,散列表的地址空间为0-6，对关键字序列{32,13,49,18,22,38,21}按链地址法处理冲突的办法构造哈希表，并指出查找各关键字要进行几次比较。16．选取哈希函数Ｈ（key）=keymod7，用链地址法解决冲突。试在0~6的散列地址空间内对关键字序列｛31,23,17,27,19,11,13,91,61,41｝构造哈希表，并计算在等概率下成功查找的平均查找长度。17．设散列函数为H(K)=KMOD11,解决冲突的方法为链接法，试将下列关键字集合{35,67,42,21,29,86,95,47,50,36,91}依次插入到散列表中（画出散列表的示意图）。并计算平均查找长度ASL。18．已知散列表的地址空间为A[0..11]，散列函数H（k）=kmod11，采用线性探测法处理冲突。请将下列数据{25,16,38,47,79,82,51,39,89,151,231}依次插入到散列表中，并计算出在等概率情况下查找成功时的平均查找长度。19．设输入的关键字序列为：22,41,53,33,46,30,13,01,67,Hash函数为：H