浙大遠(yuǎn)程教育數(shù)據(jù)結(jié)構(gòu)與算法離線作業(yè)參考答案

1、浙江大學(xué)遠(yuǎn)程教育學(xué)院數(shù)據(jù)結(jié)構(gòu)與算法課程離線作業(yè)姓名：學(xué) 號(hào)：年級(jí)：學(xué)習(xí)中心：一、填空題：（【序號(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)?！?，1，2】存儲(chǔ)結(jié)構(gòu)可根據(jù)數(shù)據(jù)元素在機(jī)器中的位置是否一定連續(xù)分為 順序存儲(chǔ)結(jié)構(gòu) ， 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)?！?，1，3】度量算法效率可通過(guò) 時(shí)間復(fù)雜度 來(lái)進(jìn)行。【5，1，3】設(shè)n 為正整數(shù)，下面程序段中前置以記號(hào)的語(yǔ)句的頻度是 n(n+1)/2 。 for (i=0; i<n; i+) for (j=0

2、; j<n; j+) if (i+j=n-1) aij=0; 【6，1，3】設(shè)n 為正整數(shù)，試確定下列各程序段中前置以記號(hào)的語(yǔ)句的頻度: (1) i=1; k=0; while (i<=n-1) i+; k+=10 * i; / 語(yǔ)句的頻度是n-1。 (2) 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ǔ)利用率較高；順序可以隨機(jī)存??；鏈?zhǔn)讲?/p>

3、可以隨機(jī)存??；鏈?zhǔn)讲迦牒蛣h除操作比較方便?！?，3，2】從一個(gè)長(zhǎng)度為n的順序表中刪除第i個(gè)元素（1in）時(shí)，需向前移動(dòng) n-i 個(gè)元素。【9，3，2】帶頭結(jié)點(diǎn)的單鏈表Head為空的條件是Head->next=NULL?！?0，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->

4、next->next ; free(q);【12，3，2】帶頭結(jié)點(diǎn)的單循環(huán)鏈表Head的判空條件是Head->next=Head； 不帶頭結(jié)點(diǎn)的單循環(huán)鏈表的判空條件是Head=NULL?！?3，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ǔ)句序列是10 12 8 11 4 14。b. 刪除結(jié)點(diǎn)P的語(yǔ)句序列是10 12 7 3 14。c. 刪除尾元結(jié)點(diǎn)的語(yǔ)句序列是9 11 3 14。(1) P = P->next;(2) P->next = P;(3) P->

5、;next = P->next ->next;(4) P = P->next ->next;(5) while (P != NULL) P = P->next;(6) while (Q->next != NULL)P = Q; Q = Q->next;(7) 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

6、) 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件是head->next=NULL ?！?6，3，3】下列程序把十進(jìn)制數(shù)轉(zhuǎn)換為十六進(jìn)制數(shù)，請(qǐng)?zhí)顚懞线m的語(yǔ)句成分。void conversion10_16() InitStack(&s); scanf(“%d”,&N); while(N)Push(s,N%16) ; N = N/16;

