1、初级程序员下午试题-76 及答案解析(总分：90.00，做题时间：90 分钟)一、试题一(总题数：1，分数：15.00)1.【说明】本程序可以将字符串 s1中出现的所有 s2子串替换成 s3，形成一个新串，但不破坏字符串 s1。【代码】#includestdio.h#includestdlib.h#includestring.hchar*replace(char *s1, char *s2,char *s3)char *p, *q, *r, *s; int |2，|3, i=0;|2=strlen(s2);|3=strlen(s3);p=s1;while(p=strstr(p,s2)!=NUL
2、L)i+; /* 统计 s2串出现的次数*/(1) ;i= (2) ;s=r=(char*)malloc(i); /*分配动态内存存放新字符串*/p=s1;while(1)q=strstr(p, s2); /* s2串是否在 s1中出现，q 是首次出现的位置*/if(q!=NULL)i=q-p;(3) ;r+=i;(4) ;r+=|3;p=q+|2; /*将指向 s1串的指针移到 s2子串出现的位置后，为下一次循环做好准备*/else /*q为空，表示剩余的 s1串中已经没有 s2*/(5) ;break; /*终止循环*/return(s); /*返回指向所形成的新串的指针*/void ma
3、in()char *a=“sabcababde“, *b=“ab“, *c=“efg“, *d;d=replace(a, b, c); printf(“result=%s/n“, d); free(d);（分数：15.00）_二、试题二(总题数：1，分数：15.00)2.1说明】本程序可以打印出如下图形(菱形)：*【函数 2.1】main()int i,j,k;for(i=0;i=3;i+)for(j=0;j=2-i;j+)printf(“ “);for( (1) )printf(“*“);printf(“/n“);for(i=0;i=2;i+)for( (2) )printf(“ “);fo
4、r(k=0;k=4-2*i;k+)printf(“*“);printf(“/n“);【函数 2.2说明】通过本程序，可以从键盘输入一个字符串，将小写字母全部转换成大写字母，然后输出到一个磁盘文件“CsaiWgm”中保存，输入的字符串以“!”结束。【函数 2.2】#include “stdio.h“main()FILE *fp;char str100,filename10;int i=0;if(fp=fopen(“CsaiWgm“,“w“)=NULL)printf(“cannot open the file/n“);exit(0);printf(“please input a string:/n
5、“);gets(str);while( (3) )if(stri=afputc(stri,fp);(5) ;fclose(fp);fp=fopen(“CsaiWgm“,“r“);fgets(str,stden(str)+1,fp);printf(“%s/n“,str);fclose(fp);（分数：15.00）_三、试题三(总题数：1，分数：15.00)3.【说明】设 M叉树采用列表法表示，即每棵子树对应一个列表，列表的结构为：子树根结点的值后跟用“()”括起来的各子树的列表(若有子树的话)，各子树的列表间用“，”分隔。例如，如下图所示的三叉树可用列表a(b(c,d),e,f(g,h,i)表示
6、。本程序根据输入的列表生成一棵 M叉树，并由 M叉树再输出列表。（分数：15.00）_四、试题四(总题数：1，分数：15.00)4.【说明】本程序利用非递归算法实现二叉树后序遍历。【函数】#includestdio.h#includestdlib.htypedef struct node/*二叉树的结点数据结构类型*/char data;struct node *left;struct node *right;BTREE;void SortTreelnsert(BTREE *tree, BTREE *s)if(*tree=NULL)*tree=s;elseif(s-data(*tree)-da
7、ta)SortTreelnsert( (1) ,s);else if(s-data=(*tree)-data)SortTreelnsert( (2) ,s);void TraversalTree(BTREE *tree)BTREE *stack1 000,*p;int tag1000,top=0;p=tree;dowhile(p !=NULL)stack+top=p;(3) ;tagtop=0; /*标记栈顶结点的左子树已进行过后序遍历*/while(top0putchar(p-data);if(top0)/*对栈顶结点的右子树进行后序遍历*/(5) ;tagtop=1;while(top0)
8、;void PrintSortTree(BTREE *tree)if(tree !=NULL)printSortTree(tree-left);putchar(tree-data);pdntSortTree(tree-right);main()BTREE *root=NULL, *node;char ch;ch=getchar();while(ch !=#)node=(BTREE*)malloc(sizeof(BTREE);node-data=ch;node-left=node-right=NULL;SortTreelnsert(ch=getchar();PrintSortTree(root)
9、;putchar(/n);TraversalTree(root);（分数：15.00）_五、试题五(总题数：1，分数：15.00)5.【说明】主窗口有一个按钮、一个文本框和一个复选框，初始时窗口大小不能调整，选中复选框后窗口大小可以调整，如果撤销复选框的选择，则窗口的大小又不能调整，如下图所示。（分数：15.00）_六、试题六(总题数：1，分数：15.00)6.【说明】本程序的功能是实现任意两个大整数的乘法运算，例如：输入整数 1：8934793850094505800243958034985058输入整数 2：234584950989689084095803583095820923二者之积：
10、209596817742739508050978890737675662366433464256830959194834854876 8534【C+代码】#includeiostream.hconst int MAXINPUTBIT=100;const int MAXRESULTBIT=500;class LargeNumberint i,j;int temp;int oneMAXINPUTBIT+1;int onebit; /one的位数int twoMAXINPUTBIT+1;int twobit; /two的位数int resultMAXRESULTBIT+1;public:LargeN
11、umber();LargeNumber();int inputone(); /出错返叫 0，否则返回 1int inputtwo(); /同上void multiplication(); /乘void clearresult(); /清零void showresult(); /显示;LargeNumberLargeNumber()for(i=0;i=MAXINPUTBIT;i+)onei=0;twoi=0;onebit=0;twobit=0;inputone();inputtwo();LargeNumberLargeNumber()int LargeNumberinputone()char N
12、umberMAXINPUTBIT+1;cout“Please enter one:“;cinNumber;i=0;j=MAXINPUTBIT;while(Numberi!=/0)i+;onebit=i;for(i-;i=0;i-,j-)if(int(Numberi)=48 /由字符转换为数字elsereturn 0;return 1;int LargeNumberinputtwo()char NumberMAXINPUTBIT+1;cout“Please enter two:“;cinNumber;i=0;j=MAXINPUTBIT;while(Numberi!=/0)i+;twobit=i;
13、for(i-;i=0;i-,j-)if(int(Numberi)=48 /由字符转换为数字elsereturn 0;return 1;void LargeNumbermultiplication() /乘法clearresult();int m;for(i=MAXINPUTBIT;i=0;i-)temp=twoi;for(j= (2) ,m=MAXINPUTBIT;m=0;m-,j-)resultj+=temp*onem;if(resultj9)resultj-1+=resultj/10;(3) ;cout“one*two=“;showresult();void LargeNumbershow
14、result()i=0;while(resulti=0if(iMAXRESULTBIT)cout“0“; /输出 0for(;i=MAXRESULTBIT;i+)cout (4) ;coutendl;void LargeNumberclearresult()for(i=0;i=MAXRESULTBIT;i+)(5) ;void main()LargeNumber a;a.multiplication();（分数：15.00）_初级程序员下午试题-76 答案解析(总分：90.00，做题时间：90 分钟)一、试题一(总题数：1，分数：15.00)1.【说明】本程序可以将字符串 s1中出现的所有 s
15、2子串替换成 s3，形成一个新串，但不破坏字符串 s1。【代码】#includestdio.h#includestdlib.h#includestring.hchar*replace(char *s1, char *s2,char *s3)char *p, *q, *r, *s; int |2，|3, i=0;|2=strlen(s2);|3=strlen(s3);p=s1;while(p=strstr(p,s2)!=NULL)i+; /* 统计 s2串出现的次数*/(1) ;i= (2) ;s=r=(char*)malloc(i); /*分配动态内存存放新字符串*/p=s1;while(1)
16、q=strstr(p, s2); /* s2串是否在 s1中出现，q 是首次出现的位置*/if(q!=NULL)i=q-p;(3) ;r+=i;(4) ;r+=|3;p=q+|2; /*将指向 s1串的指针移到 s2子串出现的位置后，为下一次循环做好准备*/else /*q为空，表示剩余的 s1串中已经没有 s2*/(5) ;break; /*终止循环*/return(s); /*返回指向所形成的新串的指针*/void main()char *a=“sabcababde“, *b=“ab“, *c=“efg“, *d;d=replace(a, b, c); printf(“result=%s/
17、n“, d); free(d);（分数：15.00）_正确答案：(1)p+=12(2)strlen(s1)-i*12+i*13+1(3)strncpy(r,p,i)(4)strcpy(r,s3)(5)strcpy(r,p)解析：分析本题考查用 C语言实现对字符串的操作。题目要求将字符串 s1中出现的所有子串 s2替换成 s3，形成一个新串，但不破坏字符串 s1。要不破坏字符串 s1，只有用一个新串来存放处理结果；要用到新串，那么就需要重新分配空间。第(1)空在第一个循环体中，此循环体的作用在注释中已经给出，用来统计串 s2在串 s1中出现的次数，这里的统计变量已经给出，并将结果存放在统计变量
18、i中，但每次统计成功后串 s1的位置应该往后移动串 s2的长度，由程序我们可以看出，串 s1存放在指针变量 p中，因此，指针变量 p指的位置需要往后移动串 s2的长度，而串 s2的长度存放在变量 12中。因此，此空答案为 p+=12。第(2)空很明显是用来给变量 i赋一个值，但根据 s=r=(char*)malloc(i)语句我们可以推断出，当前变量i中存放的是新串的长度。而新串的长度应该等于串 s1的长度减去串中 x个串 s2的长度，加上 x个串 s3的长度再加 1，而在上面的循环中已经求出了串 s2在串 s1中出现的次数，结果存放在变量 i中。因此，此空答案为 strlen(sl)-i*1
19、2+i*13+1。第(3)空是在 if(q !=NULL)成立的情况下运行的语句，而变量 q指向的是 s2在 s1中首次出现的位置，如果条件成立，说明串 s2在串 s1中出现了，语句 i=q-p用来表示出现的位置到 s1开始位置的距离。在这些条件都清楚了后，应该往新的串中写字符了，首先写串 s1的前 i个字符，此空就是用来完成这个功能的，因此，此空答案为 strncpy(r,p,i)。第(4)空是接着上一空而来的，在上面我们分析到，把串 s1的前 i个字符写入新串，那么在新串中接着要出现的应该是替换串 s2的串 s3，此空的任务应该是将串 s3写入新串中，因此，此空答案为strcpy(r,s3
20、)。第(5)空是在 if(q !=NULL)不成立的情况下运行的语句，这说明串 s2不在串 s1中出现，在这种情况下，串应该不需要进行替换操作，而直接将串 s1写入到新串中，此空的作用就是用来实现这个功能的，因此，此空答案为 strcpy(r,p)。二、试题二(总题数：1，分数：15.00)2.1说明】本程序可以打印出如下图形(菱形)：*【函数 2.1】main()int i,j,k;for(i=0;i=3;i+)for(j=0;j=2-i;j+)printf(“ “);for( (1) )printf(“*“);printf(“/n“);for(i=0;i=2;i+)for( (2) )pr
21、intf(“ “);for(k=0;k=4-2*i;k+)printf(“*“);printf(“/n“);【函数 2.2说明】通过本程序，可以从键盘输入一个字符串，将小写字母全部转换成大写字母，然后输出到一个磁盘文件“CsaiWgm”中保存，输入的字符串以“!”结束。【函数 2.2】#include “stdio.h“main()FILE *fp;char str100,filename10;int i=0;if(fp=fopen(“CsaiWgm“,“w“)=NULL)printf(“cannot open the file/n“);exit(0);printf(“please input
22、 a string:/n“);gets(str);while( (3) )if(stri=afputc(stri,fp);(5) ;fclose(fp);fp=fopen(“CsaiWgm“,“r“);fgets(str,stden(str)+1,fp);printf(“%s/n“,str);fclose(fp);（分数：15.00）_正确答案：(1)k=0;k=2*i;k+ (2)j=0;j=i;j+ (3)stri!=!(4)stri-32 (5)i+)解析：分析本题考查用 C语言实现菱形的输出与大小写字母的转换。在函数 2.1中，题目要求实现对菱形的输出，从图中可以看出每行的“*”字符个
23、数为(2行号-1)，最长的一行其长度为 8个“*”字符，最短的一行是 1个“*”字符，从最短到最长一共是 4行。下面来分析代码。第(1)空是第二重循环的循环条件，从程序中可以推断出这个循环的作用是用来输出一行的“*”字符，根据上面的分析，每行的“*”字符个数为(2行号-1)可以得到循环的上界，再结合程序可以知道此空用的变量是 k，而每行的行号存放在变量 i中，因此，此空答案为 k=0;k=2*i;k+。第(2)空在第二个二重循环下面，这个二重循环用来输出图形中下半部分，此空是循环的条件。由于菱形具有对称性，我们可以对照程序上面相应的循环中的条件，很容易就可以得到结果，此空答案为j=0;j=i;
24、j+。在函数 2.2中，题目要求从键盘输入一个字符串，将小写字母全部转换成大写字母，然后输出到一个磁盘文件 CsaiWgm中保存。此题的关键在于如何将小写字母变成大写字母。第(3)空是循环的循环条件，从程序中可以推断出这个循环的作用是用来将字符串的小写字母全部转换成大写字母，那么可以知道循环的条件是只要取到的字符不为结束字符“!”，循环就继续，因此，此空答案为 stri!=!。第(4)空是条件判断语句下面的语句，根据程序给出的代码不难发现，如果此条件判断语句结果为真，说明当前取到的字符是小写字母，那么应该将其转换为大写字母，因此，此空答案为 stri-32。第(5)空是循环的最后一条语句，从程
25、序中不难发现，循环对字符串的位置没有移动，那么此空应该用来实现对字符串位置的往后移动。而记录当前字符串位置的是变量 i，因此，此空答案为 i+。三、试题三(总题数：1，分数：15.00)3.【说明】设 M叉树采用列表法表示，即每棵子树对应一个列表，列表的结构为：子树根结点的值后跟用“()”括起来的各子树的列表(若有子树的话)，各子树的列表间用“，”分隔。例如，如下图所示的三叉树可用列表a(b(c,d),e,f(g,h,i)表示。本程序根据输入的列表生成一棵 M叉树，并由 M叉树再输出列表。（分数：15.00）_正确答案：(1)(NODE*)malloc(sizeof(NODE)(2)makeT
26、ree()(3)*str(4)putchar(t-val)(5)walkTree(t-subTreei)解析：分析本题考查在 C语言中实现用列表表示 M叉树。题目要求程序根据输入的列表生成一棵 M叉树，并由 M叉树再输出列表。题目中给出了列表与树的对应关系，从这种对应关系中我们可以看出，每个结点后紧跟的那层括号下结点的个数就是这个根结点的孩子个数，用列表表示得到的序列有点像树的先序遍历，因此，根据列表来生成 M叉树时，应该是首先生成左子树，然后才依次往右的生成过程。下面来具体分析代码。第(1)空很明显是给变量 s赋一个初值，从程序中可以知道，变量 s是一个指向 NODE型结点的指针变量，但程序
27、中并没有给出这样的结点，那么此空应该是动态创建一个这样的结点。在 C语言中，动态分配空间要用函数 malloc()，因此，此空答案为(NODE*)malloc(sizeof(NODE)。第(2)空在循环体中，从程序中不难推断出此循环体的作用是由列表生成 M叉树，此空是给 s-subTreek这个指针数组赋值，这个数组中存放的是当前结点的孩子结点的指针，在树的生成过程中是根据列表来递归生成其对应的三叉树的，此空应该是递归调用生成结点的函数 makeTree()。因此，此空答案为 makeTree()。第(3)空是循环结束的判断条件，而这个循环的作用是根据列表来生成三叉树，只有列表的所有元素都被考
28、虑了循环才结束。从程序中可以知道列表的元素存放在数组中，指针变量 s廿指向这个数组，且在程序中对列表的操作都是通过指针变量 str来实现的，因此，此空答案为*str。第(4)空在条件判断语句下面，此条件判断语句结果为真，说明当前取到的是结点，接下来应该把该结点的值写入列表中，从后面的程序我们很容易知道实现此功能的函数，因此，此空答案为 putchar(t-val)。第(5)空在一个循环体下面，根据循环的条件，可以推断出这是对一个结点的所有孩子结点进行循环搜索。由 M叉树生成列表可以说是由列表生成 M叉树的逆过程，需要对树中的每个结点进行检索来生成列表，这里也要用到递归调用，而这个函数的当前检索
29、的结点指针为 t-subTreei。因此，此空答案为walkTree(t-subTreei)。四、试题四(总题数：1，分数：15.00)4.【说明】本程序利用非递归算法实现二叉树后序遍历。【函数】#includestdio.h#includestdlib.htypedef struct node/*二叉树的结点数据结构类型*/char data;struct node *left;struct node *right;BTREE;void SortTreelnsert(BTREE *tree, BTREE *s)if(*tree=NULL)*tree=s;elseif(s-data(*tree
30、)-data)SortTreelnsert( (1) ,s);else if(s-data=(*tree)-data)SortTreelnsert( (2) ,s);void TraversalTree(BTREE *tree)BTREE *stack1 000,*p;int tag1000,top=0;p=tree;dowhile(p !=NULL)stack+top=p;(3) ;tagtop=0; /*标记栈顶结点的左子树已进行过后序遍历*/while(top0putchar(p-data);if(top0)/*对栈顶结点的右子树进行后序遍历*/(5) ;tagtop=1;while(t
31、op0);void PrintSortTree(BTREE *tree)if(tree !=NULL)printSortTree(tree-left);putchar(tree-data);pdntSortTree(tree-right);main()BTREE *root=NULL, *node;char ch;ch=getchar();while(ch !=#)node=(BTREE*)malloc(sizeof(BTREE);node-data=ch;node-left=node-right=NULL;SortTreelnsert(ch=getchar();PrintSortTree(r
32、oot);putchar(/n);TraversalTree(root);（分数：15.00）_正确答案：(1)const int MAXRESULTBIT=500;class LargeNumberint i,j;int temp;int oneMAXINPUTBIT+1;int onebit; /one的位数int twoMAXINPUTBIT+1;int twobit; /two的位数int resultMAXRESULTBIT+1;public:LargeNumber();LargeNumber();int inputone(); /出错返叫 0，否则返回 1int inputtwo(
33、); /同上void multiplication(); /乘void clearresult(); /清零void showresult(); /显示;LargeNumberLargeNumber()for(i=0;i=MAXINPUTBIT;i+)onei=0;twoi=0;onebit=0;twobit=0;inputone();inputtwo();LargeNumberLargeNumber()int LargeNumberinputone()char NumberMAXINPUTBIT+1;cout“Please enter one:“;cinNumber;i=0;j=MAXINP
34、UTBIT;while(Numberi!=/0)i+;onebit=i;for(i-;i=0;i-,j-)if(int(Numberi)=48 /由字符转换为数字elsereturn 0;return 1;int LargeNumberinputtwo()char NumberMAXINPUTBIT+1;cout“Please enter two:“;cinNumber;i=0;j=MAXINPUTBIT;while(Numberi!=/0)i+;twobit=i;for(i-;i=0;i-,j-)if(int(Numberi)=48 /由字符转换为数字elsereturn 0;return
35、1;void LargeNumbermultiplication() /乘法clearresult();int m;for(i=MAXINPUTBIT;i=0;i-)temp=twoi;for(j= (2) ,m=MAXINPUTBIT;m=0;m-,j-)resultj+=temp*onem;if(resultj9)resultj-1+=resultj/10;(3) ;cout“one*two=“;showresult();void LargeNumbershowresult()i=0;while(resulti=0if(iMAXRESULTBIT)cout“0“; /输出 0for(;i=
36、MAXRESULTBIT;i+)cout (4) ;coutendl;void LargeNumberclearresult()for(i=0;i=MAXRESULTBIT;i+)(5) ;void main()LargeNumber a;a.multiplication();（分数：15.00）_正确答案：(1)onej=int(Numberi-48)(2)MAXRESULTBIT-(MAXINPUTBIT-i)(3)resultj%=10(4)resulti(5)resulti=0)解析：分析本题考查用 C+实现大整数的乘法运算。题目要求程序能实现从键盘任意输入的两个大整数的乘法运算。在程
37、序中定义了一个大整数类，在类中抽象了大整数的一些属性，如长度等，还声明了一些操作，有对大整数输入的操作和对大整数求乘积的操作等。下面来具体分析程序。第(1)空在第一个大整数的输入函数中，根据此空后面的注释我们知道，其功能是把字符转换为数字。在这里需要注意的是，从键盘输入的是字符型的一串字符，此空所在的条件判断语句是用来把这串字符中的数字找出来，接下来就是此空，要求把字符型的数字转换为整型的数字，而字符型数字与整型数字之间的ASC码值相差 48。从第二个大整数的输入函数中，我们也可以很容易知道此空答案为 onej=int(Numberi-48)。第(2)空在对大整数求乘积的函数中，是一个循环的初
38、始条件，从程序中不难看出，这个二重循环是用来实现对两个大整数求乘积的，而变量 j是用来存放计算结果数组的当前下标的，根据乘法的规则，不难得出此空答案为 MAXRESULTBIT-(MAXINPUTBIT-i)。第(3)空也在求积的二重循环中，它是在语句 if(resultj9)为真的情况下执行的语句，如果这个条件为真，说明当前需要进位，但到底是进几位，进位后余下的数又应该是多少呢?这就是这个条件判断语句下要完成的任务，从程序中不难看出，对于到底进几位这个问题已经解决，剩下的就是对进位后余数的处理，此空的任务就是求出进位后的余数并存放到数组的当前位置。所以，此空答案为 resultj%=10。第(4)空在输出计算结果的函数中，从程序中可以看出，此空在_个循环中，循环的作用是输出计算结果，而计算结果存放在数组中，因此，这个循环是用来输出数组中的所有元素。因此，此空答案为 resulti。第(5)空是在清除计算结果的函数中，函数中只有一个循环，此空就在循环下面，计算结果存放在数组中，要清除计算结果就是把数组清零，那么此空的任务是把数组中的每个元素变成零，因此，此空答案为resulti=0。
