一九九九年度程序员级　下午试卷

试题一
<函数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
　　本程序在3X3方格中填入数字1~N（N>=10)内的某9个互不相同的整数，使所有相邻两个方格内的两个整数之和为质数．试求出满足这个要求的所有填法．3X3方格中的每个方格序号如图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() /*为当前方格找下一个尚未使用过的整数*/
{ 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();
}