中南大学数据结构与算法第9章查找课后作业答案.doc

《中南大学数据结构与算法第9章查找课后作业答案.doc》由会员分享，可在线阅读，更多相关《中南大学数据结构与算法第9章查找课后作业答案.doc（14页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第章查找习题练习答案、对含有n个互不相同元素得集合,同时找最大元与最小元至少需进行多少次比较？答：设变量ax与min用于存放最大元与最小元（得位置）,第一次取两个元素进行比较，大得放入ma，小得放入min。从第2次开始，每次取一个元素先与m比较,如果大于m则以它替换max，并结束本次比较；若小于a则再与min相比较,在最好得情况下,一路比较下去都不用与i相比较,所以这种情况下,至少要进行n-1次比较就能找到最大元与最小元。2、若对具有n个元素得有序得顺序表与无序得顺序表分别进行顺序查找，试在下述两种情况下分别讨论两者在等概率时得平均查找长度: （1）查找不成功,即表中无关键字等于给定值K得记录

2、;(）查找成功,即表中有关键字等于给定值K得记录。答： 查找不成功时，需进行+1次比较才能确定查找失败。因此平均查找长度为n+1，这时有序表与无序表就是一样得. 查找成功时，平均查找长度为(n1)/2,有序表与无序表也就是一样得.因为顺序查找与表得初始序列状态无关。3、画出对长度为18得有序得顺序表进行二分查找得判定树，并指出在等概率时查找成功得平均查找长度，以及查找失败时所需得最多得关键字比较次数。答： 等概率情况下,查找成功得平均查找长度为: ASL=(1+22+3*4+8+53）/1=3、56 查找失败时,最多得关键字比较次树不超过判定树得深度，此处为5、4、为什么有序得单链表不能进行折

3、半查找?答： 因为链表无法进行随机访问，如果要访问链表得中间结点，就必须先从头结点开始进行依次访问,这就要浪费很多时间，还不如进行顺序查找,而且，用链存储结构将无法判定二分得过程就是否结束,因此无法用链表实现二分查找。5、设有序表为(a,b，c，,f,g，j,k,p，)，请分别画出对给定值b,g与n进行折半查找得过程。解：(1)查找b得过程如下（其中方括号表示当前查找区间，圆括号表示当前比较得关键字） 下标: 2 3 4 56 8 10111 第一次比较： a bc d f （g） i k p q 第二次比较： a (c） defgh ij k p q 第三次比较: a （b） e fg h

4、i j k p q 经过三次比较,查找成功.（2)得查找过程如下： b cd f （g） h ij k pq 一次比较成功. （3)n得查找过程如下: 下标： 2 5 6 789 0 11 12 1 第一次比较： a b c d e (g) h i j k p 第二次比较： c d e fg h () p q 第三次比较： abc fg i jk（p) q 第四次比较： a c fgh jk p q 经过四次比较，查找失败。6、将（fr，ce， ile， la, poecte， virtual，plic，private, do， teplate， cons，f，int）中得关键字依次插入初态为

5、空得二叉排序树中，请画出所得到得树T。然后画出删去for之后得二叉排序树，若再将f 插入T中得到得二叉排序树T就是否与T相同？最后给出T得先序、中序与后序序列。答： 二叉排序树T如下图： 删去f后得二叉排序树如下图: 再插入结点for后得二叉排序树: 二叉排序树”与T不同T得先序序列就是:docaela nstwhi potected privat if for int vtu pul temate T得中序序列就是:ce ass cnst do o if int prate potectedpublic templt viuall T”得后序序列就是:onstclass as rint if

