数据结构 | 您所在的位置:网站首页 › 数据结构与算法第2版 › 数据结构 |
如有错误,敬请谅解! 此文章仅为本人学习笔记,仅供参考,如有冒犯,请联系作者删除!! 目录 第一章习题答案 第二章习题答案 第三章习题答案 第五章习题答案 第六章习题答案 第七章习题答案 第八章查找 第九章排序 第一章习题答案2、××√ 3、(1)包含改变量定义的最小范围(2)数据抽象、信息隐蔽 (3)数据对象、对象间的关系、一组处理数据的操作 (4)指针类型 (5)集合结构、线性结构、树形结构、图状结构 (6)顺序存储、非顺序存储 (7)一对一、一对多、多对多 (8)一系列的操作 (9)有限性、输入、可行性 4、(1)A(2)C(3)D 5、语句频度为1+(1+2)+(1+2+3)+…+(1+2+3+…+n) 第二章习题答案1、(1)一半,插入、删除的位置 (2)顺序和链式,显示,隐式 (3)一定,不一定 (4)头指针,头结点的指针域,其前驱的指针域 2、(1)A(2)A:E、A B:H、L、I、E、A C:F、M D:L、J、A、G或J、A、G (3)D(4)D(5)C(6)A、C 3、头指针:指向整个链表首地址的指针,标示着整个单链表的开始。 头结点:为了操作方便,可以在单链表的第一个结点之前附设一个结点,该结点的数据域可以存储一些关于线性表长度的附加信息,也可以什么都不存。 首元素结点:线性表中的第一个结点成为首元素结点。 4、算法如下: int Linser(SeqList *L,int X) { int i=0,k; if(L->last>=MAXSIZE-1) { printf(“表已满无法插入”); return(0); } while(ilast&&L->elem[i]last;k>=I;k--) L->elem[k+1]=L->elem[k]; L->elem[i]=X; L->last++; return(1); } 5、算法如下: #define OK 1 #define ERROR 0 Int 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; } else {for(j=i+k-1;jlast;j++) elem[j-k]=elem[j]; L->last=L->last-k; return OK; } } 8、算法如下: #define OK 1 #define ERROR 0 Int 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; } else {if((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(&s); scanf("%c",&ch); while(ch!='@'&&ch!='&') { Push(&s,ch); scanf("%c",&ch); } while(ch!='@'&&!IsEmpty(&s)) { Pop(&s,&temp); scanf("%c",&ch); if(ch!=temp) break; } if(!IsEmpty(&s)) printf("no!\n"); else { scanf("%c",&ch); if(ch=='@') printf("yes!\n"); else printf("no!\n"); } } 12、(1)功能:将栈中元素倒置。 (2)功能:删除栈中的e元素。 (3)功能:将队列中的元素倒置。 第五章习题答案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=1192 9、(1)(a,b)(2)((c,d))(3)(b)(4)b(5)(d) 10、D 第六章习题答案1、三个结点的树的形态有两个;三个结点的二叉树的不同形态有5个。 3、证明:分支数=n1+2n2+…+knk (1) n= n0+n1+…+nk (2) ∵n=分支数+1 (3) 将(1)(2)代入(3)得 n0= n2+2n3+3n4+…+(k-1)nk+1 4、
注:C结点作为D的右孩子(画图的时候忘记了,不好意思) 5、n0=50,n2=n0-1=49,所以至少有99个结点。 6、(1)前序和后序相同:只有一个结点的二叉树 (2)中序和后序相同:只有左子树的二叉树 (3)前序和中序相同:只有右子树的二叉树 参考: 试找出满足下列条件的二叉树: (1)先序序列与后序序列相同; (2)中序序列与后序序列相同; (3)先序序列与中序序列相同; (4)中序序列与层次遍历序列相同。 解: (1)若先序序列与后序序列相同,则或为空树,或为只有根结点的二叉树。 (2)若中序序列与后序序列相同,则或为空树,或为任一结点至多只有左子树的二叉树。 (3)若先序序列与中序序列相同,则或为空树,或为任一结点至多只有右子树的二叉树。 (4)若中序序列与层次遍历序列相同,则或为空树,或为任一结点至多只有右子树的二叉树。 7、证明:∵n个结点的K叉树共有nk个链域,分支数为n-1(即非空域)。 ∴空域=nk-(n-1)=nk-n+1 8、对应的树如下:
9、(答案不唯一) 哈夫曼树如下图所示: 哈夫曼编码如下: 频率 编码 0.07 0010 0.19 10 0.02 00000 0.06 0001 0.32 01 0.03 00001 0.21 11 0.10 0011 11、对应的二叉树如下:
12、求下标分别为i和j的两个桔点的最近公共祖先结点的值。 typedef int ElemType; void Ancestor(ElemType A[],int n,int i,int j) {while(i!=j) if(i>j) i=i/2; else j=j/2; printf("所查结点的最近公共祖先的下标是%d,值是%d",i,A[i]); } 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); else {if(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); else {BiTree p,Q[50]; int front=1,rear=1,last=1; int temp=0, maxw=0; Q[rear]=bt; while(frontlchild!=NULL) Q[++rear]=p->lchild; if (p->rchild!=NULL) Q[++rear]=p->rchild; {last=rear; if(temp>maxw) maxw=temp; temp=0;} } return (maxw); } void Print_CSTree(CSTree T,int i)//按凹入表形式打印输出树的元素,i表示结点所在层次,初次调用时i=0 { for(j=1;jdata); //打印元素,换行 for(p=T->firstchild;p;p=p->nextsib) Print_CSTree(p,i+1); //打印子树 }//Print_CSTree } 第七章习题答案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 0 1 0 0 1 0 0 0 1 0 0 0 1 0 0 1 0 1 1 1 0 0 0 0 0 1 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;长度为15 1-〉2最短路经为1,3,2;长度为19 1-〉5最短路经为1,3,5;长度为25 1-〉4最短路经为1,3,2,4;长度为29 〉6最短路经为1,3,2,4,6;长度为445. 6. 13、A(7)B(3)C(2)D(11)E(8) 第八章查找1、画出对长度为10的有序表进行折半查找的判定树,并求其等概率时查找成功的平均查找长度。 解:ASL=(1+2*2+4*3+3*4)/10=2.9 5、解:(1)插入完成后的二叉排序树如下: ASL=(1+2*2+3*3+3*4+2*5+1*6)/12=3.5 ASL=(1+2*2+3*4+4*5)=37/12 12、解:哈希表构造如下: 0 1 2 3 4 5 6 7 8 9 10 22 41 30 01 53 46 13 67 H(22)=(22*3)%11=0 H(41)=(41*3)%11=2 H(53)=(53*3)%11=5 H(46)=(46*3)%11=6 H(30)=(30*3)%11=2 与(41)冲突 H1(30)=(2+1)%11=3 H(13)=(13*3)%11=6 与46冲突 H1(13)=(6+1)%11=7 H(01)=(01*3)%11=3 与30冲突 H1(01)=(3+1)%11=4 H(67)=(67*3)%11=3 与30冲突 H1(67)=(3+1)%11=4 与01冲突 H2(67)=(3+2)%11=5 与53冲突 H3(67)=(3+3)%11=6 与46冲突 H4(67)=(3+4)%11=7 与13冲突 H5(67)=(3+5)%11=8 ASLsucc=(1*4+2*3+6)/8=2 ASLunsucc=(2+8+7+6+5+4+3+2)/8=37/8 第九章排序1、以关键字序列(503,087,512,061,908,170,897,275,653,426)为例,手工执行以下排序算法,写出每一趟派结束时的关键字状态。 (1)直接插入排序(2)希尔排序(增量序列为5,3,1) (3)快速排序 (4)堆排序(5)归并排序 解: (2)增量为5的排序结果:170,087,275,061,426,503,897,512,653,908 增量为3的排序结果:061,087,275,170,426,503,897,512,653,908 增量为1的排序结果:061,087,170,275,426,503,512,653,897,908 (3)一次划分后:{426 087 275 061 170}503{897 908 653 512} 分别进行:{170 087 275 061}426 503 {512 653} 897 {908} {061 087}170{275}426 503 512 {653} 897 908 061 087 170 275 426 503 512 653 897 908 7、已知一组关键字:(40,27,28,12,15,50,7),要求采用快速排序法从小到大排序。请写出每趟排序后的划分结果。 解:初始状态:40 27 28 12 15 50 7 一次划分:{7 27 28 12 15} 40 {50} 依次划分:7 {27 28 12 15} 40 50 7 {15 12} 27 {28} 40 50 7 12 15 27 28 40 50 16、(1)A3 B1 C4 D2 E7 (2)C (3)C 17、对,错,对 如有错误,请联系作者删除 并恳请同行朋友予以斧正,万分感谢! |
CopyRight 2018-2019 实验室设备网 版权所有 |