數(shù)據(jù)結(jié)構(gòu)與算法離線作業(yè)

1、浙江大學(xué)遠(yuǎn)程教育學(xué)院數(shù)據(jù)結(jié)構(gòu)與算法課程離線作業(yè)一、填空題：(【序號(hào)，章，節(jié)】。)1,1,2】線性結(jié)構(gòu)中元素之間存在一對(duì)一關(guān)系，樹形結(jié)構(gòu)中元素之間存在一對(duì)多關(guān)系,圖形結(jié)構(gòu)中元素之間存在多對(duì)多關(guān)系。2,1,2】為了最快地存取數(shù)據(jù)元素，物理結(jié)構(gòu)宜采用順序存儲(chǔ)結(jié)構(gòu)。3,1,2存儲(chǔ)結(jié)構(gòu)可根據(jù)數(shù)據(jù)元素在機(jī)器中的位置是否一定連續(xù)分為順序存儲(chǔ)結(jié)構(gòu),鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。4,1,3】度量算法效率可通過(guò)時(shí)間復(fù)雜度來(lái)進(jìn)行。5,1,3設(shè)n為正整數(shù),下面程序段中前置以記號(hào)的語(yǔ)句的頻度是n(n+1)/20for(i=0;i<n;i+)for(j=0;j<n;j+)if(i+j=n-1)aij=0;)6,1,3設(shè)n為正

2、整數(shù)，試確定下列各程序段中前置以記號(hào)的語(yǔ)句的頻度：(1)i=1;k=0;while(i<=n-1)i+;k+=10*i;/語(yǔ)句的頻度是_n-1)k=0;for(i=1;i<=n;i+)for(j=i;j<=n;j+)k+;/語(yǔ)句的頻度是n(n+1)/2)7,3,2】線性表(a1，a2,，an)有兩種存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，請(qǐng)就這兩種存儲(chǔ)結(jié)構(gòu)完成下列填充：順序_存儲(chǔ)密度較大；順序存儲(chǔ)利用率較高；順序存儲(chǔ)可以隨機(jī)存??；鏈?zhǔn)酱鎯?chǔ)不可以隨機(jī)存??；鏈?zhǔn)酱鎯?chǔ)插入和刪除操作比較方便。8,3,2從一個(gè)長(zhǎng)度為n的順序表中刪除第i個(gè)元素（1&in時(shí)，需向前移動(dòng)n-i個(gè)元素。

3、9,3,2】帶頭結(jié)點(diǎn)的單鏈表Head為空的條件是Head->next=NULL。10,3,2】在一個(gè)單鏈表中p所指結(jié)點(diǎn)（p所指不是最后結(jié)點(diǎn)）之后插入一個(gè)由指針s所指結(jié)點(diǎn)，應(yīng)執(zhí)行s->next=p->next二和p->next=s的操作。11,3,2】在一個(gè)單鏈表中刪除p所指結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行以下操作：q=p->next;p->data=p->next->data;p->next=p->next->next;free（q）;12,3,2帶頭結(jié)點(diǎn)的單循環(huán)鏈表Head的判空條件是Head->next=Head;不帶頭結(jié)點(diǎn)的單循環(huán)鏈表

4、的判空條件是Head=NULL;。13,3,2】已知L是帶表頭結(jié)點(diǎn)的非空單鏈表，且P結(jié)點(diǎn)既然不首元結(jié)點(diǎn)，也不是尾元結(jié)點(diǎn)試從下列提供的答案中選擇合適的語(yǔ)句序列。a.刪除P結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)的語(yǔ)句序列是_1012811414b.刪除結(jié)點(diǎn)P的語(yǔ)句序列是10127314c.刪除尾元結(jié)點(diǎn)的語(yǔ)句序列是9113140(1) P=P->next;(2) P->next=P;(3) P->next=P->next->next;(4) P=P->next->next;(5) while(P!=NULL)P=P->next;(6) while(Q->next!=

5、NULL)P=Q;Q=Q->next;while(P->next!=Q)P=P->next;(8) while(P->next->next!=Q)P=P->next;(9) while(P->next->next!=NULL)P=P->next;(10) Q=P;(11) Q=P->next;(12) P=L;(13) L=L->next;(14) free(Q);14,3,3】對(duì)一個(gè)棧，給定輸入的順序是A、B、C,則全部不可能的輸出序列有不可能得到的輸出序列有CAB。15,3,3】.在棧頂指針為HS的鏈棧中，判定?？盏臈l件是h