6、 pivaetempl publivitualrected whldo、对给定得关键字集合，以不同得次序插入初始为空得树中,就是否有可能得到同一棵二叉排序树?答: 有可能。如有两个序列：3，1，2,4 与 3，4,1，2，它们插入空树所得得二叉排序树就是相同得。、将二叉排序树T得先序序列中得关键字依次插入一空树中，所得与二叉排序树与T否相同?为什么?答: 这两棵二叉树完全相同.、设二叉排序树中关键字由至100得整数构成，现要查找关键字为363得结点，下述关键字序列哪一个不可能就是在二叉排序树上查找到得序列？ （a） 2，22,401,38，0,344，397,6； (b） 92， 220， 1

7、1， 44, 88， 258，362, 36； （c） 92, 202,91, 240，912, 245， 363； (d)2，399, 3, 21， 6， 382， 38， 278， 363、答:（c）就是不可能查找到得序列。把这四个序列各插入到一个初始为空得二叉排序树中，结果可以发现,（c）序列所形成得不就是一条路径，而就是有分支得,可见它就是不可能在查找过程中访问到得序列。10、设二叉排序树中关键字互不相同，则其中最小元必无左孩子，最大元必无右孩子。此命题就是否正确?最小元与最大元一定就是叶子吗？一个新结点总就是插在二叉排序树得某叶子上吗？答: 此命题正确。假设最小元有左孩子,则根据二叉

8、排序树性质,此左孩子应比最小元更小，如此一来就产生矛盾了，因此最小元不可能有左孩子,对于最大元也就是这个道理。 但最大元与最小元不一定就是叶子，它也可以就是根、内部结点（分支结点）等，这得根据插入结点时得次序而定。 新结点总就是作为叶子插入在二叉排序树中得。11、在一棵阶得-树中，当将一关键字插入某结点而引起该结点得分裂时，此结点原有多少个关键字?若删去某结点中得一个关键字,而导致结点合并时,该结点中原有几个关键字?答: 在一棵阶得B树中，若由于一关键字得插入某结点而引起该结点得分裂时,则该结点原有-1个关键字。 若删去某结点中一个关键字而导致结点合并时,该结点中原有m/2-个关键字。12、在

9、一棵B树中，空指针数总就是比关键字数多一个，此说法就是否正确？请问包含个关键字得阶B-树（即2-3树)最多有几个结点?最少有几个结点?画出这两种情况得B树。答: 这个说法就是正确得。包含8个关键字得3阶B树最多有7个结点，最少有4个结点。 、从空树开始,依次输入20，3，50,2，6,70，画出建立23树得过程。并画出删除50与68后得B-树状态.答：过程如下： （)插入20，30: (2) 插入50: (） 插入52： （) 插入60： （5)插入68: （) 插入70: (7)删去50： （8） 删去6 14、画出依次插入,v,o,p,，到图、12（h)所示得5阶B树得过程。 解: (1）

10、插入z后：（2)插入v，o后 （3）插入p，y后 16、为什么在内存中使用得B-树通常就是阶得,而不使用更高阶得B树？ 答： 因为查找等操作得c时间在树上就是O（lgn（/lt）)，而mlgt1,所以较大时它所费时间比平衡得二叉排序树上相应操作时间大得多,因此,仅在内存中使用得树通常取最小值7、为什么二叉排序树长高时,新结点总就是一个叶子,而B-树长高时，新结点总就是根?哪一种长高能保证树平衡？答: 因为在二叉排序树中，关键字总就是作为一个叶子结点插入以原来得树中,所以当树增高时,新结点总就是一个叶子;而B树中关键字插入总就是插入到叶子结点内部，在叶结点中得关键字数目尚未超过它能够容纳得数目之

