1 - PDF Free Download

基本練習題 1. 答 : 鄰接矩陣 : D E D E 0 0 1 0 1 0 0 0 0 1 1 0 0 1 1 0 0 1 0 1 1 1 1 1 0 5 5 D E D E 0 1 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 0 鄰接串列 : List[] List[] E List[] E List[] D E List[D] E List[E] D List[] List[] D List[] List[] E List[D] E List[E]

2. 答 : D E D E 0 1 4 3 1 0 4 0 2 5 2 0 2 3 5 2 0 5 5 D E D E 0 3 5 5 0 1 0 4 3 0 2 List[] List[] List[] List[] List[D] 1 4 E 3 1 4 D 2 E 5 2 E 2 List[E] 3 5 D 2 List[] List[] List[] List[] List[D] List[E] E 3 5 D 5 1 4 3 E 2

3. 答 : 動作說明佇列 (queue) 已拜訪頂點初始狀態 front rear 拜訪, Enqueue() Dequeue 得, 將所有與相鄰且未被拜訪的頂點一一拜訪且 Enqueue,(,),, Dequeue 得, 將所有與相鄰且未被拜訪的頂點一一拜訪且 Enqueue,(D,E) D E,,,D,E Dequeue 得, 將所有與相鄰且未被拜訪的頂點一一拜訪且 Enqueue,(F,G) D E F G,,,D,E, F,G Dequeue 得 D, 將所有與 D 相鄰且未被拜訪的頂點一一拜訪且 Enqueue,(H) E F G H,,,D,E,F G,H Dequeue 得 E, 將所有與 E 相鄰且未被拜訪的頂點一一拜訪且 Enqueue,( 無 ) F G H,,,D,E,F G,H Dequeue 得 F, 將所有與 F 相鄰且未被拜訪的頂點一一拜訪且 Enqueue,(I) G H I,,,D,E,F G,H,I Dequeue 得 G, 將所有與 G 相鄰且未被拜訪的頂點一一拜訪且 Enqueue,( 無 ) H I,,,D,E,F G,H,I

Dequeue 得 H, 將所有與 H 相鄰且未被拜訪的頂點一一拜訪且 Enqueue,( 無 ) I,,,D,E,F G,H,I Dequeue 得 I, 將所有與 I 相鄰且未被拜訪的頂點一一拜訪且 Enqueue,( 無 ),,,D,E,F G,H,I 佇列已空, 停止 4. 答 : 動作說明堆疊 ( stack ) 已拜訪頂點初始狀態 top 將起點推入堆疊拜訪, 將所有與相鄰且未被拜訪的頂點一一推入堆疊 Push(,) Pop 得, 拜訪, 將所有與相鄰且未被拜訪的頂點一一 Push,(E,F,G) Pop 得 G, 拜訪 G, 將所有與 G 相鄰且未被拜訪的頂點一一 Push,(I) Pop 得 I, 拜訪 I, 將所有與 I 相鄰且未被拜訪的頂點一一 Push,(F) Pop 得 F, 拜訪 F, 將所有與 F 相鄰且未被拜訪的頂點一一 Push,( 無 ) G F E I F E F F E F E,,,G,,G,I,,G,I,F

Pop 得 F, F 已拜訪過 E,,G, I, F Pop 得 E, 拜訪 E, 將所有與 E 相鄰且未被拜訪的頂點一一 Push,() Pop 得, 拜訪, 將所有與相鄰且未被拜訪的頂點一一 Push,(D) Pop 得 D, 拜訪 D, 將所有與 D 相鄰且未被拜訪的頂點一一 Push,(H) Pop 得 H, 拜訪 H, 將所有與 H 相鄰且未被拜訪的頂點一一 Push,( 無 ) Pop 得, 已被拜訪, 堆疊已空, 停止 D H,,G, I, F, E,,G, I, F, E,,G, I, F, E,D,,G, I, F, E,D,H,,G, I, F, E,D,H 5. 答 : 1 2 3 D 3 F 2 E 6. 答 : 2 3 1 3 D F 2 E

7. 答 : D E F G 進階練習題 1. 答 : 不一定是唯一的當有多個邊加權相同而且任選一邊加入都不會構成環路時, 任選一邊均可, 但可能因而造成不同的最少花費展開樹例如下圖, 邊 (,) 和 (,D) 邊長均為 2, 選擇任一個都是正確的, 但會造成兩棵不同的最少花費展開樹 3 6 1 D 2 2 圖形 G 3 3 1 D 1 D 2 2 最少花費展開樹 1 最少花費展開樹 2 2. 答 : Decided vertices V1 V2 V3 V4 V5 V6 V0 4/0 5/0 3/0 /0 /0 /0 V0,V1 4/0 4/3 /0 9/3 11/3 V0,V1,V2 4/3 8/1 9/3 11/3 V0V1V2V3 8/1 6/2 11/3 V0V1V3V2V4 8/1 10/5 V0V1V3V2V4V5 10/5 V0 到 V6 的最短距離為 :10 V0 到 V6 的最短路徑為 :V6 <- V5 <- V2 <-V3<- V0, 亦即 V0 -> V3 -> V2 ->

