1997年C试題精解
试题7（1997年试题6）
阅读以下程序说明和C程序，将应填入_(n)_处的字句，写在答卷的对应栏内。
【程序说明】
某系统由N个部件组成，这些部件被物理地分成若干个分离的部件组。同一组内的两件部件I和J，它们或直接相连，或间接相连（部件I和部件J间接相连是指在这两件部件之间有一个部件相连序列，其中部件I和J分别与这相连序列中的某个部件直接相连）。系统的N个部件被统一编号为0，1，…，N-1。本程序输入所有直接相连的部件号对，分别求出系统各分离部件组中的部件号并输出。
程序根据输入的直接相连的两件部件号，建立N个链表，其中第I个链表的首指针为S[I]，其结点是与部件I直接相连的所有部件号。
程序依次处理各链表。在处理S[I]链表中，用TOP工作链表重新构造S[I]链表，使S[I]链表对应系统中的一个部件组，其中结点按部件号从小到大连接。
【程序】
#INCLUDE
#DEFINE N 100
TYPEEFSTRUCTNODE{
INTDATA;
STRUCTNODE*LINK;
}NODE;
NODE *S[N];
INT I,J,N,T;
NODE *Q,*P,*X,*Y,*TOP;
MAIN()
{PRINTF("ENTERNUMBEROFPARTS.");
SCANF("%D",&N);
FOR(I=0;IDATA=J;P->LINK=S[I];S[I]=P;
P=(NODE*)MALLOC(SIZEOF(NODE));
P->DATA=I;P->LINK=S[J];S[J];=P;
}
FOR(I=0;IDATA]!=NULL)
{/将J链表也移入工作链表*/
FOR(P=S[J];P->LINK！=NULL;P=P->LINK);
P->LINK=TOP;TOP=S[J];__(3)__;
}
/*在重新生成的第I链表中寻找当前结点的插入点*/
FOR(Y=S[I];__(4)__;X=Y,Y=Y->LINK);
IF(Y!=NULL&&Y->DATA==Q->DATA)
FREE(Q);/*因重新生成的第I链表已有当前结点，当前结点删除*/
ELSE{/*当前结点插入重新生成的I链表*/
__(5)__；
IF(Y==S[I])S[I]=Q;
ELSEX->LINK=Q;
}
}
FOR(I=0;IDATA);
Q=P->LINK;FREE(P);P=Q;
}
PRINTF("\N");
}
}
[解析]
本题考查的知识要点是链表操作。链表的基本操作是简单的，仔细阅读试题说明，结合程序中的说明文字，不难发现本题的难度主要在最后一段中，"在处理链表s[i]
表中，用top工作链表重新构造s[i] 表，使s[i] 链表对应系统中的一个部件组，其中结点按部件号从小到大连结。"
阅读试题所提供的程序，我们能够从输入部分的构造链表算法中推知，这里建立的是循环链表，即链表的尾结点的指针指向链表头。结合程序说明，5个需要回答的问题集中在顺序处理各个链表部分，所以这里的关键是要结合程序理解程序中使用的算法。
仔细推敲程序，可以断定处理各链表的过程应该为：对由s[i]所指向链表，将该表移到由指针top所指的工作链表。对top链表的各结点进行如下处理：从top链表上取出一个结点，根据该结点所指出的相连部件，将由s[j]所指向的链表也移入top链中，并将取出的结点按部件递增顺序重新构造由s[i]
所指向的链表，如此重复，直到top链表为NULL。这样由s[i]
所指向链表的重新构造就结束了。所有链表处理完后，重新构造好的各非空链表，与系统中的各部件组一一对应。
仔细阅读填空（1）所在的语句，还要忽视填空（1）前是"，"，而不是"；"，可以推知，这里应该是将s[i]
置空，因为该循环的任务是重新构造链表。结合心目输入部分的链表构造及以后对由top所指向的链表的使用，不难推知由top所指向的链表也是循环链表，结合上下文，填空（2）的答案应该是"
top=top->link "，实现链表尾结点的指针指向链表头的操作。
考查填空（3）及其前面的两条语句，它们所承担的任务与"
top=s[i] "和填空（1）所承担的任务应该是相同的，由彼及此，得出（3）的应该是很容易的。
填空（4）所在的语句组完成在重新链表中寻找当前结点的插入点的任务。根据试题说明，链表是按部件号递增顺序构成的，结合基本的链表遍历知识，（4）的答案应该是"y!=NULL
&& y->data<q->data
"。根据填空所在语句及程序说明，结合链表插入操作的基本流程和程序对链表构造的要求，答案应该是"q->link=y"。
[答案]
（1）S[i]
= NULL
（2）Top
= top->link
（3）S[j]
= NULL
（4）y
!=NULL && y->data <q->data 或y
&& y->data <q->data
（5）q->link
= y
试题8（1997年试题8）
阅读以下程序说明和C程序，将应填入_(N)_处的字句，写在答卷的对应栏内。
【程序说明】
一个相连的区域被不规则地分割成N个不同的小区域；每个小区域与若干其它小区域相邻接。现用CN种不同颜色为该区域着色，要求每个小区域着同一种颜色，相邻小区域着不同颜色。
设小区域被顺序编号为0，1，…，N-1。每个小区域与其它小区域的邻接关系用两维数组BORDERING表示，元素BORDERING[I][J]表示I号小区域与J号小区域之间的邻接关系：
BORDERING[I][J]=0 J小区域与I小区域不邻接
BORDERING[I][J]=1 J小区域与I小区域相邻接
程序中，把计算结果存入于两维数组COLORED中，颜色编号为0,1,…,CN-1,元素COLORED[COLER][J]的含义是
COLORED[COLOR][J]=0 J小区域不用颜色COLOR着色
COLORED[COLOR][J]=1 J小区域用颜色COLOR着色
函数COLORCOUNTRY(BORDERING,COLORED,N,CN)根据所给的小区域邻接关系数组BORDERING、小区域个数N、颜色数CN，将找到的着色方案记录在数组COLORED中。函数采用试探法找解。首先从第一个小区域着第一种颜色开始顺序为各小区域找着色方案。对某个小区域，当为它找到一种未被它的相邻小区域着色的颜色时，就用该颜色对该小区域着色，并准备处理下一个小区域。当不能为某个小区域找到一个未被它的相邻小区域着色的颜色时，就回溯。如最终为全部小区域找到着色方案，函数返回1；否则，函数返回0。
程序假定小区域个数不超过20，颜色数为4。
【程序】
#INCLUDE
#DEFINE N 20
#DEFINE CN 4
INT
COLORCOUNTRY(INTBORDERING[][N],INTCOLORED[][N],INTN,INTCN){INTCOLOR,USED,I,C;
FOR(COLOR=0;COLORN;I++)COLORED[COLOR][I]=0;
C=0;/*从第1个小区域开始*/
COLOR=0;/*从着第1种颜色开始试控*/
WHILE(CC;I++)
IF(__(2)__)USED=1;
IF(!USED)BREAK;/*当前颜色未被相邻小区域着色*/
COLOR++
}
IF(!USED)
{/*找到一种可用颜色，用此色着色，并准备处理下一个小区域*/
__(3)__=1;COLOR=0;
}ELSE{/*未找到一种可用颜色，回溯*/
C--;IF(C<0)RETURN0;/*发现没有解的情况*/FOR(COLOR=0;__(4)__;COLOR++);__(5)__=0}}RETURN1;}PRINT(INTCOLORED[][N],INTN,INTCN)/*输出结果*/{CHAR*COLORT[]={"RED","BLUE","GREEN","YELLOW"};INTCOLOR,I;FOR(COLOR=0;COLORN;I++)
IF(COLORED[COLOR][I])PRINTF("\T%D",I);
PRINTF("\N");
}
}
INTCOLORED[CN][N],BORDERING[N][N];
MAIN()
{INTC,I,J,N;
PRINTF("ENTERNUMBEROFAREAS.");SCANF("%D",&N);
PRINTF("ENTERBORDERING:\N");
FOR(I=0;IN;J++)BORDERING[I][J]=0;
FOR(I=0;I0TONEXT).\N",I};
SCANF("&D",&J);
WHILE(J>=0)
{IF(I!=J)BORDERING[I][J]=BORDERING[J][I]=1;
SCANF("%D",&J);
}
}
IF(COLORCOUNTRY(BORDERING,COLORED,N,CN))
PRINT(COLORED,N,CN);
ELSEPRINTF("NOSOLUTION.\N");
}
[解析]
该题考查的仍然是回溯法的问题。试题说明非常详细，对算法的注释也非常详尽。关键是我们是否能够将试题说明和程序结合起来读，将试题说明中的每一部分与程序中的语句段建立联系。程序中有许多注释，这使试题说明与程序的联系非常明显。
需要解答的问题全部集中在函colorcountry(
) 数中，我们就集中精力解读这个函数。首先结合程序注释明确各个变量的含义，这是对以后程序理解的基础。然后从宏观上把握函数 结构，不难发现，函数体的主体部分是一个while循环。循环由一个while循环和if-else体构成。结合试题说明与程序注释，可以推知内层while循环对每一个小区进行着色，if-else体将处理找到合适颜色和找到合适颜色的情况，把握了程序的结构，我们甚至不用对整修程序有透彻的理解，只要结合变量含义、试题说明与程序注释就可以解答问题。
首先，我们由填空（1）后面的注释可以推知这里应该是color与cn的比较，以控制循环的结束。既然是顺序对每种颜色作试探，则在每次执行到这里时，应该递加。因为循环体中已经实现了color的递加，所以（1）的解答就可以简单地构造为"color<cn"。填空（2）所在循环完成的任务是检查当前颜色是否已被某相邻小区域着色，结合循环中两个变化的变量i、c以及对试题说明的理解，当前颜色已被某相邻小区域着色，应该表示为bordering[c][i]不为0，colored[color][i]不为0，所以填空（2）的答案就可以表示为"bordering[c][i]
&& colored[color][i]"。
填空（3）、（4）、（5）集中在处理找到或没有找到的体中。找到了如何处理？首先要在colored[]中登记，即colored[colored][c]将置1。如果单从这一个处理来看，这样的答案也算是正确的结合注释中"准备处理下一个小区域"的语句，通观全局，准备工作自然不能在处理没有找到合适颜色时进行，那么我们在这里实现对c的递加，即将答案改为colored[colored][c++]，注意c++与++c的区别，体会在这里这样填写的理由。
显然，填空（4）和（5）完成没有找到合适颜色时的处理。结合心上着色的算法推算回溯的算法，不难推出回溯的基本算法，即回溯过程中不但要回到前一步，还要能将当前已设置的信息恢复到它原告的状态，然后，以便可以根据前一步的状态继续试探其他方案。我们知道，数组colored中已经记录了将当前颜色要重新返回到上一个区域的颜色值。程序中（4）的解答为"colored[colored][c]"。回溯的过程除了恢复状态外，还要取消原有的选择，继续进行选择，得到下一个可能的值。因此填空（5）的内容应该为"colored[colored++][c]"。通过该语句，就未完成了回溯过程，可以继续篁，向前继续试探。
我们可以看到，本题的5个问题中只有（4）和（5）才涉及到回溯法的构造，其余的3个问题都是可以通过对试题说明和程序结构、功能的把握来解答的，这也从另一个方面说明了在钥解题时仔细阅读试题说明和从结构上把握程序的重要性。
[答案]
（1）color
< cn 或 color <
4
（2）bordering[c][i]
&& colored[color][i] 或
bordering[c][i] == 1&&colored[color][i]==1
或bordering[c][i] *
colored[color][i] == 1 其中bordering[c][i]可写成bordering
[i][c]
（3）colored[color][c++]
（4）colored[color][c]=0
或！colored[color][c]
或
colored[color] != 1
（5）colored[color++][c]
|
