2000年度程序员级上午试卷

试题一(15分)
　　阅读下列函数说明和 C 代码，将应填入其中__(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-&gtval&ltb-&gtval; q = p, p = p-&gtnext);
          if (p == h) __(1)__; else __(2)__;
          q = b; b = b-&gtnext; __(3)__;
       }
       return h;
    }  
【函数1.2说明】
　　递归函数 dec(int a[],int n) 判断数组 a[] 的前 n 个元素是否是不递增的。不递增返
回 1 ，否则返回 0 。
【函数1.2】
    int dec(int a[],int n)
    {  if (n <= 1) __(4)__;
       if (a[0] < a[1]) return 0;
       return __(5)__;
    }

试题二(18分)
    阅读下列函数说明和 C 代码，将应填入__(n)__处的字句写在答卷的对应栏内。
【函数2.1说明】
    设长正整数用数组存储，如有 k 位的长整数m用数组 a[] 存储：
       m = a[k]*10k-1a[k-1]*10K-2+……+a[2]*101+a[1]*100
    并用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!
     = u1*u2*…*ub/(d1*d2*…*db)
其中u1 = a，u2 = a-1，…，ub = a-b+1；d1 = 1，d2 =2 ，…，db = b 。
    从而计算 a 和 b 的组合 c(a,b)，可变成计算上述分式。
    为计算上述分式，先从 u1，u2，…，ub 中去掉所有 d1*d2*…*db 的因子，得到新的
u1，u2，…，ub。然后再将它们相乘。以下函数中调用的外部函数 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中的长整数规整*/
         }
    }

试题三(21分)
　　阅读下列函数说明和 C 代码，将应填入__(n)__处的字句写在答卷的对应栏内。
【程序3说明】
    本程序中的函数 expr() 实现将中缀表达式转换成后缀表达式。设中缀表达式只有加
(+)、减(-)、乘(*)和除(/)四则运算符(双目)，运算分量只能是变量，变量用英文字母开
头英文字母和数字符组成的标识符命名。与平常四则运算的计算规则相一致，即先乘除，
后加减，括号内的子表达式优先计算。例如，中缀表达式 a*(c3-x2z/y)+u 的后缀表达式
为 ac3x2zy/-*u+
    程序给每个运算符和括号设定一个优先级，并引入一个栈和一个存储后缀表达式的工
作数组。函数 expr() 工作时，按自左至右逐个顺序扫描中缀表达式，如当前符号是变量
名，就将该变量名直接复制到工作数组；如当前符号是运算符或括号，将当前符号的优先
级和栈顶符号的优先级进行比较；若当前符号的优先级高，则当前符号进栈；反之，则进
行出栈处理，并将从栈中退出的运算符依次复制到工作数组中，直到栈顶符号的优先级比
当前符号的优先级低为止，然后将当前的运算符或左括号进栈。为使子表达式能优先处理，
所以给左括号设定较高的优先级，但又为了能正确处理随后的子表达式，在左括号进栈时，
它在栈中的优先级作了一定的改变。
    初始时，expr() 函数预先在栈底设置一个符号'#'，其优先级比所有运算符和括号的
优先级都低。程序还检查输入表达式的运算符和运算分量的合理性，以及括号是否正确配
对。
【程序3】
    #include &ltstdio.h>
    #include &ltctype.h>
    #include &ltstdlib.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},{'\0', 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-&gtdata = x; q-&gtcode = c; q-&gtpri = p; ___(1)___ ; *toppt = q;
    }
    int pop(char *op, int *cp, NODE **toppt)  /*链接存储栈的出栈函数*/
    { NODE q = toppt;
       if (*toppt == NULL) return 1;  /*空栈 */
       *op = q-&gtdata; cp = q-&gtcode; ___(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, &ampoptop);  /*预先在栈中置一个0优先级的符号 */
       while (1) { while (c==' '||c == '\t') 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; opchTb1[i].code != -1 && ___(4)___ ; i++)
              if (opchTb1[i].code == -1) return 3;  /*非法字符 */
              op = &ampopchTbl[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 2;   /*圆括号不匹配*/
       if  ( ___(5)___ )   /*运算符或括号进栈 */
           if (op-&gtdata == '(' ) push(op-&gtcode, 1, &ampoptop);
           else push(op-&gtdata, op-&gtcode, op-&gtpri, &ampoptop);
       else { while (optop != NULL && op-&gtpri <= optop-&gtpri) {
                  pop( ___(6)___ );
                  if ( ___(7)___ ) {   /* 运算符复制到工作数组*/
                     *numtop++ = ' '; *numtop++ = stop;
                     }
                  }
                  if (op-&gtdata=='0')
                     return (n!=0||(m!=1&&ampnumtop&gtnum))?4( *numtop='\0');
                  else if(op-&gtdata!=')')
                     push (op-&gtdata, op-&gtcode, op-&gtpri, &ampoptop);
             }
       }
    }
    void main()
    { int d;
       printf("请输入表达式  !\n"); gets(expStr);
       if ((d = expr(expStr)) == 0) printf("后缀表达式为 %s\n",num);
       else printf("表达式句法错！错误类型为%d\n",d);
    }