11、前就是不会增加结点得,当关键字数超过结点可容纳得数目时,叶结点就会发生分裂，产生一个新结点(但不一定引起树增高）,并且将其中得中间结点传至上一层,只有当这种分裂操作传递至根结点并引起根结点得分裂时,才能引起树高增加，此时产生一个新得根结点。所以说B树长高时，新结点总就是根。 显然，后一种长高总能保证树得平衡.9、对于一组给定得、固定不变得关键字序列,有可能设计出无冲突得散列函数H,此时称H为完备得散列函数(erfecthig uction）,若能无冲突地将关键字完全填满散列表，则称H就是最小完备（miimal peret)得散列函数.通常找完备得散列函数非常困难，找最小完备得散列函数就更困难。

12、请问： (1）若h就是已知关键字集合K得完备得散列函数，若要增加一个新得关键字到集合K,一般情况下还就是完备得吗？ (2）已知关键字集合为（，29,3,38,434，6，42，48,24),散列函数为H（x)=(+18)63，请问就是完备得吗？它就是最小完备得吗?(3）考虑由字符串构成得关键字集合(Brt,Jae，Sily,Brye,Michele，Heathe），试为散列表0、6设计一个完备得散列函数.(提示:考虑每个字符串得第3个字符，即s2）答: （1)一般情况下H不就是完备得，如果说插入一个新得关键字它还就是完备得，那么再插入一个呢?它岂不就是永远就是完备得散列函数了？所以一般情况下它

13、不能总就是完备得,只有一些很少得情况下它还可能就是完备得。(2)这个H就是完备得，其函数值依次为：,，5,0，7,3，6,8，.如果散列表长=9时，它就就是最小完备得。 （） 这个函数如下: it Hash （char ky） retunkey2%7;20、设散列函数为h（ey）ky%101,解决冲突得方法为线性探查，表中用”1”表示空单元.若删去散列表T中得304（即令T1=)之后，在表H中查找70将会发生什么?若将删去得表项标记为”2,查找时探查到2继续向前搜索，探查到-1时终止搜索。请问用这种方法删30后能否正确地查找到7？0 1 2 100 H202 304 57 、 答：查找70时,

14、首先根据散列函数计算得出该元素应在散列表中得0单元，但就是在0单元没有找到，因此将向下一单元探查，结果发现该单元就是1(为空单元),所以结束查找，这将导致7无法找到。 如果改用-2作为删除标记,则可以正确找到70所在得结点。2、设散列表长度为11，散列函数h()=x%1，给定得关键字序列为：,13,13，3，38,3，2，22、试画出分别用拉链法与线性探查法解决冲突时所构造得散列表,并求出在等概率情况下，这两种方法查找成功与失败时得平均查找长度。请问装填因子得值就是什么？答: (）拉链法如下图: T0、1 0 33 22 1 1 1234 2 1 3 4 5 27 6 7 8 10 （2）线性

15、探查法如下图: 下标 1 9 0 0、031 112432722 探查次数 1 11 3 4 1 7 8用拉链法得查找成功平均查找长度为： SLsc=（*233*1)/1、25 查找失败时平均查找长度为： Auncc=（2+1+0+0+2+0+0+0+0）/1=0、73用线性探查法查找成功时平均查找长度为:ASLuc=(1+11+3+178）=3、25 查找失败时平均查找长度为： SLnsuc=（987+65+421+11)/11=4、3装填因子拉链11=0、36 线性探查=8/1=0、322、假定有k个关键字互为同义词，若用线性探查法把这些同义词存入散列表中,至少要进行多少次探查?答： 至少

16、要进行12、1+k次探查. 也就就是说,在散列表得一连串连续空间内，第一个关键字只需探查一次，第二个就要探查2次，如此这般,第k个关键字就要探查k次才能找到位置存放。所以至少要把它们全加起来才够。3、为什么说当装填因子非常接近时，线性探查类似于顺序查找？为什么说当装填因子比较小（比如、7左右）时,散列查找得平均查找时间为O（1）？答: 当非常接近时，整个散列表几乎被装满。由于线性探查法在关键字同义时解决冲突得办法就是线性地向后查找，当整个表几乎装满时,它就很类似于顺序查找了。当比较小时,关键字碰撞得几率比较小,一般情况下只要按照散列函数计算出得结果能够1次性就找到相应结点，因此它得平均查找时间

17、接近于1、24、设顺序表中关键字就是递增有序得，试写一顺序查找算法,将哨兵设在表得高下标端.然后求出等概率情况下查找成功与失败时得ASL、答： tpdef struct KeyType key; InfoTpe oterinfo； /此类型依赖于应用 NoeType；typdef deTpe SqLt； /n号单元用作哨兵 n SeqSearch（Seqist,eyType K） /在关键字递增有序得顺序表0、n-中顺序查找关键字为K得结点， /成功时返回找到得结点位置，失败时返回- inti； Rn、keyK; /设置哨兵 o（0;Ri、ey=K;i）； /从表前往后找 f （iRi、key

18、=K）retn i;/i就是要找得结点 els reur /Seqeac等概率情况下查找成功ASL（+2+3+）/n 等概率情况下查找失败时得AL（123+n1）（n+1)25试写出二分查找得递归算法。解： inBinSer(SeqList R，eT K，intow,ithgh） /在有序表Rlow、hih中进行二分查找，成功时返回结点得位置，失败时返回零 it id；/置当前查找区间上、下界得初值 if （o=high) 当前查找区间Row、hih非空 i=(low+hh）/2; （mid、key=K） etur md; /查找成功返回 if(Rid、kdyK） retu BiSech( R

19、，K，lo,md）/在Rl、mid-1中查找 ele rurn BinSerh( R，K,mid+1，hih）； /在Rd+1、hh中查找 return 0； /当lohigh时表示查找区间为空，查找失败 /BinSeareh2试写一算法判别给定得二叉树就是否为二叉排序树,设此二叉树以二叉链表为存储结构，且树中结点得关键字均不相同。解: 由二叉排序树得定义可得:二叉排序树中左子树得所有结点得值都小于根结点得值,所有右子树中结点得值都大于根结点得值.那么只要对待判定得二叉树中得结点按层遍历并判断即可.在该算法中要用到队列保存已遍历得结点指针。 typedef BinTN DataTyp;/循环队

20、列中元素为二叉树结点指针inBirtSe(BinTre T) CirQe ; BnNod *; i(!T) eturn 1；/空树为二叉排序树 IiQueue（Q）； EQeue（Q,T）； hile（！QuueEmt（&Q)） pDeQueue（Q); if （plcild) i （-datalchild)； if (-rchld) if （pdatarchild-data）rtrn1；/不就是二叉排序树 else EnQeue（&，-rchild）； return 1;/就是二叉排序树 27、试写一递归算法,从大到小输出二叉排序树中所有其值不小于x得关键字。要求算法得时间为O（gn+m），

21、n为树中结点数,m为输出关键字个数(提示：先遍历右子树，后遍历左子树).答：typf itKeyTyp； /假定关键字类型为整数 typee stru oe /结点类型 eyTypeke; /关键字项 Ifypeotherinf；/其它数据域,InfoType视应用情况而定，下面不处理它 strc nde *lchil,rcild； /左右孩子指针 STNoe；tpef BSTNode *BTre;voiOTPUTNODE（STree ，KyTpex)/从大到小输出二叉排序树中所有其值不小于x得关键字 f (T) OTPUTNODE( T-rchild，x)； if（-ey=） prntf(，

22、ky）; OTPNODE(T-Lcild,x）; 28、写一个遍历B-树得算法，使输出得关键字序列递增有序.算法中得读盘操作可假定为DiskRead。答：#define a l000/结点中关键字得最大数目：Max=m1，就是B树得阶defin Min 500 /非根结点中关键字得最小数目:Mim/2（-1 typedef in KeyType; /KeyTp应由用户定义typdef tru ode/结点定义中省略了指向关键字代表得记录得指针 tkeynu； /结点中当前拥有得关键字得个数,keyumMax ype yx+； /关键字向量为e1、keynm,key0不用。 sc n *pare

23、nt； /指向双亲结点 sctnoe sonMa1;/孩子指针向量为on0、keynum Breeoe; typdf BTrdeBTree; vid taere(ee） /按关键字递增序输出B树序列 in； if （) fr(=0；=Tkeynum;i+）/Tkyum个关键字得结点有-nu+1棵子树 f（T-soni) Dikad（Tsoi)；/读入根结点得第i棵子树 aveBree（T-sn)；/遍历第棵子树 f(iTeynu)/若刚遍历得子树不就是最后一棵子树 prnt(d”,Tkeyi+1； 29若采用除余法作为散列函数，线性探查解决冲突,则9。4节中通用得散列表查找算法可改写为对线性探

24、查专用得查找算法：nt HhSrch（HashTable，eTyp K,int pos）t=0;/记录探查次数 o=K%m; /散列函数值作为第一个散列地址while（im） /最多探查m次 i(Tpos、ky=K）rtur 1;/查找成功返回 if（T*ps、k=IL) retr 0；/查找失败返回 *pos=（*s+1)m;用线性探查法求下一个探查地址 reurn 1；/查找失败，且表满 /ashearc 假设散列表上得删除操作已将结点得关键字标记为DELETED（例如,不妨设ELEED为-2）。请修改上述散列表上得查找算法及插入算法HshInsert，使之能正确地查找与插入。解： （1）

