1999年度程序员级下午试卷

1999年度程序员级下午试卷 1999年度程序员级 下午试卷 试题一 函数strcpy(char *to,char *from)将字符串from复制到字符串to. void strcpy(char *to,char *from) {while (____(1)____);} 函数merge(int a[],int n,int b[],int m,int *c)是将两个从小到大有序数组,a和b复制合并出一个有序整数序列c,其中形参n和m分别是数组a和b的元素个数. void merge(int a[],int n,int b[],int m,int *c) { int i,j; for (i=j=0;i *c++=a[i] while (____(2)____) *c++=a[i++]; while (____(3)____) *c++=b[j++]; } 递归函数sum(int a[],int n)的返回值是数组a[]的前n个元素之和 int sum(int a[],int n) { if (n>0) return ____(4)____ ; else ____(5)_____; } 试题二 阅读下列函数说明和C代码,将应填入____(n)____处的子句写在答卷的对应栏内. 本题中的函数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 n=____(1)____; c=____(2)____; for (k=0;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 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. #include #include #include #include #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 N>=10)内的某9个互不相同的整数， 本程序在3X3方格中填入数字1~N( 使所有相邻两个方格内的两个整数之和为质数(试求出满足这个要求的所有填法(3X3方格中的每个方格序号如图4所示( 程序采用试探法，即从序号为0的方格开始，为当前方格寻找一个合理的可填整数，并在当前位置正确填入后，为下一方格寻找可填入的合理整数(如不能为当前方格寻找一个合理的可填整数，就要后退到前一方格，调整前一方格的填入整数(当直至序号为8的方格也填入合理的整数后，就找到了一个解。为了检查当前方格的填入整数的合理性，程序引入二维数组CheckMatrix,存放需要进行合理性检查的相邻方格的序号。 #include #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 for (j=0;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 if (m%i==0) return 0; i+=2; ) return 1; ) int selectNum(int start) { int j; for (j=start;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 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 find(); )