V5->V6 V0 至其餘各點以此類推 3. 答 : 先算出每個頂點的最早時間和最晚時間頂點 D E F G 最早時間 0 3 6 10 7 12 16 最晚時間 0 8 6 10 10 12 16 因此到達頂點 G 的最早時間為 16 再算出每個工作的最早時間和最晚時間工作 D E D D DF DG EG FG 最早時間 0 0 0 3 3 6 10 10 7 12 最晚時間 5 0 5 6 7 6 10 13 10 12 最早時間和最晚時間相等的, 即為關鍵路徑上的邊因此關鍵路徑為 : -> -> D -> F -> G n 4. 答 :(D) M ( i, j) /2 n i= 1 j = 1 5. 答 :(D) 程式題 1. 答 : #include <stdio.h> #include <stdlib.h> #define MX_ITEM 20 #define MX_V 20 /* 最多頂點數目 */

void FS(); void Visit(); int Enqueue(); int Dequeue(); int IsEmpty(); char Find_dj(); void ReaddjMatrix(); typedef struct tagqueue int item[mx_item]; int front; int rear; QUEUE; QUEUE q; int RealV; int ol; int Visited[MX_V]; int [MX_V][MX_V]; void main(void) int V0; ReaddjMatrix(); printf(" 請輸入起點 : "); scanf("%d",&v0); FS(V0); void ReaddjMatrix(void) int i,j; FILE *fin; if ((fin=fopen("fs.dat","r")) == NULL ) printf("fs.dat Not Found!\n"); exit(1); fscanf(fin,"%d",&realv); if (RealV>MX_V)

RealV = MX_V; for ( i=0 ; i<realv; i++) for (j=0; j<realv; j++) fscanf(fin,"%d",&[i][j]); fclose(fin); void FS (int V0) int Vx,Vy; Visit(V0); Enqueue(V0); while(!isempty()) Dequeue(&Vx); Vy=Find_dj(Vx,1); while(vy!=-1) Visit(Vy); Enqueue(Vy); Vy=Find_dj(Vx,0); void Visit(int Vx) Visited[Vx]=1; printf("v%2d\n",vx); int Enqueue(int Vx) if ((q.rear+1)%mx_item==q.front) return(0); q.rear=(q.rear+1)%mx_item; q.item[q.rear]=vx; return(1); int Dequeue(int *Vx)

if(isempty()) return(0); q.front=((q.front+1)%mx_item); *Vx=q.item[q.front]; return(1); int IsEmpty() if(q.front == q.rear) return (1); return (0); char Find_dj(int Vx,char first) if (first) ol=0; ol++; while(ol < RealV) if ([Vx][ol]==0 Visited[ol]) ol++; return (ol); return (-1); FS.dat 的內容 9 0 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 1 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 1

0 0 1 0 0 1 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 2 答 : #include <stdio.h> #include <stdlib.h> #define MX_ITEM 20 #define MX_V 20 /* 最多頂點數目 */ typedef struct tagstk int item[mx_item]; /* 資料欄位 */ int top; STK; STK S; void DFS(); void Visit(); char Find_dj(); int PUSH(),IsFull(),POP(),IsEmpty(); void ReaddjMatrix(); int RealV; int ol; int Visited[MX_V]; int [MX_V][MX_V];

void main(void) int V0; ReaddjMatrix(); printf(" 請輸入起點 :"); scanf("%d",&v0); DFS(V0); void ReaddjMatrix(void) int i,j; FILE *fin; if ((fin=fopen("dfs.dat","r")) == NULL ) printf("dfs.dat Not Found!\n"); exit(1); fscanf(fin,"%d",&realv); if (RealV>MX_V) RealV = MX_V; for ( i=0 ; i<realv; i++) for (j=0; j<realv; j++) fscanf(fin,"%d",&[i][j]); fclose(fin); void DFS(int V0) int Vx,Vy; PUSH (V0); while(!isempty(&s)) POP (&Vx); if(!visited[vx]) Visit(Vx); Vy=Find_dj(Vx,1); while(vy!=-1) PUSH(Vy); Vy=Find_dj(Vx,0);

void Visit(int Vx) Visited[Vx]=1; printf("v%2d\n",vx); char Find_dj(int Vx,char first) if (first) ol=0; ol++; while(ol < RealV) if ([Vx][ol]==0 Visited[ol]) ol++; return (ol); return(-1); int PUSH(int X) if(isfull(&s)) return(0); S.top=S.top+1; S.item[S.top]=X; return(1); int IsFull(STK *s) if (s->top == (MX_ITEM-1)) return(1);

