1、初级程序员下午试题-56 及答案解析(总分：90.00，做题时间：90 分钟)一、B试题一/B(总题数：1，分数：15.00)1.【说明】 已知头指针分别为 La和 lb的有序单链表，其数据元素都是按值非递减排列。现要归并 La和 Lb得到单链表 Lc，使得 Lc中的元素按值非递减排列。程序流程图如下所示： （分数：15.00）_二、B试题二/B(总题数：1，分数：15.00)2.【程序 2.1说明】 已知一个排好序的数组，现输入一个数，要求按原来的顺序规律，将它插入到数组中。 【程序 2.1】 #include stdioh #define N 100 void main() float a
2、N+l,x; int i,p; printf(“输入已经排好序的数列： “); for(i=0; iN; i+) scanf(%f“, printf(“输入要插入的数：“); scanf(“%f“, for(i=0,p=N; iN; i+) if(xai) U(1) /U break; for(i=N-1; i=p; i-) U (2) /U U(3) /U for(i=0; i=N; i+) prinff(“%f/t“,ai); 【程序 2.2说明】 本程序用变量 count统计文件中字符的个数。 【程序2.2】 #include stdio.h #include stdlib.h void
3、 main() FILE *fp; long count=0; if(fp=fopen(“letter.txt“,“r“)=NULL) printf(“can not open file/n“); exit(0); while(!feof(fp) U (4) /U count+; printf(“count=%d/n“,count); U (5) /U （分数：15.00）_三、B试题三/B(总题数：1，分数：15.00)3.【说明】Fibonacci数列 A=1，1，2，2，5，8，)有如下性质：a0=a1=1ai=ai-1+ai-2，i1对于给定的 n，另外有一个由 n个元素组成的数列 x
4、n，该数列中各元素的值为：xi=ai/ai+1，i=0，1，n现要求对 xn中的元素按升序进行排序，然后以分数形式输出排序后的 xn。例如 n=5时，排序前的xn=1/1，1/2,2/3,3/5,5/8，排序后的 xn=1/2,3/5,5/8,2/3,1/1。程序中函数 make()首先生成排序前的 xn，然后调用函数 sort()进行排序，最后输出所求结果。【程序】#include stdio.h#include stdlib.h#include malloc.hstruct factlong m,n;void sort(int n,struct fact *p)int a;long s,t
5、,u,v;struct fact *q,*end;for(end=p+(n-1),a=1;a;end-)for(a=0,q=p;qend;p+)s=q-m;t=q-n;u=(q+1)-m;v=(q+1)-n;if(U (1) /U)q-m=u;U (2) /UU (3) /U(q+1)-n=t;a=1;void make(int n)int i;long a,b,c;struct fact *x,*y;x=(struct fact *)malloc(sizeof(struct fact)*n);x-m=1:x-n=1;for(a=1,b=1,i=2;i=n;i+)U (4) /Ua=b;b=c
6、;(x+(i-1)-m=a;(x+(i-1)-n=b;U (5) /Uprintf(“x%d=%1d/%1d“,n,x-m,x-n);for(y=x+1;yx+n;y+)printf(“,%1d/%1d“,y-m,y-n);printf(“/n“);free(x);void main()int n;printf(“input n:“);scanf(“%d“,make(n);（分数：15.00）_四、B试题四/B(总题数：1，分数：15.00)4.【说明】本程序对某电码文(原文)进行加密形成密码文，其加密算法如下：假定原文为 C1,C2,C3,，C n加密后形成的密文为 S1,S2,S3,，S
7、n，首先读入正整数 key(key1)作为加密钥匙，并将密文字符位置按顺时针方向连成一个环，如下图所示：（分数：15.00）_五、B试题五/B(总题数：1，分数：15.00)5.【说明】 字符串在程序设计中扮演着重要角色。现需要设计字符串基类 string，包含设置字 符串、返回字符串长度及内容等功能。另有一个具有编辑功能的串类 edlt_string，派生于 string，在其中设置一个光标，使其能支持在光标处的插入、删除操作。 【程序】 #include iostream.h #include stdio.h #include string.h class string int lengt
8、h; char *data; public: int get_length() return length; char *get_data() return data; string() delete data; int set data(int in_length, char *in_data); int set_data(char *data); void print() coutdataendl; ; class edit_string: public string int cursor; public: int get_cursor() return cursor; void move
9、_cursor(int dis) cursor=dis; int add_data(string *new_data); void delete_data(int num); ; int string:set_data(int in_length,char *in_data) length=in_length; if(!data) delete data; U (1) /U strcpy(data,in_data); return length; int string:set data(char *in_data) U (2) /U if(!data) delete data; U (1) /
10、U strcpy(data,in_data); return length; int edit_string:add_data(string *new_data) int n,k,m; char *cp,*pt; n=new_data-get_length(); pt=new_data-get_data(); cp=this-get_data(); m=this-get_length(); char *news=new charn+m+1; for(int i=0; icursor; i+) newsi=cpi; k=i; for(int j=0; jn; i+,j+) newsi=ptj;
11、cursor=i; for(j=k; jm; j+,i+) U (3) /U newsi=/0; U (4) /U delete news; return cursor; void edit string:delete_data( int num) int m; char *cp; cp=this-get_data(); m=this-get_length(); for(int i=cursor; im; i+) U (5) /U cpi=/0; （分数：15.00）_六、B试题六/B(总题数：1，分数：15.00)6.【说明】 IC 卡和 200卡都是从电话卡派生的。下面的程序将电话卡定义为
12、抽象类。其中 balance 为双精度变量，代表电话卡中的余额；cardNumber 是长整型变量，代表电话卡的卡号；password 是整型变量，代表电话卡的密码；connectNumber 是字符串变量，代表电话卡的接入号码；connected 是布尔变量，代表电话是否接通。 performDial()实现各种电话接通后的扣除费用的操作。其中 200卡每次通话扣除 0.5元的通话费用和附加费用；IC 卡每次通话扣除 0.9元的通话费。TimeLeft()方法用于测试电话卡余额还可以拨打电话的次数。performConnection()用于电话接入操作，如果卡号和密码正确，则接通；否则，接不
13、通。 【程序】 abstract class PhoneCard doubte balace; U (1) /UperfermDial(); double getBalance() return balance; double TimeLeft() double current=balance; int times=0; do U (2) /U times+; white(balance=0); balance=current; return times-1; abstract class Number_PhoneCard extends PhoneCard long cardNumber:
14、int password; String connectNumber; Boolean connected; Boolean performConnection(long cn, int pw) if(cn=cardNumber return true; else return false; class IC CardU (4) /U boolean performDial() if(balance0.9) balance-=0.9; return true; else return false; class D200_CardU (4) /U static double additoryFe
15、e; static additoryFee=0.1; boolean performDial() if(balance(0,5+additeryFee) U (5) /U return true; else return false; （分数：15.00）_初级程序员下午试题-56 答案解析(总分：90.00，做题时间：90 分钟)一、B试题一/B(总题数：1，分数：15.00)1.【说明】 已知头指针分别为 La和 lb的有序单链表，其数据元素都是按值非递减排列。现要归并 La和 Lb得到单链表 Lc，使得 Lc中的元素按值非递减排列。程序流程图如下所示： （分数：15.00）_正确答案：(
16、)解析：(1)pa-data=pb-data (2)pc-next=pa (3)pc=pb (4)pb=pb-next (5)pc-next=pa?pa:pb 分析 本题考查程序流程图和有序链表的归并。 题目要求我们归并头指针分别为 La和 Lb的有序单链表，组成一个新的有序单链表 Lc，而 Lc又是指向 La的。首先，我们来了解一下单链表的结构。单链表中一般有两个域，一个是数据域，用来存放链表中的数据；另一个是指针域，用来存放指向下个结点的指针。其归并的过程应该是先比较链表 La和 Lb中第一个元素，将较小的从其链表中取出放到 k中，再取下一个结点的值去比较，重复这个过程，直到一个链表被全部
17、取完，再将另一个链表剩下的部分连接到 Lc后面即可。 下面，我们来看程序流程图的内容。首先是用两个指针变量 pa和 pb分别指向La和 Lb的当前待比较插入的结点，而 pc指向 Lc表中当前最后一个结点。再下面是一个条件判断语句，其作用是判断链表 La和 Lb是否为空，如果有一个为空，只要将另一个链表剩下的部分连接到 Lc后面，程序应该就可以结束了。 第(1)空是条件判断语句的条件，根据我们上面的分析，再结合流程图下面的内容，我们可以知道，这个条件语句的作用是比较当前待插入的两个值的大小，而指针变量 pa和 pb分别指向 La和 Lb的当前待比较插入的结点，因此，此空的答案为 pa-data=
18、pb-data。 第(2)空是在条件为真的情况下执行的语句，如果条件判断为真，应该将 pa所指结点连接到 pc所指结点后面，因此，pc所指结点的指针域应该存放 pa所指结点的地址。所以，此空的答案为 pc-next=pa。 第(3)空和第(4)空都是在条件为假的情况下执行的语句，如果条件为假，说明 pb 所指结点的值小于 pa所指结点的值，应该将 pb所指结点连接到 pc所指结点后面，图中已经实现这一功能，要我们完成的是在插入后的后继工作。由于 pc指向的是 Lc表中当前最后一个结点，在插入一个结点后，要修改 pc的值。在将 pb所指结点插入后，链表中的最后一个结点就是 pb所指结点，第(3)
19、空的答案应该为 pc=pb。执行完这些功能后，指针 pb应该要往后移动，即指向下一个结点，第(4)用来完成这个功能，所以答案为 pb=pb-next。 在前面，我们已经讲到如果链表 La和 Lb有一个为空，只要将另一个链表剩下的部分连接到 Lc后面即可。第(5)空就是用来完成这个功能的，但我们不知道具体是哪个链表为空，还需要判断，因此，此空答案为pc-next=pa?pa:pb。二、B试题二/B(总题数：1，分数：15.00)2.【程序 2.1说明】 已知一个排好序的数组，现输入一个数，要求按原来的顺序规律，将它插入到数组中。 【程序 2.1】 #include stdioh #define
20、N 100 void main() float aN+l,x; int i,p; printf(“输入已经排好序的数列： “); for(i=0; iN; i+) scanf(%f“, printf(“输入要插入的数：“); scanf(“%f“, for(i=0,p=N; iN; i+) if(xai) U(1) /U break; for(i=N-1; i=p; i-) U (2) /U U(3) /U for(i=0; i=N; i+) prinff(“%f/t“,ai); 【程序 2.2说明】 本程序用变量 count统计文件中字符的个数。 【程序2.2】 #include stdio
21、.h #include stdlib.h void main() FILE *fp; long count=0; if(fp=fopen(“letter.txt“,“r“)=NULL) printf(“can not open file/n“); exit(0); while(!feof(fp) U (4) /U count+; printf(“count=%d/n“,count); U (5) /U （分数：15.00）_正确答案：()解析：(1)p=i (2)ai+1=ai; (3)ap=x; (4)fgetc(fp); (5)fclose(fp); 分析 本题考查在 C语言中实现对数组的
22、插入和对文件中字符个数的统计。 我们先来看程序 2.1。题目要求在程序 2.1中实现在排好序的数组中插入一个数，但不能改变数组中数字排序的规律。由于数组是已经排好序的，它有可能是按不递减的方法排序，也有可能是按不递增的方法排序。在插入时，从数组中第一个数开始，逐个进行比较，直到找到比其大或相等的数，在其前面进行插入，在插入前应该先将数组中的元素逐个后移。 下面我们来看代码。代码中有三个循环，第(1)空在第一个循环体下面的条件判断语句里，条件判断语句是判断要插入的数 J与数组中元素的大小，如果数 x小于数组中的元素，就执行第(1)空的语句。从上面的分析，再结合第二个循环语句的条件，我们可以知道，
23、此空的作用是记录数要插入的位置，并把这个结果存放在变量 p中，所以，答案为 p=i。 第(2)空所在的位置是第二个循环体下面，根据分析，要完成的任务应该是将数组中要插入位置后的元素逐个往后移动。所以，此空的答案为 ai+1=ai。 在完成了上述两空之后，再结合整个程序来看，很明显还有一个功能没有完成，那就是插入数 x，第(3)空就是用于完成这个任务的。由于在代码的前面已经记录下了要插入的位置，所以，此空答案为 ap=x。 在程序 2.2中，题目要求完成的任务是用变量 count统计文件中字符的个数，要实现对文件中字符个数的统计，首先需要我们判断出哪些是字符，这就涉及 C语言中对文件中字符的判定
24、。此外，还需要我们掌握对文件的基本操作。 下面，我们来看程序 2.2的代码。首先用一个条件判断语句来打开一个文件，如果打开成功，则执行下面的 while循环语句，循环体的功能是对文件中的内容逐个判断，如果是字符，则统计变量count加 1，因此，第(4)空的功能就是要找出文件中的所有字符。这里没有条件判断语句来判段是否是字符，需要用到 C语言中对文件处理的一个函数 fgetc()，其作用是可以取出文件中所有的字符，因此，此空答案为 fgetc(fp)。 第(5)空在代码的最后面，如果我们对文件操作很熟悉的话，不难发现文件在打开后还没有关闭，此空要实现的功能是关闭文件，因此，此空答案为 fclo
25、se(fp)。三、B试题三/B(总题数：1，分数：15.00)3.【说明】Fibonacci数列 A=1，1，2，2，5，8，)有如下性质：a0=a1=1ai=ai-1+ai-2，i1对于给定的 n，另外有一个由 n个元素组成的数列 xn，该数列中各元素的值为：xi=ai/ai+1，i=0，1，n现要求对 xn中的元素按升序进行排序，然后以分数形式输出排序后的 xn。例如 n=5时，排序前的xn=1/1，1/2,2/3,3/5,5/8，排序后的 xn=1/2,3/5,5/8,2/3,1/1。程序中函数 make()首先生成排序前的 xn，然后调用函数 sort()进行排序，最后输出所求结果。【
26、程序】#include stdio.h#include stdlib.h#include malloc.hstruct factlong m,n;void sort(int n,struct fact *p)int a;long s,t,u,v;struct fact *q,*end;for(end=p+(n-1),a=1;a;end-)for(a=0,q=p;qend;p+)s=q-m;t=q-n;u=(q+1)-m;v=(q+1)-n;if(U (1) /U)q-m=u;U (2) /UU (3) /U(q+1)-n=t;a=1;void make(int n)int i;long a,b
27、,c;struct fact *x,*y;x=(struct fact *)malloc(sizeof(struct fact)*n);x-m=1:x-n=1;for(a=1,b=1,i=2;i=n;i+)U (4) /Ua=b;b=c;(x+(i-1)-m=a;(x+(i-1)-n=b;U (5) /Uprintf(“x%d=%1d/%1d“,n,x-m,x-n);for(y=x+1;yx+n;y+)printf(“,%1d/%1d“,y-m,y-n);printf(“/n“);free(x);void main()int n;printf(“input n:“);scanf(“%d“,ma
28、ke(n);（分数：15.00）_正确答案：()解析：(1)s*v=t*u (2)q-n=v; (3)(q+1)-m=s;(4)c=a+b; (5)sort(n,x);分析本题考查在 C语言中实现对数列的排序。题目要求我们对 xn中的元素按升序进行排序，然后以分数形式输出排序后的 xn，程序中函数 make()用来生成排序前的 xn，而使用函数 sort()进行排序。在生成排序前的 xn以前，我们应该仔细理解题目中给出的生成规则。首先，我们来看函数 sort()，此函数的功能是排序。在函数体中我们可以看到它是用双重循环来实现对数列元素排序的，从整个函数我们可以分析出它排序的方法是从数列中找出一
29、个最大的数存放到数列的最后面，在下次循环时，再从剩下的部分找出其最大的数存放到剩下部分的最后面，这样直到整个数列排好序。第(1)空是一个条件判断语句的条件，在第二重循环下面，根据上面的分析，该循环的作用是在数列中找出最大的数，那么，这个条件判断语句应该是判断相临两个数的大小，再结合程序中的内容，此空的答案应该是 s*v=t*u。第(2)空和第(3)空是条件判断语句结果为真的情况下执行的语句，如果条件为真，则说明前面的数要大于后面的数。而根据上面的分析，要将较大：的数放到后面位置，以方便下次和再后面的数比较，因此，这两个空的作用是要实现对两个数位置的交换，答案应该分别为 q-n=v 和(q+1)
30、-m=s。接着，我们来看函数 make()，它的功能是用来生成排序前的 xn，在生成数列时，我们应该注意 Fibonacci数列的性质，它的每一项等于前两项的和。在函数体中，我们可以发现第一个循环体就是用来生成排序前的 zn的。第(4)空就在循环体内，我们仔细看代码，就可以发现变量 c没有初值，但后面又把变量 c的值赋给了变量 b，因此，第(4)空应该是给变量 c赋初值，但应该给它一个什么样的初值呢?结合 Fibonacci数列的性质 a i=ai-1+ai-2，我们很容易知道变量 c存放的就是 ai的值。因此，此空答案为 c=a+b。第(5)空是在循环体下面，上面我们已经说到，循环体生成了排
31、序前的 xn，根据题目的要求，应该要调用函数 sort()进行排序了，因此，此空答案为 sort(n,x)。四、B试题四/B(总题数：1，分数：15.00)4.【说明】本程序对某电码文(原文)进行加密形成密码文，其加密算法如下：假定原文为 C1,C2,C3,，C n加密后形成的密文为 S1,S2,S3,，S n，首先读入正整数 key(key1)作为加密钥匙，并将密文字符位置按顺时针方向连成一个环，如下图所示：（分数：15.00）_正确答案：()解析：(1)loopi.backward=(2)looplength-1.backward=(3)p-ch=*old+;(4)p=p-forward;
32、(5)Newi=loopi.ch;分析本题考查加密算法在 C语言中的实现及双向循环链的生成。题目给出了具体加密算法的过程，要求函数 decode用于将原文 old加密并返回密文字符数组的首指针，并告诉我们函数采用一个双向循环链表 CODE来表示密文环。函数 strlen 用于计算一个字符串中的字符个数在程序中已经实现。下面，我们来看程序。根据题目给出的条件，我们知道函数 decode的基本功能和一些其他的性质。在函数 decode中，loop=(CODE*)malloc(length*sizeof(CODE)要求动态分配能存放 length个 CODE类型的内存空间，这说明分配了 length
33、个 CODE链表结点的空间，并把其首地址存放到指针变量 loop中。但题目要求 CODE链表是双向循环链表，因此，还需要将这些结点连接起来使其成为双向循环链表。程序通过一个循环语句来对除首结点和尾结点外的其他结点的前后指针域赋值，使 forward指针域指向其后一个结点，使 backward指针域指向其前一个结点。因此第(1)空的答案出来了，是 loopi.backward= char *data; public: int get_length() return length; char *get_data() return data; string() delete data; int se
34、t data(int in_length, char *in_data); int set_data(char *data); void print() coutdataendl; ; class edit_string: public string int cursor; public: int get_cursor() return cursor; void move_cursor(int dis) cursor=dis; int add_data(string *new_data); void delete_data(int num); ; int string:set_data(int
35、 in_length,char *in_data) length=in_length; if(!data) delete data; U (1) /U strcpy(data,in_data); return length; int string:set data(char *in_data) U (2) /U if(!data) delete data; U (1) /U strcpy(data,in_data); return length; int edit_string:add_data(string *new_data) int n,k,m; char *cp,*pt; n=new_
36、data-get_length(); pt=new_data-get_data(); cp=this-get_data(); m=this-get_length(); char *news=new charn+m+1; for(int i=0; icursor; i+) newsi=cpi; k=i; for(int j=0; jn; i+,j+) newsi=ptj; cursor=i; for(j=k; jm; j+,i+) U (3) /U newsi=/0; U (4) /U delete news; return cursor; void edit string:delete_dat
37、a( int num) int m; char *cp; cp=this-get_data(); m=this-get_length(); for(int i=cursor; im; i+) U (5) /U cpi=/0; （分数：15.00）_正确答案：()解析：(1)data=new charlength+1; (2)length=strlen(in_data); (3)newsi=cpj; (4)set_data(news); (5)cpi=cpi+num; 分析 本题考查 C+中字符串的操作。 字符是程序设计中常用的一种数据类型，而字符串表示一串字符，在程序设计中扮演着重要角色，是考
38、试中常出现的内容。题目要求设计一个基类能实现字符串设置、返回字符串长度及内容等功能，设计一个子类能支持在光标处的插入、删除操作。 下面我们来看代码。首先定义了一个 string基类，在 string基类中，声明了两个成员变量和几个成员函数。接着定义了一个继承 string类的派生类 edit_string。再下面是对类中成员函数的实现。 第(1)空在 set_data()函数体中，int string:set_data()表明此函数是基类中的成员函数，根据基类要实现的功能，此函数要实现返回字符串长度和设置其内容，在函数体中其长度已经给出，但分配存储空间被 delete data删除掉了，应该重
39、新分配，在 C+中一般用关键字 new实现空间的动态分配。因此，第(1)空的答案是 data=new charlength+1。 第(2)空在另一个 set_data()函数体中，这两个函数同名，但参数不同，这是 C+ 中用同名函数实现多态的技巧。此函数功能同上一个函数，但它的形参中没有指明字符串的长度，因此，在函数开始时要求出字符串的长度，用函数 strlen()。所以，此空答案为 length=strlen(in_data)。 第(3)空和第(4)空在函数 add_data()中，此函数是派生类中的成员函数，根据题目要求它要实现的功能是在光标处进行插入。在此函数体中重新分配了一块内存空间，
40、其长度是原有字符串长度和要插入字符串长度之和加 1，用来存放这两个字符串。第(3)空所在的位置是循环体下面，根据循环体的判断条件 im 我们可以想到这是要对长度为 m的字符串进行插入。因此，此空答案为newsi=cpj。而第(4)空是在完成了插入工作以后，根据程序上下文推断，应该是计算字符长度并返回，因此，答案为 Set_data(news)。 第(5)空在函数 delete_data()中，根据题目要求，此函数应该是实现子类在光标处进行删除的功能。删除一般采用覆盖技术，即将后面的字符往前移动来覆盖掉要删除的字符，第(5)空实现的就是这个功能，要删除 num个字符，后面的字符应该往前移动 nu
41、m，因此，此空答案为cpi=cpi+num。六、B试题六/B(总题数：1，分数：15.00)6.【说明】 IC 卡和 200卡都是从电话卡派生的。下面的程序将电话卡定义为抽象类。其中 balance 为双精度变量，代表电话卡中的余额；cardNumber 是长整型变量，代表电话卡的卡号；password 是整型变量，代表电话卡的密码；connectNumber 是字符串变量，代表电话卡的接入号码；connected 是布尔变量，代表电话是否接通。 performDial()实现各种电话接通后的扣除费用的操作。其中 200卡每次通话扣除 0.5元的通话费用和附加费用；IC 卡每次通话扣除 0.9
42、元的通话费。TimeLeft()方法用于测试电话卡余额还可以拨打电话的次数。performConnection()用于电话接入操作，如果卡号和密码正确，则接通；否则，接不通。 【程序】 abstract class PhoneCard doubte balace; U (1) /UperfermDial(); double getBalance() return balance; double TimeLeft() double current=balance; int times=0; do U (2) /U times+; white(balance=0); balance=current
43、; return times-1; abstract class Number_PhoneCard extends PhoneCard long cardNumber: int password; String connectNumber; Boolean connected; Boolean performConnection(long cn, int pw) if(cn=cardNumber return true; else return false; class IC CardU (4) /U boolean performDial() if(balance0.9) balance-=0.9; return true; else return false; class D200_CardU (4) /U static double additoryFee; static additoryFee=0.1; boolean performDial() if(balance(0,5+additeryFe
