1999年度程序员级下午试卷

试题一
[函数1.1说明]
    函数 strcpy(char *to, char *from) 将字符串 from 复制到字符串 to。
[函数1.1]
    void strcpy(char *to, char *from)
    { while (____(1)____); }

[函数1.2说明]
    函数 merge(int a[], int n, int b[], int m ,int *c)是将两个从小到大有序数组, a 和 b复制合并出一个有序整数序列 c ,其中形参 n 和 m 分别是数组 a 和 b 的元素个数。
[函数1.2]
      void merge(int a[],int n,int b[],int m,int *c)
   { int i,j;
　   for (i = j = 0;i < n && j < m;)
　　     *c++ = a[i] < b[j] ? a[i++] : b[j++];
　　 while (____(2)____) *c++ = a[i++];
　　 while (____(3)____) *c++ = b[j++];
　　}

[函数 1.3说明]
　　递归函数 sum(int a[],int n) 的返回值是数组 a[] 的前 n 个元素之和。
[函数 1.3]
    int sum(int a[] ,int n)
    { if (n>0) return ____(4)____ ;
　　  else ____(5)_____;
    }

试题二
    阅读下列函数说明和 C 代码,将应填入____(n)____处的子句写在答卷的对应栏内。
[函数 2说明]
　　本题中的函数 encode() 和 decode() 分别实现对字符串的变换和复原。变换函数 encode() 顺序考察已知字符串的字符，按以下规则逐组生成新字符串:
　　(1)若已知字符串的当前字符不是数字字符，则复制该字符于新字符串中。
　　(2)若已知字符串的当前字符是一个数字字符，且它之后没有后继字符，则简单地将它复制到新字符串中。
　　(3)若已知字符串的当前字符是一个数字字符，并且还有后继字符，设该数字字符的面值为 n ，则将它的后继字符（包括后继字符是一个数字字符）重复复制 n+1 次到新字符串中。
　　(4)以上述一次变换为一组，在不同组之间另插入一个下划线'_'用于分隔。例如：encode() 函数对字符串 26a3t2 的变换结果为 666_a_tttt_2 。
　　复原函数 decode() 做变换函数 encode() 的相反的工作。即复制不连续相同的单个字符，而将一组连续相同的字符（不超过10个)变换成一个用于表示重复次数的数字符和一个重复出现的字符，并在复原过程中掠过变换函数为不同组之间添加的一个下划线字符。
　　假定调用变换函数 encode() 时的已知字符串中不含下划线字符。
[函数]
    int encode(char *instr, char *outstr)
    {　char *ip, *op ,c ; int k,n ;
　     ip = instr; op = outstr;
　     while (*ip) {
　　      if (*ip >= '0' && *ip <= '9' && *(ip+1))　｛
　　　　    n = ____(1)____;
　　　　    c = ____(2)____;
　　　　    for (k = 0;k < n; k++)
　　　　　　  *op++ = c;
　　　    ｝else ____(3)____;
　　　    *op++ = '_';
　　　    ip++;
　　   }
　　   if (op > outstr) op--;
　　   ____(4)____;
　　   return op - outstr;
    }
    int decode(char *instr, char *outstr)
    {　char *ip , *op , c ; 　int n;
　　   ip = instr; op = outstr;
　　   while (*ip) {
　　　  c = *ip; n = 0;
　　　  while (*ip == c && n < 10) {ip++; n++; }
　　　  if (____(5)_____) *op++='0'+n-1;
　　　  *op++ = c;
　　　  if (____(6)____) ip++;
　   }
　   *op = '\0';
　   return op - outstr;
　}

