1. 您所在位置：首页 > 给排水规范 > 设计规范 > 《数据结构(C语言描述)》-马秋菊-源代码和习题参考答案.doc

《数据结构(C语言描述)》-马秋菊-源代码和习题参考答案.doc 27页

  • 390.50 KB
  • 2022-04-22 11:27:25 发布

《数据结构(C语言描述)》-马秋菊-源代码和习题参考答案.doc

  • 27页
  • 当前文档由用户上传发布，收益归属用户
  1. 1、本文档共5页，可阅读全部内容。
  2. 2、本文档内容版权归属内容提供方，所产生的收益全部归内容提供方所有。如果您对本文有版权争议，可选择认领，认领后既往收益都归您。
  3. 3、本文档由用户上传，本站不保证质量和数量令人满意，可能有诸多瑕疵，付费之前，请仔细先通过免费阅读内容等途径辨别内容交易风险。如存在严重挂羊头卖狗肉之情形，可联系本站下载客服投诉处理。
  4. 文档侵权举报电话：19940600175。
'习题配套第一章2．C、A、B、B、A、A、D3．D={A,B,C,E,F,G,H,I,J};R={,,,,,,,,,}ABCEFGHI题1-3图J4．顺序、链式、索引、哈希。*5．解：100n2>2nn至少要多大6.Ｏ(n)、Ｏ(n)、Ｏ(n)、Ｏ()、(5)当n>m，Ｏ(n),当m>n，Ｏ(m)7．n!2100>lgn>n1/2>n3/2>(3/2)n>2n>nlgn>nn第二章1．×、√、×、√、√2．AAD4．顺序表voidDelete_SeqListx(SeqList*L,ElemTypex)/*删除表中值为x元素*/{inti,j;for(i=1;i<=L->length;i++){if(L->elem[i]==x){for(j=i;j<=L->length-1;j++)L->elem[j]=L->elem[j+1];L->length--;}/*向上移动*/}O(n2) 链表voiddel_link(LinkListH，intx)/*删除数据域为x的结点*/{LNode*p，*q;p=H;q=H->next;while(q!=NULL){if(q->data==x){p->next=q->next;free(q);q=p->next;}else{p=q;q=q->next;}}}O(n)5．intDelete_SeqListx(SeqList*L,inti,intk)/*删除表中删除自第i个结点开始的k个结点*/{intj;if(i<1||k<0||i+k-1>L->length)/*检查空表及删除位置的合法性*/{printf(＂不存在第i个元素＂);returnERROR;}for(j=i;j<=L->length-k;j++)L->elem[j]=L->elem[j+k];/*向上移动*/L->length-=k;ReturnOK;/*删除成功*/}O(n)6．voidDelete_SeqListx(SeqList*L,ElemTypex)/*将表中值为x元素换成y*/{inti,j;for(i=1;i<=L->length;i++){if(L->elem[]==x){L->elem[i]=y;}/**/}O(n)7．写一算法在循环单链表上实现线性表的CList_length(L)运算。intlink_length(LinkListH){LNode*p;inti=0;p=H; while(p->next!=H){i++;p=p->next;}returni;}O(n)8．在用头指针表示的单循环链表中，查找开始结点a1的时间是O(1)，然而要查找终端结点则需从头指针开始遍历整个链表，其时间是O(n)。但在很多实际问题中，表的操作常常是在表的首、尾位置上进行，如果改用尾指针rear来表示单循环链表，则查找开始结点a1和终端结点an都很方便，它们的存储位置分别是rear->next->next和rear，显然，查找时间都是O(1)。9.intInsert_LinkListab(LinkListH,ElemTypea,ElemTypeb)/*在单链表中值为a的结点前插入一个值为b的结点*/{LNode*q=H,*s;*p=H->next;while(p!=NULL&&p->data!=a)/*q->next&&q->next->data!=a*/{q=p;p=p->next;}/*查找a结点*/s=(LinkList)malloc(sizeof(LNode));/*申请、填装结点*/s->data=b;s->next=q->next;/*新结点插入在第i-1个结点的后面*/q->next=s；returnOK;}/*Insert_LinkListab*/10．顺序表voidReverse_Sq(SqList*L)/*顺序表的就地逆置*/{for(i=1，j=L.len;inext;q=p->next;s=q->next;p->next=NULL;while(s->next){q->next=p;p=q;q=s;s=s->next;/*把H的元素逐个插入新表表头*/} q->next=p;s->next=q;H->next=s;}/*Reverse_L*/分析：本算法的思想是，逐个地把L的当前元素q插入新的链表头部，p为新表表头。11．voidmerge1(LinkList&A,LinkList&B,LinkList&C)/*把链表A和B合并为C,A和B的元素间隔排列,且使用原存储空间*/{p=A->next;q=B->next;C=A;while(p&&q){s=p->next;p->next=q;/*将B的元素插入*/if(s){t=q->next;q->next=s;/*如A非空,将A的元素插入*/}p=s;q=t;}/*while*/}/*merge1*/12．StatusDelete_Pre(CiLNodes)/*删除单循环链表中结点p的直接前驱*/{q=p;while(q->next->next!=p)q=q->next;/*找到p的前驱的前驱*/s=q->next;q->next=p;free(s);returnOK;}/*Delete_Pre*/13．StatusInsert_SqList(SeqList&L，intx){if(L->length+1>m-1)returnERROR;L->length++;i=L->length;while(L->elem[i]>x&&i>0;){L->elem[i+1]=L->elem[i];i--;}L->elem[i+1]=x;returnOK;}/*Insert_SqList14．intInsert_Linkx(LinkListH,ElemTypex)/*在值递增单链表中插入一个值为x的结点，仍递增*/{LNode*q=H,*s;*p=H->next;while(p!=NULL&&p->datanext&&q->next->datanext;}/*查找a结点*/s=(LinkList)malloc(sizeof(LNode));/*申请、填装结点*/s->data=x;s->next=q->next;/*新结点插入*/q->next=s；returnOK;}/*Insert_Linkx*/15．源程序代码：（在TubroC2.0测试通过）#include#includestructnode{intnumber;/*人的序号*/intcipher;/*密码*/structnode*next;/*指向下一个节点的指针*/};structnode*CreatList(intnum)/*建立循环链表*/{inti;structnode*ptr1,*head;if((ptr1=(structnode*)malloc(sizeof(structnode)))==NULL){perror("malloc");returnptr1;}head=ptr1;ptr1->next=head;for(i=1;inext=(structnode*)malloc(sizeof(structnode)))==NULL){perror("malloc");ptr1->next=head;returnhead;}ptr1=ptr1->next;ptr1->next=head;}returnhead;}main(){inti,n=30,m;/*人数n为30个*/structnode*head,*ptr;randomize();head=CreatList(n);for(i=1;i<=30;i++){ head->number=i;head->cipher=rand();head=head->next;}m=rand();/*m取随机数*/i=0;/*因为我没办法删除head指向的节点，只会删除head的下一节点，所以只能从0数起。*/while(head->next!=head)/*当剩下最后一个人时，退出循环*/{if(i==m){ptr=head->next;/*ptr记录数到m的那个人的位置*/printf("number:%dn",ptr->number);printf("cipher:%dn",ptr->cipher);m=ptr->cipher;/*让m等于数到m的人的密码*/head->next=ptr->next;/*让ptr从链表中脱节，将前后两个节点连接起来*/head=hea/d->next;/*head移向后一个节点*/free(ptr);/*释放ptr指向的内存*/i=0;/*将i重新置为0，从0再开始数*/}else{head=head->next;i++;}}printf("number:%dn",head->number);printf("cipher:%dn",head->cipher);free(head);/*让最后一个人也出列*/}16．voidSqList_Intersect(SqListA,SqListB,SqList&C)/*求元素递增排列的线性表A和B的元素的交集并存入C中*/{i=1;j=1;k=0;while(A.elem[i]&&B.elem[j]){if(A.elem[i]B.elem[j])j++;if(A.elem[i]==B.elem[j]){C.elem[++k]=A.elem[i];//当发现了一个在A,B中都存在的元素,//就添加到C中i++;j++;}}/*while*/}/*SqList_Intersect*/17．StatusDuLNode_Pre(DuLinkList*H)/*完成双向循环链表结点的pre域*/{ p=H;while(q->next!=H){p->next->pre=p;p=p->next;}returnOK;}/*DuLNode_Pre*/第三章栈与队列1．假定有编号A、B、C的3辆列车顺序开进一个栈式结构的站台，请写出每一种开出站台的列车编号顺序(注：每一列车开出栈开出站台后，不允许再进栈)。2．指出下述程序段的功能是什么？voidDemo1(SeqStack*S){inti;arra[16];n=16；initStack(&S);for(i=0,inext=NULL;s=(LinkStack*)malloc（sizeof（LinkStack））;s->top=p;}⑵判栈空intEmpty_LS（LinkStack*s）{returns->top->next==NULL;}⑶入栈LinkStack*Push_LS（LinkStack*s,ElemTypex）{StackNode*p=(StackNode*)malloc（sizeof（StackNode））;p->data=x;p->next=s->top->next;/*将元素x插入链栈顶*/s->top->next=p;returns;}⑷出栈intPop_LS(LinkStack*s,ElemType*y){StackNode*p;if（Empty_LS（s））{printf("StackUnderflow.");/*下溢*/returnOVERFLOW;}else{*y=s->top->next->data;=s->top->next;s->top->next=p->next;free(p);returnOK;}}取栈顶元素intGetTop(LinkStack*s,ElemType*y) {if(Empty_LS(s)){printf("Stackunderflow.");/*下溢*/returnOVERFLOW;}else{*y=s->top->next->data;returnOK;}}4．StatusAllBrackets_Test(charstr)/*判别表达式中三种括号是否匹配*/{InitStack(s);for(p=str;*p;p++){if(*p=="("||*p=="["||*p=="{"}push(s,*p);elseif(*p==")"||*p=="]"||*p=="}"){if(StackEmpty(s))returnERROR;pop(s,c);if(*p==")"&&c!="(")returnERROR;if(*p==")"&&c!="["]returnERROR;if(*p==")"&&c!="{"}returnERROR;/*必须与当前栈顶括号匹配*/}}/*for*/if(!StackEmpty(s))returnERROR;returnOK;]/*AllBrackets_Test*/或intPairBracket(char*S){/*检查表达式中括号是否配对*/inti;SeqStackT;/*定义一个栈*/InitStack(&T);for(i=0;i0){push(S,n);n=n-1;}while(!EmptyStack(S)){Pop(S,i);f=f*i;}return(f);}8.voidhuiwen(){Init_LS(s);printf("Pleaseinputastring:n");for(i=0;(i<20)&&((a[i]=getchar())!="n");++i);/*输入字符串*/for(j=0;jrear-sq->frontsq->rear>=sq->frontcount=m-(sq->front-sq->rear)sq->rearfront11．循环队列的优点是什么？如何判别它的空和满？优点：防止假溢出；判别循环队列的空：return(sq->rear>==sq->front)；判别循环队列的满：return((sq->rear+1)%MAXSIZE==sq->front)12．假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素位置(注意不设头指针)，试编写相应的置空队、判队空、入队和出队等算法。typedefstructqnode{ElemTypedata;structqnode*next;}QCNode;/*链式循环链队列结点的类型*/typedefstruct{QCNode*rear;}LCQueue;/*只设一个指向队尾元素的指针*/（1）置空队算法： voidInit_LCQueue(LCQueue*Lcq){p=(QCnode*)malloc(sizeof(QCNode));/*申请头结点*/p->next=p;Lcq->rear=p;}（2）判队空算法：intEmpty_LCQueue(LCQueue*Lcq){returnLcq->rear->next==Lcq->rear;/*或Lq->rear==NULL;*/}（3）入队算法：voidIn_LCQueue(LCQueue*Lcq,ElemTypex)/*进队操作*/{LCQueue*p;p=(QCNode*)malloc(sizeof(QCNode));/*申请新结点*/p->data=x;p->next=Lcq->rear->next;Lcq->rear->next=p;Lcq->rear=p;}/*In_LCQueue*/（4）出队算法：intOut_LCQueue(LCQueue*Lq,ElemType*y){LCQueuep;if(Empty_LCQueue(Lq)){printf("队空");returnOVERFLOW;}/*队空,出队失败*/else{p=Lcq->rear->next->next;/*队头第一个数据元素结点*/Lcq->rear->next->next=p->next;*y=p->data;/*队头元素放y中*/free(p);returnOK;}}13．假设用一个数组Q[M]来表示队列，该队列只设一个队头指针front，不设队尾指针，用计数器count来记录队列中元素的个数。试编写出相应的置空队列、入队列和出队列的算法。typedefstructqueuenode{ElemTypeelem[MAXSIZE];/*队列中数据元素的存储空间*/intfront,count;/*队头指针、队中元素数量*/}CirQueue;/*以上是结点类型的定义*/voidInit_Queue(CirQueue*Q)/*置空队*/{Q->front=Q->count=0;}intEmpty_Queue(CirQueue*Q)/*判队空*/{return(Q->count==0);}intIn_Queue(CirQueue*Q,ElemTypex)/*入队*/{if(Q->count==MAXSIZE){printf("队已满，不可以入队");returnOVERFLOW};}Q->elem[(sq->front+sq->count)%MAXSIZE]=x;sq->count++; returnOK;}intOut_Queue(CirQueue*Q,ElemType*y)/*出队*/{if(Empty_Queue(Q)){printf("队已空，无元素可以出队");returnOVERFLOW);}*y=sq->elem[sq->front];/*读出队头元素*/sq->front=(sq->front+1)%MAXSIZE;sq->count--;returnOK;}}intFront_Queue(CirQueue*Q,ElemType*y)/*取队头元素*/{if(Empty_Queue(Q)){printf("队空，无元素可取");returnOVERFLOW);}*y=sq->elem[sq->front];/*读出队头元素*/returnOK;}}14．设长度为n的链队列用单循环链表表示，若只设头指针，则入队出队操作的时间复杂度是多少？若只设尾指针呢？若只设头指针，则入队操作的时间复杂度是O(1)，出队操作的时间复杂度是O(n)；若只设尾指针，则入队操作的时间复杂度都是O(1)。*15．写一个算法，借助于栈将一个单链表置逆。第4章数组1．请按行和按列优先顺序列出二维数组A3×4的所有元素在内存中的存储次序，开始结点为a00。a00a10a20a01a11a21a02a12a22a03a13a232．写出三维数组地址计算公式。设三维数组Am×n*p，先行，列，最后Z方向LOC（A[i][j][k]）=LOC（A[0][0][0]）+(i×m×n+j×m+k)×L3．设有三对角矩阵An×n，将其三条对角线上的元素逐行地存储到向量B[0‥3n-3]中，使得B[k]=a[i][j]，求：用i,j表示k的下标变换公式。A[i][j]之间的对应关系为：k=2×i+j4．二维数组M的元素是4个字符（每个字符占一个存储单元）组成的串，行下标i的范围从0到4，列下标j的范围从0到5，M按行存储时元素M[3][5]的起始地址与M按列存储时元素（）的起始地址相同。A.m[2][4]B.M[3][4]C.M[3][5]D.M[4][3]M[3][5]与M存储时元素M[3][5]起始地址相同。5．数组A中，每个元素A的存储占3个单元，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元个数是（1），若该数组按行存放时，元素A[8][5]的起始地址是（2），若该数组按列存放时，元素A[8][5]的起始地址是（３）。 （1）A.80B.100C.240D.270（2）A.SA+141B.SA+144C.SA+222D.SA+225（3）A.SA+141B.SA+180C.SA+222D.SA+225（1）C.（2）C.（3）A6．对于二维数组A[m][n]，其中m<=80，n<=80，先读入m，n，然后读入该数组的全部元素，对如下三种情况分别编写相应函数：(1)求数组A边界元素之和。intsum(L){introw,col,sum=0;for(row=0;rowrhead[i]; while((q)&&(q->colright;if(!q){printf(“notsearched!”;returnNULL;)p=M->chead[j];while((q)&&(q->rowdown;if(!p){printf(“notsearched!”;returnNULL;)returnp;}（2）已知数据元素的值x，查找x在A中的行、列号；QLNode*searchx(CrossListM,ElemTypex){inti;/*mu,nu*/for(i=1;irhead[i];if((q)&&(q->v<>x))q=q->right;elsereturnq;}}9．简述广义表和线性表的区别和联系。答：相同点：线性；不同点：数据元素分为原子和广义表。10．设广义表L=((),())，试问head(L),tail(L)，L的长度、深度各为多少？head(L)=()tail(L)=())L的长度为2。11．求下列广义表运算的结果(1)head((a,b,c))=(a,b,c)；(2)tail((b,d,p,h))=()；(3)head(((a,b),(c,d)))=((a,b),(c,d))；(4)tail(((a,b),(c,d)))=()；(5)head(tail(((a,b),(c,d))))=()；(6)tail(head(((a,b),(c,d))))=()第6章树树的形状acbfgdeljkimmh1.根据题意画出树的形状为右图：a是根结点，mndfjkl是叶结点；c是g的双亲；c，a是g的祖先；j，k是g的孩子；imn是e的子孙；d是e的兄弟；g，h是f的兄弟；b的层次是2；n的层次是5；树的深度是5；以c为根的子树深度是3；树的度数是3。2．三个结点的二叉树如下所示：有五种形态： (1)(2)(3)(4)(5)3．分别写出图6-28(a)所示的二叉树的前序、中序和后序遍历序列。前序ABCDEF中序ACEDB后序EDCBA4．画出图6-28(b)所示二叉树顺序存储和二叉链表的存储结构。BACDEABCDGEFHI(b)(a)图6-285．请画出如图6-29所示两棵二叉树的顺序存储结构，并比较每棵二叉树所用的存储空间的大小。CBADLKMN图6-29(a)(b) (b)所用的存储空间的大6．一棵完全二叉树的第3层上有4个叶子结点，问该二叉树最多有多少个结点？7个结点7．已知一棵二叉树只存在度数为0或度数为2的结点，度数为2的结点有19个，问度数为0的结点有多少个？20个，分析：根据公式n0=n2+1，有n0=19+1=208．写出用非递归实现二叉树的中序遍历算法，并分析其时间复杂度和栈所需要的最大容量。二叉树的中序遍历的非递归算法。voidInorder2（BTNode*bt）/*利用栈实现前序遍历非递归算法*/{p=bt；top=-1；while(p||top>-1){if(p)/*二叉树非空*/{++top；s[top]=p；/*根结点指针进栈*/p=p->lchild；}/*p移向左孩子*/else/*栈非空*/{p=s[top]；--top；/*双亲结点指针出栈*/printf(p->data)；/*访问根结点，输出结点*/p=p->rchild；}/*p移向右孩子*/}}/*Inorder2*/9．若已知某二叉树的前序遍历序列为ABCDEFGHI和中序遍历序列为BCAEDGHFI，试画出该二叉树。并写出后序遍历的结果。ABDCHEFGI10．设二叉树以二叉链表形式存储，写一算法交换各结点的左右子树。voidExchange1(BTNode*bt){/*交换左右子树的第一种方法*/if(*bt){/*这里以指针为参数使交换在实参结点上进行*/BTNodep;Exchange1(&(*bt)->lchild);Exchange1(&(*bt)->rchild);p=(*bt)->lchild;(*bt)->lchild=(*bt)->rchild;(*bt)->rchild=p; }}voidExchange2(BTNode*bt){/*交换左右子树的第二种方法*/if(bt){BTNode*p;p=bt->lchild;bt->lchild=bt->rchild;bt->rchild=p;Exchange2(bt->lchild);Exchange2(bt->rchild);}}/*Exchange2*/11．设二叉树以二叉链表形式存储，写出一个求叶子结点总个数的算法。voidLeaf_BiTree(BTNode*T)/*求树的深度及叶子结点个数*/{if(T){if(T->lchild==NULL&&T->rchild==NULL){printf("%cn",T->data);count++;}Leaf_BiTree(T->lchild,j);Leaf_BiTree(T->rchild,j);}}/*Leaf_BiTree*/12．画出6-28(b)所示二叉树对应的森林。ABCDGEFHI13．画出图6-28(b)所示二叉树所对应的中序线索二叉树。ABCDGEFHI中序遍历序列为DGBAECHFI 14．写出在中序线索二叉树上查找值为x的结点的算法。15．对给定的一组权值：15，2，9，13，8，20，22，构造一棵哈夫曼树，并计算出带权路径长度。16．写出实现图6-27(c)所示将百分制转换为五级分判定过程的算法。第8章习题V0V1V2V3V5V4图7-22有向图1．对图7-22所示的有向图中，试求出：(1)每个顶点的入度和出度；ID0=1,OD0=1ID1=2,OD1=1ID2=1,OD2=2ID3=0,OD3=2ID4=3,OD4=0ID5=1,OD5=2(2)邻接矩阵；000010100000010001001010000000010010A=(3)写出该图的邻接表。V0V1V2V30∧54∧14∧2∧1∧1∧V4V5 2．求如图7-22所示图的每个结点的入度和出度和总度数，并编写算法。每个结点的总度数：OD0=2OD1=3OD2=3OD3=2OD4=3OD5=3假设用邻接矩阵存储结构，入度和出度和总度数的算法如下：voidMages(Mgraph*ma){Mgraphma;intind[VERTEX_MAX]={0},outd[VERTEX_MAX]={0},totled[VERTEX_MAX]={0};for(i=0;in;i++)/*求出度*/{for(j=0;in;j++){If(ma->arcs[i][j]==1)outd[i]++;}}for(i=0;in;i++)/*求出度*/{for(j=0;in;j++){If(ma->arcs[j][i]==1)ind[i]++;}}for(i=0;in;i++){totled[i]=ind[i]+outd[i];}printf("vertexidodtoteldn");/*求总度数*/for(i=0;in;i++){printf("%s%d%d%dn",G->adjlist[i].vertex,ind[i],outd[i],totled[i]);}}}3．对于n个顶点构成的无向图（或有向图），采用邻接矩阵和邻接表两种方式进行存储，写出下面要求的算法：(1)求图中的边数；有向图邻接矩阵intMages(Mgraph*ma) {intages=0;for(i=0;in;i++)/*求出度*/{for(j=0;in;j++){If(ma->arcs[i][j]==1)ages++;}}returnMages;}如果是无向图，最后Mages要除以2。有向图邻接表存储结构求边数：voidf_ind(ALGraph*G){inti;intALages;/*三个变量分别为入度、出度和总度数*/EdgeNode*p;for(i=0;in;i++)/*求出度*/{p=G->adjlist[i].firstedge;while(p!=NULL){ALages++;p=p->next;}}returnALages;}如果是无向图，最后ALages要除以2。(2)任意两个顶点的邻接关系；邻接矩阵存储结构voidMcnn(Mgraph*ma){for(i=0;in;i++)/*求出度*/{for(j=0;in;j++){If(ma->arcs[i][j]==1)printf(“v%d,v&d)n”,i,j);} }returnMages;}邻接表存储结构voidconn(ALGraph*G){EdgeNode*p;for(i=0;in;i++)/*求出度*/{p=G->adjlist[i].firstedge;while(p!=NULL){printf(“v%d,v&d)n”,i,p->adjvex);p=p->next;}}}(3)每个顶点的度，有向图的入度和出度。邻接表存储voidf_ind(MGraph*G){inti;intALages;/*三个变量分别为入度、出度和总度数*/EdgeNode*p;for(i=0;in;i++)/*求出度*/{p=G->adjlist[i].firstedge;while(p!=NULL){ALages++;p=p->next;}}returnALages;}有向图邻接表voidf_ind(ALGraph*G){inti;intind[VERTEX_MAX]={0},outd[VERTEX_MAX]={0},totled[VERTEX_MAX]={0};/*三个变量分别为入度、出度和总度数*/EdgeNode*p; for(i=0;in;i++)/*求出度*/{p=G->adjlist[i].firstedge;while(p!=NULL){outd[i]++;p=p->next;}}for(i=0;in;i++)/*求入度，依次扫描每个链表*/{p=G->adjlist[i].firstedge;while(p!=NULL){ind[p->adjvex]++;p=p->next;}}for(i=0;in;i++){totled[i]=ind[i]+outd[i];}printf("vertexidodtoteldn");/*求总度数*/for(i=0;in;i++){printf("%s%d%d%dn",G->adjlist[i].vertex,ind[i],outd[i],totled[i]);}}4．对于如图7-23所示的无向图，完成如下题目：(1)画出邻接表。ABCD3∧4∧24∧2EF3∧1205∧31005∧310 (2)写出邻接矩阵；010010101010010101001010110101001010A=(3)深度优先遍历:ABCDEF广度优先遍历ABECDF5．强连通分量。V0V1V2V3V5V46．n-1,2(n-1)7．对带权路径无向图7-24，求解下面的问题：(1)求该图的邻接矩阵。∧62441321ABCDEF5∧73∧320553301052∧∧65345606∧472(2)最小生成树——两种情况 ABCDFE2663545662EAFB43CD8．对于图7-25所示的连通图，分别用Prim和Kruskal算法构造其最小生成树。FE45B4226DA371C5HGB2Prim算法构造其最小生成树过程（从A点开始）ACDAC33ACD311ACD13B2E44FACD13B2E4ACD13B2E44FH2G5Kruskal算法构造其最小生成树过程FGEFEG2B1DCABADHHC1 HF2EG2B31DCA2B1DCAF2HEGFG2HF44E2B31CAG4E2B31DCA2DHAC13B2E44FH2GD59．根据dijkstra算法求出图7-24中顶点A到各个顶点之间的最短路径。终点从A到各终点的Dist值和最短路径的求解过程i=1i=2i=3i=4i=5B2(A,B)C∞5(A,B,C)D∞∞10(A,B,C,D)E6(A,E)6(A,E)6(A,E)F∞∞12(A,B,C,F)12(A,B,C,F)12(A,B,C,F)BCEDFS{A,B}{A,B,C}{A,C,D,E}(A,B,C,D)(A,B,C,F)'

您可能关注的文档

相关文档

最近下载