●試題五
閱讀下列程序說明和C代碼，將應填入(n)處的字句寫在答題紙的對應欄內。
【程序5說明】
著名的四色定理指出任何平面區域圖均可用四種顏色著色，使相鄰區域著不同的顏色。本程序對給定的區域圖找出所有可能的不超過四種顏色的著色方案。
程序中用1~4表示四種顏色。要著色的N個區域用0~N-1編號，區域相鄰關系用adj［］［］矩陣表示，矩陣的i行j列的元素為1，表示區域i與區域j相鄰；矩陣的i行j列的元素為0，表示區域i與區域j不相鄰。數組color［］用來存儲著色結果，color［i］的值為區域i所著顏色。
【程序5】
#include<stdio.h>
#define N 10
void output(int color［］)/*輸出一種著色方案*/
{int i;
for(i=0;i<N;i++)
printf("%4d"，color［i］);
printf("＼n");
}
int back(int*ip,int color［］)/*回溯*/
{int c=4;
while(c==4){
if(*ip<=0)return 0;
--(*ip);
c=  (1)  ;
color［*ip］=-1;
}
return c;
}
/*檢查區域i，對c種顏色的可用性*/
int color0k(int i,int c,int［］［N］,int color［］}
{int j;
for(j=0;j<i;j++)
if(  (2)  )
return 0;
return 1;
}
/*為區域i選一種可著的顏色*/
int select(int i,int c,int adj［］［N］,int color［］)
{int k;
for(k=c;k<=4;k++)
if(colorOK(  (3)  ))
return k;
return 0;
}
int coloring(int adj［］［N］)/*尋找各種著色方案*/
{int color［N］,i,c,cnt;
for(i=0;i<N;i++)color［i］=-1;
i=c=0;cnt=0;
while  (1)  {
if((c=  (4)  )==0){
c=back(&i,color);
if(c==0)return cnt;
}else{  (5)  ;i++;
if(i==N){
output(color);
++cnt;
c=back(&i,color);
}else c=0;
}
}
}
void main()
{int adj［N］［N］=
{{0，1，0，1，1，1，1，1，1，1},
{1，0，1，1，0，1，1，1，1，0},
{0，1，0，1，0，1，1，0，1，1},
{1，1，1，0，1，1，0，0，1，1},
{1，0，0，1，0，1，0，0，0，0},
{1，1，1，1，1，0，1，0，0，1},
{1，1，1，0，0，1，0，0，1，0},
{1，1，0，0，0，0，0，0，1，1},
{1，1，1，1，0，0，1，1，0，1},
{1，0，1，1，0，1，0，1，1，0}
}；
printf("共有%d組解.＼n",coloring(adj));
}

2007下半年計算機軟件水平考試模擬試題匯總

希望與其他軟考考生進行交流？點擊進入軟考論壇>>>

進入考試吧博客記錄下自己的備考歷程吧

更多信息請訪問：考試吧軟件水平考試欄目