资源预览内容
第1页 / 共7页
第2页 / 共7页
第3页 / 共7页
第4页 / 共7页
第5页 / 共7页
第6页 / 共7页
第7页 / 共7页
亲,该文档总共7页全部预览完了,如果喜欢就下载吧!
资源描述
第一章第一章 习题答习题答案 2、3、 (1)包含改变量定义的最小范围(2)数据抽象、信息隐蔽(3)数据对象、对象间的关系、一组处理数据的操作(4)指针类型(5)集合结构、线性结构、树形结构、图状结构(6)顺序存储、非顺序存储(7)一对一、一对多、多对多(8)一系列的操作(9)有限性、输入、可行性4、 (1)A(2)C(3)C5、语句频度为1+(1+2)+(1+2+3)+(1+2+3+n)第二章 习题答案 1、 (1)一半,插入、删除的位置(2)顺序和链式,显示,隐式(3)一定,不一定(4)头指针,头结点的指针域,其前驱的指针域 2、 (1)A(2)A:E、AB:H、L、I、E、AC:F、MD:L、J、A、G 或 J、A、G(3)D(4)D(5)C(6)A、C3、头指针:指向整个链表首地址的指针,标示着整个单链表的开始。头结点:为了操作方便,可以在单链表的第一 个结点之前附设一个结点,该结点的数据域可以 存储一些关于线性表长度的附加信息,也可以什 么都不存。首元素结点:线性表中的第一个结点成为首元 素结点。 4、算法如下:int Linser(SeqList *L,int X) int i=0,k;if(L-last=MAXSIZE-1) printf(“表已满无法插入”);return(0);while(ilastk=I;k-)L-elemk+1=L-elemk;L-elemi=X;L-last+;return(1);5、算法如下:#define OK 1#define ERROR 0Int LDel(Seqlist *L,int i,int k) int j;if(i(L-last+2) printf(“输入的 i,k 值不合法”);return ERROR;if(i+k)=(L-last+2) L-last=i-2;ruturn OK;elsefor(j=i+k-1;jlast;j+)elemj-k=elemj;L-last=L-last-k;return OK;6、算法如下:#define OK 1#define ERROR 0Int Delet(LInkList L,int mink,int maxk) Node *p,*q;p=L;while(p-next!=NULL)p=p-next;if(minknext-data=mink)|(p-datanext-datanext;while(q-datanext=q-next;free(q);q=p-next;return OK;9、算法如下:int Dele(Node *S) Node *p;P=s-next;If(p= =s)printf(“只有一个结点,不删除”);return 0;elseif(p-next= =s)s-next=s;free(p);return 1;Else while(p-next-next!=s)P=p-next;P-next=s;Free(p);return 1;第三章 习题答案 2、 (1)3、栈有顺序栈和链栈两种存储结构。在顺序栈中,栈顶指针 top=-1时,栈为空;栈顶指针 top=Stacksize-1时,栈为满。在带头结点链栈中,栈顶指针 top-next=NULL,则代表栈空;只要系统有可用空间,链栈就不会出现溢出,既没有栈满。 5、#include#include “stdio.h“void main( )char ch,temp;SeqStack s;InitStack(scanf(“%c“,while(ch!=scanf(“%c“,while(ch!=scanf(“%c“,if(ch!=temp)break;if(!IsEmpty(elsescanf(“%c“,if(ch=) printf(“yes!n“);else printf(“no!n“);12、 (1)功能:将栈中元素倒置。(2)功能:删除栈中的 e 元素。(3)功能:将队列中的元素倒置。 第四章习题答案 1、StrLength(s)操作结果为14;SubString(sub1,s,1,7)操作结果为 sub1=I AM A ;SubString(sub2,s,7,1)操作结果为 sub2= ;StrIndex(s,A,4) 操作结果为5;StrReplace(s,STUDENT,q) 操作结果为I AM A WORKER;StrCat(StrCat(sub1,t), StrCat(sub2,q) 操作结果为I AM A GOOD WORKER;2、int StrReplace(SString S,Sstring T,SString V)int i=1; /从串 S 的第一个字符起查找串Tif(StrEmpty(T) /T 是空串return ERROR;doi=Index(S,T,i); /结果 i 为从上一个 i 之后找到的子串 T 的位置if(i) /串 S 中存在串 TStrDelete(S,i,StrLength(T); /删除该串 TStrInsert(S,i,V); /在原串 T 的位置插入串 Vi+=StrLength(V); /在插入的串 V 后面继续查找串 Twhile(i);return OK;第五章习题答案 1、 (1)数组 A 共占用48*6=288个字节;(2)数组 A 的最后一个元素的地址为1282;(3)按行存储时 loc(A36)=1000+(3-1)*8+6-1*6=1126(4)按列存储时 loc(A36)=1000+(6-1)*6+3-1*6=11929、 (1) (a,b) (2) (c,d) ) (3) (b) (4)b(5) (d)10、D第六章 习题答案 1、三个结点的树的形态有两个;三个结点的二叉树的不同形态有5个。2、略3、证明:分支数=n1+2n2+knk (1)n= n0+n1+nk (2)n=分支数+1 (3)将(1) (2)代入(3)得n0= n2+2n3+3n4+(k-1)nk+14、注:C 结点作为 D 的右孩子(画图的时候忘记了,不好意思) 5、n0=50,n2=n0-1=49,所以至少有99个结点。6、 (1)前序和后序相同:只有一个结点的二叉树(2)中序和后序相同:只有左子树的二叉树(3)前序和中序相同:只有右子树的二叉树7、证明:n 个结点的 K 叉树共有 nk 个链域,分支数为 n-1(即非空域) 。空域=nk-(n-1)=nk-n+18、对应的树如下: 9、 (答案不唯一)哈夫曼树如下图所示:哈夫曼编码如下: 频率 编码 0.07 00100.19 100.02 000000.06 00010.32 010.03 000010.21 110.10 001111、对应的二叉树如下:12、求下标分别为 i 和 j 的两个桔点的最近公共祖先结点的值。 typedef int ElemType;void Ancestor(ElemType A,int n,int i,int j)while(i!=j)if(ij) i=i/2; else j=j/2; printf(“所查结点的最近公共祖先的下标是%d,值是%d“,i,Ai);15、编写递归算法,对于二叉树中每一个元素值为 X 的结点,删去以它为根的子树,并释放相应的空间。 void Del_Sub(BiTree T) if(T-lchild) Del_Sub(T-lchild);if(T-rchild) Del_Sub(T-rchild);free(T);void Del_Sub_x(BiTree T,int x) if(T-data=x) Del_Sub(T);elseif(T-lchild) Del_Sub_x(T-lchild,x);if(T-rchild) Del_Sub_x(T-rchild,x);22、int Width(BiTree bt)if (bt=NULL) return (0); elseBiTree p,Q50;int front=1,rear=1,last=1;int temp=0, maxw=0; Qrear=bt; while(frontlchild!=NULL) Q+rear=p-lchild; if (p-rchild!=NULL) Q+rear=p-rchild; last=rear; if(tempmaxw) maxw=temp;temp=0;return (maxw);第七章 习题答案 1、 (1)顶点1的入度为3,出度为0;顶点2的入度为2,出度为2;顶点3的入度为1,出度为2;顶点4的入度为1,出度为3;顶点5的入度为2,出度为1;顶点6的入度为2,出度为3;(2)邻接矩阵如下:0 0 0 0 0 01 0 0 1 0 00 1 0 0 0 10 0 1 0 1 11 0 0 0 0 01 1 0 0 1 0(3)邻接表(4)逆邻接表2、答案不唯一(2)深度优先遍历该图所得顶点序列为:1,2,3,4,5,6边的序列为:(1,2)(2,3) (3,4) (4,5) (5,6)(3)广度优先遍历该图所得顶点序列为:1,5,6,3,2,4边的序列为:(1,5)(1,6) (1,3) (1,2) (5,4)3、(1)每个事件的最早发生时间:ve(0)=0,ve(1)=5,ve(2)=6, ve(3)=12, ve(4)=15, ve(5)=16,ve(6)=16, ve(7)=19, ve(8)=21, ve(9)=23每个事件的最晚发生时间::vl(9)=23, vl(8)=21, vl(7)=19, vl(6)=19, vl(5)=16, vl(4)=15,vl(3)=12, vl(2)=6, vl(1)=9, vl(0)=0(2)每个活动的最早开始时间:e(0,1)=0, e(0,2)=0, e(1,3)=5, e(2,3)=6, e(2,4)=6, e(3,4)=12, e(3,5)=12,e(4,5)=15, e(3,6)=12, e(5,8)=16, e(4,7)=15, e(7,8)=19, e(6,9)=16, e(8,9)=21每个活动的最迟开始时间:l(0,1)=4, l(0,2)=0, l(1,3)=9, l(2,3)=6, l(2,4)=12, l(3,4)=12, l(3,5)=12, l(4,5)=15, l(3,6)=15, l(5,8)=16, l(4,7)=15, l(7,8)=19, l(6,9)=19, l(8,9)=21(3)关键路径如下图所示:4、顶点1到其余顶点的最短路经为:1-3最短路经为1,3;长度为151-2最短路经为1,3,2;长度为191-5最短路经为1,3,5;长度为251-4最短路经为1,3,2,4;长度为291-6最短路经为1,3,2,4,6;长度为4413、A(7)B(3)C(2)D(11)E(8)14、略15、略第八章 查找 1、画出对长度为10的有序表进行折半查找的判定树,并求其等概率时查找成功的平均查找长度。 解:ASL=(1+2*2+4*3+3*4)/10=2.95、解:(1)插入完成后的二叉排序树如下:ASL=(1+2*2+3*3+3*4+2*5+1*6)/
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号