6、ead->next=NULL016,3,3】下列程序把十進(jìn)制數(shù)轉(zhuǎn)換為十六進(jìn)制數(shù)，請(qǐng)?zhí)顚懞线m的語(yǔ)句成分。voidconversion10_16()InitStack(&s);scanf("d,&N);while(N)Push(s,N%16);N=N/16;while(!StackEmpty(s)Pop(s,e);if(e<=9)printf("d,e);elseprintf("0+,eA');/*conversion*/17,3,4若用一個(gè)大小為6個(gè)元素的數(shù)組來(lái)實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear=0和front=3。當(dāng)從隊(duì)列中刪除一個(gè)元

7、素，再加入兩個(gè)元素后，rear和front的值分別是N和4018,3,4】堆棧和隊(duì)列都是線性表，堆棧是后進(jìn)先出的線性表，而隊(duì)列是先進(jìn)先出的線性表。19,3,4若用一個(gè)大小為6個(gè)元素的數(shù)組來(lái)實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear=0和front=3。當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，rear和front的值分別是2和4。20,4,2已知一棵樹邊的集合是<a,d>,vd,c>,vd,j>,ve,a>,vf,g>,vd,b>,vg,h>,vg,i>,ve,f>。那么根結(jié)點(diǎn)是e:結(jié)點(diǎn)b的雙親是d:結(jié)點(diǎn)a的子孫有bcdj,樹的深度是4,樹的度是二

8、,結(jié)點(diǎn)g在樹的第3層。21,4,3從概念上講，樹與二叉樹是二種不同的數(shù)據(jù)結(jié)構(gòu)，將樹轉(zhuǎn)化為二叉樹的基本的目的是樹可采用二叉樹的存儲(chǔ)結(jié)構(gòu)并利用二叉樹的已有算法解決樹的有關(guān)問(wèn)題022,4,3】滿三叉樹的第i層的結(jié)點(diǎn)個(gè)數(shù)為f,深度為h時(shí)該樹中共有必1結(jié)點(diǎn)023,4,3】已知一棵完全二叉樹有56個(gè)葉子結(jié)點(diǎn)，從上到下、從左到右對(duì)它的結(jié)點(diǎn)進(jìn)行編號(hào)，根結(jié)點(diǎn)為1號(hào)。則該完全二叉樹總共結(jié)點(diǎn)有111個(gè):有7層；第91號(hào)結(jié)點(diǎn)的雙親結(jié)點(diǎn)是45號(hào):第63號(hào)結(jié)點(diǎn)的左孩子結(jié)點(diǎn)是126號(hào)。24,4,3】下列表示的圖中，共有5一個(gè)是樹；有_3個(gè)是二叉樹；有2個(gè)是完全二叉樹n、最小深度為log2n+125,4,4】n個(gè)結(jié)點(diǎn)的二叉排

9、序樹的最大深度是26,4,3】如果某二叉樹的后序遍歷序列是ABCDEFGHI,中序遍歷序歹是ACBIDFEHG，則其先序遍歷序列的第一個(gè)字母是I.最后一個(gè)字母是G。27,4,3】下列二叉樹的中序遍歷序列是DBNGOAEC；后序遍歷序歹U是DNOGBECA28,5,4設(shè)HASH表的大小為n(n=10),HASH函數(shù)為h(x)=x%7,如果二次探測(cè)再散列方法Hi=(H(key)+di)mod10(di=12,22,32)解決沖突，在HASH表中依次插入關(guān)鍵字1,14,55,20,84,27以后，關(guān)鍵字1、20和27所在地址的下標(biāo)分別是J、7和5。插入上述6個(gè)元素的平均比較次數(shù)是2029,6,3設(shè)無(wú)

10、權(quán)圖G的鄰接矩陣為A,若(vi,vj)屬于圖G的邊集合，則對(duì)應(yīng)元素Aij等于/_,22、設(shè)無(wú)向圖G的鄰接矩陣為A,若Aij等于0,則A皿i等于0030,6,3若一個(gè)圖用鄰接矩陣表示，則刪除從第i個(gè)頂點(diǎn)出發(fā)的所有邊的方法是矩陣第i行全部置為零。31,6,2】設(shè)一個(gè)圖G=V,A,V=a,b,c,d,e,f,A=<a,b>,<b,e>,<a,e>,<c,a>,<e,d>,<d,f>,<f,c>。那么頂點(diǎn)e的入度是2:出度是1:通過(guò)頂點(diǎn)f的簡(jiǎn)單回路有2條:就連通性而言，該圖是強(qiáng)連通圖;它的強(qiáng)連通分量有1個(gè):其生成樹可能

11、的最大深度是5o32,7,1】排序過(guò)程一般需經(jīng)過(guò)兩個(gè)基本操作，它們是比較和移動(dòng)。33,7,2在對(duì)一組關(guān)鍵字是(54,38,96,45,15,72,60,23,83的記錄進(jìn)行直接插入排序時(shí)，當(dāng)把第七個(gè)記錄(關(guān)鍵字是60)插入到有序表時(shí)，為尋找插入位置需比較3次34,7,4】插入排序、希爾排序、選擇排序、快速排序、堆排序、歸并排序、和基數(shù)排序方法中，不穩(wěn)定的排序方法有希爾排序、快速排序、堆排序。二、綜合題(選自教材數(shù)據(jù)結(jié)構(gòu)各章習(xí)題，采用word文件格式上傳)1,1,3】試分析下面一段代碼的時(shí)間復(fù)雜度:if(A>B)for(i=0;i<N;i+)for(j=N*N;j>i;j-)A

12、+=B;)elsefor(i=0;i<N*2;i+)for(j=N*2;j>i;j-)A+=B;)分析：ifA>B為真，則for語(yǔ)句的外循環(huán)N次，內(nèi)循環(huán)為N(N-1)次，因此時(shí)間復(fù)雜度為O(N*N(N-1),也就是N的三次方。1)ifA>B為假，則for語(yǔ)句的外循環(huán)2N次，內(nèi)循環(huán)為N次，因此時(shí)間復(fù)雜度為O(2N*N),也就是N的平方。2,1,3測(cè)試?yán)?.3中秦九韶算法與直接法的效率差別。令f(x)=1+Z100xi/i,計(jì)算f(1.1)的值。利用clock()函數(shù)得到兩種算法在同一機(jī)器上的運(yùn)行時(shí)間。運(yùn)行結(jié)果：#include<stdio.h>#include

