《数据结构基础教程》习题及解答.docx

《《数据结构基础教程》习题及解答.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,请用图示来表达构造一棵哈夫曼树的全过程。答：构造这棵哈夫变树的全过程如下所示.双亲的孩子链表表示法(我们介绍过双亲表示法和孩子融表表示法,没有介绍过带双亲的孩子链非表示法.里能够把两者结合起来)：(3)孩子/兄弟链衣衣示法.答：双亲去示法如下图依)所示:(2)带双亲的孩子链求去示法如图下(b)所示;(3)孩子/兄弟链表表示法如卜图(c)所示。loot-|IIAlBjTcTlIlDl+TeF11ItIf4g|ha1Ihl11N3 .将图626所示的二叉树转换成相应的森林。