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)系?！?，1，2】為了最快地存取數(shù)據(jù)元素，物理結(jié)構(gòu)宜采用 序存儲(chǔ) 結(jié)構(gòu)。3，1，2】數(shù)據(jù)結(jié)構(gòu)的三要素是 邏輯結(jié)構(gòu)， 物理結(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ù)雜度和空間復(fù)雜度_來(lái)進(jìn)行?！?，1，3】設(shè)n 為正整數(shù)，下面程序段中前置以記號(hào)的語(yǔ)句的頻度是 n(n+1)/2 。 for (i=0;

2、i<n; i+) for (j=0; 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ǔ)

3、結(jié)構(gòu)_ 存儲(chǔ)密度較大；_順序存儲(chǔ)結(jié)構(gòu)_存儲(chǔ)利用率較高；_順序存儲(chǔ)結(jié)構(gòu)_可以隨機(jī)存??；_鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)_不可以隨機(jī)存??；_鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)_插入和刪除操作比較方便。【8，3，2】從一個(gè)長(zhǎng)度為n的順序表中刪除第i個(gè)元素（1in）時(shí)，需向前移動(dòng) n-i 個(gè)元素?！?，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í)行以下操作：

4、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=null _； 不帶頭結(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

5、 3 14_。c. 刪除尾元結(jié)點(diǎn)的語(yǔ)句序列是_9 11 3 14_。(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 != NULL)P = Q; Q = Q->next;(7) while (P->next != Q) P = P->next;(8) while (P->next->nex

6、t != 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，則全部不可能的輸出序列有 C A B 。【15，3，3】.在棧頂指針為HS的鏈棧中，判定棧空的條件是head->next=null。【16，3，3】下列程序把十進(jìn)制數(shù)轉(zhuǎn)換為十六進(jìn)制數(shù)，請(qǐng)?zhí)顚懞线m的語(yǔ)句成分。void conversi

7、on10_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); 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 ?！?8，3，4】堆棧和隊(duì)列都是

8、線性表, 堆棧是_后進(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è)元素，再加入兩個(gè)元素后，rear和front的值分別是 2 和 4 。【20，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 ，樹的度

9、是 3 ，結(jié)點(diǎn)g在樹的第 3 層?！?1，4，3】從概念上講，樹與二叉樹是二種不同的數(shù)據(jù)結(jié)構(gòu)，將樹轉(zhuǎn)化為二叉樹的基本的目的是樹可采用二叉樹的存儲(chǔ)結(jié)構(gòu)并利用二叉樹的已有算法解決樹的有關(guān)問(wèn)題【22，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)是_號(hào)。【24，4，3】下列表示的圖中，共有_5_個(gè)是樹；有_3_個(gè)是二叉樹；有_2_個(gè)是完全二叉樹?！?/p>

10、25，4，4】n個(gè)結(jié)點(diǎn)的二叉排序樹的最大深度是 n ，最小深度為 log2+1 _ 【26，4，3】如果某二叉樹的后序遍歷序列是ABCDEFGHI，中序遍歷序列是ACBIDFEHG，則其先序遍歷序列的第一個(gè)字母是 I ，最后一個(gè)字母是 G ?！?7，4，3】下列二叉樹的中序遍歷序列是_ DBNGOAEC _ _;后序遍歷序列是_ DNOGBECA _。 【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,

11、55,20,84,27以后，關(guān)鍵字1、20和27所在地址的下標(biāo)分別是 、 _ 和 。插入上述6個(gè)元素的平均比較次數(shù)是 。答案：1、7、5、2【29，6，3】設(shè)無(wú)權(quán)圖G的鄰接矩陣為A，若（vi,vj）屬于圖G的邊集合，則對(duì)應(yīng)元素Aij等于 1 ，22、設(shè)無(wú)向圖G的鄰接矩陣為A，若Aij等于0，則Aji等于 0 ?！?0，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>

12、;,<d,f>,<f,c>。那么頂點(diǎn)e的入度是 2 ；出度是 1 ；通過(guò)頂點(diǎn)f的簡(jiǎn)單回路有 2 條；就連通性而言，該圖是 強(qiáng)連通圖 圖；它的強(qiáng)連通分量有 1 個(gè)；其生成樹可能的最大深度是 5。【32，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 次 分別與54、72、96比較【34，7，4】插入排序、希爾排序、選擇排序、快速排序、堆排序、歸并排序、和基數(shù)排序方法中，不