试题四(21分)
    阅读下列程序说明和C代码，将应填入 ___(n)___ 处的字句写在答卷的对应栏内。
[程序4说明]
    有一种单人玩的游戏：设有 n(2 <= n <= 200) 堆薄片，各堆顺序用 0 至 n-1 编
号，极端情况，有的堆可能没有薄片。在游戏过程中，一次移动只能取某堆上的若干张薄
片，移到该堆的相邻堆上。如指定 i 堆 k 张 k 移到 i-1(i&gt0) 堆，和将 k 张薄片移至
 i+1(i&ltn-1) 堆。所以当有两个堆与 i 堆相邻 时，i 堆原先至少有 2k 张薄片；只有一
个堆与 i 堆相邻 时，i 堆原先至少有 k 张薄片。
    游戏的目标是对给定的堆数，和各堆上的薄片数，按上述规则移动薄片，最终使各堆
的薄片数相同。为了使移动次数较少些，移动哪一堆薄片，和移多少薄片先作以下估算：

设 
    ci: i 堆的薄片数(0 <= i < n,0 <= ci <= 200);
    v： 每堆的平均薄片数；
    ai: i 堆的相邻堆可以从 i 堆得到的薄片数。
估算方法如下：
    v = c0+a1-a0          a1 = v+a0-c0
    v = c1+a0+a2-2a1      a2 = v+2a1-a0-c1
      ……                    ……
    V = ci+ai-1+ai+1-2ai  ai+1 = v+2ai-ai-1-ci
    这里并不希望准确地求出 A0 至 an-1，而是作以下处理：若令 a0 为 0，能按上述算
式计算出 A1 至 an-1。程序找出 a 中的最小值，并让全部a值减去这最小值，使每堆移去
的薄片数大于等于 0。
    实际操作采用以下贪心策略：
    (1)每次从第一堆出发顺序搜索每一堆，若发现可从 i 堆移走薄片，就完成一次移动。
即，i 堆的相邻堆从 i 堆取走 ai 片薄片。可从 i 堆移薄片到相邻堆取于 i 堆薄片数：
若 i 堆是处于两端位置( i = 0  i = n-1), 要求 ci >= ai ；若 i 堆是中间堆，则要求
ci >= 2ai。
    (2)因在 ai&gt0 的所有堆中，薄片数最多的堆在平分过程中被它的相邻堆取走的薄片数
也最多。在用策略 (1) 搜索移动时，当发生没有满足条件 (1) 的可移走薄片的堆时，采用
本策略，让在 ai&gt0 的所有堆中，薄片数最多的堆被它的相邻堆取走它的全部薄片。
[程序4]
    #include &ltstdio.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 )   /* 输入初始数据，估算ai */
    { int i, n, d, min, v; long sum = OL;
       printf ("输入n:"); scanf ("%d",&ampn); printf ("输入各堆的薄片数(<%d)\n", M);
       for (i = 0; i < n; i++)
           { scanf ( "%d",&ampd); c[i] = ( d >= 0 && d < M) ? d : 0; }
       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 &ltn-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, int n, 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(&ampn, c, a) == 0 ) { printf("薄片总数不能被平分\n"); return; }
      search(c, a, n); printf(" 序号 移动位置号 各相邻位置得到薄片数\n");
      for (i = 0; i < mc; i++)
           printf("%4d%10d%18d\n", i+1, way[i].id, way[i].k);
      printf("\n");}