2016数据结构课后习题答案.pdf

《2016数据结构课后习题答案.pdf》由会员分享，可在线阅读，更多相关《2016数据结构课后习题答案.pdf（35页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、习题一答案1 .填空题（1）数据元素的有限集合，k上关系的有限集合（2）顺 序 存 储（连续），链 式 存 储（不连续）（3）有穷性，确定性，可行性，输入，输出（4）时间复杂度，空间复杂度2 .简述下列术语（1）数据一是信息的载体，它是描述客观事物的数、字符以及所有能输入到计算机中被计算机程序识别、加工处理的信息的集合。（2）数据元素一是数据的基本单位，是对一个客观实体的数据描述。一个数据元素可以由一个或若干个数据项组成。数据元素也被称为结点或记录。（3）数据对象一具有相同性质的数据元素的集合就是一个数据对象，它是数据的一个子集。（4）数据结构一数据结构就是数据之间的相互关系（即数据的组织形式

2、）及在这些数据上定义的数据运算方法的集合。（5）存储结构一数据的存储结构是数据的逻辑结构在计算机内部的表示或实现，又称为数据的物理结构，它包括数据元素的表示和关系的表示。（6）数据类型一是具有相同性质的计算机数据的集合及定义在这个数据集合上的一组操作的总称。3 .举例说明一下数据结构和算法的关系。通过公式：|程序=数 据 结 构 镇 祖 我们可以比较直观地看出二者的关系，即数据结构（包个完整的程序括逻辑结构和存储结构）的设计和算法的编写是程序设计的两个关键步骤，一就是由一套合理的数据结构和建立在该结构上的算法构成的。具体的说：在进行程序设计之前我们首先要为待处理的数据设计一个合理的逻辑结构，进

3、而为之设计一种适合的存储结构，因为光有逻辑结构是不够的，只有存储结构才是与计算机语言直接相关的！有了这一套前期准备，我们才能在这个基础上设计算法，用一种计算机语言去处理这些数据，最终达到程序设计的目的。当然，随着逻辑结构和存储结构的不同，我们设计的算法也会有所差别，这在以后的学习中会体会到。卜面通过个简单的例子说明这种关系。假设我们要设计一个两个n阶方阵相乘的程序：已知两个n阶方阵A和 B,我们要计算它们的乘积，得到一个新的n阶方阵C。那么在设计这个程序之前首先想到得就是设计一种逻辑结构表示方阵，这里我们用二维数组表示它们，因为二维数组最能直观地表示这种结构；有了逻辑结构了自然还要为之设计一种

