数据结构及算法课后习题答案

1、-. z.2.3 课后习题解答2.3.2 判断题1线性表的逻辑顺序与存储顺序总是一致的。2顺序存储的线性表可以按序号随机存取。3顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。4线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有一样的特性，因此属于同一数据对象。5在线性表的顺序存储构造中，逻辑上相邻的两个元素在物理位置上并不一定相邻。6在线性表的链式存储构造中，逻辑上相邻的元素在物理位置上不一定相邻。7线性表的链式存储构造优于顺序存储构造。8在线性表的顺序存储构造中，插入和删除时移动元素的个数与该元素的位置有关。9线性表的链式存储构造是用一组

2、任意的存储单元来存储线性表中数据元素的。10在单链表中，要取得*个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储构造。11静态链表既有顺序存储的优点，又有动态链表的优点。所以它存取表中第i个元素的时间与i无关。12线性表的特点是每个元素都有一个前驱和一个后继。2.3.3 算法设计题1设线性表存放在向量Aarrsize的前elenum个分量中，且递增有序。试写一算法，将* 插入到线性表的适当位置上，以保持线性表的有序性，并且分析算法的时间复杂度。【提示】直接用题目中所给定的数据构造顺序存储的思想是用物理上的相邻表示逻辑上的相邻，不一定将向量和表示线性表长度的变量封装成一个构造体，因