7、while(!StackEmpty(s) Pop(s,e) ; if(e<=9)printf(“%d”,e); else printf(“%c”,e-10+A); /* 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è)元素，再加入兩個(gè)元素后，rear和front的值分別是 2 和 4 。【18，3，4】堆棧和隊(duì)列都是線性表, 堆棧是后進(jìn)先出的線性表, 而隊(duì)列是先進(jìn)先出的線性表?！?9，3，4】若用一個(gè)大小為6個(gè)元素的數(shù)組來(lái)實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear=0和front=3。當(dāng)從隊(duì)列中刪除一個(gè)元素，再

8、加入兩個(gè)元素后，rear和front的值分別是 2 和 4 ?！?0，4，2】已知一棵樹邊的集合是<a,d>,<d,c>,<d,j>,<e,a>,<f,g>,<d,b>,<g,h>,<g,i>,<e,f>。那么根結(jié)點(diǎn)是 e ，結(jié)點(diǎn)b的雙親是 d ，結(jié)點(diǎn)a的子孫有 bcdj ，樹的深度是 4 ，樹的度是 3 ，結(jié)點(diǎn)g在樹的第 3 層?！?1，4，3】從概念上講，樹與二叉樹是二種不同的數(shù)據(jù)結(jié)構(gòu)，將樹轉(zhuǎn)化為二叉樹的基本的目的是采用二叉樹的存儲(chǔ)結(jié)構(gòu)并利用二叉樹的已有算法解決樹的有關(guān)問(wèn)題?！?2，

9、4，3】滿三叉樹的第i層的結(jié)點(diǎn)個(gè)數(shù)為 3i-1 ，深度為h時(shí)該樹中共有 3h-1 結(jié)點(diǎn)?！?3，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)是 32 號(hào)?！?4，4，3】下列表示的圖中，共有 5 個(gè)是樹；有 3 個(gè)是二叉樹；有 2 個(gè)是完全二叉樹?！?5，4，4】n個(gè)結(jié)點(diǎn)的二叉排序樹的最大深度是 n ，最小深度為 log2n+1 ?！?6，4，3】如果某二叉樹的后序遍歷序列是ABCDEFGHI，中序遍歷序列是ACBIDFEHG，則其先

10、序遍歷序列的第一個(gè)字母是 I ，最后一個(gè)字母是 G ?！?7，4，3】下列二叉樹的中序遍歷序列是DBNGOAEC ;后序遍歷序列是DNIGBECA 。 【28，5，4】設(shè)HASH表的大小為 n (n=10), HASH函數(shù)為 h(x)=x % 7, 如果二次探測(cè)再散列方法Hi=(H(key)+di) mod 10 (di = 12,22,32,)解決沖突，在HASH表中依次插入關(guān)鍵字1,14,55,20,84,27以后，關(guān)鍵字1、20和27所在地址的下標(biāo)分別是 1 、 7 和 5 。插入上述6個(gè)元素的平均比較次數(shù)是 2 ?！?9，6，3】設(shè)無(wú)權(quán)圖G的鄰接矩陣為A，若（vi,vj）屬于圖G的邊集

11、合，則對(duì)應(yīng)元素Aij等于 1 ，22、設(shè)無(wú)向圖G的鄰接矩陣為A，若Aij等于0，則Aji等于 0 ?！?0，6，3】若一個(gè)圖用鄰接矩陣表示，則刪除從第i個(gè)頂點(diǎn)出發(fā)的所有邊的方法是 矩陣第i行全部置為零 ?！?1，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è)；其生成樹可能的最大深度是 5

12、?！?2，7，1】排序過(guò)程一般需經(jīng)過(guò)兩個(gè)基本操作，它們是 比較 和 移動(dòng) ?！?3，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 次?！?4，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+

13、 ) for ( j=N*N; j>i; j- ) A += B;else for ( i=0; i<N*2; i+ ) for ( j=N*2; j>i; j- ) A += B;答： if A>B為真，則for語(yǔ)句的外循環(huán)N次，內(nèi)循環(huán)為N（N-1）次，因此時(shí)間復(fù)雜度為O(N* N（N-1）)，也就是N的三次方。 if A>B為假，則for語(yǔ)句的外循環(huán)2N次，內(nèi)循環(huán)為N次，因此時(shí)間復(fù)雜度為O（2N*N），也就是N的平方。整段取最大的，時(shí)間復(fù)雜度就是N立方?！?，1，3】測(cè)試?yán)?.3中秦九韶算法與直接法的效率差別。令，計(jì)算的值。利用clock()函數(shù)得到兩種算法在

14、同一機(jī)器上的運(yùn)行時(shí)間。答： 直接法：0.1 s 秦九韶算法：0.04 s【3，1，3】 試分析最大子列和算法1.3的空間復(fù)雜度。答：算法1.3的基本思路是將原問(wèn)題拆分成若干小型問(wèn)題，分別解決后再將結(jié)果合而治之，用遞歸方法實(shí)現(xiàn)。算法1.3的負(fù)責(zé)度分析略有難度：若記整體時(shí)間復(fù)雜度為T(N)，則函數(shù)DivideAndConquer中通過(guò)遞歸實(shí)現(xiàn)“分”的復(fù)雜度為2T(N/2)，因?yàn)槲覀兘鉀Q了2個(gè)長(zhǎng)度減半的字問(wèn)題。求跨分界線的最大子列和時(shí)，有兩個(gè)簡(jiǎn)單的for循環(huán)，所用步驟一共不超過(guò)N，所以可以在O(N)時(shí)間完成。其他步驟都只需常熟O(1)時(shí)間。綜上分析則有遞推式：T(1)=O(1)；T(N)=2T(N/

15、2)+O(N) =22T(N/2)/2+O(N/2)+O(N)=22T(N/22)+2O(N) =2KT(N/2k)+kO(N)當(dāng)不斷對(duì)分直到N/2k=1,即2k=N時(shí)，就得到T(N)=NT(1)+logN*O(N)=O(N log N)。此算法比算法1.2又快了一些，當(dāng)N=104時(shí)，效果會(huì)非常明顯。但是這仍然不是最快的算法?！?，1，3】試給出判斷是否為質(zhì)數(shù)的的算法。答:int sushu(int N) int i; int flag=1; if (N=1) return false; /1既不是合數(shù)也不是質(zhì)數(shù) if (N=2) return true for (i=2;i<=sqrt

16、(N);i+) if (N%i=0) flag=0； break; return flag;【5，2，2】請(qǐng)編寫程序，輸入整數(shù)n和a，輸出S=a+aa+aaa+aaa(n個(gè)a)的結(jié)果。答：#include"stdio.h"int main() int a,b,n,i,s=0; scanf("%d %d",&a,&n); b=a; for(i=1;i<=n;i+) s+=a; a=a*10+b; printf("%dn",s);【6，2，3】請(qǐng)編寫遞歸函數(shù)，輸出123.n的全排列（n小于10）,并觀察n逐步增大時(shí)程

17、序的運(yùn)行時(shí)間。答：#include <stdio.h> #define N 8 int n = 0;void swap(int *a, int *b) int m; m=*a; *a=*b; *b=m;void perm(int list, int k, int m) int i; if(k > m) for(i = 0; i <= m; i+) printf("%d", listi); printf("n"); n+; else for(i = k; i <= m; i+) swap(&listk,&lis

18、ti); perm(list,k + 1, m); swap(&listk,&listi); int main() int listN; int num,i=0; printf("Pleaseinput a num:"); scanf("%d",&num); while(num != 0) listi=num%10; num=num/10; i+; perm(list,0, i-1); printf("total:%dn",n); return 0;【7，3，2】 給定一個(gè)順序存儲(chǔ)的線性表L = (, , &#

19、188;, )，請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法刪除所有值大于min而且小于max的元素。答：#include <stdio.h> #include <stdlib.h> #include <math.h> typedef int ElemType; typedef struct LNode ElemType data; /* 數(shù)據(jù)子域 */ struct LNode *next; /* 指針子域 */ LNode; /* 結(jié)點(diǎn)結(jié)構(gòu)類型 */ LNode *L; /* 函數(shù)聲明 */ LNode *creat_L();void delete_L(LNode *L,int i)

20、; /返回值格式變?yōu)榭?* 建立線性鏈表*/LNode *creat_L() LNode *h,*p,*s; ElemType x; h=(LNode *)malloc(sizeof(LNode); /* 分配頭結(jié)點(diǎn) */ h->next=NULL; p=h; printf("輸入一串?dāng)?shù)字（以-1結(jié)束）:ndata= "); scanf("%d",&x); /* 輸入第一個(gè)數(shù)據(jù)元素 */ while( x!=-1) /* 輸入-1，結(jié)束循環(huán) */ s=(LNode *)malloc(sizeof(LNode); /* 分配新結(jié)點(diǎn) */ s-

21、>data=x; s->next=NULL p->next=s; p=s; printf("data= "); scanf("%d",&x); /* 輸入下一個(gè)數(shù)據(jù)*/ return(h); /* creat_L */* 輸出單鏈表中的數(shù)據(jù)元素*/void out_L(LNode *L) LNode *p; p=L->next; printf("n數(shù)據(jù)是:"); while(p!=NULL) printf("%5d",p->data); p=p->next; /* out

22、_link */* 刪除大于x小于y的值*/void delete_L(LNode *L,int a,int b) LNode *p,*q; p=L; q=p; p=p->next; if(p=NULL) printf("ERROR:鏈表為空"); while(p!=NULL) if(p->data >a) && (p->data <b) q->next=p->next; free(p); p=q->next; else q=p; p=p->next; /* delete_L */void main()

23、int a,b L=creat_L( ); out_L(L); printf("nn請(qǐng)輸入你要?jiǎng)h除的元素的范圍min和max:n"); scanf("%d%d",&a,&b); delete_L(L,a,b); out_L(L); printf("n"); /* main */【8，3，2】給定一個(gè)順序存儲(chǔ)的線性表L = (, , ¼, )，請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法查找該線性表中最長(zhǎng)遞增子序列。例如，(1,9,2,5,7,3,4,6,8,0)中最長(zhǎng)的遞增子序列為(3,4,6,8)。答：#include <iost

24、ream>#include <algorithm>using namespace std;#define MAXN 1003int AMAXN;int dpMAXN;/ 動(dòng)態(tài)規(guī)劃思想O(n2)int main() int n, i, j, k; cin >> n; for (i=1; i<=n; i+) cin >> Ai; dp1 = 1; / 有n個(gè)階段 for (i=2; i<=n; i+) dpi = 1; / 每個(gè)階段只有1個(gè)狀態(tài) / 每個(gè)狀態(tài)有i種決策,以得出以元素i結(jié)尾的最長(zhǎng)遞歸子序列的長(zhǎng)度 for (j=i-1; j>

25、=0; j-) if (Ai>Aj) dpi = max(dpi, dpj+1); int maximum = dp1; for (i=2; i<=n; i+) maximum = max(maximum, dpi); cout << maximum; 【9，3，3】 如果有1、2、3、4、5按順序入棧，不同的堆棧操作（pop, push）順序可得到不同的堆棧輸出序列。請(qǐng)問(wèn)共有多少種不同的輸出序列？為什么？答： 共有34種不同的輸出序列 12345 12354 12435 12543 13245 13254 14325 15432 21345 21435 21543 2

26、3145 23154 23415 23451 23541 24315 24351 24531 25431 32145 32154 32415 32451 32541 34215 34251 34521 35421 43215 43251 43521 45321 54321【10，3，2】請(qǐng)編寫程序?qū)⒅芯Y表達(dá)式轉(zhuǎn)換為后綴表達(dá)式。答:#include <iostream>#include <stack>#include <string>using namespace std;int prior(char op)if(op='+'|op='