return(0); int POP(int *X) if(isempty(&s)) return (0); *X=S.item[S.top]; S.top--; return(1); int IsEmpty(STK *s) if(s->top == -1) return(1); return(0); DFS.dat 的內容 9 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 1 0 0 1 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0

3 答 : #include <stdio.h> #include <stdlib.h> #define MX_ITEM 20 #define MX_V 20 /* 最多頂點數目 */ void FS(int); void Visit(int); int Enqueue(); int Dequeue(); int IsEmpty(); char Find_dj(); void ReaddjList(); void InsertNode(int,int); typedef struct tagqueue int item[mx_item]; int front; int rear; QUEUE; QUEUE q; int RealV; int Visited[MX_V]; typedef struct tagnode int data; struct tagnode *next; NODE; NODE [MX_V]; NODE *ol; void main(void) int V0; ReaddjList();

printf(" 請輸入起點 : "); scanf("%d",&v0); FS(V0); void InsertNode(int Row,int ol) NODE *p,*newnode; for( p=&[row]; (p->next!=null)&&(p->data<ol); p=p->next); if ((NewNode=(NODE *)malloc(sizeof(node))) ==NULL) return; NewNode->data=ol; NewNode->next=p->next; p->next = NewNode; void ReaddjList(void) int i,j,indata; FILE *fin; if ((fin=fopen("fs.dat","r")) == NULL ) printf("fs.dat Not Found!\n"); exit(1); fscanf(fin,"%d",&realv); if (RealV>MX_V) RealV = MX_V; for ( i=0 ; i<realv; i++) [i].next = NULL; for (j=0; j<realv; j++) fscanf(fin,"%d",&indata); if (InData==1) InsertNode(i,j); fclose(fin); void FS (int V0)

int Vx,Vy; Visit(V0); Enqueue(V0); while(!isempty()) Dequeue(&Vx); Vy=Find_dj(Vx,1); while(vy!=-1) Visit(Vy); Enqueue(Vy); Vy=Find_dj(Vx,0); void Visit(int Vx) Visited[Vx]=1; printf("v%2d\n",vx); int Enqueue(int Vx) if ((q.rear+1)%mx_item==q.front) return(0); q.rear=(q.rear+1)%mx_item; q.item[q.rear]=vx; return(1); int Dequeue(int *Vx) if(isempty()) return(0); q.front=((q.front+1)%mx_item); *Vx=q.item[q.front]; return(1);

int IsEmpty() if(q.front == q.rear) return (1); return (0); char Find_dj(int Vx,char first) if (first) ol=[vx].next; ol=ol->next; while(ol!= NULL) if (Visited[ol->data]) ol=ol->next; return (ol->data); return (-1); 4 答 : #include <stdio.h> #include <stdlib.h> #include <conio.h> #define MX_ITEM 20 #define MX_V 20 /* 最多頂點數目 */ void FS(); void ddedge(int,int); void Visit(); int Enqueue(); int Dequeue(); int IsEmpty(); char Find_dj();

void ReaddjMatrix(); typedef struct tagqueue int item[mx_item]; int front; int rear; QUEUE; QUEUE q; int RealV; int ol; int Visited[MX_V]; int [MX_V][MX_V]; void main(void) int V0; ReaddjMatrix(); printf(" 請輸入起點 : "); scanf("%d",&v0); FS(V0); getch(); void ReaddjMatrix(void) int i,j; FILE *fin; if ((fin=fopen("fs.dat","r")) == NULL ) printf("fs.dat Not Found!\n"); exit(1); fscanf(fin,"%d",&realv); if (RealV>MX_V) RealV = MX_V; for ( i=0 ; i<realv; i++) for (j=0; j<realv; j++) fscanf(fin,"%d",&[i][j]); fclose(fin);

void FS (int V0) int Vx,Vy; Visit(V0); Enqueue(V0); while(!isempty()) Dequeue(&Vx); Vy=Find_dj(Vx,1); while(vy!=-1) Visit(Vy); ddedge(vx,vy); Enqueue(Vy); Vy=Find_dj(Vx,0); void ddedge(int Vx,int Vy) printf("dd Edge (V%2d,V%2d)\n",Vx,Vy); void Visit(int Vx) Visited[Vx]=1; printf("v%2d\n",vx); int Enqueue(int Vx) if ((q.rear+1)%mx_item==q.front) return(0); q.rear=(q.rear+1)%mx_item; q.item[q.rear]=vx; return(1);

int Dequeue(int *Vx) if(isempty()) return(0); q.front=((q.front+1)%mx_item); *Vx=q.item[q.front]; return(1); int IsEmpty() if(q.front == q.rear) return (1); return (0); char Find_dj(int Vx,char first) if (first) ol=0; ol++; while(ol < RealV) if ([Vx][ol]==0 Visited[ol]) ol++; return (ol); return (-1);