13、穩(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 += B;else for ( i=0; i<N*2; i+ ) for ( j=N*2; j>i; j- ) A += B;if中的時(shí)間復(fù)雜度為：O(n*n²)即O(n³)else中的時(shí)間復(fù)雜度為：O(n*n)即O(n²)【2，1，3】測(cè)試?yán)?.3中秦九韶算

14、法與直接法的效率差別。令，計(jì)算的值。利用clock()函數(shù)得到兩種算法在同一機(jī)器上的運(yùn)行時(shí)間。答：從運(yùn)行結(jié)果可以看出秦九昭算法效率上有很大優(yōu)勢(shì)；#include <stdio.h>#include <time.h>#include <math.h>clock_t start,stop;double duration;#define MAXN 10#define MAXK 1e7double f1(int n ,double a,double x);double f2(int n ,double a,double x);/秦九昭算法double f1(int

15、n ,double a,double x)int i =0 ;double p = a0;for(i=n;i>0;i-)p = ai-1 + x * p;return p;/直接算法double f2(int n ,double a,double x)int i =0 ;double p = a0;for(i=n;i>0;i-)p += ai*pow(x,i);return p;int main()int i ;double aMAXN ;for(i=0;i<MAXN;i+)ai=(double)i;start = clock();for(i=0;i<MAXK;i+)f

16、2(MAXN-1,a,1.1);stop = clock();duration = (double)(stop-start)/CLK_TCK/MAXK ;printf("直接算法：");printf("ticks = %fn",(double)(stop-start);printf("duration = %6.2en",duration);for(i=0;i<MAXN;i+)ai=(double)i;start = clock();for(i=0;i<MAXK;i+)f1(MAXN-1,a,1.1);stop = clo

17、ck();printf("秦九昭算法：");printf("ticks = %fn",(double)(stop-start);printf("duration = %6.2en",duration);return 0;【3，1，3】 試分析最大子列和算法1.3的空間復(fù)雜度。答：在1.4中存在4種解決最大子列的算法，具體空間復(fù)雜度如下：1、 窮舉法：算法并沒(méi)有開辟另外的存儲(chǔ)空間進(jìn)行存儲(chǔ)，利用的是累加所以空間復(fù)雜度為O(2);2、 部分窮舉：同上3、 分而治之：利用遞歸解決問(wèn)題，故空間復(fù)雜度為O(N);4、 在線處理：為O(2);【4，

18、1，3】試給出判斷是否為質(zhì)數(shù)的的算法。答案：#include <stdio.h>#include <math.h>int is_prime(int n)int i = 0; if(n!= 2 && n % 2 = 0) return 0; for(i=3;i<=sqrt(double)n);i+=2) if(n % i = 0) return 0; return 1;void main()int num = 0 ,result =0 ;printf("Input the num:"); scanf("%d",

19、 &num);result = is_prime(num); if(result) printf("%d is a primen", num); else printf("%d is not a primen", num);Input the num: 55 is a prime.【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

20、,&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í)程序的運(yùn)行時(shí)間。答案：#include <stdio.h>#include <time.h>void pailie(int* data, int n, int curr)int i = 0 ; if (curr=n-1) for (i = 0; i < n; +i ) printf("%d", datai)

21、; printf("n"); else for (i = curr; i < n; +i) int t; t = datacurr, datacurr = datai, datai = t; pailie(data, n, curr+1); t = datacurr, datacurr = datai, datai = t; int main()clock_t end;clock_t start = clock(); int n = 0;int i = 0; int as10 = 0,0,0,0,0,0,0,0,0,0;/n小于等于10 scanf("%d&

22、quot;, &n); for (i = 0; i < n; +i) asi = i+1; pailie(as, n, 0);end = clock();printf("The time was: %dn", (end - start) / CLK_TCK); return 0;N為7N為9 分析來(lái)看時(shí)間上雖然有比較大的增長(zhǎng)，但主要用于打印；但在時(shí)間復(fù)雜度上是隨著n的變大呈直線上升趨勢(shì)；【7，3，2】 給定一個(gè)順序存儲(chǔ)的線性表L = (, , ¼, )，請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法刪除所有值大于min而且小于max的元素。SeqList Delete(SeqLis

23、t &L, int min, int max) int i;=0,j=0 for (i=0; i<L.Length; i+) if(L.elemi>min && L.elemi<max)for(j=i;j<L.length;j+)L.elemj=L.elemj+1;-L.length; return L ;【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)。void main() int n,

