2007年11月软件设计师模拟试题（3）下午试卷

 
●试题五
阅读下列程序说明和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下半年计算机软件水平考试模拟试题汇总

希望与其他软考考生进行交流？点击进入软考论坛>>>

进入考试吧博客记录下自己的备考历程吧

更多信息请访问：考试吧软件水平考试栏目