1999年C试題精解

试题3（1999年试题5）

   阅读下列程序说明和C代码，将应填入（n）处的字句写在答卷的对应栏内。

[程序说明]

   本程序实现两个多项式像乘。多项式用链表表示，链表上的各表元按多项式的幂指数降序链接。例如：

[程序]

#include <stdio.h>
#include <malloc.h>
typedef struct elem{int index;double coef;struct elem *next
}POLYNODE;
void write(POLYNODE *g)
{ POLYNODE *p=g;
while(p){ printf("%8.4f",p->coef);
if(p->index) printf("*^%d",p->index);
if(p->next && p->next->coef>0) printf("+");
p = p->next;
}
printf("\n\n");
}
main()
{ POLYNODE *f,*g,*s,*inpoly(),*polymul();
f=inpoly();g=inpoly();s=polymul(f,g);write();
}
POLYNODE *reverse(POLYNODE *g)
{ POLYNODE *u=NULL,*v=g,*w;
while(v){ w=v->next;v->next=u;u=v;v=w;}
return u;
}
POLYNODE *polymul(POLYNODE *f, POLYNODE *g)
{ POLYNODE *fp,*gp,*tail,*p=NULL,*q;
int i,maxindex; double temp;
maxindex = f->index+g->index; g=reverse(g);
for(i=maxindex;i>=0;i--){
fp=f;gp=s;
while(fp!=NULL &&fp->index>i) fp = fp->next;
while(gp!=NULL && gp->index<i-fp->index) gp = gp->next;
temp = 0.0;
while(fp && gp)
if(fp->index + gp->index ==i){
temp +=fp->coef*gp->coef; fp=fp->next; gp=gp->next;
else if( (1) ) fp=fp->next;
else gp=gp->next;
if(temp!=0.0){
q=( POLYNODE*)malloc(sizeof(POLYNODE));
q->index=i; q-coef=temp; q-next=NULL;
if( (2) ) p=q;
else (3) ;
tail =q;
}
}
g=reverse(g);
return p;
}
POLYNODE *inpoly()
{ POLYNODE *u,*v,*h=NULL,*p;
int index; double coef;
printf("Input index(<0 for finish)"); scanf("%d",&index);
while(index >=0){
printf("input coef"); scanf("%lf",&coef);
p=( POLYNODE*)malloc(sizeof(POLYNODE));
p->index=index; p->coef = coef;
v=h;
while(v!=NULL &&index<v->index) { nu=v;v=v->next;}
if(v==NULL || index > v->index)
{
p->next=v; if(v==h) (4) ;else (5) ;}
else v->coef +=coef;
printf("Input index(< 0 for finish)"); scanf("%d",&index);
}
return h;
}

[解析]

   这道试题看起来很麻烦，其实不然，程序中科学地使用3函数，使程序的结构非常清晰。函数inpoly()完成输入一个多项式各项的指数和系数，并建立链表的任务。函数polymul()完成两项式的相乘的任务。现在我们就来分别研究这两个函数。

   先看函数inpoly()，它在输入多项式每一项指数和系数的过程中建立链表。语句"returnu;"完成回送返回值的操作，所以要特别函数中对h的操作。

   一直到语句"p->coef;"是完成一个结点的输入，此后的"v=h"，因为"v=NULL"，所以这以后又有许多关于v是否为NULL的判断，足见v和h的变化对程序功能实现有极大关系。

   接下来是一个循环体，如果仔细理解"index<v->index"这个循环条件的含义，就不难确定这是在"v= =NULL"的时候在中寻找当前输入结点的合适位置，以建成一个指数从大到小的链表形式的多项式。那么"v= =NULL"又代表什么？从程序中看，"v= =NULL"有两种情况：1、第一次输入，链表还没有建立；2、在寻找该结点的合适位置时遍历鲐链表的最后一个结点，即需要插入的结点应该在链表的末尾。

   有了以上的理解，不难确定，以下if-else体中"index>v->index"的含义就是要在当前结点之前插入该结点。而"v->coef +=coef"则是完成在指数相等时的系数相加。仔细研究if-else体中的if部分，不难发现，该部分完成一个结点的插入，或者是在第一个结点输入后的处理。

   先考虑第一次输入的情况，"p->next = v;"使p->next置空。填空（4）显然是处理第一次输入的情况（也包括当前输入结点指数大于链表中任何结点指数，该结点需要插入到链首的情况，读者可自己思考）。我们不管填空（5）的内容，当再次执行到"v=h;"和其后的循环体时，不难发现在（4）中要将当前链表的首指针赋给h，否则这个while循环就不能完成任务。那么（4）的内容显然是"h=p"。权衡上述各种情况，可以确定即使在当前输入结点指数大于链表中任何结点指数的情况下，程序仍能够完成任务。

   基于上述的分析，不难确定填空（5）应完成在链表中或链表尾插入结点的功能。已经有了"p->next =v;"，这里只要填写"u->next=p"就可以完成任务了。

   现在回到函数polymul。首先，程序取两个多项式中最大指数的和为乘积的最大指数，然后调用函数reverse()将链表g反转，使g的各个结点指数从链首到链尾由小到大进行排列。关于函数reverse()的理解，这里就不多说了。

   进入for循环之后的两个while循环让人摸不着头脑，但如果将i=maxindex和gp->index<i-fp->index以及fp->index+gp->index>=i联系起来则不难看出，这是在两个多项式gp和fp中寻找两个结点，这两个结点相乘后的指数（index）先于或大于当前正在处理的指数（当然不会有大于maxindex的，但在程序处理过程中两结点指数和大于当前正在处理指数的机会会有很多）。
   显然，在找到一对指数和先于当前正在处理指数的时候，这是通过指数的相加和系数的相乘来生成一个由q来表示的新结点。这个结点应该插入链表中去，这就是填空（2）和（3）所在的if-else体应该完成的任务了。

   这里的插入操作由一个if-else体和语句"tail=q"来完成。显然，插入时p有空和非空两种可能的状态，如果在（2）填写"p!=NULL"，那么"p=q"的结果是非常危险的，因为这将丢掉以前的运算结果，使我们最后只能悼念到运算结果的最后一项。因此这里只能填写"p==NULL"。

   由此就可以确定（3）处理p!=NULL时的插入操作。由"tail=1"来看，tail永远指向链尾的结点，那么这里应该先将q接到tail后，于是我们确定在（3）中填写"tial->next=q"。

   现在只剩下填空（1）没有解决了。只有在两种情况下才能进入由"while(fp&&gp)"引导的循环：1、"gp->index+fp->index>i"；2、"gp->index+fp->index==i"。这里应该处理这两种情况，但为什么还要用一个if-else体呢？如果考虑gp->index+fp->index==i在进的处理我们可以看到　，fp和gp各自抽后移动了一个结点。fp是按结点指数从大到小连接的，而gp是从小到大连接的，在处理了一次"gp->index+fp->index==i"的情况之后，很容易出现gp->index+fp->index>i或gp->index+fp->index<i的情况。当gp->index+fp->index>i时，为使其趋向gp->index+fp->index == i，应该使fp向下移动一个结点反之使gp向下移动一个结点（为什么这样，请读者自己思考）。有了以上的理解，填空（1）的解答就显得很容易了，即"gp->index+fp->index>i"。

[答案]

（1）fp->index+gp->index>i

（2）p == NULL

（3）tail->next=q;

（4）h=p

（5）u->next =p

试题4（1999年试题6）

   阅读下列程序说明和C代码，将应填入 （n）处的字句写在答卷的对应栏内。

[程序说明]

   本程序从n种不同重量、不同价值的物品中选取一部分物品。要求在不超过限定重量limw的前提下，使被选取的那些物品的总价值较大。这里约定limw不超过n种物品的重量总和,也没有一种物品的重量超过limw，并且各物品的价值都大于0。

   程序中，n种物品被顺序编号为0、1、2、......、n-1。

【程序】

#include <stdio.h>
#define N 100
double limw;
int opts[N]; /* 存储临时最佳的选择方案，当opts[i]为1，物品i在解中 */
struct elem { double weight;
double value;
} a[N]; /* 物品的重量和价值信息 */
int k, n ;
struct { int flg; /* 物品的考虑状态：0：不选，1：将被考虑，2：曾被选中 */
double tw; /* 已达到的总重量 */
double tv; /* 期望的总价值 */
｝twv[N]; /* 当前候选解中各物品的考虑状态，以及候选解的状态 */
main()
{ double maxv, find();
printf("Enter number of matter. "); scanf("%d", &n);
printf("Enter limit of weight. "); scanf("%1f", &limw);
printf("Enter weight and values of matters. ");
for (k = 0; k < n; k++) scanf("%1f%1f", &a[k].weight, &a[k].value);
maxv = find(a,n);
for(k = 0; k < n; k++) if(opts[k]) printf("%4d", k);
printf("\nTotal value = %1f\n", maxv);
}
next(int i , double tw, double tv) /* 将考虑i号物品 */
{ twv[i].flg = 1; twv[i].tw = tw; twv[i].tv = tv; }
look(int i, int *f, double *tw, double *tv) / * 取i 号物品在解中的状态信息 * /
{ *f = twv[i].flg; *tw = twv[i].tw; *tv = twv[i].tv; }
double find (struct elem *a, int n )
{ int i, k, f;
double maxv, tw, tv, totv = 0.0;
maxv = 0;
for(k=0; k < n; k++) ____(1)____;
next(0, 0.0, totv);
i = 0;
while(i >= 0) {
look(i, &f, &tw, &tv);
switch (f) {
case 1: twv[i].flg++; /* 先考虑被选中 */
if(____(2)____ <= limw) /* 选中可行吗？ */
if(i < n-1) { /* 后面还有物品吗？ */
next(____(3)____); /* 置i+1物品的状态 */
i++;
}
else if (tv > maxv) { /* 是一个更好的候选解吗？ */
maxv = tv;
for(k = 0; k < n; k++)
opts[k] = twv[k].flg != 0;
}
break;
case 0: i--; break; /* 回退 */
default: /* f == 2 */
twv[i].flg = 0;
if (____(4)____) /* 不选i号物品可行吗？ */
if(i < n-1) { /* 后面还有物品吗？ */
next(____(5)____);
i++;
}
else {
maxv = tv - a[i].value;
for(k = 0; k < n; k++)
opts[k] = twv[k].flg != 0;
i--;
}
break;
}
}
return maxv;
}

[解析]

   仔细阅读程序说明和程序，不能发现试题中需要解答的问题全部集中在函数find( )中。在理解了函数next( )和函数look( )之后，我们开始阅读函数find( )。

   首先，由于后面有关于next( )调用时参数表的填空，应该研究函数next( )的3个参数的含义。阅读的next( )函数体，能够确认：

参数i代表物品编号；

参数tw代表当前已经达到的总重量；

参数tv代表期望的总价值。

   填空（1）之前有"totv=0.0"，之后totv作为函数next( )的一个参数使用。通过研究函数next( )，发现totv的值传给了tw[i].tv，其含义应该是期望的总国。，显然totv不能是0.0，那么（1）应该是对totv的值操作。究竟应该怎样赋值呢？根据说明，我们能够理解期望的价值应该人总价值开始试探，那么作为for循环的循环体，（1）应该主用来计算总价值的。所以我们在这里填写"totv+=a[k].value"。

   现在看下面的程序。填空（2）所在的语句是通过if语句来判断选中某个物品是否可行，这里是考虑选中a[i]是否可行。不可行的条件只有一个，即a[i]的weight与当前已达到的总之和超过了重量限制limw。通过对函数look( )的解读，可以知道程序中tw即表示当前已经达到的总重量，那么结合后面的"v<=limw"，这里应该填写"tw+a[i].weight"。继续往下阅读程序，包含填空（3）的语句及注释和此前的语句表明这里对函数next( )的调用是在第i个物品已经被选中后，考虑第i+1个物品。

   由于是第i+1个物品，因此这里的第1个参数就是i＋1。第2个参数，因为第i个物品已经被选中，所以已经达到的总重量就应该是"tw+a[i].weight"；第3个参数是期望的总价值，在经过函数next( )和look( )的操作之后　，tv的值即为期望达到的总价值。在没有超过limw的情况下还可以继续选择物品，这表明该期望值是合理的，所以应该维持原来的数值，即tv。所以（3）的正确答案为"i+1, tw+a[i].weight,tv"。

   由"if(tv>maxv)"引导的if条件句是处理这样一种情况，即选中当前物品会使总重量超过limw，从而在不选择物品i的情况下得到一个解。由此不难确定，maxv记录了程序处理过程中达到的最大价值的数值。有必要说明一下，因为得到的解的总价值是各不相同的，所以最大的值就被记录下来，这里被选中物品的编号也就被记录在数组ops[ ]中作为最佳方案。

   现在看CASE结构的default分支。在这里，填空（4）所在的if语句判断不选物品i是否可行。若选中物品i也不能够使总价值达到期望总价值，就可以不选物品，那么（4）的解答可以这样构造，即"tv-a[i].value>maxv"。同时，在这种情况下应该修改期望的总价值，上述情况表明当前期望的价值是不合理的。

   填空（5）要求解答的是在不选物品i的情况下考虑下一个(i+1)物品。参照填空（3）的解答，第1个参数就是i＋1。那么第2个参数呢，这里决定不选物品i了，已经达到的总重量中就不能将物品i的重量包括进来，仍旧是tw。第3个参数比较麻烦，物品i未选中，而且即使加上i的价值，当前最大价值仍旧不能够达到期望价值，就只好考虑修改期望价值，合理的修改方式是tv-a[i].value。

   另外，由于函数next( )和look( )使变量tw和twv[i].tw、tv和twv[i].tv具有等值关系，那么在解题时凡是使用的，都可以替换为twv[i].twltwv[i].tv。

[答案]

（１） totv+=a[k].value

（２） tw+a[i].weight

（３） i+1,tw+a[i].weight,tv

（４） tv-a[i].value>maxv

（５） i+1,tw,tv-a[i].value

(注：解答中的tw可答为twv[i].tw，tv可答为twv[i].tv).