1998年程序员考试下午试题

试题1
    阅读以下程序说明和 C 程序，将应填人__(n)__处的字句，写在答卷的对应栏内。
[程序说明]
    函数 int commstr(char *str1，char *str2，int *sublen) 从两已知字符串 Strl 和 Str2 
中，找出它们的所有最长的公共子串。如果最长公共子串不止 1个，函数将把它们全部找出，并输
出。约定空串不作为公共子串。
    函数将最长公共子串的长度送入由参数 sublen 所指的变量中，并返回字符串 str1 和 stf2 
的最长公共子串的个数。如果字符串 strl 和 str2 没有公共子串，约定最长公共子串的个数和最
长公共子串的长度均为 0 。
[程序]
  int strlen(char *s)
  {  char * t = s；
     while (*t++)；
     return t-s-1；
  }
  int commstr(char *str1，char *str2, int *sublen)
  { char*sl，*s2；
    int count = 0, len1, len2 , k, j, i, p;
    len1 = strlen(str1);
    len2 = strlen(str2);
    if (len1 > len2)
      { s1 = str1; s2 = str2;}
    else { len2 = len1; s1 = str2; s2 = str1;}
    for(j = len2; j > 0; j--)  /* 从可能最长子串开始寻找  */
      { for(k = 0; __(1)__ <= len2; k++)  /*  k 为子串 S2 的开始位置  */
         { for( i = 0; s1[ __(2)__ ] != '\0';   i ++;)  /* i 为子串 s1 的开始位置  */
            {  /*  s1 的子串与 S2 的子串比较  */
               for (p = 0; p < j && __(3)__; p++);
                  if ( __(4)__ )  /*  如果两子串相同   */
                     { for (p = 0; p < j ; p++)  /* 输出子串 */
                         printf("%c", s2[k + p]);
                       printf("\n");
                       count++;  /* 计数增   */
                     }
            }
         }
         if (count > 0 ) break;
      }
    *sublen = (count > 0) ? __(5)__ ; 0 ;
    return  count;
  }

试题二 略（FORTRON 程序）

试题三
    阅读以下程序说明和 C 程序，将应填入__(n)__处的字句，写在答卷的对应栏内。
[程序说明]
    打保龄球是用一个滚球去打出十个站立的柱，将柱击倒。一局分十轮，每轮可滚球一
次或多次，以击倒的柱数为依据计分。一局得分为十轮得分之和，而每轮的得分不仅与本
轮滚球情况有关，还可能与后续一两轮的；滚球情况有关。即，某轮某次滚球击倒的柱数
不仅要计入本轮得分，还可能会计入前一两轮得分。具体的滚球击柱规则和计分方法如下：
    (1) 若某一轮的第一次滚球就击倒全部十个柱，则本轮不再滚球。(若是第十轮则还需
另加两次滚球)。该轮得分为本次倒柱数 10 与以后两次滚球所击倒柱数之和。
    (2) 若某一轮的第一次滚球未击倒十个柱，则可对剩下未倒的柱再滚球一次。如果这
两次滚球击倒全部十个柱，则本轮不再滚球(若是第十轮则还需另加一次滚球)，该轮得分
为本次倒柱数 10 与以后一次滚球所击倒柱数之和。
    (3) 若某一轮的两次滚球未击倒全部十个柱，则本轮不再继续滚球，该轮得分为这两
次滚球击倒的柱数这和。          
    总之，若一轮中一次滚球或两次滚球击倒十个柱，则本轮得分是本轮首次滚球开始的
连续三次滚球击倒柱数之和(其中有一次或两次不是本轮滚球)。若一轮内二次滚球击倒柱
数不足十个，则本轮得分即为这两次击倒柱数之和。
    以实例说明如下：

    本程序是模拟打一局保龄球的过程，统计各轮得分和累计总分。程序交互地逐轮逐次
