《《数据结构基础教程》习题及解答.docx》由会员分享，可在线阅读，更多相关《《数据结构基础教程》习题及解答.docx（16页珍藏版）》请在课桌文档上搜索。
1、ptr=r-Ncx(:)7.一个单能表1.k的表头指针为1.kj不同结点的Data域值有可能相同,期个驾法，功能是计算出Daui域值为X的结点的个数，答：算法应当遍历链表的每一个结点，遇到一个结点的Ddla域侑为X时，计数器n就加1。最终返回计数器!UCMinl-1.k(1.k-h)(n=0;pDau=x)n=n*l;ptr=pNextIreturn(n):第3章习题解答一、填空限定插入和删除操作只能在一端进行的线性表,被称为是2 .假如在依次栈满时仍准备进行进栈操作，就称为发生了“上溢”出错.3 .黄如在依次栈空时仍准爸迸行出栈操作，就称为发生了“下溢”出错，4 .在具有“个数据结点的循环队
2、列中，队满时共有个数据元素。5 .忸如操作依次是先让字母A、B,C进栈.做两次出栈：可让字母D、E.F进栈，做一次出栈：最终让字母G进栈，做三次山栈.最终这个堆校从校顶到栈底的余留元素应当是_DA_.6 .中一衣达式(u+bMc(de)洌应的后衣达式是abde+/-)7 .函数的递灯调用行两种形式：假如一个函数是干脆调用自己.就称其为一曲递归阿用：假如一个函数是通过另一个函数来调用自己，就称其为间接递归正用.8 .设某栈的元素输入依次是I、2、3、4、5.S!得到4、3、5、2、1的输出依次。那么push,pop的操作序列应“i是push、push、push、push*pop、pop、push
3、、pop、PoP、POP，9 .设鞋栈的栈顶指针为1.sop.那么它非空的条件应当是1.Stop!=Nu1.1.10 .队列中，允许进行删除的一米称为队首.二、选界1. 一个栈的元素进栈序列是a、b、c、d.e,瘠么下面的C不能做为一个出栈序列.A.cd、c、taB.d、e、c、b、aC.d、c、e、a、bD.a、b、c、d、eelseH队列/空！/qlr=Qx_trnl：while(qtr:qlr*+：3.编写一个算法，它能够取得链式队列首元素的值。答：取得链式队列百元索的值,只有在队列非空的前途下才有意义。算法端写如卜GetfJ-q(lA|_fr(nt,lxi_rcair)(if(1.q_
4、fron(=1.q_tear)/队丹f!*fprinl(Ibelinkedqueueiempty!、else卢队列作空！/(tr=1.q_front-Ncxi:x=pcrl(a;return(x);I)4 .有万.个人依次坐在一起，问第5个人多少岁，回答说比第4个人大2岁：问第4个人多少岁.回答说比第3个人大2岁：何笫3个人多少岁.回答说比第2个人大2岁：问第2个人多少岁，I可答说比第I个人大2岁：问第I个人多少岁，叵1答说是IO岁.试给出该递归的公式、结束条件，并编写出相应的遢心算法，答；递归公式为：agc(n)=agc(n-l)+22=11return(IOkelse(x=agl个具有相同
5、类型的数描的有序集十.8 .矩阵与通常所说的二数组有关.9 .所谓“特别矩阵”,是指那些元素在矩阵中的分布具干i确定规律性的矩阵：而矩阵中的零元崇个数远远多于非零元素的个数,但非零元素的分布却没有规律，这样的矩阵被称为“稀矩口10 .在一个”阶方阵A中，若全部元素都有性质：ay=1(7n).就称其为对林矩二、选异I.设有两个由Sl和$2.求s2在SI中首次出现的位置的操作称为_5_.连接B.模式匹桎C.求子申D.求申长2 .有用：P那么它的长度是B。A.0B.1C.2D.33 .设有率sl=ABCDEFGBs2=PQRST-.已知：尊法COn(x.y)返回中X和y的连接申；SUbS(S.i.j
6、)返回申S的第i个字符起先往后j个字符殂成的子中：Ien(三)返回申$的长度.那么，COn(SUbS(si.2,Ien(s2).subs(sl.Ien(s2).2)的操作结果是用D。A.BCDEEB.BCDEFGC.BCPQRSD.BCDEMiFA.33B.30C.13D.235 .一个由”的对称电阵,假如以行优先的方式压缩存入内存.那么所需存储区的容量应当是C.A.m*(m-l)1f2B.ntt,tn2C.M(m+X2D.(m+1)(+1X26 .二维数组M的每个元素含4个字符(句个字符占用一个存储单元),行卜标，从1变到5.列下标j从I交到6,那么按行依次存储时元素MHH6的起始地址与M按
7、列依次存储时元素立的起始地址相同，A.M351B.M451C.M461D.M(51157 .二维数组M中的每个元素占用3个存储单元，行下标i从1变到8.列下标j从!变到10.现从首地址为SA的存储区起先存放A.那么该数组以行优先存放时,元素A85的起始地址应当是.SA+141B.SA+180C.SA+222D.SA+2258 .设有一个S阶上三角矩阵A,将其元素按列优先依次存放在一维数组B中.己知年个元素占用2个存储单元,B川的地址是I(Xh那么A网闾的地址是工_.A.116B.118C.120D.122(分析：把一个上三角矩阵按列优先依次存放在一个一维数组B中，元素的依次是：aa2a22a3
8、A3.4的地址=100+3前面的元南个A*2=I(XH(前3列的个数+本列a”前面的个数*2=100+*2=116Moveij(St,i,j)(if(i+j三StJcn)(for(k=i+j;k*将i+j起先往后的全都字符的移j个位贸/SUk-j=Sk;St_len=Sj_lai-j;SiISi-Ien=,J;I*修改SI的长度*)/安胶款的小结束符/Prin参攻不合理,无法进行BH除【,I;)6.在算法412的最终,为了群放被刷结点运用的存储空间,先做了操作:pNcxt-NU1.1.;把出指计Pu指向的最终个要林放宽间的结点的Next域设汽为NU1.1.,然后通过while循环完成择放.其实
9、，由于知道要移放空间的结点共有r个，因此可以取消这一操作,改用Ior循环通过m来限制好放空间的结点个数.请试着依据这一思路改写那一小段算法.答：改写-小段算法如下.Forg:卜二(ptr=rtr;rtr=11rNcxt;fnx;7.弟写一个葬法,功能是复制一个鞋串.答：复制一个完整的鞋中，是一件比较简洁的事情.其算法起名为CoPy-1.1(),参数为1.tk详细编写如下.COPy_1.M1.d)pDala=p(r-Dala;U2_h=rtnpNcM;while(r!=N1.1.1.(qtr=mai!oc(sizc):qtr-Data=Daa.rtrel=q(r;ptr=pNcx(;IHrQNe
10、XNU1.1.:rctum(1.l2h):4.将-棵有50个结点的完全二叉树按层编号,承么潟号为25的结点是A.无左、右孩子B.有左孩子，无右孩子C.有右孩子，无左孩子D.有左、有孩子A.63B.64C.127D.1286 .在一探非空二叉树的中序遍历序列里，根结点的右边，上结点，A只有左子树上的部分B,只有左子树上的全部C.只有右子椅上的部分D,只有右子树上的全部7 .在任何一棵二叉树的各种遍历序列中.叶结点的相对次序是AA.不发生变更B.发生变更C.不能确定D.以上都不对8.权值为1、2、6、8的四个结点，所构造的哈夫曼树的带权路径长度是旦.A.18B.28C.19D.29A.6B.7C.
11、8D.910.在一棵二叉树中，第S层上的结点数最多是上个.A.8B.15C.16D.32三、问答1 .试问满二叉树与完全二叉树之间有何关系？答，由满二叉豺与完全二叉树的定义可知.满二叉树确定是一棵完全二叉树，但完全二叉树却不确定是一棵满二叉树.假如一棵：叉树不是完全：叉树,那么它确定不行能是棵满二叉树。这就是海：叉树与完全：叉树之间的关系，2 .请画出由3个结点构成的全部二叉树，它们的高度分别是多少？答：大小为3的不同的二叉树共有5种,如下图所示.其中，4棵树的高度为2,1棵树的高度为I.3 .一黑高度为3的满：叉树有多少个叶站点？有多少个度为2的结点？总共有多少个结点？孥有218个叶结点,有
12、度为2的结点2口=7个，总共有2U=K1=15个结点.4 .有人说，任何一探其空满：叉树，它的叶结点数等于其分支结点数加I-这样的一个结论正确吗？请说明理由.（提示：利用性质，3）答：在我初介绍的二叉树性质中,只有性麻S-3是涉及叶结点数与（度为2的）分支结点数的关系的.对于满二叉树来说,全部的分支结点都是度为2的结点.因此,正好可以干脆利用性质5-3褥出所须要的结论.所以，此人说的结论是完全正确的.5 .有人说，有一棵结点数为，a1的二叉树，只包含有一个叶站点.这可能吗？假如可能的话，这样一-棵二叉树应当是个什么样子呢？答：这是完全可能的,这种二叉树是从根结点起先只有左子树.或只有右子树的单
13、支二叉树,如图所示.二叉构.答：这株二叉树如应用即3答案图所示.4 .若一棵二叉树的左、右子树均有3个结点，其左子树的先序遍历序列与中序避历序列相同，右子树的中序论历序列与后序溺历序列相同,请画出这株二叉树。答：这棵二又树如“用即4答案图所示.5 .理解算法5-10在图S25(b)的基础上,进行下一次组合。试给出第2次组合后数组的情彬,以及那时二叉树的样子.答：第2次组合后数组的情形如下图所示，那时二叉树的样子如下图(b)所示.6 .权值序列为：10、16、20,6、30、24,请用图示来表达构造一棵哈夫曼树的全过程。答：构造这棵哈夫变树的全过程如下所示.双亲的孩子链表表示法(我们介绍过双亲表
14、示法和孩子融表表示法,没有介绍过带双亲的孩子链非表示法.里能够把两者结合起来)：(3)孩子/兄弟链衣衣示法.答：双亲去示法如下图依)所示:(2)带双亲的孩子链求去示法如图下(b)所示;(3)孩子/兄弟链表表示法如卜图(c)所示。loot-|IIAlBjTcTlIlDl+TeF11ItIf4g|ha1Ihl11N3 .将图626所示的二叉树转换成相应的森林。答；转换成的森林如下图所示。4 .给出如图6-27所示树的先序遍历序列和后序通历序列，答：该树的先序泗历序列为：A-B-E-F-K-1.-M-C-G-D-H-I-J;该树的后序遍历序列是:E-K-M-1.-F-B-G-C-H-I-J-D-A.
15、答：这两个舞法的处理思路的确较为相像.主要区分在于：Pnm算法是从V-U里选择山下一个与MST中某个顶点相距最近的顶点,而DijkStra算法是从V-U里选择山下一个离源点燃近的顶点，5 .对有,“个顶点的无向图G,如何通过它的邻接矩阵判定下列问甥；(1)图中有多少条边？(2)随意两个顶点iHlj之间是否有边相连？(3)随意一个顶点i的度是多少？答：(1)邻接矩阵中非零元泰个数的一半，是图中边的数目：(2)通过推断邻接矩阵中元索AwJl和AR是否不为0.可知顶点i和/之间是否有边相连：(3)第i行或第i列上非零元素的个数,就是顶点i的度.6 .对图724回答下列何SS：3)5)每个顶点X的度D
16、(X);一个长度为4的回路:(1)顶点集合V；(2)边集合E：(4)一个长度为5的路径：(6)答：(I)顶点集合V=v.-2.V3.EVsjyJ(2)(3)(4)(5)(6)(7)(8)边集合E=,3,4,D(v2)=3,D(VJ)=D34)=4,DV2-V-l-V4-V5“Vj-vj-V5-V4-Vj.等个顶点的度：D(l=l,一个长度为5的路径是：一个长度为4的回路是:如下图所示。O3OO2J2一如卜图(b)所示,加下图(C)所示“l-AlA*I5I*H6II-z*-=kcy%13.运用开放地址法的线性探测解抉冲突,请完成下面散列表的填写比如.第I个插入的是36,它的散列地址为10.由于没
17、有发生冲突，所以比较次就存放在了地址为IO的位置），求出其平均查找长度AS1.,地址美依字比核.次效012712103611112答：最终的散列衣如图所示.其平均IS我长度AS1.为：AS1.-性探测=(2+l+2+l+2+5+l+!+3+l+l+3/12=1.92数到地址关依字比较次圾09021271240236814812514569717331g22391036111241122335 .已知由12个关键字祖成的序列:Jan-Feb.Mar.Apr.May.Jun.JulAugSep.Oct.Nov.Dec(1)依据所给依次构造一棵初始为空的二叉查找树.画出最终形成的二叉查找树,求在等概
18、率下查找胜利的平均查找长度.(2若对关键字序列依据字母递埴的依次排列成有序表，求在等概率下这黑二叉食找树查找胜利的平均杳找长度。答：(1)最终形成的二叉查找树如下图所示,其平均查找长度为：AS1.=l+2*2+3*3+34+2*5+6)/12=42/12=3.5(Jai)De，Oct(2)这时成为只有右子国的总支树,其平均查找长度为：AS1.=Aug.Sep.Oct.Nov.Dec散列表长为13(地址为(kl2),散列函数为：h(kcy)=iZ2,其中i为关健字中第1个字母在字母表里的序号.(I)用线性探测法解决冲突，给出所构造的敌列衣以及直找胜利的平均位找长度。(2)用链地址法斛决冲突，给出
19、所构迨的散列表以及杳找胜利的平均查找长度。答：(1)用线性探测法解决冲突时,插入地址及比较次数如下：h(Jan)=10.2=5.比较1次插入：h(f%b)=6=3.比较I次插入：.构造的股列表如图所示。MMarK2=6,比较I次插入;h(Apr)=l2=3,比较I次插入:h(MayE32=6,比较2次插入:h(Jun)=lW2=5,比较4次插入；h(Jul尸Iw2=5,比较5次插入：h(Aug=l2=0,比较2次插入：h(Scp)三192=9,比较2次插入:h(Oct-7,比较5次插入:UNov)=l4,2=7.比较6次插入：hDecRf2=2,比较I次插入，所以，构造的散列表如图所示。O23
20、4567g9】OuI213141516AUglDeClFeblIJanlMarJUnIJUlISepI。CtlNVFIAPlAUglDeClFeblIJanlMarlMaylJUnlJullSePlOetlNOVl|平均也我长度为：AS1.=(I+1+1+1+2+4+5+2+2+5+61)12=3112-2.6(2)用链地址法解决冲突时,构造的散列表如图所示.平均查找长度为：AS1.=ArU.kcy正是它保证了干16插入排序算法的稔定性.比如在例9-2里，由于比较到第2个76大于、等于第I个K，所以WhiIe循环就结束了，不再往后移动比较范附内的记录。因此，第2个76确定在第I个筌的后面，不会
21、跑到它的前面去F假如将while循环改为：while(tcmp.kcy=Aryj.kcy)&(j=l)那么，它就不会保证干脆插入排序舞法是桧定的了.2 .在肾泡抖.序和法里，是什么条件保证它的枪定性？答：臼泡排序是种稳定排序尊.法，主要是因为算法里母鹤扫描时的判定条件设定为：ArUIkCyArU+1Jkcy,它保证原先在前面的记录.排序后仍旧排在前面.不会变史它们之间的相对依次.假如把大于号改为大于等于，那么算法就不是稳定的3 .试问内排序与外排序有什么区分？答：内、外序虽然都是排序，但由于排序过程中所运用存储器的不同，而被分为内排序和外排序.所消“内排序”,是指待排记录序列全部存放在内存,整
22、个排序过程福在内存里完成：所谓“外排序”,是指内存中容纳不下全部待排记录序列,排序过程中须要不断地与外存进行数据交换，4 .有两个关键字序列：3、10、12、22、36、18.28、40和5、8、II、15、23、20、32、7.试问谁是堆,谁不足推？把不足堆的序列通过筛选将它谓整为一个堆.答：依照序列的依次，画出对应的完全二叉例如（八）和(b)所示.可以看出，（八）是一个堆，(b)则不是，因为结点7破坏了堆的性质，为此，先将7和15对换，如图(C)所示：然后再将23,21.28.15.19.3.73.7.15.19.21.23.2819.23.3,15,7.21.2819.7.15.28,2
23、3.21.3对它们果纳快速排序方法进行排序,试问哪一种状况速度最慢？答：在爆终一种状况时，序列己经排好序，因此对它的排序速度嫉慢,四、应用I.将冒泡排序算法修改成记录关键字由大到小递减排列.答；己却有”个记录的无序序列，存放在一个一维数殂Ar里，对它进行递减的旨泡排序，井呆终得到排序结果.算法名为BUkSort10,参数为Ar,小Bub_Srt1(Ar.n)f对无存记录序列进行n-l超打描*1flag=0;for(j=hji:j*)if(A1j.keyl;Affj-*11=temp:Ilag=I;if(Hag=0)break:/若没有发生.交族就结束打法”J2.有待排关雄字序列：68、70、6
24、7,73、23、67、28、92、18，以图示的方式对它进行快速排序，并说明快速排序是种不枪定的排序算法.答：图(U)是快速排序一次划分前的初始状态，图(b)是一次划分完成时的结果，这时关A4A5A1AR；IiIlowI67I6?67I23|(力Iow=Hight彳2A3A4A5三67I67Ia(e)-l丘_jh67I(0,三hI28IaI67I21(g).一O2328I67I及(NIOW=high下面特地来看左边的待排子序列，它由AIJ=I8.A(2)28A(3=fi24J=67.A5=23组成，对其进行快速排序一次划分前的初始状态如图所示，一次划分完成时的结果，关过:18已经到达它的股终位
25、置，其他关键字只有右子序列,如图(d)所示.图(C下图（三）和小对右字序列一次划分的过程.从最终结果可以看出，原来在左边的61现在被支也到了右边，如图（三）所示，这表明快速排序不具有检定性，3 .把干脆选择排序算法修改成各关键字最终由大到小排列，Sc1.SOa(Ar.n)(x(i=ji=n-hi+)(large-i;fur(j=i+l;jv=n：j+)if1large.keyIarjjc=j;if(Iaigc!=i)Iemp=ri;rfi=Arlarc;答：修改的算法如下所示./T限制nl衲门描/*用-IiUal趾记住当IW最大关彼字的位置*/Qj限制这越扫揄的比校范用*/祖如发觉更大若，的时
26、修改IarjtC的帆”larI批较莅IH酋兀东卜林不问.姬交换”/*交换是利用临时变fittemp进行的!Aiilargcl=mp:4 .已知待排的关雄字序列：70、83、99、65、10、32、7.9.请给出果纳干腌插入排序方法时好皑的图示过程，答：采纳干脆插入持序方法时俗措的图示过程如K.初始技奇：PO第1次扫描IPO第2次扫描：PO83I到83999916565103279第3次扫捕：BT7083叨10第4次扫描“布-6570839932第5次扫描：10657083997第6次加描：式一1032657083999I料火扫描(7J9103265708399J,行待排序的关键字序列：18、02、22、15、56、18、88、27、68.说给出采纳国泡排序方法时越越的图示过程(留.京：这里有两个关键字都是18.答：采纳印泡推序方法时每建的图示过程如下.1202221556188827630218152218562768880215IS1822275668880215182227566888初姑伏态1第1於柏格;笫2蜷柏搐:第3必启楼:AlA2AA4A5A6A7A同A9