25、查找算法defie DELTED 2#defie NIL -1 /空结点标记依赖于关键字类型，本节假定关键字均为非负整数#dfie M 997 /表长度依赖于应用,但一般应根据。确定m为一素数 tpedef stuct /散列表结点类型 Typekey；InfoTe thernfo; /此类依赖于应用 NodeType; typdef NodeypashTablem; /散列表类型 int Hashearh(ashTableT,Keyype K,int*ps） =0；/记录探查次数 *pom;/散列函数值作为第一个散列地址 hle(i+m）/最多探查次 i（*os、key=K） etn；/查找

26、成功返回 if(T*pos、ky=NIL） return ；/查找失败返回 *os（pos1）%；/用线性探查法求下一个探查地址 retun 1;/查找失败，且表满 /asheac (2)插入算法HshInsrt intHahInsert（HashleT，KTy K) /返回1，表示表中已有k,返回表示正常插入,返回表示插入失败int i=0；/记录探查次数 int j=;/记录DLETD得位置 nt o=K%m； /散列函数值作为第一个散列地址 whil（+keK;pnext=Tddr;Tar=p；/将p插入链表Tdr得头部 ndf/aHahInert解: (1）建表 oid ChainHa

27、sheat(CHasTable T） /设散列函数为h（)=Km，建立以拉链法为解决冲突方法得散列表 CodeTyp *p； int ddr; int ；KeyTe K； for（i；ikey=K;p-nt=Taddr；addr=p;/将p插入链表Tddr得头部 /endif scan(”%d”，）； /endhile/ChanaCeat （2）查找 CNodeTyChanHashSearch（HhTb T,KeyType ) /查找关键字值为得结点，若有返回该结点指针,否则返回NULL CNodeype p; int add； addr=K%m；/求散列函数值 pTaddr； wile (p)(p-ky!=) p=pnext; eurn p; (）删除CNoye ainaDete（HahTable T，KyTyp K） /删除关键字值为K得结点，若有返回该结点指针,否则返回NL CNodType *p，*; in adr; drK%m；求散列函数值 p=Tddr； if (p)(p-key=）Tadd=pe;/要删得就是Tadd表得第一个结点 whi（pnext)&(-nete!=K） =p-nxt； i (p-） =p;ppx；qnxt=pnext；/删除p rern p；