27、-') return 1;if(op='*'|op='/') return 2;return 0;string middletolast(string middle)stack<char> op;string ans; for(int i=0;i<middle.size();i+) char c=middlei; if(c>='0'&&c<='9') ans.append(1,c); else if(c='(') op.push('('); el

28、se if(c=')') while(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()&&prior(c)<=prior(op.top() ans.append(1,op.top(); op.pop(); op.push(c); while(!op.empty() ans.ap

29、pend(1,op.top(); op.pop(); return ans;int main()string mdata,res;cin>>mdata; res=middletolast(mdata);for(int i=0;i<res.size();i+) if(i=0) cout<<resi; else cout<<' '<<resi;cout<<endl;return 0;【11，4，3】設(shè)二叉樹的存儲(chǔ)結(jié)構(gòu)如下：12345678910Lchild00237580101dataJHFDBACEGIRchild

30、0009400000其中根結(jié)點(diǎn)的指針值為6，Lchild，Rchild分別為結(jié)點(diǎn)的左、右孩子指針域，data為數(shù)據(jù)域。（1） 畫出二叉樹的邏輯結(jié)構(gòu)。答：ABCEDFGIHJ（2） 寫出該樹的前序、中序和后序遍歷的序列。答：前序序列： ABCEDFHGI 中序序列： ECBHFDJIGA 后序序列： ECHFJIGDBA【12，4，4】可以生成如下二叉排序樹的關(guān)鍵字的初始排列有幾種？請(qǐng)寫出其中的任意4個(gè)。答：可以生成如上二叉排序樹的關(guān)鍵字的初始排列有30種 任寫4個(gè)序列如下：（5， 7， 6，4，2，1，3）（5， 7， 6，4，2，3，1）（5， 4， 2，3，7，6，1） （5， 4， 2，

31、1，7，6，3）【13，4，5】給定關(guān)鍵字序列（11、7、16、4、22、13、5），請(qǐng)回答：（1） 畫出依次插入到一棵空的二叉排序樹后的最終二叉樹（6分）；答： 11 7 13 4 16 22 5 （2）畫出依次把給定序列關(guān)鍵字插入一棵空的平衡二叉樹后的結(jié)果（4分）； 11 5 16 4 7 13 22 【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)注相應(yīng)的字符；答：01010001111egbcd（2） 若這些字符在文本中出現(xiàn)的頻

32、率分別為：3,35,13,15,20,5,9，求該哈夫曼樹的帶權(quán)路徑長(zhǎng)度。答：WPL=4*(3+5)+3*(9+13+15)+2*(20+35)=253【15，5，3】用公式5.6計(jì)算一下你的身份證號(hào)碼的散列值是多少。答：924300【16，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ú)沖

33、突，類似的6+1對(duì)13取余，最后可得H(71)=6；H（28）=2；H（46）=7；H(14)=1；H(2)=3；H(20)=8；H(85)=9；H(58)=10；哈希表存儲(chǔ)結(jié)構(gòu)： 0 1 2 3 4 5 6 7 8 9 10 14 28 2 71 46 20 85 58 平均查找長(zhǎng)度=（1×4+2×2+3×1+4×1）/8=15/8【17，5，4】將關(guān)鍵字序列（7，8，30，11，18，9，14）散列存儲(chǔ)到散列列表中，散列表的存儲(chǔ)空間是一個(gè)下標(biāo)從0開始的一個(gè)一維數(shù)組。處理沖突采用線性探測(cè)法，散列函數(shù)為：H（key）=（key×3）mod Ta

34、bleSize，要求裝入因子為0.7。答：（1）由裝載因子0.7，數(shù)據(jù)總數(shù)7個(gè)存儲(chǔ)空間長(zhǎng)度為10P=10所以，構(gòu)造的散列表為：01234567893071411818.9.H（7）=（7×3）MOD10=1（2）查找成功的ASL=(1+1+1+1+2+1+1)/7=8/7查找不成功的ASL=(7+6+5+4+3+2+1+2+1+1)/10=3.2【18，6，3】已知一個(gè)無(wú)向圖的頂點(diǎn)集為V0，V1，V7，其鄰接矩陣如下所示：V0 0 1 0 1 1 0 0 0V1 1 0 1 0 1 0 0 0V2 0 1 0 0 0 1 0 0V3 1 0 0 0 0 0 1 0V4 1 1 0 0

35、 0 0 1 0V5 0 0 1 0 0 0 0 0V6 0 0 0 1 1 0 0 1V7 0 0 0 0 0 0 0 1(1) 畫出該圖的圖形； 答：23104756(2) 給出從V0出發(fā)的深度優(yōu)先遍歷序和廣度優(yōu)先遍歷序。答：深度優(yōu)先序列 V0,V1,V2,V5,V4,V6,V3,V7廣度優(yōu)先序列 V0 V1 V3 V4 V2 V6 V5 V7【19，6，3】已知有向圖如右圖所示，請(qǐng)給出該圖的（1） 每個(gè)頂點(diǎn)的入度和出度； （2） 鄰接矩陣；（3） 鄰接表；（4） 逆鄰接表；（5） 各個(gè)強(qiáng)連通分量。答： （1）各頂點(diǎn)的入度和出度如下：3/0 2/2 1/2 1/2 2/1 2/3（2）鄰接

36、矩陣如下：123456100000021001003010001400101151000006110010（3）鄰接表如下： 6 5425 21631112345623424366 64（4）逆鄰接表如下：123456（5）有三個(gè)強(qiáng)連通分量: 【20，6，3】試?yán)肈ijkstra算法求下圖在從頂點(diǎn)A到其它頂點(diǎn)的最短距離及對(duì)應(yīng)的路徑，寫出計(jì)算過(guò)程中各步狀態(tài)。答：1 c:2 2 c:2 f:6 3 c:2 f:6 e:10 4 c:2 f:6 e:10 d:115 c:2 f:6 e:10 d:11 g:14 6 c:2 f:6 e:10 d:11 g:14 b:15【21，6，3】給出如下圖所

37、示的具有7個(gè)結(jié)點(diǎn)的網(wǎng)G。請(qǐng)：（1） 畫出該網(wǎng)的鄰接矩陣；（2） 采用Prim算法，從4號(hào)結(jié)點(diǎn)開始，給出該網(wǎng)的最小生成樹（畫出Prim算法的執(zhí)行過(guò)程及最小生成樹的生成示意圖）。0123645164432315725答：void prim(MGraph g,int v0,int &sum)   int lowcostMAXSIZE,vsetMAXSIZE;   int v,preMAXSIZE;             &

38、#160;   /pre存入前驅(qū)結(jié)點(diǎn)數(shù)組   int i,j,k,min;   v=v0;                                /初始起點(diǎn)   for(i=1;i<=g.n;i+

39、)      lowcosti=g.edgesv0i;       /lowcost的數(shù)組      prei=v0;      vseti=0;      vsetv0=1;   sum=0;   for(i=1;i      min=INF; &

40、#160;    for(j=1;j<=g.n;j+)          if(vsetj=0&&lowcostj             min=lowcostj;             k=j; 

41、60;                      vsetk=1;        /將此結(jié)點(diǎn)并入到所夠造的生成樹中      v=k;      if(min!=INF)      

42、;    printf("邊的起點(diǎn)為：   %d   終點(diǎn)為：    %d   權(quán)值為    %dn",prev,v,min);          sum+=min;               el

43、se          break;            for(j=1;j<=g.n;j+)/并入新結(jié)點(diǎn)后修改剩下的結(jié)點(diǎn)到生成樹的權(quán)值          if(vsetj=0&&g.edgesvj        &

44、#160;    lowcostj=g.edgesvj;             prej=v;   /并記其下全趨結(jié)點(diǎn)                   【22，7，4】給定數(shù)組48, 25, 6, 90, 17, 84, 62, 48, 27, 96, 49, 7

45、2, 17，請(qǐng)分別用簡(jiǎn)單選擇排序、直接插入排序和冒泡排序分別進(jìn)行排序，寫出排序過(guò)程中每一步操作后的結(jié)果，分析各自比較和交換的次數(shù)，以及排序結(jié)果是否穩(wěn)定。答：簡(jiǎn)單選擇排序：6，25，48， 90, 17, 84, 62, 48, 27, 96, 49, 72, 176，17， 48， 90,25, 84, 62, 48, 27, 96, 49, 72, 176，17， 17， 90,25, 84, 62, 48, 27, 96, 49, 72, 486，17， 17， 25,90 84, 62, 48, 27, 96, 49, 72, 486，17， 17， 25, 27, 84, 62, 48, 90 96, 49, 72, 486，17， 17， 25, 27, 48 62 84