习题第九章查找

第九章查找一、选择题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.下面关于二分查找的叙述正确的是()【南京理工大学1996一、3（2分）】A.表必须有序，表可以顺序方式存储，也可以链表方式存储C.表必须有序，而且只能从小到大排列B.表必须有序且表中数据必须是整型，实型或字符型D.表必须有序，且表只能以顺序方式存储4.对线性表进行二分查找时，要求线性表必须（）【燕山大学2001一、5（2分）】A.以顺序方式存储B.以顺序方式存储,且数据元素有序C.以链接方式存储D.以链接方式存储,且数据元素有序5．适用于折半查找的表的存储方式及元素排列要求为()【南京理工大学1997一、6（2分）】A．链接方式存储，元素无序B．链接方式存储，元素有序C．顺序方式存储，元素无序D．顺序方式存储，元素有序6．当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度()A．必定快B.不一定C.在大部分情况下要快D.取决于表递增还是递减【南京理工大学1997一、7（2分）】7．当采用分快查找时，数据的组织方式为()【南京理工大学1996一、7（2分）】A．数据分成若干块，每块内数据有序B．数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块C.数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块D.数据分成若干块，每块（除最后一块外）中数据个数需相同8.二叉查找树的查找效率与二叉树的(（1）)有关,在(（2）)时其查找效率最低【武汉交通科技大学1996一、2(4分)】(1):A.高度B.结点的多少C.树型D.结点的位置(2):A.结点太多B.完全二叉树C.呈单枝树D.结点太复杂。9.要进行顺序查找，则线性表（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)10．如果要求一个线性表既能较快的查找，又能适应动态变化的要求，则可采用()查找法。A.分快查找B.顺序查找C.折半查找D.基于属性【西安电子科技大学2001应用一、8（2分）】11.既希望较快的查找又便于线性表动态变化的查找方法是()【北方交通大学2000二、4（2分）】A．顺序查找B.折半查找C.索引顺序查找D.哈希法查找12．分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是()【合肥工业大学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)13.散列表的地址区间为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.514.将10个元素散列到100000个单元的哈希表中，则（）产生冲突。【北京邮电大学2001一、4（2分）】A.一定会B.一定不会C.仍可能会15.设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链地址法构造散列表，散列函数为H（key）=keyMOD13,散列地址为1的链中有（）个记录。【南京理工大学1997一、4（2分）】A．1B.2C.3D.416.下面关于哈希(Hash，杂凑)查找的说法正确的是()【南京理工大学1998一、10（2分）】A．哈希函数构造的越复杂越好，因为这样随机性好，冲突小B．除留余数法是所有哈希函数中最好的C．不存在特别好与坏的哈希函数，要视情况而定D．若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可17.若采用链地址法构造散列表，散列函数为H（key）=keyMOD17，则需(（1）)个链表。这些链的链首指针构成一个指针数组，数组的下标范围为(（2）)【南京理工大学1999一、12(13)（4分）】（1）A．17B.13C.16D.任意（2）A．0至17B.1至17C.0至16D.1至1618.设哈希表长为14，哈希函数是H(key)=key%11,表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是()【南京理工大学2001一、15（1.5分）】A．8B．3C．5D．919.假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行多少次探测？()A．k-1次B.k次C.k+1次D.k（k+1）/2次【中国科技大学1998二、3（2分）】【中科院计算所1998二、3（2分）】20.哈希查找中k个关键字具有同一哈希值，若用线性探测法将这k个关键字对应的记录存入哈希表中，至少要进行()次探测。【西安电子科技大学1998一、8（2分）】A．kB.k+1C.k(k+1)/2D.1+k(k+1)/2三、填空题1.在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找关键码值20，需做的关键码比较次数为___.【北方交通大学2001二、2】2.给定一组数据{6，2，7，10，3，12}以它构造一棵哈夫曼树，则树高为_______，带权路径长度WPL的值为________。【南京理工大学1997三、4（2分）】3.己知有序表为(12,18,24,35,47,50,62,83,90,115，134)当用二分法查找90时，需________次查找成功，47时________成功，查100时，需_______次才能确定不成功。【南京理工大学2000二、7（4.5分）】4.平衡二叉树又称______，其定义是___。【青岛大学2001六、3（3分）】5.在哈希函数H（key）=key%p中，p值最好取__。【青岛大学2002三、9（2分）】6．假定有k个关键字互为同义词，若用线性探测再散列法把这k个关键字存入散列表中，至少要进行___次探测。【西安电子科技大学2001软件一、7（2分）】7.执行顺序查找时，储存方式可以是__(1)__，二分法查找时，要求线性表__(2)_，分块查找时要求线性表__(3)__，而散列表的查找，要求线性表的存储方式是__(4)__。【山东大学1998一、1(3分)】8.平衡因子的定义是___【北京轻工业学院2000一、2（2分）】9.假设有n个关键字，它们具有相同的Hash函数值，用线性探测方法解决冲突，把这n个关键字散列到大小为n的地址空间中，共计需要做___次插入和探测操作。【武汉大学2000一、8】10.可以唯一的标识一个记录的关键字称为______。【燕山大学1998一、7（1分）】11.已知二叉排序树的左右子树均不为空，则___上所有结点的值均小于它的根结点值，___上所有结点的值均大于它的根结点的值。【燕山大学1998一、8（2分）】12.动态查找表和静态查找表的重要区别在于前者包含有_____和______运算，而后者不包含这两种运算。【厦门大学2001一、3（14%/5分）】13.已知N元整型数组a存放N个学生的成绩，已按由大到小排序，以下算法是用对分（折半）查找方法统计成绩大于或等于X分的学生人数，请填空使之完善。(C语言）#defineN/*学生人数*/intuprx(inta[N],intx)/*函数返回大于等于X分的学生人数*/{inthead=1,mid,rear=N;do{mid=(head+rear)/2;if(x=a[mid])__(1)__else__(2)_;}while(__(3)__);if(a[head]x)returnhead-1;returnhead;}【西南交通大学2000一、12】四、应用题1.设有一组关键字{9,01,23,14,55,20,84,27}，采用哈希函数：H（key）=keymod7，表长为10，用开放地址法的二次探测再散列方法Hi=(H(key)+di)mod10(di=12,22,32,…,)解决冲突。要求：对该关键字序列构造哈希表。【东北大学2002二、2（5分）】2.对下面的关键字集{30,15,21,40,25,26,36,37}若查找表的装填因子为0.8，采用线性探测再散列方法解决冲突，做：（1）设计哈希函数；（2）画出哈希表；【东北大学2001六(18分)】由于装填因子为0.8，关键字有8个，所以表长为8/0.8=10。3.设哈希表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中4.设一组数据为{1,14,27,29,55,68,10,11,23}，现采用的哈希函数是H(key)=keyMOD13，即关键字对13取模，冲突用链地址法解决，设哈希表的大小为13(0..12)，试画出插入上述数据后的哈希表。【南京理工大学1996三、3（5分）】5.设哈希函数H（k）=3Kmod11，散列地址空间为0～10，对关键字序列（32,13,49,24,38,21,4,12）按下述两种解决冲突的方法构造哈希表（1）线性探测再散列（2）链地址法，6.使用散列函数hashf(x)=xmod11,把一个整数值转换成散列表下标，现要把数据：1,13,12,34,38,33,27,22插入到散列表中。（1）使用线性探查再散列法来构造散列表。（5分）（2）使用链地址法构造散列表。（5分）7.设散列函数为H（K）=KMOD13，给定的键值序列为13,41,15,44,06,68,12,25,38,64,19,49，画出用链地址法处理冲突构造得的哈希表。【福州大学1998三、3(6分)】8.已知散列表的地址空间为A[0..11]，散列函数H（k）=kmod11，采用线性探测法处理冲突。请将下列数据{25,16,38,47,79,82,51,39,89,151,231}依次插入到散列表中.【合肥工业大学2000四、3（5分）】9.设输入的关键字序列为：22,41,53,33,46,30,13,01,67,Hash函数为：H（key）=keyMOD11。HASH表长度为11。试用线性探测法解决冲突，将各关键字按输入顺序填入Hash表中。【南京航空航天大学1998二（10分）】10.已知关键字序列R={11,4,3,2,17,30,19}，请按算法步骤：【北方交通大学1996四】（1）构造一棵哈夫曼树，并计算出它的带权路径长度WPL（7分）11.按下述次序输入关键字：e,i,p,k,,m,l,b,试画出AVL树的构造与调整过程。（要求画出每插入一个关