3、为是顺序存储，分配的存储空间是固定大小的，所以首先确定是否还有存储空间，假设有，则根据原线性表中元素的有序性，来确定插入元素的插入位置，后面的元素为它让出位置，也可以从高低标端开场一边比拟，一边移位然后插入* ，最后修改表示表长的变量。int insert (datatype A,int *elenum,datatype *)/*设elenum为表的最大下标*/if (*elenum=arrsize-1) return 0;/*表已满，无法插入*/else i=*elenum;while (i=0 & Ai*)/*边找位置边移动*/Ai+1=Ai;i-; Ai+1=*;/*找到的位置是插入位的

4、下一位*/ (*elenum)+;return 1;/*插入成功*/时间复杂度为O(n)。2一顺序表A，其元素值非递减有序排列，编写一个算法删除顺序表中多余的值一样的元素。【提示】对顺序表A，从第一个元素开场，查找其后与之值一样的所有元素，将它们删除；再对第二个元素做同样处理，依此类推。void delete(Seqlist *A)i=0;while(ilast)/*将第i个元素以后与其值一样的元素删除*/k=i+1;while(klast&A-datai=A-datak)k+;/*使k指向第一个与Ai不同的元素*/n=k-i-1;/*n表示要删除元素的个数*/for(j=k;jlast;j+

5、)A-dataj-n=A-dataj;/*删除多余元素*/A-last= A-last -n;i+;3写一个算法，从一个给定的顺序表A中删除值在*y(*datai是否介于*和y之间，假设是，并不立即删除，而是用n记录删除时应前移元素的位移量；假设不是，则将A-datai向前移动n位。n用来记录当前已删除元素的个数。void delete(Seqlist *A,int *,int y)i=0;n=0;while(ilast)if (A-datai=*&A-dataidatai 介于*和y之间，n自增*/else A-datai-n=A-datai;/*否则向前移动A-datai*/i+;A-la

6、st-=n;4线性表中有n个元素，每个元素是一个字符，现存于向量Rn中，试写一算法，使R中的字符按字母字符、数字字符和其它字符的顺序排列。要求利用原来的存储空间，元素移动次数最小。【提示】对线性表进展两次扫描，第一次将所有的字母放在前面，第二次将所有的数字放在字母之后，其它字符之前。int fch(char c)/*判断c是否字母*/if(c=a&c=A&c=0&c=9) return (1);else return (0);void process(char Rn)low=0;high=n-1;while(lowhigh)/*将字母放在前面*/while(lowhigh&fch(Rlow)

7、low+;while(lowhigh&!fch(Rhigh) high-;if(lowhigh)k=Rlow;Rlow=Rhigh;Rhigh=k;low=low+1; high=n-1;while(lowhigh)/*将数字放在字母后面，其它字符前面*/while(lowhigh&fnum(Rlow) low+;while(lowhigh&!fnum(Rhigh) high-;if(lowhigh)k=Rlow;Rlow=Rhigh;Rhigh=k;5线性表用顺序存储，设计一个算法，用尽可能少的辅助存储空间将顺序表中前m个元素和后n个元素进展整体互换。即将线性表：a1, a2, , am,

8、b1, b2, , bn改变为：b1, b2, , bn , a1, a2, , am。【提示】比拟m和n的大小，假设mn，则将表中元素依次前移m次；否则,将表中元素依次后移n次。voidprocess(Seqlist *L,int m,int n)if(m=n)for(i=1;idata0;for(k=1;klast;k+)L-datak-1=L-datak;L-dataL-last=*;else for(i=1;idataL-last;for(k=L-last-1;k=0;k-)L-datak+1=L-datak;L-data0=*;6带头结点的单链表L中的结点是按整数值递增排列的，试写一

9、算法，将值为* 的结点插入到表L中，使得L仍然递增有序，并且分析算法的时间复杂度。LinkList insert(LinkList L,int *)p=L;while(p-ne*t&*p-ne*t-data)p=p-ne*t;/*寻找插入位置*/s=(LNode *)malloc(sizeof(LNode);/*申请结点空间*/s-data=*; /*填装结点*/s-ne*t=p-ne*t;p-ne*t=s;/*将结点插入到链表中*/return(L); 7假设有两个已排序递增的单链表A和B，编写算法将它们合并成一个链表C而不改变其排序性。LinkList bine(LinkList A, L

10、inkList B)C=A;rc=C;pa=A-ne*t;/*pa指向表A的第一个结点*/pb=B-ne*t;/*pb指向表B的第一个结点*/free(B);/*释放B的头结点*/while(pa&pb)/*将pa、pb所指向结点中，值较小的一个插入到链表C的表尾*/if(pa-datadata)rc-ne*t=pa;rc=pa;pa=pa-ne*t;elserc-ne*t=pb;rc=pb;pb=pb-ne*t;if(pa)rc-ne*t=pa;elserc-ne*t=pb;/*将链表A或B中剩余的局部到链表C的表尾*/return(C);8假设长度大于1的循环单链表中，既无头结点也无头指针

11、，p为指向该链表中*一结点的指针，编写算法删除该结点的前驱结点。【提示】利用循环单链表的特点，通过s指针可循环找到其前驱结点p及p的前驱结点q，然后可删除结点*p。viod delepre(LNode *s)LNode *p, *q;p=s;while (p-ne*t!=s)q=p; p=p-ne*t;q-ne*t=s;free(p);9两个单链表A和B分别表示两个集合，其元素递增排列，编写算法求出A和B的交集C，要求C同样以元素递增的单链表形式存储。【提示】交集指的是两个单链表的元素值一样的结点的集合，为了操作方便，先让单链表C带有一个头结点，最后将其删除掉。算法中指针p用来指向A中的当前结

12、点，指针q用来指向B中的当前结点，将其值进展比拟，两者相等时，属于交集中的一个元素，两者不等时，将其较小者跳过，继续后面的比拟。LinkList Intersect(LinkList A, LinkList B)LNode *q, *p, *r, *s; LinkList C;C= (LNode *)malloc(sizeof(LNode);C-ne*t=NULL;r=C;p=A; q=B;while (p & q )if (p-datadata) p=p-ne*t;elseif (p-data=q-data)s=(LNode *)malloc(sizeof(LNode);s-data=p-d

13、ata;r-ne*t=s;r=s;p=p-ne*t;q=q-ne*t;else q=q-ne*t;r-ne*t=NULL;C=C-ne*t;return C;10设有一个双向链表，每个结点中除有prior、data和ne*t域外，还有一个访问频度freq域，在链表被起用之前，该域的值初始化为零。每当在链表进展一次Locata(L,*)运算后，令值为*的结点中的freq域增1，并调整表中结点的次序，使其按访问频度的非递增序列排列，以便使频繁访问的结点总是靠近表头。试写一个满足上述要求的Locata(L,*)算法。【提示】在定位操作的同时，需要调整链表中结点的次序：每次进展定位操作后，要查看所查找

14、结点的freq域，将其同前面结点的freq域进展比拟，同时进展结点次序的调整。typedef struct dnodedatatype data;int freq;struct DLnode *prior,*ne*t;DLnode,*DLinkList;DlinkList Locate(DLinkList L,datatype *)p=L-ne*t;while(p&p-data!=*) p=p-ne*t;/*查找值为*的结点，使p指向它*/if(!p) return(NULL);/*假设查找失败，返回空指针*/p-freq+;/*修改p的freq域*/while(p-prior!=L&p-pr

15、ior-freqfreq)/*调整结点的次序*/k=p-prior-data;p-prior-data=p-data;p-data=k;k=p-prior-freq;p-prior-freq=p-freq;p-freq=k;p=p-prior;return(p);/*返回找到的结点的地址*/3.3 课后习题解答 #3.3.1 选择题1向一个栈顶指针为Top的链栈中插入一个p所指结点时，其操作步骤为C。ATop-ne*t=p;Bp-ne*t=Top-ne*t;Top-ne*t=p;Cp-ne*t=Top;Top=p; Dp-ne*t=Top;Top=Top-ne*t;2对于栈操作数据的原则是B。

16、A先进先出 B后进先出 C后进后出 D不分顺序3假设一个栈的入栈序列是1,2,3,n，其输出序列为p1,p2,p3，pN,假设pN是n，则pi是D。AiBn-i C n-i+1 D不确定4表达式a*(bc)d的后缀表达式是B。Aabcd*-+ Babc-*d+ Cabc*-d+ D+-*abcd5采用顺序存储的两个栈共享空间S1.m，topi代表第i个栈( i=1,2)的栈顶，栈1的底在S1，栈2的底在Sm，则栈满的条件是B。Atop2-top1|=0 Btop1+1=top2Ctop1+top2=m Dtop1=top26一个栈的入栈序列是a,b,c,d,e，则栈的不可能的输出序列是C。A

17、edcba B decba Cdceab D abcde7在一个链队列中，假设f,r分别为队首、队尾指针，则插入s所指结点的操作为B。Af-ne*t=r;f=s;Br-ne*t=s;r=s;Cs-ne*t=r;r=s;Ds-ne*t=f;f=s;8用不带头结点的单链表存储队列时，在进展删除运算时D。A仅修改头指针B仅修改尾指针C头、尾指针都要修改D头、尾指针可能都要修改9递归过程或函数调用时，处理参数及返回地址，要用一种称为C的数据构造。A队列B静态链表C栈D顺序表10栈和队都是C。A顺序存储的线性构造B链式存储的非线性构造C限制存取点的线性构造D限制存取点的非线性构造3.3.2 判断题1栈和

18、队列的存储，既可以采用顺序存储构造，又可以采用链式存储构造。2任何一个递归过程都可以转换成非递归过程。3假设输入序列为1,2,3,4,5,6，则通过一个栈可以输出序列3,2,5,6,4,1。4通常使用队列来处理函数的调用。5循环队列通常用指针来实现队列的头尾相接。3.3.3 简答题1循环队列的优点是什么？如何判别它的空和满？循环队列的优点是能够克制假溢满现象。设有循环队列sq，队满的判别条件为：sq-rear+1%ma*size=sq-front;或sq-num=ma*size。队空的判别条件为：sq-rear=sq-front。2栈和队列数据构造各有什么特点，什么情况下用到栈，什么情况下用到

19、队列？栈和队列都是操作受限的线性表，栈的运算规则是后进先出，队列的运算规则是先进先出。栈的应用如数制转换、递归算法的实现等，队列的应用如树的层次遍历等。3什么是递归？递归程序有什么优缺点？一个函数在完毕本函数之前，直接或间接调用函数自身，称为递归。例如，函数f在执行中，又调用函数f自身，这称为直接递归；假设函数f在执行中，调用函数g，而g在执行中，又调用函数f，这称为间接递归。在实际应用中，多为直接递归，也常简称为递归。递归程序的优点是程序构造简单、清晰，易证明其正确性。缺点是执行中占存空间较多，运行效率低。4设有编号为1,2,3,4的四辆车，顺序进入一个栈式构造的站台，试写出这四辆车开出车站

20、的所有可能的顺序每辆车可能入站，可能不入站，时间也可能不等。1234,1243,1324,1342,1432,213,2143,2314,2341,2431,3214,3241,3421,43214.3 课后习题解答#4.3.1 选择题1下面关于串的表达错误的选项是C。A串是字符的有限序列B串既可以采用顺序存储，也可以采用链式存储C空串是由空格构成的串D模式匹配是串的一种重要运算2串的长度是指B。A串中所含不同字母的个数 B串中所含字符的个数C串中所含不同字符的个数 D串中所含非空格字符的个数3串S=aaab,其Ne*t数组值为A。A0123 B1123 C1231 D12114二维数组M的成

21、员是6个字符每个字符占一个存储单元组成的串，行下标i的围从0到8，列下标j的围从1到10，则存放M至少需要D个字节；M的第8列和第5行共占A个字节；假设M按行优先方式存储，元素M85的起始地址与当M按列优先方式存储时的C元素的起始地址一致。1A90 B180 C240 D5402A108 B114 C54 D603AM85 BM310 CM58 DM095数组A中，每个元素的存储占3个单元，行下标i从1到8，列下标j从1到10，从首地址SA开场连续存放在存储器，存放该数组至少需要的单元个数是C，假设该数组按行存放，元素A85的起始地址是D，假设该数组按列存放，元素A85的起始地址是B。1A80

22、 B100 C240 D2702ASA+141 BSA+144 CSA+222 DSA+2253ASA+141 BSA+180 CSA+117 DSA+2256稀疏矩阵采用压缩存储，一般有C两种方法。A二维数组和三维数组 B三元组和散列C三元组表和十字链表 D散列和十字链表4.3.2 判断题1串相等是指两个串的长度相等。2KMP算法的特点是在模式匹配时指示主串的指针不会变小。3稀疏矩阵压缩存储后，必会失去随机存取功能。4数组是线性构造的一种推广，因此与线性表一样，可以对它进展插入，删除等操作。5假设采用三元组存储稀疏矩阵，把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算。6假设一个广

23、义表的表头为空表，则此广义表亦为空表。7所谓取广义表的表尾就是返回广义表中最后一个元素。4.3.3 简答题1KMP算法较朴素的模式匹配算法有哪些改良KMP算法主要优点是主串指针不回溯。当主串很大不能一次读入存且经常发生局部匹配时，KMP算法的优点更为突出。2设字符串S=aabaabaabaac，P=aabaac。1给出S和P的ne*t值和ne*tval值；2假设S作主串，P作模式串，试给出利用KMP算法的匹配过程。【解答】 1S的ne*t与ne*tval值分别为9和9，p的ne*t与ne*tval值分别为012123和002003。 2利用BF算法的匹配过程： 利用KMP算法的匹配过程：第一趟

24、匹配：aabaabaabaac 第一趟匹配：aabaabaabaacaabaac(i=6,j=6) aabaac(i=6,j=6) 第二趟匹配：aabaabaabaac 第二趟匹配：aabaabaabaac aa(i=3,j=2) (aa)baac 第三趟匹配：aabaabaabaac 第三趟匹配：aabaabaabaac a(i=3,j=1) (成功) (aa)baac第四趟匹配：aabaabaabaac aabaac(i=9,j=6)第五趟匹配：aabaabaabaacaa(i=6,j=2)第六趟匹配：aabaabaabaac a(i=6,j=1)第七趟匹配：aabaabaabaac(成功

25、) aabaac(i=13,j=7)3假设按行优先存储整数数组A9358时，第一个元素的字节地址是100，每个整数占个字节。问以下元素的存储地址是什么？(1) a0000 (2)a1111 (3)a3125 (4)a8247【解答】(1) LOC( a0000)=100(2) LOC( a1111)=100+(3*5*8*1+5*8*1+8*1+1)*4=776(3) LOC( a3125)=100+(3*5*8*3+5*8*1+8*2+5) *4=1784(4) LOC( a8247)= 100+(3*5*8*8+5*8*2+8*4+7) *4=48164假设一个准对角矩阵：aa11 a12

26、a21 a22a33 a34a43 a44 . aij a2m-1,2m-1 a2m-1,2m a2m,2m-1 a2m,2m 按以下方式存储于一维数组B4m中m为一个整数：012345 6 k 4m-1 4ma 11a 12a21a22a33a34a43aija2m-1,2ma2m,2m-1a2m,2m写出下标转换函数k=f(i,j)。【解答】由题目可知，每一行有两个非0元素。当i为奇数时，第i行的元素为：ai,i、ai,(i+1)，此时k=2*(i-1)+j-i=i+j-2当i为偶数时，第i行的元素为：ai,(i-1)、ai,i，此时k=2*(i-1)+j-I+1=i+j-1综上所述，k=

27、i+j-i%2-1。5设有nn的带宽为3的带状矩阵A，将其3条对角线上的元素存于数组B3n中，使得元素Buv=aij，试推导出从i,j到 (u,v)的下标变换公式。【解答】u=j-i+1v=j-16现有如下的稀疏矩阵A如下图，要求画出以下各种表示方法。1三元组表表示法2十字链表法。0 0 0 22 0 -150 0 0 22 0 -150 13 3 0 0 00 0 0 -6 0 00 0 0 0 0 091 0 0 0 0 00 0 28 0 0 0【解答】1三元组表表示法:i j v1234567 4 221 6 -152 2 132 3 33 4 -65 1 916 3 282十字链表法

28、：0012345012345519123334-61422632816-1522137画出以下广义表的头尾表示存储构造示意图。1A=(a,b,c),d,(a,b,c)2B=(a,(b,(c,d),e),f)1111111 1 1 d0 a1 b1 c211111 1 1 0 f0 a0 b0 c1 10 c0 d5.3 课后习题解答 5.3.1 选择题1以下说确的是C。A二叉树中任何一个结点的度都为2 B二叉树的度为2C一棵二叉树的度可小于2 D任何一棵二叉树中至少有一个结点的度为22以二叉链表作为二叉树的存储构造，在具有n个结点的二叉链表中n0，空链域的个数为C。A2n-1Bn-1Cn+1D

29、2n+13线索化二叉树中，*结点*p没有孩子的充要条件是B。Ap-lchild=NULL Bp-ltag=1且p-rtag=1Cp-ltag=0 Dp-lchild=NULL 且p-ltag=14如果结点A有3个兄弟,而且B是A的双亲,则B的度是B。A3 B4 C5 D1 5*二叉树T有n个结点,设按*种顺序对T中的每个结点进展编号，编号值为1,2,.n。且有如下性质:T中任意结点v,其编号等于左子树上的最小编号减,而v的右子树的结点中,其最小编号等于v左子树上结点的最大编号加，这是按B编号的。A 中序遍历序列B 先序遍历序列 C 后序遍历序列 D 层次顺序6设F是一个森林，B是由F转换得到的

30、二叉树，F中有n个非终端结点,B中右指针域为空的结点有C个。An-1 B n C n+1 Dn+2 7一棵完全二叉树上有1001个结点，其中叶子结点的个数是C。A 500 B 501 C490D4958设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为N1，N2和N3。与森林F对应的二叉树根结点的右子树上的结点个数是D。AN1 BN1+N2 CN2 DN2+N39任何一棵二叉树的叶结点在先序、中序、后序遍历序列中的相对次序A。A不发生改变 B 发生改变 C 不能确定 D 以上都不对10假设一棵二叉树的后序遍历序列为dabec，中序遍历序列为debac，则先序遍历序列为D。Acbed Bd

31、ecab Cdeabc Dcedba11假设一棵二叉树的先序遍历序列为abdgcefh，中序遍历的序列为dgbaechf，则后序遍历的结果为D。 A gcefhaB gdbecfhaC bdgaechfDgdbehfca12一棵非空二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足B。A所有的结点均无左孩子 B所有的结点均无右孩子C只有一个叶子结点 D是一棵满二叉树13引入线索二叉树的目的是A。A加快查找结点的前驱或后继的速度B为了能在二叉树中方便的进展插入与删除C为了能方便的找到双亲D使二叉树的遍历结果唯一14设高度为h的二叉树上只有度为和度为的结点，则此类二叉树中所包含的结点数

32、至少为B。A2*h B 2*h-1 C 2*h+1 Dh+115一个具有567个结点的二叉树的高h为D。A9 B10 C9至566之间 D10至567之间16给一个整数集合3，5，6，7，9，与该整数集合对应的哈夫曼树是B。A B C D937693765 3567979536765395.3.2 判断题1二叉树是树的特殊形式。2由树转换成二叉树，其根结点的右子树总是空的。3先根遍历一棵树和先序遍历与该树对应的二叉树，其结果不同。4先根遍历森林和先序遍历与该森林对应的二叉树，其结果不同。5完全二叉树中，假设一个结点没有左孩子，则它必是叶子。6对于有N个结点的二叉树，其高度为log2N1。7假设

33、一个结点是*二叉树子树的中序遍历序列中的最后一个结点，则它必是该子树的先序遍历序列中的最后一个结点。8假设一个结点是*二叉树子树的中序遍历序列中的第一个结点，则它必是该子树的后序遍历序列中的第一个结点。9不使用递归也可实现二叉树的先序、中序和后序遍历。10先序遍历二叉树的序列中，任何结点的子树的所有结点不一定跟在该结点之后。11先序和中序遍历用线索树方式存储的二叉树，不必使用栈。12在后序线索二叉树中，在任何情况下都能够很方便地找到任意结点的后继。13哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。14在哈夫曼编码中，出现频率一样的字符编码长度也一定一样。15用一维数组存放二叉树

34、时，总是以先序遍历存储结点。16由先序序列和后序序列能唯一确定一棵二叉树。17由先序序列和中序序列能唯一确定一棵二叉树。18对一棵二叉树进展层次遍历时，应借助于一个栈。19完全二叉树可采用顺序存储构造实现存储，非完全二叉树则不能。20满二叉树一定是完全二叉树，反之未必。5.3.3 简答题1一棵度为2的树与一棵二叉树有何区别？树与二叉树之间有何区别？【解答】二叉树是有序树，度为2的树是无序树，二叉树的度不一定是2。ADBADBGEHCF(图 1)2对于图1所示二叉树，试给出：1它的顺序存储构造示意图；2它的二叉链表存储构造示意图；3它的三叉链表存储构造示意图。【解答】1顺序存储构造示意图：ABC

35、DEFGH2二叉链表存储构造示意图： 3三叉链表存储构造示意图：A A BC D E F G H ABC D E F G H IDIDEFGCBANMKJH(图 2)1双亲数组表示法示意图；2孩子链表表示法示意图；3孩子兄弟链表表示法示意图。【解答】1双亲数组表示法示意图： 2孩子链表表示法示意图：00A-11B02C03D24E25F16G17H58I29J410K411M312N82 6410 15311 97 12 0A1B2C3D4E5F6G7H8I9J10K11M12N8 3孩子兄弟链表表示法示意图：A A B N H C GF EDI J K M 4画出图3所示的森林经转换后所对应

36、的二叉树，并指出森林中满足什么条件的结点在二叉树中是叶子。DDBCIG HAFE J(图 3)【解答】HHFGIJABCED在二叉树中*结点所对应的森林中结点为叶子结点的条件是该结点在森林中既没有孩子也没有右兄弟结点。5将题5图所示的二叉树转换成相应的森林。HHGDE FBACC(题5图)【解答】森林：AABHEGDCF6证明：在结点数多于1的哈夫曼树中不存在度为1的结点。证明：由哈夫曼树的构造过程可知，哈夫曼树的每一分支结点都是由两棵子树合并产生的新结点，其度必为2，所以哈夫曼树中不存在度为1的结点。7证明：假设哈夫曼树中有n个叶结点，则树中共有2n1个结点。证明：n个叶结点，需经n-1次合

37、并形成哈夫曼树，而每次合并产生一个分支结点，所以树中共有2n-1个结点。8证明：由二叉树的前序序列和中序序列可以唯一地确定一棵二叉树。证明：给定二叉树结点的前序序列和对称序中序序列，可以唯一确定该二叉树。因为前序序列的第一个元素是根结点，该元素将二叉树中序序列分成两局部，左边设l个元素表示左子树，假设左边无元素，则说明左子树为空；右边设r个元素是右子树，假设为空，则右子树为空。根据前序遍历中根左子树右子树的顺序，则由从第二元素开场的l个结点序列和中序序列根左边的l个结点序列构造左子树，由前序序列最后r个元素序列与中序序列根右边的r个元素序列构造右子树。9一棵度为m的树中有n1个度为1的结点，n

38、2个度为2的结点，nm个度为m的结点，问该树中共有多少个叶子结点？有多少个非终端结点？解：设树中共有n个结点，n0个叶结点，则n=n0+n1+nm (1)树中除根结点外，每个结点对应着一个分支，而度为k的结点发出k个分支，所以： n=n1+2*n2+m*nm+1 (2)由(1)、(2)可知n0= n2+2*n3+3*n4+(m-1)*nm+110在具有nn1个结点的树中，深度最小的那棵树其深度是多少？它共有多少叶子和非叶子结点？深度最大的那棵树其深度是多少？它共有多少叶子和非叶子结点？2; n-1; 1; n; 1, n-111设高度为h的二叉树上只有度为0和度为2的结点，问该二叉树的结点数可

39、能到达的最大值和最小值。最大值：2h-1；最小值：2h-112求表达式： ab*(cd)e/f的波兰式前缀式和逆波兰式后缀式。波兰式： - + a * b c d / e f 逆波兰式：a b c d - * + e f / -13画出和以下序列对应的树T：树的先根次序访问序列为：GFKDAIEBCHJ；树的后根访问次序为：DIAEKFCJHBG。【解答】对应的二叉树和树分别如下左、右图所示：GBGBIEADKFCHJGBIEADKFCHJ14画出和以下序列对应的森林F：森林的先根次序访问序列为：ABCDEFGHIJKL；森林的后根访问次序为：CBEFDGAJIKLH。AABDGCEFHIKJ

40、L15画出和以下序列对应的树T：二叉树的层次访问序列为：ABCDEFGHIJ；二叉树的中序访问次序为：DBGEHJACIF。【解答】AABCDEFGHIJ按层次遍历，第一个结点假设树不空为根，该结点在中序序列中把序列分成左右两局部左子树和右子树。假设左子树不空，层次序列中第二个结点左子树的根；假设左子树为空，则层次序列中第二个结点右子树的根。对右子树也作类似的分析。层次序列的特点是：从左到右每个结点或是当前情况下子树的根或是叶子。16假设用于通信的电文由字符集a,b,c,d,e,f,g中的字母构成。它们在电文中出现的频度分别为0.31,0.16,0.10,0.08,0.11,0.20,0.04

41、,1为这7个字母设计哈夫曼编码。2对这7个字母进展等长编码，至少需要几位二进制数？哈夫曼编码比等长编码使电文1.000.591.000.590.410.280.210.120.310.160.800.400.200.100.111111111哈夫曼树：a：10b：110c：010d：1110e：011f：00g：11112对这7个字母进展等长编码，至少需要3位二进制数。等长编码的平均长度：0.31*3+0.16*3+0.10*3+0.08*3+0.11*3+0.20*3+0.04*3=3哈夫曼编码：0.31*2+0.16*3+0.10*3+0.08*4+0.11*3+0.20*2+0.04*4

42、=2.54哈夫曼编码比等长编码使电文总长压缩了：1 - 2.54/3=15.33%5.3.4 算法设计题1给定一棵用二叉链表表示的二叉树，其根指针为root，试写出求二叉树结点的数目的算法。【提示】采用递归算法实现。二叉树结点的数目二叉树结点的数目0 当二叉树为空左子树结点数目右子树结点数目1 当二叉树非空int count(BiTree root)if (root=NULL)return (0); else return (count(root-lchild)+count(root-rchild)+1);2请设计一个算法，要求该算法把二叉树的叶结点按从左至右的顺序链成一个单链表。二叉树按lc

43、hild-rchild方式存储，时用叶结点的rchild域存放链指针。【提示】这是一个非常典型的基于二叉树遍历算法，通过遍历找到各个叶子结点，因为不管前序遍历、中序遍历和后序遍历，访问叶子结点的相对顺序都是一样的，即都是从左至右。而题目要将二叉树中的叶子结点按从左至右顺序建立一个单链表，因此，可以采用三种遍历中的任意一种方法遍历。这里使用中序递归遍历。设置前驱结点指针pre，初始为空。第一个叶子结点由指针head指向，遍历到叶子结点时，就将它前驱的rchild指针指向它，最后叶子结点的rchild为空。LinkList head,pre=NULL;/*全局变量*/LinkList InOrde

44、r(BiTree T)/*中序遍历二叉树T，将叶子结点从左到右链成一个单链表，表头指针为head*/if(T)InOrder(T-lchild);/*中序遍历左子树*/if(T-lchild=NULL & T-rchild=NULL)/*当前是叶子结点*/if(pre=NULL) head=T; pre=T;/*处理第一个叶子结点*/elsepre-rchild=T; pre=T; /*将叶子结点链入链表*/InOrder(T-rchild);/*中序遍历右子树*/pre-rchild=NULL;/*设置链表尾结点*/return(head);3给定一棵用二叉链表表示的二叉树，其根指针为roo

45、t，试写出求二叉树的深度的算法。【提示】采取递归算法。int Height(BiTree root)int hl,hr;if (root=NULL) return(0);else hl=Height(root-lchild); hr=Height(root-rchild);if(hlhr) return (hl+1); else return(hr+1); 4给定一棵用二叉链表表示的二叉树，其根指针为root，试求二叉树各结点的层数。【提示】采用先序递归遍历算法实现。二叉树结点的层次数二叉树结点的层次数1当结点为根结点其双亲结点的层次数1当结点非根结点void fun (BiTree root

46、, int n)if (t=NULL) return;else printf(%d,n);fun(root-lchild,n+1);fun(root-rchild,n+1);5给定一棵用二叉链表表示的二叉树，其根指针为root，试写出将二叉树中所有结点的左、右子树相互交换的算法。【提示】设root 为一棵用二叉链表存储的二叉树，则交换各结点的左右子树的运算可基于后序遍历实现：交换左子树上各结点的左右子树；交换左子树上各结点的左右子树；再交换根结点的左右子树。void E*change(BiTree root) BiTNode *p;if (root) E*change(root-lchild)

47、;E*change(root-rchild);p=root-lchild; root-lchild=root-rchild;root-rchild=p;6一棵具有n个结点的完全二叉树采用顺序构造存储，试设计非递归算法对其进展先序遍历。【提示】二叉树的顺序存储是按完全二叉树的顺序存储格式按层次存储的，双亲结点与子女结点的下标间有确定的关系。对顺序存储构造的二叉树进展先序遍历，与二叉链表存放二叉树的遍历策略类似。但是在顺序存储构造下，判二叉树结点为空的条件为：结点下标大于n，或结点值为0一般二叉树中的虚结点。void PreOrder (datatype datan+1) /*0号单元未用*/in

48、t stackn ; int top; if(n1) return;t=1;top=0; while (t0)while (t=n&datat!=0)Visite(datat);stacktop=t;top+;t=t*2; if (topdata=*)/*假设当前结点值为*，依次输出栈中元素的值*/while (!Empty_Stack(S) Pop(S,q);printf(q-data); return;elsePush_Stack(S,p);/*假设当前结点值不是*，压栈*/ p=p-lchild; if(!Empty_Stack(S) Pop_Stack(S,r);/*当栈非空，栈顶元素

49、出栈，进入右子树*/p=r-rchild; else return; 8一棵二叉树的后序遍历序列和中序遍历序列，写出可以确定这棵二叉树的算法。【提示】根据后序遍历和中序遍历的特点，采用递归算法实现。void InPost 中序遍历序列和后序遍历序列，t=(BiTNode *) malloc(sizeof(BiTNode); t-data=postpr;m=il;while (inm!=post pr ) m+;if (m= il)t-lchild=NULL ; else InPost ( in, post,il,m-1,pl,pl+m-1-il, t-lchild); if (m=ir)t-r

50、child=NULL;else InPost (in,post,m+1,ir,pr-ir+m,pr-1,t-rchild);9编写算法判断一棵二叉链表表示的二叉树是否是完全二叉树。【提示】根据完全二叉树的定义可知，对完全二叉树按照从上到下，从左到右的次序遍历应满足：假设*结点没有左孩子，则一定无右孩子；假设*结点缺左或右孩子，则其所有后继一定无孩子。因此，可采用按层次遍历二叉树的方法依次对每个结点进展判断。这里增加一个标志以表示所有已扫描过的结点均有左、右孩子，将局部判断结果存入CM中，CM表示整个二叉树是否是完全二叉树，B为1表示到目前为止所有结点均有左右孩子。int pleteBT(BiT

51、ree T) Init_Queue(Q); /*初始化队列Q*/ B=1; CM=1; if (T!=NULL) In_Queue(Q,T); while(!Empty_Queue(Q)/*当队列不为空时执行循环*/ p=Out_Queue(Q); if(p-lchild=NULL) B=0;/*B=0表示缺少左、右孩子*/ if(rchild!=NULL) CM=0;/*CM=0表示不是完全二叉树*/ else CM=B;In_Queue(Q,p-lchild);/*左孩子入队列*/if(p-rchild=NULL) B=0; else In_Queue(Q,p-rchild);/*右孩子入

52、队列*/ return(CM);10有n个结点的完全二叉树存放在一维数组A1.n中，试据此建立一棵用二叉链表表示的二叉树。BiTree Create(dataype A,inti)/*n个结点的完全二叉树存于一维数组A中，据此建立以二叉链表表示的完全二叉树,初始调用时,i=1*/BiTree T;if (idata=Ai;if(2*in) T-lchild=NULL;elseT-lchild=Create(A,2*i);if(2*i+1n) T-rchild=NULL;elseT-rchild=Create(A,2*i+1);return (T);11编写算法判定两棵二叉树是否相似。所谓两棵二

53、叉树s和t相似，即要么它们都为空或都只有一个结点，要么它们的左右子树都相似。【提示】两棵空二叉树或仅有根结点的二叉树相似；对非空二叉树，可判左右子树是否相似，采用递归算法。intSimilar(BiTree s, BiTree t) if(s=NULL & q=NULL) return (1);else if(!s & t | s & !t) return (0);else return(Similar(s-lchild,t-lchild) & Similar(s-rchild,t-rchild)12写出用逆转链方法对二叉树进展先序遍历的算法。【提示】用逆转链的方法遍历二叉树，不需要附加的栈空

54、间，而是在遍历过程中沿结点的左右子树下降时，临时改变结点lchild或者rchild的值，使之指向双亲，从而为以后的上升提供路径，上升时再将结点的lchild或者rchild恢复。typedef struct tnode datatype data; int tag; /*tag的值初始为0，进入左子树时置1，从左子树回来时，再恢复为0*/ struct tnode *lchild, *rchild; Bnode, *Btree;void PreOrder(Btree bt) Bnode *r, *p, *q; /*p指向当前结点，r指向p的双亲，q指向要访问的下一结点*/if(bt=NULL

55、) return; p=bt; r= NULL: while( p) Visit(p);/*访问p所指结点*/ if(p-lchild)/*下降进入左子树*/ p-tag=1; q=p-lchild; q=p-lchild=r; r=p; p=q; else if(p-rchild)/*下降进入右子树*/ q=p-rchild; p-rchild=r; r=p; p=q; else /*上升*/whle(r&t-tag=0) | (r&t-tag=1&r-rchild=NULL) if(r&t-tag=0) q=r-rchild; r-rchild=p; p=r; r=q;/*从右子树回来*/

56、else r-tag=0; q=r-lchild; r-lchild=p; p=r; r=q;/*从左子树回来*/ if (r=NULL) return;else r-tag=0; q=r-rchild; r-rchild= r-lchild; r-lchild=p; p=q;/*从左子树回来，准备进入右子树*/13对以孩子兄弟链表表示的树编写计算树的深度的算法。【提示】采用递归算法实现。树的深度树的深度0 假设树为空Ma*第一棵子树的深度1，兄弟子树的深度 假设树非空int high(CSTree T) if (T=NULL )return ( 0 );/*假设树为空，返回0*/else h

57、1=high (t-lchild );/*h1为T的第一棵子树的深度*/h2=high(t-ne*tsibling );/*h2为t的兄弟子树的深度*/return(ma*(h1+1,h2); 14对以孩子链表表示的树编写计算树的深度的算法。【提示】采用递归算法实现。树的深度树的深度1 假设根结点没有子树ma*(所有子树的深度)1 假设根结点有子树#define MA*NODE 树中结点的最大个数int high(SNode tMA*NODE,int j)if(tj.firstchild=NULL) return(1);/*假设根结点没有子树*/elsep=ti.firstchild;ma*=

58、high(t,p-data);p=p-ne*tchild;while(p)h=high(t,p-data);if(hma*) ma*=h; p=p-ne*tchild;return(ma*+1);15对以双亲链表表示的树编写计算树的深度的算法。【提示】从每一个结点开场，从下向上搜索至根结点，记录结点的层次数，其中的最大值就是树的深度。int high(PNodet , int n)/*求有n个结点的树t的深度*/ ma*h=0;for (i=0 ;ima*h) ma*h=h; return(ma*h) ;6.3.1 选择题1n条边的无向图的邻接表的存储中，边结点的个数有A。An B2n Cn/

59、2 Dn*n2n条边的无向图的邻接多重表的存储中，边结点的个数有A。An B2n Cn/2 Dn*n3以下哪一种图的邻接矩阵是对称矩阵？B。A有向图B无向图 CAOV网 DAOE网4最短路径的生成算法可用C。A普里姆算法 B克鲁斯卡尔算法 C迪杰斯特拉算法 D哈夫曼算法5一个无向图的邻接表如以下图所示：序号序号verte*firstedge0v11v22v33v4320310111从顶点v0出发进展深度优先搜索，经历的结点顺序为B。Av0, v3, v2, v1 Bv0, v1, v2, v3 Cv0, v2, v1, v3 Dv0, v1, v3, v22从顶点V0出发进展广度优先搜索，经历

60、的结点顺序为D。Av0, v3, v2, v1 Bv0, v1, v2, v3 Cv0, v2, v1, v3 Dv0, v1, v3, v26设有向图n个顶点和e条边，进展拓扑排序时，总的计算时间为D。AO (nlog2e) BO (en ) CO ( elog2n) DO (n+e)7含有n个顶点e条边的无向连通图，利用Kruskal算法生成最小生成树，其时间复杂度为A。AO (elog2e) BO (en ) CO ( elog2n) DO (nlog2n)8关键路径是事件结点网络中A。A从源点到汇点的最长路径 B从源点到汇点的最短路径 C最长的回路 D最短的回路9下面关于求关键路径的说