13、<time.h>#include<math.h>clock_tstart,stop;doubleduration;#defineMAXN10#defineMAXK1e7doublef1(intn,doublea,doublex)(inti;doublep=a0;for(i=1;i<=n;i+)p+=(ai*pow(x,i);returnp;doublef2(intn,doublea,doublex)(inti;doublep=an;for(i=n;i>0;i-)p=ai-1+x*p;returnp;voidrun(double(*f)(int,double*

14、,double),doublea,intcase_n)(inti;start=clock();for(i=0;i<MAXK;i+)(*f)(MAXN-1,a,1.1);stop=clock();duration=(double)(stop-start)/CLK_TCK;printf("ticks%d=%fn",case_n,(double)(stop-start);printf("duration%d=%6.2en”,case_n,duration);intmain()inti;doubleaMAXN;for(i=0;i<MAXN;i+)ai=(dou

15、ble)i;run(f1,a,1);run(f2,a,2);return0;運(yùn)行結(jié)果：ticks1=10654.000000duration1=1.07e+001ticks2=796.000000duration2=7.96e-0013,1,3】試分析最大子列和算法1.3的空間復(fù)雜度。若記整體時(shí)間復(fù)雜度為T(N)0通過(guò)遞歸實(shí)現(xiàn)“分”的復(fù)雜度為2T(N/2)。求跨分界線的最大子列和有兩個(gè)簡(jiǎn)單的for循環(huán)，所用步驟一共不超過(guò)N,可以在O(N)時(shí)間完成。其他步驟都只需要常數(shù)O(1)T二0；T(N)=2T(N/2)+0(N)=22T(N/2)/2)+0(N/2)+0(N)=22T(N/22)+20(N

16、)=,=2kT(N/2k)+k0(N)不斷對(duì)分到N/2k=1,即2k=N,可得到T(N)=NT(1)+logN0(N)=0(NIogN)4,1,3】試給出判斷N是否為質(zhì)數(shù)的0(JN)的算法。#include<stdio.h>#include<math.h>intis_prime(intn)inti;if(n!=2&&n%2=0|n=1)return0;10if(n=2)return1;for(i=3;i<=sqrt(double)n);i+=2)if(n%i=0)return0;return1;voidmain()intnum,result;pri

17、ntf("pleaseinputthenum:");scanf("%d”,&num);result=is_prime(num);if(result)printf("%disaprimen",num);elseprintf("%disnotaprimen",num);執(zhí)行結(jié)果：11ttinclude<stdio.h>Kinclude<math.h>int15_priie(intn)inti;5,2,2】請(qǐng)編寫程序，輸入整數(shù)n和a,輸出S=a+aa+aaa+aa-a（n個(gè)a）的結(jié)果。#includ

18、e<stdio.h>voidmain()inta,b,n,i,s=0;printf("請(qǐng)輸入整數(shù)n和a:n"）;scanf("%d%d",&n,&a);b=a;for(i=1;i<=n;i+)s+=a;個(gè)a)=%dn",s);a=a*10+b;printf("S=a+aa+aaa+,+aa,a(n12執(zhí)行結(jié)果:ilinclude<5tdlo.h>voidnain()intaFb,n,i,5=0；printf(,請(qǐng)輸入整數(shù)n和:二l-月dq口一一,h”'C:testDebugCppi

19、.exe¥請(qǐng)輸入整數(shù)n和息：106S=a+aa+ai*a+,+aa,a<n個(gè)a)=-1182S2!7192Pressanykeytocontinue6,2,3】請(qǐng)編寫遞歸函數(shù)，輸出123.n的全排列(n小于10),并觀察n逐步增大時(shí)程序的運(yùn)行時(shí)間。#include<stdio.h>#include<time.h>voidpailie(int*data,intn,intcurr)inti;if(curr=n-1)for(i=0;i<n;+i)printf("%d",datai);printf("n");else

20、for(i=curr;i<n;+i)intt;t=datacurr,datacurr=datai,datai=t;13pailie(data,n,curr+1);t=datacurr,datacurr=datai,datai=t;)intmain()clock_tend;clock_tstart=clock();intn=0;inti=0;intas10;scanf("%d",&n);for(i=0;i<n;+i)asi=i+1;)pailie(as,n,0);end=clock();printf("Thetimewas:%dn",(

21、end-start)/CLK_TCK);return0;14執(zhí)行結(jié)果:include<stdio-h>Ninclude<tine.h>voidpailie(int*dataTintn,intcurr)(-&<4.一'C:testDebugCppl,xe*613425613542&13524E132546132456143526143256145326145236142536142居615432“5423615342&1S3246152346152436124536124356125436125m461235461234sThetim

22、ewas：3Q7,3,2給定一個(gè)順序存儲(chǔ)的線性表L=(ai,a2,，an),請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法刪除所有值大于min而且小于max的元素#include<stdio.h>voiddels(inta口,int*n,intmin,intmax)inti,j,k;15for(i=j=k=0;i<*n;i+)if(ai>min&&ai<max)k+;elseaj+=ai;*n-=k;intmain()inta14=67,57,76,78,99,90,96,87,93,76,68,79,24,98;intmax,min,n=14,i;printf("原有

23、的數(shù):n");for(i=0;i<n;i+)16printf("nminmax=");scanf("%d%d",&min,&max);dels(a,&n,min,max);printf("刪除后的數(shù):n");for(i=0;i<n;i+)printf("%d",ai);return0;執(zhí)行結(jié)果:17ttinclude<stdio.h>uoiddls<int*nTintmin,intmax)<inti,j,l<8,3,2給定一個(gè)順序存儲(chǔ)的線性

24、表L=(ai,a2,，aj,請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法查中最長(zhǎng)的遞增子序找該線性表中最長(zhǎng)遞增子序列。例如，(1,9,2,5,7,3,4,6,8,0)列為(3,4,6,8)#include<stdio.h>structnodeintb;/存儲(chǔ)當(dāng)前數(shù)的數(shù)值intk;記錄該數(shù)開始的遞增情況)s100001;intmain()inti,j;intn;18intmaxi=1,c;scanf("%d",&n);for(i=0;i<n;i+)scanf("%d",&si.b);for(i=0;i<n;i+)si.k=1;for(i=0;i&

25、lt;n-1;i+)for(j=i+1;j<n;j+)/判斷是否為遞增的，后面的大于前面的，即為遞增if(sj.b>sj-1.b)si.k+;elsebreak;for(i=0;i<n;i+)if(si.k>maxi)/連續(xù)遞增的數(shù)的個(gè)數(shù)大于當(dāng)前最大值19c=i;/從i開始的序列)for(i=c;i<c+maxi-1;i+)printf("%d",si.b);printf("%dn",sc+maxi-1.b);return0;)執(zhí)行結(jié)果：'C:tfstDebugCppl.exe"in垣一8anykeytoc