4、存储结构，这里我们选择顺序存储方法，因 为 C语言对这种存储结构给予了很好的支持，例如定义一个n阶实型的二维数 组 A只要用float A n n;这条语句就可以了，C语言在内存种为之分配了一个n*n长度的顺序存储空间（注意：C 语言默认二维数组是按行优先存储的），是不是很方便？有了这些准备，我们就可以设计算法进行计算了，其算法如下：void matrixmult（float Ann,float Bnn,float Cnn）i n t i,j ,k ；f l o a t x;f o r (i=0;i n;i+)(f o r(j=0;j n;j+)(x=0;f o r (k=0;k n;k+)(

5、x+=A i k *B k j ;)C i j =x；)通过上面这个例子我们简单的阐述了数据结构与算法的关系，更深入的内涵还要读者在以后的学习中自己慢慢地体会。4 .设 有 数 据 逻 辑 结 构 为 B=(K,R ),K=k l ,k 2 ,.,k 9r=,k 2,k 5 ，,k 4,k 7 ，k 4,k 6 画出这个逻辑结构的图示，并确定相对于r哪些结点是开始结点，哪些结点是终端结点？通过以后的学习我们会知道这是一个有向图，图中共有9 个结点，其中开始结点有2个，分别为K 1 和 K2；终端结点有2个，分别为K 6 和 K7。逻辑结构图表示如下：7.何 谓 算 法？试详述算法设计的目的和算

6、法必须满足的条件。算法是对特定问题求解步骤的一种描述，实际上是指令的有限序列，其中每一条指令表示一个或多个操作。我们知道，程序设计的第一步是为待处理的数据设计一种合理的数据结构(包括逻辑结构和物理结构)，这一步固然重要，但这不是我们的目的，设计数据结构的最终目的是为了在这个基础上编写算法进而对其进行相关的操作(例如：遍历，查找，排序，插入，删除等)，如果不去编写相应的算法那么设计数据结构也就失去了它的意义，你所输入到计算机的数据永远都是 死数据，程序设计也就成了空谈！一句话：设计数据结构的目的是为了对它们进行处理，而数据处理正是通过相应的算法实现的！总的来说，一个算法应具有以下5个重要特性：第

7、一，有穷性：一个算法必须总是(对任何合法的输入值)在执行有穷步之后结束，且每一步都可在有穷时间内完成；第二，确定性：算法中每条指令必须有确切的含义，读者理解时不会产生二意性。并且，在任何条件下，算法只有唯一的一条执行路径，即对相同的输入只能得到相同的输出；第三，可行性：一个算法是能行的，即算法中描述的操作都是通过已经实现的基本运算执行有限次来实现的；第四，输入：一个算法有零个或多个的输入，这些输入取自于某个特定的对象的集合；第五，输出：一个算法有一个或多个的输出。这些输出是同输入有着某些特定关系的量。8.编写一个算法，对三个两位数按由大到小的顺序进行排序，描述构造该算法的思维程。算法如下：vo

8、id order(short a,short b,short c)(short t;if(ab)t=a;a=b;b=t;if(ac)t=a;a=c;c=t;if(bnext=p-next-next;(3)Head-next=Head(Head 为链表的头结点)，Head=NULL(Head为链表的第一个结点)(4)Head-next=Head-next-next(Head 为 链 表 的 头 结 点)；Head=Head-next(Head为 链 表 的 第 一 个 结 点)，以上均假设链表存在至少两 个 结 点。(5)D(因为顺序表具有随即存取的优点)2.动态与静态数据结构在计算机内存中的存

9、储方式有何不同？各有何优缺点？参考答案：静态存储方式(顺序存 储)一 逻 辑 相 邻，物理相邻。优点：便于数据的随即存取，结点存储利用率高(不需要存储指针)；缺点：存取数据时要移动大量的元素，由于事先不知道存储结点的最大个数，所以应该分配尽可能大的存储空间，从而可能会造成空间浪费！动态存储方式(链式存 储)一逻辑相邻，物理不一定相邻。优点：动态分配和释放存储单元，避免了空间浪费，插入删除结点不需要移动大量的其他结点，只需要修改有限的指针变量；缺点：不具备顺序存储结构随即存取的优点，查找结点需要从表头开始，一个结点的存储利用率较低，以为每个结点都要存储一个指向下个结点的指针变量。3.描述以下三个

10、概念的区别：头指针、头结点、第一个结点。参考答案：头指针一指向头结点的指针变量；头结点一为了操作链表方便而设置的一个特殊的结点，该结点用于标示一个链表结构的存在，他不存储实在的数据；第一个结点一链表中的第一个实际存储数据的结点，区别于头结点！在有头结点的链表中第一个结点应该是头结点后面的那个结点。4.试写出一个计算线性链表P 中结点个数的算法，其中指针P 指向该表中第一个结点,尾结点的指针域为空。int count(datatype*p)/*假设结点存储 datatype 型的数据*/(int num=0;while(p!=NULL)(+num;p=p-next;)return num;)5.

11、假 设 LA、L B 为两个递增有序的线性链表，试写出将这两个线性链表归并成个线性 链 表 L C 的操作算法。/*注意，在主函数中已经对LC数组进行了初始化，长度等于LA和 LB长度之和*/*假设数组LA和 LB中存储着datatype类型的数据元素*/Void MergeList(datatype LA,datatype LB,datatype LC)int i=O,j=O,k=O;int lenthOfLA=sizeof(LA)/sizeof(datatype);int lenthOfLB=sizeof(LB)/sizeof(datatype);while(i=lenthOfLA-l&j

12、=lenthOfLB-l)if(LAiLBrj)(LCk+=LAi+;elseLCk+=LBj+;)if(i=lenthOfLA-l)(while(i=lenthOfLA-1 )(LCk+=LAi+;)else(while(jnext;/*从链表的第一个结点开始查找*/while(p!=NULL&p-id!=idd)q=p；p=p-next;if(p!=NULL)/*找到要找的结点*/(s=p;q-next=p-next;free(s);/*删除结点*/).elseprintf(没有找到您要找的结点n);).(2)/*插入学生结点node算法，假设node在主函数中已经创建*/void Ins

13、ertNode(stuNode*head,stuNode*node)(stuNode*p=head,*q;g=p;p=p-next;/*从链表的第一个结点开始查找*/if(node-scorescore)(node-next=p;q-next=node;/*将结点插入表头*/return;/*算法结束*/)while(p!=NULL&p-scorescore)q=p；p=p-next;)if(p=NULL)(q-next=node;/*将结点插入链表的表尾*/)else/*插入结点*/(node-next=p;q-next=node;)7.某仓库中有一批零件，按其价格从低到高的顺序构成一个单链

14、表存于计算机内，链表的每一个结点说明同样价格的若干个零件。现在又新有m个价格为s的零件需要进入仓库，试写出仓库零件链表增加零件的算法。链表结点结构如下：算法提示：/*定义一个结点，每个结点表示一种零件的相关信息*/typedef s tru c t NODE .flo a t p r ic e;/*该零件的价格*/unsigned long number;/*该零件的数量*/s tru c t NODE*next;Node;/*在实结点为head的单链表中插入一个零件信息结点node的算法如下*/*假设该结点node已经在主函数中创建完毕*/void InsertNode(Node*head,

15、Node*node)Node*p=head,*q;q=p;p=p-next;/*从链表的第一个结点开始查找*/if(node-priceprice)一node-next=p;q-next=node;/*将结点插入表头*/ruturn;/*算法结束*/)while(p!=NULL&p-priceprice)(q=p;p=p-next;)if(p=NULL).q-next=node;/*将结点插入链表的表尾*/)else/*插入结点*/(node-next=p;q-next=node;)8.设指针P指向单链表的首结点，指针x指向单链表中的任意一个结点，写出在x前插入一个结点i的算法。算法提示：/*

16、假设该链表的头结点为head,且链表中的结点用Node定义*/*在结点X之前插入结点i的算法如下*/void InsertNode(Node*head,Node*i,Node*X)(Node*p=head,*q;q=p;p=p-next;/*依照题意，p 指向链表的第一个结点*/i f(p=X)/*将结点插入头结点和第一个结点之间*/(i-next=p;q-next=i;return;/*算法结束*/)while(p!=NULL&p!=X)/*查找插入位置*/(q=p;p=p-next;if(p=NULL)return NULL;/*查找失败*/else(i-next=p;q-next=i;)

17、9.设多项式A 和 B 采用线性链表的存储方式存放，试写出两个多项式相加的算法，要求把相加结果存放在A 中。算法提示：请 参 考 本 章 算 法3.23和 算 法3.24。10.设指针a 和 b 分别为两个带头结点的单链表的头指针，编写实现从单连表L a 中删除 自 第 i 个数据元素起，共 length个数据元素、并把它们插入到单链表L b 中 第 j 个元素之前的算法。算法提示：void DInsert(Node*a,Node*b,int i,int j,int length)(Node*ap=a-next,*bp=b-next;/*定义了两个分另U处理 La 和 Lb 的两 个 指 针

18、变 量*/Node*apl,*ap2,*ap3,*ap4;/*定 义 了 用 于 处 理La的4个 指 针 变 量*/Node*bpl,*bp2;/*定 义 了 用 于 处 理Lb的2个 指 针 变 量*/for(int k=l;knext;apl=ap;ap2=apl-next;ap=ap2;for(int k=l;knext;ap3=ap;ap4=ap3-next;apl-next=ap4;/*将La中 长 度 为length的 子 链 脱 链*/for(int k=l;knext;bpl=bp;bp2=bpl-next;ap3-next=bp2;bpl-next=ap2;/*将长度为 l

19、ength 的子链挂接到Lb相 应 的 位 置*/)11.设 L a 和 L b 是两个有序的循环链表，Pa和 Pb分别指向两个表的表头结点，是写一个算法将这两个表归并为一个有序的循环链表。算法提示：本题可以换个角度考虑，因为对于循环链表考虑的因素较单链表多，所以我们可以将两个循环链表首先处理成两个单链表(方法：将链表的最后一个结点的next域设置为NULL),这样问题就转化为将两个普通链表归并的问题，最后再把归并好的单链表转换成循环链表(方法：将链表的最后一个结点的next域指向该链表的头结点)。下面我们仅给出单链表归并的算法作为参考，具体的转换由于比较简单所以这里就不详述了：void Me

20、rgeList(Node*pa,Node*pb)Node*pc=pa;Node*p1=pa-next,*p2=pb-next;While(p1!=NULL&p2!=NULL)(if(p1-datadata)(pc-next=p1;pc=pc-next;p1=p1-next;)else(pc-next=p2;pc=pc-next;p2=p2-next;)if(p1!=NULL)pc-next=p1;else pc-next=p2;)12.已知有一个单向循环链表，其每个结点中含三个域：pre、d a t a 和 next,其中data为数据域，next为指向后继结点的指针域，pre也为一个指针域，

21、但是他的值为空(null),试编写一个算法将此单链表改为双向循环链表，即 使 pre成为指向前驱结点的指针域。算法提示：/*假设链表的头指针为head,用 Node来定义一个结点*/void Convert(Node*head)(Node*p=head,*q;q=p;p=p-next;/*从链表的第一个结点开始处理*/while(p!=head)(p_pre=q;q=p；p=p-next;一p-pre=q;/*构成循环*/习题三答案2.本题较简单，可参考本章栈操作示意图的画法，答案略。3.参考答案：栈和队列都是操作受限的线性表，因此二者都具备线性表的一般特性；对于栈,元素进栈出栈的原则是“后进

22、先出”,即LIFO,对于队列，元素进出队列的原则是“先进先出”,即 FIFOo4.参考答案：1 和 4。6.算法提示：利 用 栈 的 L1FO特性，如果是左括号则将其压入栈顶，然后读取下一个字符，如果仍然是左括号，再将其压入栈顶，依次类推，直到出现右括号为止，这时将最靠近栈顶的左括号弹出，它一定与该右括号相匹配。下面以圆括号为例给出算法：int match()seqstack s;char ch;initstack(&s)while(2)ch=getchar()；if(ch=$)break;if(ch=()push(&s,ch)；else if(ch=)if(stackempty($s)pri

23、ntf(the parenthess match failed!n,5)；return 0;else pop(&s)；)、if(stackempty(&s)printf(the parenthness match success!n,)5return 1;)elseprintf(the parenthness match failed!n)；return 0;)8.参考答案：这是由栈的LIFO特性决定的，可参考图4-4。9.参考答案：优点，不会出现线性队列中的队头指针“追上”队尾指针的情况，即“假溢出”;判空条件：队头指针等于队尾指针(front=rear)；判满条件：队头指针指向队尾指针的下

24、一个位置(rear+1)%MAXSIZE=front)(其中MAXSIZE为队列的长度)，约定循环队列少用个元素位。10.参考答案：由于队列是操作受限的线性表，所以该题可以参考第三章第五题的解答(因为线性表的一般特性同时适用于队列)，除此之外，要特别注意顺序存储的队列会出现“假溢出”状态，为了解决这个问题，可以利用循环队列这种存储结构，当然对于链式存储的队列是不会出现这种问题的。1 9.算法提示：typedef struct(datatype datamaxsize;int front,rear;int flag;Jsequeue;(1)初始化算法initseq(sequeue*q)q-dat

25、a=malloc(maxsize*sizeof(datatype);q-front=q-rear=-1;q-flag=0;)(2)入队列算法insertseq(sequeue*q,int x)(if(q-flag=1)return NULL;else if(q-rear+l)%maxsize=q-front)(q-rear=(q-rear+l)%maxsize;q-dataq-rear=x;q-flag=l;return 1;)else|q-rear=(q-rear+l)%maxsize;q-dataq-rear=x;)(3)出队列算法datatype delqueue(sequeue*q)(

26、if(q-flag=0)return NULL;else(q-front=(qfront-1)%maxsize;if(q-front=q-rear)q-flag=0;return(q-dataq-front);)1 2.参考答案，算法提示int G(int m,int n)(if(m=0&n=0)return 0;else return G(m-l,2n);)栈变化示意图略。1 3.算法提示：/*栈*/datatype Pop(seqstack*s),datatype p;p=s-datas-top-2;s-datas-top-2=s-datas-top-1 ;-sotop;/*栈顶指针指向栈

27、顶元素的下一个位置*/return p;/*用 P 返回其值*/*队列*/datatype Pop(sequeue*q)datatype p;p=q-dataq-front-2;q-dataq-front-2=q-dataq-front-1 ;-q-front;/*队头指针指向补头元素的卞一个位置*/return p;/*用 P 返回其值*/习题四答案1.参考答案：递归是软件设计中一个重要的算法设计方法和技术，递归子程序是通过调用自身来完成与自身要求相同的子问题的求解，并利用系统内部功能自动实现调用过程中信息的保存与恢复。2.算法提示：1*2+2*3+3*4+.+(n-1)*nint Coun

28、t(int n)(if(n=2)return 2；return(n*(n-1)+Count(n-1)；3.参考答案：功能为计算0+1+2+3+n;改为非递归算法如下：int func(int n).nint max=();int i;for(i=n;i=0;i)max+=i;)return max;)4.参考算法：利用递归工作栈的工作原理，算法如下：#define maxlen 200struct st .int no,ns;char x,y,z;stackmaxlen;其中no存放一个标识，为 0 时表示直接移动一个圆盘，为 1 时表示需进一步分解；ns存放当前圆盘数；x,y和 z 表示三个

29、塔座，由此得到如下函数：void hanoi(n,a,b,c)int n;int top=l,nl,al,bl,cl;stacktop.no=l;/*初值入栈*/stacktop.ns=n;stacktop.x=a;stacktop.y=b;stacktop.z=c;while(top0)|if(stacktopj.no=l)(nl=stacktop.ns;al=stacktop.x;bl=stacktop.y;cl=stacktop.z;stacktop.no=l;stacktopj.ns=nl-l;stacktop.x=bl;stack top.y=al;stacktop.z=cl;top

30、+;stacktopj.no=0;stacktop.ns=nl;stacktop.x=al;stacktop.y=cl;top+;stacktop.no=l;stacktop.ns=nl-l;stacktop.x=al;stacktop.y=cl;stacktop.z=bl;)while(top0&(stacktopj.no=OllstacktopJ.ns=1).if(top0&stacktop.no=0)/*将第 n 个圆盘从 x 移到 z退栈*/(printf(t将 第 d 个 盘 子 从 d 移 动到cn”,stacktop.ns,stacktop.x,stacktop.y);top-;

31、)if(top0&stacktop.ns=1)/*退栈*/(printf(7将 第 d个 盘 子 从 c移 动到%cn,stacktop.ns,stacktop.x,stacktop.z)；top-;)5 .参考算法：(1)datatype akm(datatype m,datatype n)if(m=0)return n+1;else if(m!=0&n=0)return akm(m-1,1);else return akm(m-1 ,akm(m,n-l);)(2)同样可以利用递归工作栈的工作原理将上面的递归算法进行改写，具体算法略。6 .参考答案：(1)函数功能:打印“a/b”的结果。(2

32、)i n t p (i n t a,i n t b)i f (a next;/*从第一个结点开始查找文/while(strcmp(str,p-ch)!=0)/*开始查找合适的结点*/(q=p；p=p-next;)q-next=p-next;free(p);return head;3.(3)比较串的三种存储方式的优点和缺点。参考答案：(1)顺序存储结构一优点：存储密度高(不需要存储指针变量)，可以随机存取串中的字符；缺点：存取字符时要移动大量的元素，由于事先不知道存储字符的最大数目，所以应该分配尽可能大的静态存储空间，从而造成了空间浪费！(2)单链表式存储结构一优点：插入删除一个结点不需要移动大

33、量的元素，只需要修改有限的指针变量，可以随机分配和释放结点空间，避免了空间浪费；缺点：结点的存储密度低(因为每个结点要存储指向F-个结点的指针变量)，查找结点要从头开始顺序查找，不具备随即存取的机制！为此人们设计了一种叫做块链结点的存储结构，虽然在结点的存储密度上较以前有了改进，但是却给插入删除字符元素或者子串带来了意想不到的麻烦！(3)堆结构的存储方式一优点：动态分配存储空间，避免了空间浪费。3.(4)已知：s=x y z*,t=(x+y)*z.试利用联接、求子串和置换等基本运算,将s转换为t o参考答案：t=C o n ca t i o n(1 1(,Sub St r i n g(s ub

34、 1 ,s,1,1,Sub St r i n g(s ub 2,s,2,1 ),4),s w a p(Sub St r i n g(s ub 3,s,3,2)其中swap的作用是交换两个字符的位置，Sub St r i n g和C o n ca t i o n的作用分别是求子串和串联接。3.试分别写出算法i n s er t(a,i,b)和算法del et e(a,b)。其中，i n s er t(a,i,b)将串b插入在串a中位置i之后；del et e(a,b)将串a中的子串b删掉。参考答案：假设字符串按顺序方式存储。void insert(char*a,int i,char*b)int

35、pos;intp;int lenthOfStra=sizeof(a)/sizeof(char);/*a 串的长度*/int lenthOfStrb=sizeof(b)/sizeof(char);/*b 串的长度*/for(pos=0;pos=pos;p)(ap+LenthOfStrb=ap;/*给串b让出足够的空间*/)for(p=0;p=lenthOfStrb-1;)(apos+=bp+;/*将串b插入到串a对应的位置*/)void delete(char*a,char*b)(int lenthOfStra=sizeof(a)/sizeof(char);/*a 串的长度*/int lenth

36、OfStrb=sizeof(b)/sizeof(char);/*b 串的长度*/*调 用K M P算法确定串a中首次出现串b的位置并赋值给pos*/int pos=KMPIndex(char*a,char*b);intp;for(p=pos+lenthOfStrb;plchild*/if(T-lchild!=NULL)Inorder(T-lchild);orderi+|=T-data;/*将访问到的结点放入数组中，并对记位指针i 加一*/*中序遍历二叉树T-rchild*/if(T-rchild!=NULL)Inorder(T-rchil d);/*判断该数组里面的数据是否由小到大排列，若是则

37、其为一棵二叉排序树*/void Test(int order)intj;int k=sizeof(order)/sizeof(order0);/*计算数组的长度*/for(j=0;jorderj+1 )break;)if(j=k-l)printf(“该二叉树为二叉排序树n)；else printf(“该二叉树不是二叉排序树n)；)4.2.具体算法如下：typedef struct BtreeNode/*定义一个二叉树的结点*/(int data;struct BTreeNode*lchild;struct BTreeNode*rchild;*Btree/*计算二叉树高度的递归算法如下*/int

38、 depth(Btree T)(int d,p=0;/*p记录该二叉树的高度，初始值等于0*/if(T=NULL)return p;/*空二叉树的高度为 0*/else(d=depth(T-lchild);/*考虑该二叉树的左子树，递归调用*/if(dp)p=d;/*p始终记录最大的子树高度*/d=depth(T-rchild);/*考虑该二叉树的右子树，递归调用*/if(dp)p=d;/*p始终记录最大的子树高度*/)return(p+1);/*子树的最大高度加1 为返回树的高度*/)4.4.算法如下：#define TreeSize 100#define StackSize TreeSiz

39、e/2void exit(int);typedef struct(char nodesTreeSize;int num;JBTree;typedef structint sfStackSize;int top;SeqStack;void InitStack(SeqStack*s)s-top=-l;int StackEmpty(SeqStack*s)return s-top=-1;void push(SeqStack*s,int x)(if(s-top=StackSize)printf(44Error:the stack is overflow!n);exit(-2);)s-s+s-top=x;

40、)int pop(SeqStack*s)(if(StackEmpty(s)printfC4Error:the stack is overflowin);exit(-2);)return s-ss-top;)void preorders(BTree*tree)(int i=l;SeqStack s;InitStack(&s);If(tree-num0)do(printfC%cM,tree-nodesi);while(i*2num)if(i*2+1 num)push(&s,i*2+1);i*=2;printfC%c5,tree-nodesi;)if(!StackEmpty(&s)i=pop($s)

41、;else break;while(2);4.5.递归算法如下：卜面的num和 leaf函数分别计算二叉树结点总数和叶子总数。typedef char datatype;typedef struct nodedatatype d;struct node*lchild,*rchild;JBinNode;typedef BinNode*BinTree;int num(BinTree p)(if(!p)return 0;else return 1+num(p-lchild)+num(p-rchild);)int leaf(BinTree p)(if(!p)return 0;else(if(p-lch

42、ild=NULL&p-rchild=NULL)return 1;else return(leaf(p-lchild)+leaf(p-rchild);)4.6.参考答案：假设用于通信的电文与出现的概率依次为：a (7),b (19),c (2),d (6),e(3 2),f (3),g (2 1),h (10),则最终得到的哈夫曼编码依次为:a(0 0 10),b (10),c (0 0 0 0 0),d(0 0 0 1),e (0 1),f (0 0 0 0 1),g (11),h (0 0 11)；具体实现可以参考本章算法7.5。3 7.计算二叉树宽度的算法如下(计算二叉树高度的算法可以参考

43、本章习题15)：typedef struct int front,rear;int count;BinNode*datasQueueSize;JCirQueue;void InitQueue(CirQueue*Q)Q-front=Q-rear=Q-count=0;int QueueEmpty(CirQueue*Q)return Q-front=0;int QueueFull(CirQueue*Q)return Q-count=QueueSize;void EnQueue(CirQueue*Q,BinNode*p)(if(QueueFull(Q)(print(uError:the queue i

44、s full!n);exit(-2);Q-count+;Q-dataQ-rear=p;Q-rear=(Q-rear+1 )%QueueSize;)BinNode*DeQueue(CirQueue*Q)BinQueue*t;If(QueueEmpty(Q)Printf(uError:the queue is empty!n);Exit(-2);)t=Q-dataQ-front;Q-count;Q-front=(Q-front+l)%QueueSize;Return t;)int width(BinNode*p)CirQueue q;BinNode*t;int max-width=O,width=

45、O;InitQueue(&q,p);if(P)(EnQueue(&q,p);EnQueue(&q,NULL);While(!QueueEmpty(&q)(t=DeQueue(&q);if(t)(width+;if(t-lchild)EnQueue(&q,t-lchild);if(t-rchild)EnQueue(&q,t-rchild);)elseif(!QueueEmpty(&q)EnQueue(&q,NULL);if(widthmax-width=width;width=O;return max-width;)习题八答案1.答：(1)V (2)X(3)V (4)x(5)x (6)V (7)

46、7 (8)V (9)X (10)X (11)V(12)7 (13)72 .答：(1)D (2)B(3)B(4)B(5)A (6)B(7)D (8)C(9)C、D (10)D (11)A5.答：ID(A)=1 O D(A)=3ID(B)=2 O D(B)=1ID(C)=2 O D(C)=1ID(D)=2 O D(D)=13.(2).答：邻接矩阵3.(3).答：是连通图。因为每一对顶点间都有路径存在，所以该图是连通的。深度优先搜索遍历：A,B,D,C,F,H,E广度优先搜索遍历：A,B,D,C,E,F,H3.(4).答：普里姆算法构造过程如下：3.(5).答：(1)各结点的最早开始时间VE(1)=

47、OVE(2)=VE(1)+dut 1,2=0+8=8VE(3)=VE(1)+dut 1,3=0+6=6VE(4)=MaxVE(2)+dut 2,4 +VE(3)+dut 3,4=Max11,16)=16VE(5)=VE(1)+dut 1,5 =0+7=7VE(7)=Max VE(3)+dut 3,7 ,VE(5)+dut 5,7 =Max 15,16)=16VE(6)=VE(4)+dut 4,6 =16+4=20VE(8)=Max VE(5)+dut 5,8 ,VE(7)+dut7,8 =Max 20,18=20VE(9)=MaxVE(4)+dut4,9 ,VE(7)+dut 7,9,VE(8

48、)+dut8,9 =Max35,24,26=35VE(10)=MaxVE(6)+dut6,1 0 ,VE(9)+dut 9,10=Max34,45)=45(2)各结点的最迟发生时间VL(10)=VE(10)=45VL(9)=VL(10)-dut9,10=35VL(8)=VL(9)-dut 8,9=29VL(7)=Min VL(8)-dut 7,8 ,VL(9)-dut 7,9 =Min 27,27)=27VL(6)=VL(10)-dut6,10=31VL(5)=Min VL(7)-dut 5,7 ,VL(8)-dut 5,8 =Min18,16=16VL(4)=Min VL(6)-dut 4,

49、6 ,VL(9)-dut 4,9=Min 27,16=16VL(3)=Min VL(4)-dut 3,4 ,VL(7)-dut 3,7 =Min 6,18=6VL(2)=VL(4)-dut2,4=13VL(l)=Min VL(2)-dut 1,2 ,VL(3)-dut 1,3 ,VL(5)-dut 1,5=Min 5,0,9)=0根据各结点的最早开始时间和最迟发生时间计算出各活动的最早开始时间和最迟开始时间Evl,v2=0Evl,v3=0Evl,v5=0Ev2,v4=8Ev3,v4=6Ev3,v7=6Ev5,v7=7Ev5,v8=7Ev4,v6)=16Ev4,v9=16Ev7,v9=16Ev7

50、,v8=16Ev8,v9=20Ev6,vl0=20Ev9,vl0=35Lvl,v2=5Lvl,v3=0Lvl,v5=9Lv2,v4=13Lv3,v4=6Lv3,v7=16Lv5,v7=16Lv5,v8=16Lv4,v6)=27Lv4,v9=16Lv7,v9)=27Lv7,v8=27Lv8,v9)=29Lv6,vl0=31Lv9,vl0)=35完成整个工程的最短时间是45网中的关键活动：,四.答:t t d e f i n e m a x n o d e 3 0S i n c l u d e t y p e d e f i n t e l e m t y p et y p e d e f s t