输人一次滚球击倒的柱数，计算该轮得分和累计总分。为记录因一轮内击倒十柱，还暂不
能计算该轮得分和累计总分的情况，程序引人变量 ok ，用来记录当前已完成完整计算的
轮次。程序每输人一次滚球击倒柱数，就检查还未完成完整计算的轮次，并计算之。
[程序]
   #include<stdio.h>
   #define N 13
   struct { int n; /* 一轮内滚球次数 */
            int f; /* 第一次击倒柱数 */
            int s; /* 第一次击倒柱数 */
            int score;  /* 本轮得分 */
            int total;/* 至本轮累计总分 */
            int m; /* 完成本轮得分计算，还需滚球次数 */
          }  a [N];
   int  ok = 0; /* 已完成完整计算的轮次数 */
   int ball(int i, int n, int max)  /* 完成一次滚球，输入正确击倒柱数 */
   {  int d, j, k; static c = 1;
      while(1)
      {  if (i <= 10)
            printf("  输入第 %d 轮的第 %d 次滚球击倒柱数。(<= %d)\n", i, n, max);
         else
            printf("  输入附加的第 %d 次滚球击倒柱数。(<= %d)\n", C++, max);
         scanf("%d , &d);
         if (d >=0 && d <= max) break;
         printf(" 不合理的击倒柱数，请重新输入。\n");
      }
      if (ok < __(1)__)
      {  /*   对以前未完成计算的轮次分别计算得分与累计总分  */
         for(j = ok+1; __(2)__; j++)
         { a[j].score += d;
            if (--a[j].m == 0)
              { a[j].total = (__(3)__) + a[j].score; ok =__(4)__;}
        }
     }
     return d;
   }
   main()
   {  int i, /* 轮次  */ first, second, k;
      for(i = 1; ok < 10; i++)
      { /* 处理第一次滚球  */
         a[i].score = a[i].f = first = ball(i,1,10);
         if (first == 10) a[i].m = 2;
         a[i].n=1;
         if (first < 10 && (i <= 10 || i == 11 && ok < 10 ))
         { /*  处理第二次滚球*/
            __(5)__ = second = ball(i,2,10-first);
            if (first + second == 10) a[i].m = 1;
            __(6)__;
         }
         if (i <= 10 && first < 10 && fist + second < 10)
         { a[i].total = (i > 1 ? a[i-1].total : 0) + a[i].score;
            __(7)__;
         }
         printf( " 各轮第一次得分");
         for(k = 1; k <= 1; k++)  printf("%5d", a[k].f);
         printf("\n 各轮第二次得分 ");
         for(k=1; k <= i; k++)
	    if (a[k].n < 2) printf(" /"); else printf("%5d", a[k].s);
         printf("\n  各轮得分 ");
         for(k = 1; k <= ok; k++) printf("%5d", a[k].score);
         printf("\n   累计总分  ");
         for(k = 1; k <= ok; k++) printf("%5d", a[k].total);
         printf("\n\n");
      }
   }

试题四 略（FORTRON 程序）

试题五
    阅读以下程序说明和 C 程序，将应填入__(n)__处的字句，写在答卷的对应栏内。
[程序说明]
    这里给处的程序逐一从指定课程成绩文件中读入学生的考号和成绩，对同一学生汇总
他的总成绩，并按以下格式输出名次(按总成绩由高到底的顺序)、总成绩、同一名次的学
生人数、同一名次学生的学号(按学号由小到大的顺序)。
    程序约定学生学习课程不超过 30 种，课程成绩文件的第一个数字就是课程号，统计
过程中，同一课程号的成绩文件不能重复输入。
    程序采用链表结构存储学生有关信息，链表中的每个表元对应一位学生。程序数据输
入过程中，形成一个按学号从小到大顺序链接的有序链表。当数据数输入结束后，程序按
总成绩从高到低，学号从小到大的顺序对链表排序。程序最后按指定格式输出链表中的信
息。程序的输出格式如下例所示：

[程序]
   #include <stdio.h>
   #define M 30
   #define NLEN 10
   typedef struct node {
           int cur_s; /*  最近输入成绩的科目*/
           char no[NLEN];
           int score;
           struct node *next;
         } NODE;
   int s[M], sp, ss, i, mark, order, c;
   FILE *fp;  NODE *h, *u, *v, *p;
   char fname[80], no[NLEN], ans;
   main()
   { for(h = NULL, sp = 0; ;)
       {  printf("  输入科目成绩文件名(输入aaaa表示强行结束)。 \n");
          while(1)
          { scanf("%s", fname);
            if (strcmp(fname, "aaaa") == 0) break;
            if ((fp = fopen(fname, "r")) == NULL)
               printf(" 不能打开文件 %s,  请重新输入科目文件名。 \n", fname);
            else break;
          }
          if (strcmp(fname, "aaaa") == 0) break;
          fscanf(fp, "%d", &ss); /* 输入科目号  */ s[sp]=s;
          for (i = 0; s[i] != ss; i++);
          if (__(1)__)
          { printf(" 该科目的成绩已输入，请输入别的科目成绩文件。\n");
 	    continue;
          }
          sp++;
          while (fscanf(fp, "%s%d", no, &mark) == 2)
          { /* 在链表中寻找最近输入的学号  */
  	    for(v = h; v != NULL && strcmp(v-> no, no)<0; u=v, v= v-> next);
            if (v !=NULL && strcmp(v->no, no) == 0)
  	    { /*  该生已有成绩  */
     		if (v->cur_s != ss)
    		{ /* 该生的当前科目成绩是第一次输入  */ 
      	           v->score += mark; /*  累计总成绩  */  v->cur_s = ss;
    		} /*   同一科目成绩重复输入，后输入成绩被忽略。  */
  	    }     
 	    else { p = (NODE *)malloc(sizeof(NODE)); /*   一位新的学生  */
                   strcpy(p->no,no); p->score = mark; p->cur_s = ss;
        	   p-> next = v;
        	   if ( v == h) __(2)__; else __(3)__;
      		 }
          }
          fclose(fp);
          printf(" 还有科目成绩文件要输入吗？ (Y/N)"); scanf("%c", &ans);
          if (ans == 'N' || ans == 'n') break;
       }  /* 以下按总成绩和学号对链表排序  */
       v = (NODE *)malloc(sizeof(NODE));
       v->next = h;  h = v;
       while (v->next != NULL)
       { /* 在余下的部分链表中找总成绩高学号小的表元  */
          for(p = v, u = v->next; u->next != NULL; u = u->next)
             if (u->next->score > p->next->score ||
                u->next->score == p->next->score &&
                strcmp(u->next->no, p->next->no) < 0)  p = u;
          if (p != v)  { u = p->next; p->next = __(4)__;
                         __(5)__ = v->next;  v->next = u;
                       }
          v = v->next;
       }
       v = h;  h = h->next;  free(v);
       printf(" 名次    总成绩    人数    学号\n"); /* 以下按格式要求输出  */
       v = h;  order = 1;
       while (v != NULL)
       {  for(c = 1, u = v->next; u != NULL && u->score == v->score; __(6)__);
          printf("%4d%7d%8d  ", order, v->score, c);
          for (order += c, i = 1; __(7)__; v = v->next, i++)
             { if (i > 1 && i%5 == 1) printf("\n%23c", ' ');
               printf("%s ", v->no);
             }   printf("\n");
       }
   }

试题六 略（FORTRON 程序）

试题七
    阅读以下程序说明和 C 程序，将应填入＿(n)＿处的字句，写在答卷的对应栏内。
[程序说明]
    本程序的函数
            int sum(int total， int d[]， int n)
用来从已知数组 d 的前 n 个元素中找出所有部分元素序列之和等于 total 的元素序列，约
定数组 d 的元素都是正整数，且都小于等于 total。如果函数找到了这样的部分元素序列，
函数返回非 0 值，否则函数返回 0 值。
      函数 sum 使用试探法找出全部解答。在找解过程中，依次选取候选元素，尝试组成一
个和小于 total 的部分元素序列，进行试探和回溯。
     函数中的数组 b 用来存放候选元素的下标，变量 p 用来记录当前 b 中有效下标的个
数，t 记录当前部分序列的和，函数用它们实现回溯找解。如果 t 等于 total，则表示找到
了一个解答，函数将该解答输出，然后通过回溯，再试探寻找其它的解答；如果 t 还小于
total，则继续从 d 的还未被考虑的那部分元素中找一个与 t 之和不超过 total 的元素，
如没有这样的元素，函数也得回溯。
[程序]
   #include<stdio.h>
   #define N 100
   int a[n];
   int sum(int total, int d[],int n)
   { int s, p, t, b[N], none = 1;
     b[0] = 0;  t = d[0]; p = 1;
     do
     {  if (t == total)
        { /* 找到了一个解，把当前解输出  */
          printf("%4d = %d",total, d[b[0]]);
          for(s = 1; s < p; s++)
              printf(" +%d",d[b[s]]);
          printf("\n");
          none = 0;   /*  置找到过解的标志   */
        }
        else 
        { for(s = __(1)__; s < n-1 && __(2)__ > total;s++);
          if (s < n && t + d[s] <= total) 
          { b[ __(3)__] = s;  t += d[s];
            continue; 
          }
        }
        t -= d[b[p-1]];     /*  回溯  */
        if ( p < 1 && ___(4)__)
        {  p--; t -= __(5)__;
        }
        if ( p == 1 && __(6)__) break;  /*  回溯到底，退出找解循环  */
        t += d[__(7)__]; /*  回溯后，调整 */
     } while(1);
     return !none; /*  返回找到过解答的标志   */
   }
   main( )
   { int i,n, total, d;
     printf("输入  total!\n"); scanf("%d",&amptotal);
     printf("输入  n!\n");  scanf("%d",&ampn);
     for(i = 0; i < n;) 
     { print("输入数组的第 %d 个正整数( > 0 且 <= %d)\n",i+1,total);
       scanf("%d", &d);
       if (d < 1 || d > total)
       { printf("出错，请重新输入！\n");
         continue;
       }
       a[i++] = d;
     }
     if (!sum(total, a, n)) printf("没有找到解答！\n");
     printf("\n\n");
   } 

试题八 略（FORTRON 程序）

 回目录      老顽童校对整理 2002年6月