试题一（１５分）

　　阅读下列函数说明和Ｃ代码，将应填入其中__(n)__处的字句写在答卷的对应栏内。

【函数1.1说明】

　　设链表结点的类型为

　　　　typedef struct elem{ int val;

                                                  struct elem *next;

                                              }intNode;

　　函数merge(int *a,int *b)是将两个升序链表a和b合并成一个升序链表。

【函数1.1】

    intNode *merge(intNode *a,intNode *b)

    {  intNode *h=a,*p,*q;

       while(b)

       {  for (p=h;p&&p->val<b->val;q=p,p=p->next);

          if (p==h) __(1)__;else __(2)__;

          q=b;b=b->next; __(3)__;

       }

       return h;

    } 

【函数1.2说明】

　　递归函数dec(int a[],int n)判断数组a[]的前n个元素是否是不递增的。不递增返回１，否则返回０。

【函数1.2】

    int dec(int a[],int n)

    {  if (n<=1) __(4)__;

       if (a[0]<a[1]) return 0;

       return __(5)__;

    }

试题二（１８分）

　　阅读下列函数说明和Ｃ代码，将应填入__(n)__处的字句写在答卷的对应栏内。

【函数2.1说明】

　　设长正整数用数组存储，如有k位的长整数m用数组a[]存储：

       m=a[k]*10^k-1a[k-1]*10^K-2+……+a[2]*10¹+a[1]*10⁰

并用a[0]存储长整数m的位数，即a[0]=k。

　　通常，存储长整数数组的每个元素只存储长整数的一位数字。长整数运算时，为了运算方便，产生的中间结果的某位数字可能会大于9。这时，就应调用本函数将它规整，使数组的每个元素只存储长整数的一位数字。规整运算函数formal(int *a)就实现这个特殊要求。

