您好,欢迎访问三七文档
当前位置:首页 > 商业/管理/HR > 质量控制/管理 > 第八章查找习题_数据结构
习题八查找一、单项选择题1.顺序查找法适合于存储结构为()的线性表。A.散列存储B.顺序存储或链式存储C.压缩存储D.索引存储2.若查找每个记录的概率均等,则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录,其平均查找长度ASL为()。A.(n-1)/2B.n/2C.(n+1)/2D.n3.适用于折半查找的表的存储方式及元素排列要求为()A.链接方式存储,元素无序B.链接方式存储,元素有序C.顺序方式存储,元素无序D.顺序方式存储,元素有序4.当在一个有序的顺序存储表上查找一个数据时,即可用折半查找,也可用顺序查找,但前者比后者的查找速度()A.必定快B.不一定C.在大部分情况下要快D.取决于表递增还是递减5.当采用分块查找时,数据的组织方式为()A.数据分成若干块,每块内数据有序B.数据分成若干块,每块内数据不必有序,但块间必须有序,每块内最大(或最小)的数据组成索引块C.数据分成若干块,每块内数据有序,每块内最大(或最小)的数据组成索引块D.数据分成若干块,每块(除最后一块外)中数据个数需相同6.二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这种说法()。A.正确B.错误7.二叉查找树的查找效率与二叉树的((1))有关,在((2))时其查找效率最低。(1):A.高度B.结点的多少C.树型D.结点的位置(2):A.结点太多B.完全二叉树C.呈单枝树D.结点太复杂。8.如果要求一个线性表既能较快的查找,又能适应动态变化的要求,则可采用()查找法。A.分快查找B.顺序查找C.折半查找D.基于属性9.分别以下列序列构造二叉排序树,与用其它三个序列所构造的结果不同的是()。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)10.下图所示的4棵二叉树,()是平衡二叉树。(A)(B)(C)(D)11.散列表的平均查找长度()。A.与处理冲突方法有关而与表的长度无关B.与处理冲突方法无关而与表的长度有关C.与处理冲突方法有关且与表的长度有关D.与处理冲突方法无关且与表的长度无关12.设有一组记录的关键字为{19,14,23,1,68,20,84,27,55,11,10,79},用链地址法构造散列表,散列函数为H(key)=keyMOD13,散列地址为1的链中有()个记录。A.1B.2C.3D.413.关于杂凑查找说法不正确的有几个()(1)采用链地址法解决冲突时,查找一个元素的时间是相同的(2)采用链地址法解决冲突时,若插入规定总是在链首,则插入任一个元素的时间是相同的(3)用链地址法解决冲突易引起聚集现象(4)再哈希法不易产生聚集A.1B.2C.3D.414.设哈希表长为14,哈希函数是H(key)=key%11,表中已有数据的关键字为15,38,61,84共四个,现要将关键字为49的结点加到表中,用二次探测再散列法解决冲突,则放入的位置是()A.8B.3C.5D.915.将10个元素散列到100000个单元的哈希表中,则()产生冲突。A.一定会B.一定不会C.仍可能会二、填空题1.顺序查找n个元素的顺序表,若查找成功,则比较关键字的次数最多为____次;当使用监视哨时,若查找失败,则比较关键字的次数为____。2.在顺序表(8,11,15,19,25,26,30,33,42,48,50)中,用二分(折半)法查找关键码值20,需做的关键码比较次数为____.3.一个无序序列可以通过构造一棵____树而变成一个有序序列,构造树的过程即为对无序序列进行排序的过程。4.哈希表是通过将查找码按选定的____和____,把结点按查找码转换为地址进行存储的线性表。哈希方法的关键是___和____。一个好的哈希函数其转换地址应尽可能____,而且函数运算应尽可能____。5.平衡二叉树又称__________,其定义是__________。6.在哈希函数H(key)=key%p中,p值最好取__________。7.假定有k个关键字互为同义词,若用线性探测再散列法把这k个关键字存入散列表中,至少要进行__________次探测。8.__________法构造的哈希函数肯定不会发生冲突。9.动态查找表和静态查找表的重要区别在于前者包含有__________和__________运算,而后者不包含这两种运算。10.在散列存储中,装填因子α的值越大,则____;α的值越小,则____。11.已知N元整型数组a存放N个学生的成绩,已按由大到小排序,以下算法是用对分(折半)查找方法统计成绩大于或等于X分的学生人数,请填空使之完善。#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;}三、应用题1.HASH方法的平均查找路长决定于什么?是否与结点个数N有关?处理冲突的方法主要有哪些?2.设有一组关键字{9,01,23,14,55,20,84,27},采用哈希函数:H(key)=keymod7,表长为10,用开放地址法的二次探测再散列方法Hi=(H(key)+di)mod10(di=12,22,32,…,)解决冲突。要求:对该关键字序列构造哈希表,并计算查找成功的平均查找长度。3.选取哈希函数H(key)=keymod7,用链地址法解决冲突。试在0-6的散列地址空间内对关键字序列{31,23,17,27,19,11,13,91,61,41}构造哈希表,并计算在等概率下成功查找的平均查找长度。4.输入一个正整数序列(53,17,12,66,58,70,87,25,56,60),试完成下列各题。(1)按次序构造一棵二叉排序树BS。(2)依此二叉排序树,如何得到一个从大到小的有序序列?(3)画出在此二叉排序树中删除“66”后的树结构。5.直接在二叉排序树中查找关键字K与在中序遍历输出的有序序列中查找关键字K,其效率是否相同?输入关键字有序序列来构造一棵二叉排序树,然后对此树进行查找,其效率如何?为什么?6.一棵二叉排序树结构如下,各结点的值从小到大依次为1-9,请标出各结点的值。7.假定对有序表:(3,4,5,7,24,30,42,54,63,72,87,95)进行折半查找,试回答下列问题:(1).画出描述折半查找过程的判定树;(2).若查找元素54,需依次与那些元素比较?(3).若查找元素90,需依次与那些元素比较?(4).假定每个元素的查找概率相等,求查找成功时的平均查找长度。四、算法设计题1.设记录R1,R2,…,Rn按关键字值从小到大顺序存储在数组r[1..n]中,在r[n+1]处设立一个监督哨,其关键字值为+∞;试写一查找给定关键字k的算法;并画出此查找过程的判定树,求出在等概率情况下查找成功时的平均查找长度。2.试编写算法求出指定结点在给定的二叉排序树中所在的层数。3.写出在二叉排序树中删除一个结点的算法,使删除后仍为二叉排序树。设删除结点由指针p所指,其双亲结点由指针f所指,并假设被删除结点是其双亲结点的右孩子。第九章查找一、单项选择题1.B2.C3.D4.C5.B6.B7.CC8.A9.C10.B11.A12.D13.B14.D15.C二、填空题1.nn+12.43.二叉排序4.(1)哈希函数(2)解决冲突的方法(3)选择好的哈希函数(4)处理冲突的方法(5)均匀(6)简单5.AVL树(高度平衡树,高度平衡的二叉排序树)或为空二叉树,或二叉树中任意结点左子树高度与右子树高度差的绝对值小于等于1。6.小于等于表长的最大素数或不包含小于20的质因子的合数7.k(k+1)/28.直接定址法9.插入删除10.存取元素时发生冲突的可能性就越大存取元素时发生冲突的可能性就越小11.(1)rear=mid-1(2)head=mid+1(3)headrear三、应用题1.哈希方法的平均查找路长主要取决于负载因子(表中实有元素数与表长之比),它反映了哈希表的装满程度,该值一般取0.65~0.9。散列表存储中解决碰撞的基本方法:①开放定址法形成地址序列的公式是:Hi=(H(key)+di)%m,其中m是表长,di是增量。根据di取法不同,又分为三种:a.di=1,2,…,m-1称为线性探测再散列,其特点是逐个探测表空间,只要散列表中有空闲空间,就可解决碰撞,缺点是容易造成“聚集”,即不是同义词的关键字争夺同一散列地址。b.di=12,-12,22,-22,…,k2(k≤m/2)称为二次探测再散列,它减少了聚集,但不容易探测到全部表空间,只有当表长为形如4j+3(j为整数)的素数时才有可能。c.di=伪随机数序列,称为随机探测再散列。②再散列法Hi=RHi(key)i=1,2,…,k,是不同的散列函数,即在同义词产生碰撞时,用另一散列函数计算散列地址,直到解决碰撞。该方法不易产生“聚集”,但增加了计算时间。③链地址法将关键字为同义词的记录存储在同一链表中,散列表地址区间用H[0..m-1]表示,分量初始值为空指针。凡散列地址为i(0≤i≤m-1)的记录均插在以H[i]为头指针的链表中。这种解决方法中数据元素个数不受表长限制,插入和删除操作方便,但增加了指针的空间开销。这种散列表常称为开散列表,而①中的散列表称闭散列表,含义是元素个数受表长限制。④建立公共溢出区设H[0..m-1]为基本表,凡关键字为同义词的记录,都填入溢出区O[0..m-1]。2.散列地址0123456789关键字140192384275520比较次数11123412平均查找长度:ASLsucc=(1+1+1+2+3+4+1+2)/8=15/8以关键字27为例:H(27)=27%7=6(冲突)H1=(6+1)%10=7(冲突)H2=(6+22)%10=0(冲突)H3=(6+33)%10=5所以比较了4次。3.表略ASLsucc=15/104.略5.在二叉排序树上查找关键字K,走了一条从根结点至多到叶子的路径,时间复杂度是O(logn),而在中序遍历输出的序列中查找关键字K,时间复杂度是O(n)。按序输入建立的二叉排序树,蜕变为单枝树,其平均查找长度是(n+1)/2,时间复杂度也是O(n)。6.略7.略四、算法设计题1.intSearch(rectyper[],intn,keytypek)//在n个关键字从小到大排列的顺序表中,查找关键字为k的结点。{r[n+1].key=MAXINT;//在高端设置监视哨i=1;while(r[i].keyk)i++;if(r[n+1].key==k)return(i%(n+1));elsereturn(0)}//算法search结束查找过程的判定树是单枝树,限于篇幅不再画出。本题中虽然表按关键字有序,但进行顺序查找,查找成功的平均查找长度亦为(n+1)/2。2.解答:.分析:采用递归方法,从根结点开始查找结点p,若查询结点是所要找的结点,返回其深度h0。否则,到左、右子树上去找,查找深度加1。intfind1(birtreptrT,p,inth0)/*在二叉树排序树T中查找结点p的层次,若不在时返回空值。h0为根结点T的层次*/{if(p==NULL)return(0);/*没找到,返回0*/if(p==T)return(h0);/*找到*/elseif(p-dataT-data)return(find1(T-lchild,p,h0)+1);/*到左子树去找*/elsereturn(find1(T-rchild,p,h0)+1);/*到右子树去找*/}intfind2(birtrptrT,p){return(fi
本文标题:第八章查找习题_数据结构
链接地址:https://www.777doc.com/doc-2191243 .html