26、ontinme20pop,push)順9,3,3】如果有1、2、3、4、5按順序入棧，不同的堆棧操作(序可得到不同的堆棧輸出序列。請(qǐng)問(wèn)共有多少種不同的輸出序列？為什么?共有34種不同的輸出序列12345123541243512543132451325414325154322134521435215432314523154234152345123541243152435124531254313214532154324513254134215342513452135421432154325143521453215432110,3,2】請(qǐng)編寫程序?qū)⒅芯Y表達(dá)式轉(zhuǎn)換為后綴表達(dá)式。#include<

27、iostream>#include<stack>#include<string>usingnamespacestd;intprior(charop)if(op='+'|op='-')return1;if(op='*'|op='/')return2;return0;21)stringmiddletolast(stringmiddle)(stack<char>op;stringans;for(inti=0;i<middle.size();i+)(charc=middlei;if(c>

28、;='0'&&c<二'9')(ans.append(1,c);)else(if(c='(')op.push('(');else(if(c=')')22while(op.top()!='(')(ans.append(1,op.top();op.pop();)op.pop();)else(if(op.empty()(op.push(c);)else(if(prior(c)>prior(op.top()op.push(c);else(while(!op.empty()&

29、&prior(c)<=prior(op.top()23ans.append(1,op.top();op.pop();)op.push(c);)while(!op.empty()(ans.append(1,op.top();op.pop();)returnans;)intmain()24stringmdata,res;cin>>mdata;res=middletolast(mdata);for(inti=0;i<res.size();i+)(if(i=0)cout<<resi;elsecout<<''<<resi

30、;cout<<endl;return0;11,4,3】設(shè)二叉樹的存儲(chǔ)結(jié)構(gòu)如下:12345678910Lchild0012375r801011dataJHFDBACEGIRchild0009400000data為其中根結(jié)點(diǎn)的指針值為6,Lchild,Rchild分別為結(jié)點(diǎn)的左、右孩子指針域,數(shù)據(jù)域。25(1)畫出二叉樹的邏輯結(jié)構(gòu)A(2)寫出該樹的前序、中序和后序遍歷的序列前序遍歷：ABCEDFHGIJ中序遍歷：ECBHFDJIGA后續(xù)遍歷：ECHFJIGDBA12,4,4】可以生成如下二叉排序樹的關(guān)鍵字的初始排列有幾種？請(qǐng)寫出其中的任意4答：可以生成如上二叉排序樹的關(guān)鍵字的初始排列有

31、30種任寫4個(gè)序列如下：(5,7,6,4,2,1,3)(5,7,6,4,2,3,1)261171342216511516422137(5,4,2,3,7,6,1)(5,4,2,1,7,6,3)13,4,5給定關(guān)鍵字序列（11、7、16、4、22、13、5）,請(qǐng)回答:（1）畫出依次插入到一棵空的二叉排序樹后的最終二叉樹（6分）;27畫出依次把給定序列關(guān)鍵字插入一棵空的平衡二叉樹后的結(jié)果（4分）;14,4,6】假設(shè)一個(gè)文本使用的字符集為a,b,c,d,e,f,g,字符的哈夫曼編碼依次為0110,10,110,111,00,0111,010。(1)請(qǐng)根據(jù)哈夫曼編碼畫出此哈夫曼樹，并在葉子結(jié)點(diǎn)中標(biāo)注相

32、應(yīng)的字符；010101、/、e010g)()(cd011fclaf(2)若這些字符在文本中出現(xiàn)的頻率分別為：3,35,13,15,20,5,9,求該哈夫曼樹的帶權(quán)路徑長(zhǎng)度。帶權(quán)路徑長(zhǎng)度值為：4*(3+5)+3*(9+13+15)+2*(20+35)=2532815,5,3】用公式5.6計(jì)算一下你的身份證號(hào)碼的散列值是多少。#include<stdio.h>voidmain()ints256;int*p;doubleseed=5.6;doubleh=0;scanf("%s",s);for(p=s;*p;p+)h=h*seed+*p;printf("%ll

33、un",h);執(zhí)行結(jié)果:C:testDebugCppl.exe*2916,5,4】設(shè)有一組關(guān)鍵字29,01,13,15,56,20,87,27,69,9,10,74,散列函數(shù)為：H(key)=key%17，采用平方探測(cè)方法解決沖突。試在0到18的散列地址空間中對(duì)該關(guān)鍵字序列構(gòu)造散列表。首先將各個(gè)數(shù)除以17取余數(shù)：(6,2,7,1,2,7,7,6)可見20,85與46沖突，58與71沖突。將7+1再對(duì)13取余，直到無(wú)沖突，類似的6+1對(duì)13取余，最后可得H(71)=6;H(28)=2;H(14)=1;H(2)=3;H(20)=8;H(85=9;H(58)=10);哈希表存儲(chǔ)結(jié)構(gòu)：012

34、345678910142827146208558平均查找長(zhǎng)度=(1x4+2x2+3x1+4x1)/8=15/817,5,4】將關(guān)鍵字序列(7,8,30,11,18,9,14)散列存儲(chǔ)到散列列表中，散列表的存儲(chǔ)空間是一個(gè)下標(biāo)從0開始的一個(gè)一維數(shù)組。處理沖突采用線性探測(cè)法，散列函數(shù)為：H(key)=(keyX3)modTableSize,要求裝入因子為0.7。關(guān)鍵字78301118914散列地址1403472線性探測(cè)法構(gòu)建列表的過(guò)程012345678930插入77插入88插入3030插入1111插入185d1=1插入97插入141418,6,3】已知一個(gè)無(wú)向圖的頂點(diǎn)集為V0,Vi,，V7,其鄰接矩

35、陣如下所示:V0ViV2V3V4V5V6V7二01011001010101000001000100010001000、1000010000100010000010010001j(1)畫出該圖的圖形;31(2)給出從V0出發(fā)的深度優(yōu)先遍歷序和廣度優(yōu)先遍歷序深度優(yōu)先序列V0,V1,V2,V5,V4,V6,V3,V7廣度優(yōu)先序歹UV0V1V3V4V2V6V5V719,6,3】已知有向圖如右圖所示，請(qǐng)給出該圖的(D(2)每個(gè)頂點(diǎn)的入度和出度；各頂點(diǎn)的入/出度如下：頂點(diǎn)1:3/0;頂點(diǎn)2:2/2;頂點(diǎn)3:1/2;頂點(diǎn)4:1/2;頂點(diǎn)5:2/1;頂點(diǎn)6:2/3鄰接矩陣；(6)2、4)12341561100

36、000010°1003010001400101151000006110010(3)鄰接表;1固I322>143624k3k565161255(4)逆鄰接表；1 >2562 3»63 44 25 4466 >3>4(5)各個(gè)強(qiáng)連通分量20,6,3】試?yán)肈ijkstra算法求下圖在從頂點(diǎn)A到其它頂點(diǎn)的最短距離及對(duì)應(yīng)的路徑，寫出計(jì)算過(guò)程中各步狀態(tài)。最短路徑A到B:A-B,大小為1533A到C:A-C,大小為2A到D:A-D,大小為12A到E:A-CE,大小為10A到F:ACF,大小為6A到G:A-DG,大小為1521,6,3給出如下圖所示的具有7個(gè)結(jié)點(diǎn)的

37、網(wǎng)Go請(qǐng):(1)畫出該網(wǎng)的鄰接矩陣；012345601234560130005100400630004030400072004001500071025632520(2)采用Prim算法，從4號(hào)結(jié)點(diǎn)開始，給出該網(wǎng)的最小生成樹(畫出Prim算法的執(zhí)行過(guò)程及最小生成樹的生成示意圖)。voidprim(MGraphg,intv0,int&sum)intlowcostMAXSIZE,vsetMAXSIZE;34/pre存入前驅(qū)結(jié)點(diǎn)數(shù)組intv,preMAXSIZE;inti,j,k,min;v=v0;初始起點(diǎn)for(i=1;i<=g.n;i+)lowcosti=g.edgesv0i;/lowcost附數(shù)組prei=v0;vseti=0;vsetv0=1;sum=0;for(i=1;imin=INF;for(j=1;j<=g.n;j+)if(vsetj=0&&lowcostjmin=lowcostj;k=j;vsetk=1;/將此結(jié)點(diǎn)并入到所夠造的生成樹中v=k;if(min!=INF)printf("邊的起點(diǎn)為：d終點(diǎn)為：d權(quán)值為%dn",prev,v,min);sum+=min;elsebreak;for(j=1;j<=g.n;j+)/并入新結(jié)點(diǎn)后修改剩下的結(jié)點(diǎn)到生成樹的權(quán)值if(vsetj