5. 答 : #include <stdio.h> #include <stdlib.h> #define MX_ITEM 20 #define MX_V 20 /* 最多頂點數目 */ typedef struct tagstk int item[mx_item]; /* 資料欄位 */ int top; STK; STK S; void DFS(); void ddedge(int,int); void Visit(); char Find_dj(); int PUSH(),IsFull(),POP(),IsEmpty(); void ReaddjMatrix(); int RealV; int ol; int Visited[MX_V]; int [MX_V][MX_V]; void main(void) int V0; ReaddjMatrix(); printf(" 請輸入起點 :"); scanf("%d",&v0); DFS(V0); void ReaddjMatrix(void) int i,j; FILE *fin; if ((fin=fopen("dfs.dat","r")) == NULL )

printf("dfs.dat Not Found!\n"); exit(1); fscanf(fin,"%d",&realv); if (RealV>MX_V) RealV = MX_V; for ( i=0 ; i<realv; i++) for (j=0; j<realv; j++) fscanf(fin,"%d",&[i][j]); fclose(fin); void DFS(int Vs) int Vx,Tempol; Visit(Vs); Vx=Find_dj(Vs,1); while(vx!=-1) Tempol=ol; ddedge(vs,vx); DFS(Vx); ol=tempol; Vx=Find_dj(Vs,0); void ddedge(int Vx,int Vy) printf("dd Edge (V%2d,V%2d)\n",Vx,Vy); void Visit(int Vx) Visited[Vx]=1; printf("v%2d\n",vx); char Find_dj(int Vx,char first)

if (first) ol=0; ol++; while(ol < RealV) if ([Vx][ol]==0 Visited[ol]) ol++; return (ol); return(-1); int PUSH(int X) if(isfull(&s)) return(0); S.top=S.top+1; S.item[S.top]=X; return(1); int IsFull(STK *s) if (s->top == (MX_ITEM-1)) return(1); return(0); int POP(int *X) if(isempty(&s)) return (0); *X=S.item[S.top]; S.top--; return(1);

int IsEmpty(STK *s) if(s->top == -1) return(1); return(0); 6. 答 : #define MX_V 20 /* 最多頂點數目 */ int RealV; typedef struct tagnode int data; struct tagnode *next; NODE; NODE [MX_V]; void InsertNode(int Row,int ol) NODE *p,*newnode; for( p=&[row]; (p->next!=null)&&(p->data<ol); p=p->next); if ((NewNode=(NODE *)malloc(sizeof(node))) ==NULL) return; NewNode->data=ol; NewNode->next=p->next; p->next = NewNode; void ReaddjList(void) int i,j,indata; FILE *fin; if ((fin=fopen("fs.dat","r")) == NULL ) printf("fs.dat Not Found!\n");

exit(1); fscanf(fin,"%d",&realv); if (RealV>MX_V) RealV = MX_V; for ( i=0 ; i<realv; i++) [i].next=null; for (j=0; j<realv; j++) fscanf(fin,"%d",&indata); if (InData==1) InsertNode(i,j); fclose(fin); 7. 答 : #include <stdio.h> #include <stdlib.h> #define MX_V 20 int Real_V; int OST[MX_V][MX_V]; int [MX_V][MX_V],P[MX_V][MX_V]; void Floyd(void); void SearchPath(); void ReadWeightedM(void); // Read Weighted djacency Matrix from file Floyd.dat void main(void) ReadWeightedM(); Floyd(); SearchPath(P);

void ReadWeightedM(void) int i,j; FILE *fin; if ((fin=fopen("floyd.dat","r")) == NULL) printf("floyd.dat Not Found!"); exit(1); fscanf(fin,"%d",&real_v); for (i=0; i<real_v; i++) for (j=0; j<real_v;j++) fscanf(fin,"%d",&ost[i][j]); fclose(fin); void Floyd(void) int i,j,k; for(i=0;i <Real_V;i++) for(j=0;j < Real_V;j++) [i][j]=ost[i][j]; P[i][j]=j; for(k=0;k < Real_V;k++) for(i=0;i < Real_V;i++) for(j=0;j < Real_V;j++) if([i][j] > [i][k]+[k][j]) [i][j]=[i][k]+[k][j]; P[i][j]=P[i][k]; void SearchPath(int P[][MX_V])

int i,j,row; for(i=0;i < Real_V;i++) for(j=0;j < Real_V;j++) printf("shortest Path from V%d to V%d cost is:%d\n",i,j,[i][j]); printf("shortest path is:\n from v%d",i); row=p[i][j]; while(row!= j) printf(" to V%d",row); row=p[row][j]; printf(" to V%d\n",row);