24、 i, j, k; int A1024=;int dp1024=; scanf("%d", &n); for (i=1; i<=n; i+) scanf("%d", 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>=0; j-) if (Ai>Aj) dpi = max(dpi, dpj+1); int maximum = dp1; for (i=2;

25、 i<=n; i+) maximum = max(maximum, dpi); printf("%d maximum is : n", maximum);【9，3，3】 如果有1、2、3、4、5按順序入棧，不同的堆棧操作（pop, push）順序可得到不同的堆棧輸出序列。請(qǐng)問(wèn)共有多少種不同的輸出序列？為什么？答案：按照正常情況，1,2,3,4,5的全排列組合共有5! = 120,即120種，但由于 像：12435、12534之類的無(wú)法按順序出入棧，故按照順序入棧的情況共有56種：以1開始排列組合為14種以2開始排列組合為14種以3開始的排列組合為9種以4開始的排列組合

26、為4種以5開始的排列組合為1種【10，3，2】請(qǐng)編寫程序?qū)⒅芯Y表達(dá)式轉(zhuǎn)換為后綴表達(dá)式。答案：使用棧的循序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)、棧的順序存儲(chǔ)結(jié)構(gòu)，用一維數(shù)組實(shí)現(xiàn) #include <stdio.h> #include <stdlib.h> #define OK 1 #define ERROR -1 #define TRUE 1 #define FALSE 0 #define MAXSIZE 10 typedef int Status; typedef char ElemType; typedef struct ElemType dataMAXSIZE; int top;/棧頂指針

27、 Stack; /1. 初始化 Status InitStack(Stack *S) int i; for(i=0;i<MAXSIZE;i+) S->datai=NULL; S->top=-1; return OK; /2. 創(chuàng)建一個(gè)長(zhǎng)度為n的堆棧 Status CreateStack(Stack *S,int n) int i =0; if(n>MAXSIZE | n<1) printf("輸入長(zhǎng)度有誤！n"); return ERROR; for(i=0;i<n;i+) S->datai=rand()%100+1; S->

28、top=n-1; return OK; Status push(Stack *S,ElemType e) if(MAXSIZE-1=S->top) printf("棧已滿n"); return ERROR; /棧頂指向的元素有值 +(S->top); S->dataS->top=e; return OK; /4. 出棧 Status pop(Stack *S,ElemType *e) /將棧頂元素出棧，傳給e if(-1=S->top) printf("棧為空！n"); return ERROR; *e=S->data