【函数2.1】

    void formal(int *a)

    {  int p;

       for (p=1;p<a[0]||a[p]>10;p++)

       {  if (p>=a[0] __(1)__;

          a[p+1]+=a[p]/10;  a[p]=__(2)__;

       }

       if (p>a[0]) __(3)__;

    }

【函数2.2说明】

　　函数combine(a,b,c)是计算两个整数的组合数。由于计算结果超出long int 的表示范围，故用本题【函数2.1说明】的方法存储计算结果。设整数a和b (a>=b) ，它们的组合c(a,b)=a!/((a-b)!*b!)。计算a和b的组合可采用以下方法：

       a!/(a-b)!/b!

     =a*(a-1)*(a-2)*…*(a-b+1)/b!

     =u₁*u₂*…*u_b/(d₁*d₂*…*d_b)

其中u₁=a，u₂=a-1，…，u_b=a-b+1；d₁=1，d₂=2，…，d_b=b。

　　从而计算a和b的组合c(a,b)，可变成计算上述分式。

　　为计算上述分式，先从u₁，u₂，…，u_b中去掉所有d₁*d₂*…*d_b的因子，得到新的u₁，u₂，…，u_b。然后再将它们相乘。以下函数中调用的外部函数gcd(a,b)是求两整数a和b最大公因子的函数；函数formal()就是本题中的函数2.1。

【函数2.2】

    void combine (int a,int b,int *c)

    {  int i,j,x,k;

       int d[MAXN],u[MAXN];

       for (k=0,i=a;i>=a-b+1;i--) u[++k]=i;

       __(4)__;

       for (I=1;I<=b;I++) d[I]=I; /*将整数1至b顺序存于数组d*/

       for (I=1;I<=u[0];I++) /*从u的各元素中，去掉d中整数的所有因子*/

         if (u[I]!=1)

           for (j=1;j<=b;j++)

             if (__(5)__)

             {  x=gcd(u[I],d[j]);  u[I]/=x;  d[j]/=x;

             }

       c[0]=c[1]=1;  /*长整数c初始化*/

       for (I=1;I<=u[0];I++) /*将u中各整数相乘，存于长整数c*/

         if (u[I]!=1)

         {  for (j=1;j<=c[0];j++)  c[j]=__(6)__;

             formal(c);  /*将存于c中的长整数规整*/

         }

    }

试题三（２１分）

　　阅读下列函数说明和Ｃ代码，将应填入__(n)__处的字句写在答卷的对应栏内。

【程序3说明】

本程序中的函数expr()实现将中缀表达式转换成后缀表达式。设中缀表达式只有加(+)、减(-)、乘(*)和除(/)四则运算符（双目），运算分量只能是变量，变量用英文字母开头英文字母和数字符组成的标识符命名。与平常四则运算的计算规则相一致，即先乘除，后加减，括号内的子表达式优先计算。例如，中缀表达式a*(c3-x2z/y)+u的后缀表达式为ac3x2zy/-*u+

程序给每个运算符和括号设定一个优先级，并引入一个栈和一个存储后缀表达式的工作数组。函数expr()工作时，按自左至右逐个顺序扫描中缀表达式，如当前符号是变量名，就将该变量名直接复制到工作数组；如当前符号是运算符或括号，将当前符号的优先级和栈顶符号的优先级进行比较；若当前符号的优先级高，则当前符号进栈；反之，则进行出栈处理，并将从栈中退出的运算符依次复制到工作数组中，直到栈顶符号的优先级比当前符号的优先级低为止，然后将当前的运算符或左括号进栈。为使子表达式能优先处理，所以给左括号设定较高的优先级，但又为了能正确处理随后的子表达式，在左括号进栈时，它在栈中的优先级作了一定的改变。

初始时，expr()函数预先在栈底设置一个符号‘＃’，其优先级比所有运算符和括号的优先级都低。程序还检查输入表达式的运算符和运算分量的合理性，以及括号是否正确配对。

【程序3】

    #include <stdio.h>

#include <ctype.h>

#include <stdlib.h>

typedef struct node {  /*符号、内部编号、优先级和后继栈元指针*/

                                        char data;  int code;int pri;strujct mode *link;

                                   }NODE;

struct Tb1{/*符号、内部编号、优先级*/

         char data; int ckde ; int  pri;

}opchTb1[]={{‘*’,1,4},{‘/’,2,4},{‘+’,3,2},{‘-‘,4,2},

                    {‘(‘,5,5},{‘)’,6,1},{‘’,7,0},{‘ ‘,-1,0}};

NODE *optop;/*栈顶指针*/

Char num[200],*numtop;/*工作数组和存储指针*/

Char expStr[200];/*存储中缀表达式的字符数组*/

Void push(char x,int c,int p,NODE **topt)/*链接存储栈的进栈函数*/

{NODE q=(NODE*)malloc(sizeof(NODE));

  q->data=x;q->code=c; q->pri=p;     (1)        ;*toppt=q;

 }

int pop(char*op,int *cp,NODE **toppt)/*链接存储栈的出栈函数*/

{NODE q=toppt;

  if (*toppt==NULL) return 1;/*空栈 */

  op=q->data;cp=q->code;          (2)       ;free(q); return 0;

}

int expr(char *pos)

{struct Tb1 *op; char sop; int type ,code,n,m,I,c;

  optop=NULL;numtop=num;n=m=0;c=’ ‘;

  push(‘#’,0,0,&optop);/*预先在栈中置一个0优先级的符号 */

  while (1) {while (c==’ ‘ || c==’ ’) c=*pos++; /*掠过空白符 */

             if (isalpha( c){/*复制变量名到工作数组*/

               *numtop++=’ ‘;

               while(isalpha(c)||isdigit( c)){      (3)     ;c=*pos++;}

                 if (m) return 1;/*运算符个数与运算分量个数不相容 */

                 m=1;/*运算分量比运算符多1 个 */

                 continue;

               }else {/*处理运算符或非法字符 */

                    for (I=0;opchTbl[I].code==-1&&           (4)   ;I++)

                          if (opchTbl[I].code==-1) return 3;/*非法字符 */

                    op=&opchTbl[I];

                    type=opchTbl[I].code; /*得到运算符的内部码 */

                   c=*pos++;  /*C中存储下一个字符*/

        }

          if (type<5) {/*如是运算符 */

            if(m!=1) return 1;/*运算符个数与运算分量个数不相容*/

            m=0;/*运算符与运算分量一样多 */

         }

       if(type==5) n++;/*左括号计数增1*/

       if (type==6){if(n--==0) return 1;/* 圆括号不匹配*/

       if  (      (5)     )/*运算符或括号进栈 */

           if (op->data==’(‘) push (op->code,1,&optop);

           else push(op->data, op->code, op->pri,&optop);

      else {while(optop!=NULL &&op->pri<=optop->pri){

                   pop(      (6)         );

                   if (        (7)        ) {/* 运算符复制到工作数组*/

                        *numtop++=’ ‘; *numtop++=stop;

                  }

              }

if (op->data==’0’)

                  return (n!=0||(m!=1&&numtop>num))?4( *numtop=’’);

            else if(op->data!=’)’)

                 push (op->data,op->code,op->pri,&optop);

            }

        }

}

void main()

{int d;

printf(“请输入表达式  ! ”);gets(expStr);

if ((d=expr(expStr))==0) printf(“后缀表达式为 %s ”,num);

else printf(“表达式句法错！错误类型为%d ”,d);

}

试题四（21分）

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

[程序4说明]

    有一种单人玩的游戏：设有n(2<=n<=200)堆薄片，各堆顺序用0至 n-1编号，极端情况，有的堆可能没有薄片。在游戏过程中，一次移动只能取某堆上的若干张薄片，移到该堆的相邻堆上。如指定

I堆k张 k 移到I-1(I>0)堆，和将k 张薄片移至I+1(I<n-1)堆。所以当有两个堆与 I 堆相邻 时，I堆原先至少有2k 张薄片；只有一个堆与 I 堆相邻 时， I 堆原先至少有k张薄片。

   游戏的目标是对给定的堆数，和各堆上的薄片数，按上述规则移动薄片，最终使 各堆的薄片数相同。为了使移动次数较少些，移动哪一堆薄片，和移多少薄片先作以下估算：

设

c_i:I堆的薄片数(0<=I<n,0<=c_i<=200);

v：每堆 的平均薄片数；

a_i:I堆的相邻堆可以从I堆得到的薄片数。

估算方法如下：

v=c₀+a₁-a₀          a₁=v+a₀-c₀

v=c₁+a₀+a₂-2a₁              a₂=v+2a₁-a₀-c₁

……..                                ……….

V=c_i+a_i-1+a_i+1-2a_I        a_i+1=v+2ai-a_i-1-c_i

这里并不希望准确地求出A₀ 至a_n-1，而是作以下处理：若令  a0 为0，能按上述算式计算出 A₁至 a_n-1。程序找出 a 中的最小值，并让全部a值减去这最小值，使每堆移去的薄片数大于等于0。

实际操作采用以下贪心策略：

（1）每次从第一堆出发顺序搜索每一堆，若发现可从 I堆移走薄片，就完成一次移动。即， I堆的相邻堆从 I堆取走  a_i片薄片。可从I  堆移薄片到相邻堆取于 I堆薄片数：若I 堆是处于两端位置( I=0    I=n-1), 要求 c_i>=a_i ；若 I堆是中间堆，则要求c_i>=2a_i。

（2）因在a_i>0的所有堆中，薄片数最多的堆 在平分过程中被它的相邻堆取走的薄片数也最多。在用策略（1）搜索移动时，当发生没有满足条件（1）的可移走薄片的堆时，采用本策略，让在a_i>0的所有堆中，薄片数最多的堆被它的相邻堆取走它的全部薄片。

[程序4]

#include <stdio.h>

#define N 200

#define M 200

#define  Limit 2000

struct {int id; int k;

}way[Limit];/*存储每次移动的位置和薄片张数 */

int mc=0;/*移动次数 */

int c[N],a[N],n

         Int  init(int *np,int *c,int *a)  /*输入初始数据，估算a_i*/

{int i,n,d,min,v;long sum=ol;

printf(“输入n:”);scanf(“%d”,&n); printf(“输入各堆的落款薄片数（<%d） ”,m);

for(i=0;i<n;i++) sum+=c[i];

if (sum % m)return 0;

v=(int)(sum/n); a[0]=0;a[1]=v-c[0];

for(i=1;i<n-1;i++) a[i+1]=  (1);

for(min=0,i=1;i<n;i++) if (a[i]<min) min=a[i];

for(i=0;i<n;i++) a[i]-=min;

*np=n;return 1;

}

void move (int i,int k,intn,int*c,int*a)

{if (i>0){c[i-1]+=k;c[i]-=k;}

 if(i<n-1){c[i+1]+=k;c[i]-=k;}

 a[i]-=k; way[mc].id=i; way[mc++].k=k;

}

void search(int *c,int *a,int n)

{int i,d,m,pov,moved;

 do {pov=moved=0;

for (i=0;i<n;i++)    /*搜索满足策略（1）的堆*/

 if (   (2)  ) {pov=1

  if ((   (3)  )?(c[i]>=a[i]:c[i]>=2*a[i])){

   move(        (4)         )/*完成一次移动*/

moved=1;break;

}

}

if (pov && !moved) /*找薄片数最多的堆，且被相邻堆全部取走*/

 for(m=0,i=0;i<n;i++)

   if (     (5)   &&    (6)       ) {k=i; m=c[i];}

 if (k>0 && d<n-1)         (7)      ; move(k,m,.n,c,a);

}

}while(mc<limit && pov);

}

void main()

{int i;

 if (init(&n,c,a)==0){printf(“薄片总数不能被平分 ”);return;}

search(c,a,n); printf(“ 序号    移动位置号    各相邻位置得到薄片数 ”);

for(i=0;i<mc;i++)

  printf(“%4d%10d%18d ”,i+1,way[i].id,way[i].k);

printf(“ ”);}      

试题一（１５分）

　　阅读下列函数说明和Ｃ代码，将应填入其中__(n)__处的字句写在答卷的对应栏内。

【函数1.1说明】

　　设链表结点的类型为

　　　　typedef struct elem{ int val;

                                                  struct elem *next;

                                              }intNode;

　　函数merge(int *a,int *b)是将两个升序链表a和b合并成一个升序链表。

【函数1.1】

    intNode *merge(intNode *a,intNode *b)

    {  intNode *h=a,*p,*q;

       while(b)

       {  for (p=h;p&&p->val<b->val;q=p,p=p->next);

          if (p==h) __(1)__;else __(2)__;

          q=b;b=b->next; __(3)__;

       }

       return h;

    } 

【函数1.2说明】

　　递归函数dec(int a[],int n)判断数组a[]的前n个元素是否是不递增的。不递增返回１，否则返回０。

【函数1.2】

    int dec(int a[],int n)

    {  if (n<=1) __(4)__;

       if (a[0]<a[1]) return 0;

       return __(5)__;

    }