试题三
　　本程序从正文文件 text.ini 读入一篇英文短文，统计该短文中不同单词和它的出现次数，并按词典编辑顺序将单词及它的出现次数输出到正文文件 word.out 中．
　　程序用一棵有序二叉树存储这些单词及其出现的次数，一边读入一边建立．然后中序遍历该二叉树，将遍历经过的二叉树上结点的内容输出。
　　程序中的外部函数
　　  int getword(FILE *fpt,char *word)
从与 fpt 所对应的文件中读取单词置入 word，并返回 1；若读单词遇文件尾，已无单词可读时，则返回 0 。
[程序3]
　#include <stdio.h>
　#include <malloc.h>
　#include <ctype.h>
　#include <string.h>
　#define INF "TEXT.IN"
　#define OUTF "WORD.OUT"
　typedef struct treenode { char *word;
　　　　　　　　　　　　　　int count;
　　　　　　　　　　　　　　struct treenode *left, *right;
　　　　　　　　　　　　　 ｝BNODE;
  int getword(FILE *fpt,char *word);
  void binary_tree(BNODE **t,char *word)
  { BNODE *ptr, *p; int cmpres;
　  p = NULL; ____(1)____;
　  while (ptr) {/*寻找插入位置*/
　　　cmpres = strcmp( word ,____(2)____); /* 保存当前比较结果 */
　　　if (!cmpres) { ____(3)____; return;}
　　　else { ____(4)____;
　　　　　　ptr = cmpres > 0 ? ptr->right : ptr->left;
　　　　　　}
    }
    ptr = (BNODE *)malloc(sizeof(BNODE));
    ptr->right = ptr->left = NULL;
    ptr->word = (char *)malloc(strlen(word)+1);
    strcpy(ptr->word,word );  ptr->count = 1;
    if (p == NULL) ____(5)_____ ;
    else if (cmpres > 0) p->right = ptr;
　　　　 else p->left = ptr;
  }

  void midorder(FILE *fpt, BNODE *t)
  { if ( ____(6)____) return;
　  midorder( fpt , t->left);
　  fprintf( fpt , " %s 　%d\n " , t->word , t->count);
　  midorder( fpt , t->right);
  }

  void main()
  { FILE *fpt; char word[40];
　  BNODE *root = NULL;
　  if ((fpt = fopen(INF , "r")) == NULL) {
　　　printf("Can't open file %s\n",INF);
　　　return;
    }
    while (getword(fpt,word) == 1)
　　　binary_tree(____(7)____);
　  fclose(fpt);
　  fpt = fopen(OUTF,"w");
　  midorder(fpt, root);
　  fclose(fpt);
  }

试题4
　　本程序在 3×3 方格中填入数字 1～N（N >= 10)内的某 9 个互不相同的整数，使所有相邻两个方格内的两个整数之和为质数。试求出满足这个要求的所有填法．3×3方格中的每个方格序号如图4所示．
　　程序采用试探法，即从序号为0的方格开始，为当前方格寻找一个合理的可填整数，并在当前位置正确填入后，为下一方格寻找可填入的合理整数．如不能为当前方格寻找一个合理的可填整数，就要后退到前一方格，调整前一方格的填入整数．当直至序号为8的方格也填入合理的整数后，就找到了一个解。为了检查当前方格的填入整数的合理性，程序引入二维数组CheckMatrix,存放需要进行合理性检查的相邻方格的序号。

图４

[程序4]
　#include <stdio.h>
　#define N 12
　int pos;
　int a[9]; /*用于存储方格所填入的整数　*/
　checkMatrix[][3] = {{-1},{0,-1},{1,-1},
　　　　　　　　　　  {0,-1},{1,3,-1},{2,4,-1},
　　　　　　　　　　　{3,-1},{4,6,-1},{5,7,-1}};
  void write(int a[])
  { int i, j;
　  for ( i = 0; i < 3; i++) {
　　    for ( j = 0; j < 3; j++) printf("%3d",a[3*i+j]);
　　    printf("\n");
　　}
  }
  int isPrime(int m)
  { int i;
　  if (m == 2) return 1;
　  if (m == 1 || m % 2 == 0) return 0;
　  for (i = 3; i * i <= m; ) {
　　　if (m % i == 0) return 0;
　　　i+ = 2;
　  }
　  return 1;
  }
  int selectNum(int start)
  { int j;
　  for (j = start; j <= N; j++)
　　if (b[j]) return j;
　return 0;
  }
  int check() /*检查填入pos位置的整数是否合理*/
  { int i, j;
　  for (i = 0; (j = ____(1)____) >= 0; i++)
　　　　if (!isPrime(a[pos] + a[j])) ____(2)____;
　  　　(3)　　;
  }
  extend()　/*为下一方格找一个尚未使用过的整数*/
  { a[____(4)____] = selectNum(1); b[a[pos]] = 0; }
  void change()  /*为当前方格找下一个尚未使用过的整数。（找不到回溯）*/
  {　int j;
　   while (pos >= 0 && (j = selectNum(____(5)____)) == 0) _____(6)_____;
　   if (pos < 0) return;
　   b[a[pos]] = 1; a[pos] = j; b[j] = 0;
  }
  find()
  { int ok = 1;
　  pos = 0; a[pos] = 1; b[a[pos]] = 0;
　  do {
　　　 if (ok)
　　　　 if (____(7)____) {
　　　　　　write(a);
　　　　　　change();
　　　　 ｝
　　　　 else extend();
　　　 else change();
　　　 ok = check(pos);
　　} while (pos>=0);
  }
  main()
  { int i;
　  for (i = 1;i <= N; i++) b[i] = 1;
　  find();
  }