29、S->top; -(S->top); return OK; /5. 中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式 void MidToFinal(char *mid,char *final) /中綴表達(dá)式為middle，要轉(zhuǎn)換成后綴表達(dá)式傳給last /新建一個(gè)棧，來(lái)存儲(chǔ)符號(hào) char e; Stack S; if(OK!=InitStack(&S) printf("初始化棧失?。"); /當(dāng)帶轉(zhuǎn)換的字符串*mid未終止時(shí)，循環(huán)處理 while(*mid) /如果是數(shù)字，則直接輸出 if(*mid>='0' && *mid<=&#

30、39;9') *(final+)=*(mid+); continue; else if(*mid='+' | *mid='-' | *mid='*' | *mid='/' | *mid='(' | *mid=')') /輸入的是合法運(yùn)算符號(hào),比較之前是否有更高優(yōu)先級(jí)的符號(hào) if(S.top=-1 | '('=*mid) /當(dāng)符號(hào)棧為空或遇到左括號(hào)時(shí)，符號(hào)入棧 push(&S,*(mid+); continue; if(')'=*mid) /遇到右括號(hào)時(shí)

31、，棧頂元素依次出棧；直到遇到第一個(gè)左括號(hào)時(shí)結(jié)束 pop(&S,&e); *(final+)=e; while(pop(&S,&e) && e!='(') *(final+)=e; / printf("%cn",e); mid+; continue; /后續(xù)的處理都要取出臨時(shí)的棧頂元素，與當(dāng)前輸入的符號(hào)*mid相比較；當(dāng)臨時(shí)棧頂元素優(yōu)先級(jí)大于等于輸入符號(hào)的優(yōu)先級(jí)時(shí)，出棧；否則符號(hào)入棧（已經(jīng)彈出一個(gè)，記得把彈出的元素也入棧） pop(&S,&e); if('+'=*mid | 

32、9;-'=*mid) if(e='(') push(&S,'('); push(&S,*(mid+); continue; else *(final+)=e; push(&S,*(mid+); continue; else if('*'=*mid | '/'=*mid) if('*'=e | '/'=e) *(final+)=e; push(&S,*(mid+); continue; else push(&S,e); push(&S,*(mid

33、+); continue; else printf("輸入的字符不合法！%cn",*mid); return; /當(dāng)待轉(zhuǎn)換的字符已經(jīng)結(jié)束時(shí)，符號(hào)棧至少還有一個(gè)元素（中綴表達(dá)式的特點(diǎn)：數(shù)字結(jié)尾；后綴表達(dá)式以符號(hào)結(jié)尾）；將棧中的元素依次出棧 while(S.top!=-1) pop(&S,&e); *(final+)=e; /字符串的結(jié)束符！ *final='0' int main() char data="3+(5*6-7/1*7)*9" char final="" MidToFinal(data,fin

34、al); printf("%sn",final); return 0; 【11，4，3】設(shè)二叉樹的存儲(chǔ)結(jié)構(gòu)如下：12345678910Lchild00237580101dataJHFDBACEGIRchild0009400000其中根結(jié)點(diǎn)的指針值為6，Lchild，Rchild分別為結(jié)點(diǎn)的左、右孩子指針域，data為數(shù)據(jù)域。（1） 畫出二叉樹的邏輯結(jié)構(gòu)。（2） 寫出該樹的前序、中序和后序遍歷的序列。答：前序遍歷：ECBHFDJIGA中序遍歷：ABCEDFHGIJ后序遍歷：ECHFJIGDBA【12，4，4】可以生成如下二叉排序樹的關(guān)鍵字的初始排列有幾種？請(qǐng)寫出其中的任意5個(gè)

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

36、哈夫曼樹，并在葉子結(jié)點(diǎn)中標(biāo)注相應(yīng)的字符；（2）若這些字符在文本中出現(xiàn)的頻率分別為：3,35,13,15,20,5,9，求該哈夫曼樹的帶權(quán)路徑長(zhǎng)度。答：【15，5，3】用公式5.6計(jì)算一下你的身份證號(hào)碼的散列值是多少。答：公式5.6如下h(key)=key mod 11;身份證號(hào)碼信息如下設(shè)身份證為數(shù)字類型，對(duì)11求余后為4【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)造散列表。答：散列

37、地址012345678910111213141516說(shuō)明插入2929無(wú)沖突插入0101無(wú)沖突插入1313無(wú)沖突插入1515無(wú)沖突插入5656無(wú)沖突插入2020無(wú)沖突插入8787無(wú)沖突插入2727無(wú)沖突插入6969d2=-1插入99無(wú)沖突插入1010d1=1插入7474無(wú)沖突【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 TableSize，要求裝入因子為0.7。答：tableSize為7/0.7，即10，散列函數(shù)為h(key

38、)=(key*3) mod 10;下面為散列表插入過(guò)程散列地址0123456789說(shuō)明插入77無(wú)沖突插入88無(wú)沖突插入3030無(wú)沖突插入1111無(wú)沖突插入1818d1=1插入99無(wú)沖突插入1414無(wú)沖突【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 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) 畫出該圖的圖形； (2)

39、 給出從V0出發(fā)的深度優(yōu)先遍歷序和廣度優(yōu)先遍歷序。答：深度優(yōu)先：01254673廣度優(yōu)先：01324657【19，6，3】已知有向圖如右圖所示，請(qǐng)給出該圖的（1） 每個(gè)頂點(diǎn)的入度和出度； （2） 鄰接矩陣；（3） 鄰接表；（4） 逆鄰接表；（5） 各個(gè)強(qiáng)連通分量答案：（1）：節(jié)點(diǎn)號(hào)入度出度130222312413521623（2）：1 0 1 0 0 1 1 2 1 0 1 1 0 1 3 0 1 0 1 0 1 4 0 1 1 0 1 1 5 1 0 0 1 0 1 6 1 1 1 1 1 0 (3)：（4）：（5）：1：無(wú)強(qiáng)連通分量 【20，6，3】試?yán)肈ijkstra算法求下圖在從頂點(diǎn)

40、A到其它頂點(diǎn)的最短距離及對(duì)應(yīng)的路徑，寫出計(jì)算過(guò)程中各步狀態(tài)。答：初始（第0步）第一步（選C）第二步(選F)第三步(選E)第四步(選G)第五步(選D)第六步(選B)終點(diǎn)DPDPDPDPDPDPDPB15015A15A15A15A15A15AC202A2A2A2A2A2AD12012A12A12A12A12A12AE10C10C10C10C10C10CF6C6C6C6C6C6CG16F16F16F15D15D【21，6，3】給出如下圖所示的具有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ò)程及最小生成樹的生成

41、示意圖）。0123645164432315725答：（1）：0 0 1 1 0 0 0 1 1 1 0 0 1 0 0 1 2 1 0 0 0 1 0 1 3 0 1 0 0 0 1 1 4 0 0 1 0 0 1 1 5 0 0 0 1 1 0 1 6 1 1 1 1 1 1 0 【22，7，4】給定數(shù)組48, 25, 6, 90, 17, 84, 62, 48, 27, 96, 49, 72, 17，請(qǐng)分別用簡(jiǎn)單選擇排序、直接插入排序和冒泡排序分別進(jìn)行排序，寫出排序過(guò)程中每一步操作后的結(jié)果，分析各自比較和交換的次數(shù)，以及排序結(jié)果是否穩(wěn)定。答：簡(jiǎn)單選擇排序：不穩(wěn)定48 25 6 90 17

42、84 62 48 27 96 49 72 17第3與第1元素互換位置，值分別為6、486 25 48 90 17 84 62 48 27 96 49 72 17第5與第2元素互換位置，值分別為17、256 17 48 90 25 84 62 48 27 96 49 72 17第13與第3元素互換位置，值分別為17、486 17 17 90 25 84 62 48 27 96 49 72 48第5與第4元素互換位置，值分別為25、906 17 17 25 90 84 62 48 27 96 49 72 48第9與第5元素互換位置，值分別為27、906 17 17 25 27 84 62 48 9

43、0 96 49 72 48第8與第6元素互換位置，值分別為48、846 17 17 25 27 48 62 84 90 96 49 72 48第13與第7元素互換位置，值分別為48、626 17 17 25 27 48 48 84 90 96 49 72 62第11與第8元素互換位置，值分別為49、846 17 17 25 27 48 48 49 90 96 84 72 62第13與第9元素互換位置，值分別為62、906 17 17 25 27 48 48 49 62 96 84 72 90第12與第10元素互換位置，值分別為72、966 17 17 25 27 48 48 49 62 72

44、84 96 906 17 17 25 27 48 48 49 62 72 84 96 90第13與第12元素互換位置，值分別為90、966 17 17 25 27 48 48 49 62 72 84 90 96插入排序：是穩(wěn)定的過(guò)程如下：48 25 6 90 17 84 62 48 27 96 49 72 1725 48 6 90 17 84 62 48 27 96 49 72 176 25 48 90 17 84 62 48 27 96 49 72 176 25 48 90 17 84 62 48 27 96 49 72 176 17 25 48 90 84 62 48 27 96 49 7

45、2 176 17 25 48 84 90 62 48 27 96 49 72 176 17 25 48 62 84 90 48 27 96 49 72 176 17 25 48 48 62 84 90 27 96 49 72 176 17 25 27 48 48 62 84 90 96 49 72 176 17 25 27 48 48 62 84 90 96 49 72 176 17 25 27 48 48 49 62 84 90 96 72 176 17 25 27 48 48 49 62 72 84 90 96 176 17 17 25 27 48 48 49 62 72 84 90 96

46、6 17 17 25 27 48 48 49 62 72 84 90 96冒泡排序:是穩(wěn)定的；48 25 6 90 17 84 62 48 27 96 49 72 17第1與第2元素互換位置，值分別為48、2525 48 6 90 17 84 62 48 27 96 49 72 17第2與第3元素互換位置，值分別為48、625 6 48 90 17 84 62 48 27 96 49 72 17第4與第5元素互換位置，值分別為90、1725 6 48 17 90 84 62 48 27 96 49 72 17第5與第6元素互換位置，值分別為90、8425 6 48 17 84 90 62 48 27 96 49 72 17第6與第7元素互換位置，值分別為90、6225 6 48 17 84 62 90 48 27 96 49 72 17第7與第8元素互換位置，值分別為90、4825 6 48 17 84 62 48 90 27 96 49 72 17第8與第9元素互換位置，值分別為90、2725 6 48 17 84 62 48 27 90