1、初级程序员下午试题-102 及答案解析(总分：90.00，做题时间：90 分钟)一、试题一(总题数：1，分数：15.00)说明下面流程图完成快速排序算法。快速排序法通过分割的方法来进行排序。其本质是把数组分成左右两个部分，在左边部分只保存数组中小于某个特定数值的那些数据，而在右边的部分保存数组中大于这个特定数值的那些数据，在两个部分之间插入这个特定的数值。当快速排序算法对数组的分割完成后，这个数值就在正确的排序位置了(这时它就没有必要继续和后面的数据比较了)，于是快速排序法产生了两个单独的数组。如果这两个数组不相关，单独排序，于是又产生了两个排序的单独数组，对这两个单独的表进行快速排序，重复上
2、述步骤直到所有的数据都处在各自适当的位置。注：快排函数定义为 run(data，left，right)，left 和 right分别为数组上下界。（分数：15.00）填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_二、试题二(总题数：1，分数：15.00)函数 2.1说明L为一个带头结点的循环链表。函数 deletenode(LinkList L，int c)的功能是删除 L中数据域 data的值大于 c的所有结点，并由这些结点组建成一个新的带头结点的循环链表，其头指针作为函数的返回值。函数 2.1LinkList deletenode(LinkList L, int c
3、)LinkList Lc，p，pre; pre=L;p= (1) ; Lc=(LinkList)malloc(sizeof(ListNode);Lc-next=Lc;while(p!=L)if(p-datac)(2) ;(3) ;Lc-next=p;p=pre-next;elsepre=p;p=pre-next;return Lc;函数 2.2说明递归函数 dec_to_k_2(int n，int k)的功能是将十进制正整数 n转换成 k(2k9)进制数，并打印。函数 2.2dec_to_k_2 (int n,int k)/将十进制正整数 n转换成 k(2k9)进制数。if(n!=0)dec_
4、to_k_2( (4) ，k); printf(“%d“， (5) ); （分数：15.00）填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_三、试题三(总题数：1，分数：15.00)说明函数 int psort(int a,int n)实现将含 n个整数的数组 a的不同元素按从小到大顺序存于数组 a中。实现方法是从未确定的元素列中找到最小元素并将 a的第 i最小元素交换至 ai位置。如该最小元素比已确定的最后一个最小元素大，则将它接在已确定的元素序列的后面; 否则，忽视该元素。函数int psort (int a ,int n)int i, j ,k,p;for(i=0
5、,k=0ji (1) ;i+) for(j=i+1, (2) ;jn;j+)if (apaj)p=j;if (p!=i) t=apap=ai;ai=t;if( (3) ) k+;else if ( (4) a i)(5) =ai; return k;int a=5,7,5,6,4,3,4,6,7;main()int k,n;for (k=0 ; k(sizeof a) /sizeof (int); k+)printf (“ %5d“ ,a k) ;printf (“/n/n“) ;n=psort (a, (sizeof (a) /sizeof (int);printf(“%5d“,ak);pr
6、intf (“/n/n“) ;（分数：15.00）填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_四、试题四(总题数：1，分数：15.00)说明从文件 IN.DAT中读取一篇英文文章存入到字符串数组 XX中; 请编写程序，其功能是：以行为单位把字符串中的所有小写字母 o左边的字符串内容移到该串的右边存放，然后把小写字母 o删除，余下的字符串内容移到已处理字符串的左边存放，最后把已处理的字符串仍按行重新存入字符串数组 XX中，最后调用函数 writedat()把结果 XX输出到文件 OUT5.DAT中。原始数据文件存放的格式是：每行的宽度均小于 80个字符，含标点符号和空格
7、。函数# include “stdio.h“# include “string.h“# include “conio.h“# include “ctype.h“# include “mem.h“unsigned char xx5080 ;int maxline=0;int readdat (void) ;void writedat (void) ;/*将题目要求的字符串中所有小写字母。左边的字符串内容移到该串的右边存放，即将串中*/*“最后”一个字母 o左右两侧的内容互换*/void StrOR (void)int i;char *p1, *p2 , t80;for (i=0;imaxline
8、; i+)p2=xx i ;while (*p2) /*找到最后一个,o */if ( (1) ) p1=p2p2+;strcat (t,p1+1) ;strcat (t,xx i) ;p1=xxi;p2=t ;while(*p2) /*删符o*/jf( (2) )( (3) )=*p2;p2+;(4) ;void main ()clrscr () ;if (readdat () printf(“Cant open the file IN.DAT!/n“);return;StrOR () ;writedat () ;int readdat (void)FILE *fp;int i=0;char
9、 *p;if (fp= fopen (“in.dat“ , “r“ =NULL)return 1;while (fgets (xx i , 80, fp)! =NULL)p=strchr (xx i, /n) ;if (p)i+;maxline= (5) ;fclose (fp) ;return 0;void writedat (void)FILE *fp;int i;fp=fopen (“in.dat “ , “w“) ;for (i=0; imaxline; i+)printf(“%s/n“,xxi);fprintf(fp, “%s/n“,xxi) ;fclose (fp) ;（分数：15
10、.00）填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_五、试题五(总题数：1，分数：15.00)说明阅读下面程序，指出其中代码的错误及原因。C+程序01 #include iostream.h02 class employee03 private:04 short age;05 float salary ;06 friend void funcl () ;07 protected:08 char* name;09 public:10 employee (char* nn, short ag, float salr) ;11 void print () const ;12
11、 employee () ;13 ;14 manage:public employee15 char* department;16 /.17 public:18 void print () ;19 void setEmployee () ;20 /.21 22 /.23 void manage:print ()24 25 cout “name: “ nameendl;26 cout“salary: “salaryendl; /- (1) 27 28 void manager:setEmployee(char* dept)29 30 employee:employee(char* nm,shor
12、t ag,float salr) ; /- (2) /- (3) 31 department=dept;32 33 void funcl ()34 35 cout “department:“department 11- (4) 36 “,name: “nameendl;37 /.38 39 void main ()40 41 employee aemp; /- (5) 42 manager amngr (“ Kng “ , 35, 578. 9);43 /.44 （分数：15.00）填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_六、试题六(总题数：1，分数：15.00)
13、说明下面程序输出一个矩形面积，以及矩形区域上的假想的作物产量。Java程序public class Mainjava public static void main(String args) Lot_size small = new Lot_size() ;Lot_size medium = new Lot_size();small.set (5,5,5,25) ;medium.set (10,10,10, 50) ;System.out.println(“For a small lot of area “+small.get_area () +“/n“);System.out.println
14、(“the actual crops are $“+small.get_data2 () +“ /n“) ;System.out.println(“and ideal crops are $“+small.get_data () +“/n“) ;System.out.println(“For a medium lot of area“+medium.get_area () +“/n“);system.out.println (“the actual crops are $ “+medium.get_data2 () +“/n “);System.out.println (“and ideal
15、crops are $“+medium.get_data () +“/n“);class Crop_assessmentprivate int actual_crop;private int ideal_crop;public void set(int in_actual,int in_ideal) actual_crop = in_actual;ideal_crop = in_ideal;public int get_actual_crop () return (1) ; public int get_ideal_crop() return (2) ;class Lot_sizeprivat
16、e int length;private int width;private Crop_assessment crop = (3) ;public void set(int 1,int w,int a,int i) length =1;width = w;crop.set (a,i) ;public int get_area () return lengt h*width; public int get_data() return (4) ; public int get_data2 () return (5) ;（分数：15.00）填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空
17、项 1:_初级程序员下午试题-102 答案解析(总分：90.00，做题时间：90 分钟)一、试题一(总题数：1，分数：15.00)说明下面流程图完成快速排序算法。快速排序法通过分割的方法来进行排序。其本质是把数组分成左右两个部分，在左边部分只保存数组中小于某个特定数值的那些数据，而在右边的部分保存数组中大于这个特定数值的那些数据，在两个部分之间插入这个特定的数值。当快速排序算法对数组的分割完成后，这个数值就在正确的排序位置了(这时它就没有必要继续和后面的数据比较了)，于是快速排序法产生了两个单独的数组。如果这两个数组不相关，单独排序，于是又产生了两个排序的单独数组，对这两个单独的表进行快速排序
18、，重复上述步骤直到所有的数据都处在各自适当的位置。注：快排函数定义为 run(data，left，right)，left 和 right分别为数组上下界。（分数：15.00）填空项 1:_ （正确答案：dataimid 且 iright）解析：填空项 1:_ （正确答案：datajmid 且 jleft）解析：填空项 1:_ （正确答案：i=i+1,j=j-1）解析：填空项 1:_ （正确答案：run(data,left,i)）解析：填空项 1:_ （正确答案：run(data,i,right)）解析：解析 本试题考查流程图。根据题目中给出的算法，再根据流程图，可以看出，算法取了数组的一个中间
19、值来作为某个特定的值，然后从左扫描大于中间值的数 datai，从右扫描小于中间值的数 dataj，找到后，经过位置判断(i=j)，将这一对数进行交换。由此，空(1)应填入 dataimid 且 iright，空(2)应填入 datajmid 且jleft.交换后，继续改变扫描界限下标，开始新一轮的寻找交换，空(3)应填入 i=i+1,j=j-1，直到两边扫描的下标交错，这说明已经将数组分成了有序的两部分。当左边部分有值(leftj)，递归左半边，当右边部分有值(righti)，递归右半边。因此，空(4)和空(5)分别填入 run(data，left，i)和run(data，i，right)。二
20、、试题二(总题数：1，分数：15.00)函数 2.1说明L为一个带头结点的循环链表。函数 deletenode(LinkList L，int c)的功能是删除 L中数据域 data的值大于 c的所有结点，并由这些结点组建成一个新的带头结点的循环链表，其头指针作为函数的返回值。函数 2.1LinkList deletenode(LinkList L, int c)LinkList Lc，p，pre; pre=L;p= (1) ; Lc=(LinkList)malloc(sizeof(ListNode);Lc-next=Lc;while(p!=L)if(p-datac)(2) ;(3) ;Lc-n
21、ext=p;p=pre-next;elsepre=p;p=pre-next;return Lc;函数 2.2说明递归函数 dec_to_k_2(int n，int k)的功能是将十进制正整数 n转换成 k(2k9)进制数，并打印。函数 2.2dec_to_k_2 (int n,int k)/将十进制正整数 n转换成 k(2k9)进制数。if(n!=0)dec_to_k_2( (4) ，k); printf(“%d“， (5) ); （分数：15.00）填空项 1:_ （正确答案：pre-next 或 L-next）解析：填空项 1:_ （正确答案：pre-next=p-next）解析：填空项
22、1:_ （正确答案：p-next=Lc-next）解析：填空项 1:_ （正确答案：n/k）解析：填空项 1:_ （正确答案：n%k）解析：解析 这一题共有两个函数，第一个函数是考查链表的删除和插入操作，第二个函数是考查递归函数。先看第一个函数。空(1)所在语句是对指针 p赋初值，通过下面的程序可以判断指针 pre所指的结点是指针 p所指的结点前驱结点，因此空(1)处应填写“pre-next”或“L-next”。空(2)、(3)所在的语句块是处理当指针 p所指的结点是一个大于 c的结点，则将该结点从链表 L中删除，再将它插入到链表 Lc中。由指针 pre和指针 p的关系，从链表中删除指针 p所
23、指结点很简单，只需将指针 pre的 next域修改为指针 p的 next域即可，因此空(2)处应填写“pre-next=p-next”或其等价形式。将指针 p所指的结点插入到链表 Lc的过程是，先将指针 p的 next域指向指针 1c的 next所指的结点，再将指针 1c的next指向指针 p所指的结点。因此空(3)处应填写“p-next=Lc-next”或其等价形式。再来分析第二个函数。将十进制正整数转换成 k进制数，采用除 k取余法。最开始得到余数作为 k进制数的最低位，最后得到的余数作为 k进制数的最高位。用 n不断地除以 k，直到商为 0。转换所得到的 k进制数是从低位开始生成，而输出
24、则应该从高位开始。根据这一特点，用递归法求解时，应先将 n/k转换成k进制，再输出 n%k。因此空(4)、空(5)处分别填写“n/k”、 “n%k”。当然这个问题也可以通过非递归的算法来完成，这样在转换过程中，需要一个栈来暂存 n除以 k所得到的各位余数。三、试题三(总题数：1，分数：15.00)说明函数 int psort(int a,int n)实现将含 n个整数的数组 a的不同元素按从小到大顺序存于数组 a中。实现方法是从未确定的元素列中找到最小元素并将 a的第 i最小元素交换至 ai位置。如该最小元素比已确定的最后一个最小元素大，则将它接在已确定的元素序列的后面; 否则，忽视该元素。函
25、数int psort (int a ,int n)int i, j ,k,p;for(i=0,k=0ji (1) ;i+) for(j=i+1, (2) ;jn;j+)if (apaj)p=j;if (p!=i) t=apap=ai;ai=t;if( (3) ) k+;else if ( (4) a i)(5) =ai; return k;int a=5,7,5,6,4,3,4,6,7;main()int k,n;for (k=0 ; k(sizeof a) /sizeof (int); k+)printf (“ %5d“ ,a k) ;printf (“/n/n“) ;n=psort (a,
26、 (sizeof (a) /sizeof (int);printf(“%5d“,ak);printf (“/n/n“) ;（分数：15.00）填空项 1:_ （正确答案：n-1）解析：填空项 1:_ （正确答案：P=i）解析：填空项 1:_ （正确答案：k=0）解析：填空项 1:_ （正确答案：ak-1）解析：填空项 1:_ （正确答案：ak+）解析：解析 本程序排序方法是从未确定的元素列中找到最小元素并将 a的第 i最小元素交换至 ai位置。如该最小元素比已确定的最后一个最小元素大，则将它接在已确定的元素序列的后面：否则，忽视该元素。这是采用选择法对数组元素进行排序，因此空(1)填 n-1，
27、空(2)填 P=i。若该最小元素比已确定的最后一个最小元素大，则将它接在已确定的元素序列的后面; 否则，忽视该元素。因此，空(3)填k=0，而当 ak-1ai时，则 ak+=ai，否则忽略元素 ai。所以空(4)填 ak-1，空(5)填 ak+。四、试题四(总题数：1，分数：15.00)说明从文件 IN.DAT中读取一篇英文文章存入到字符串数组 XX中; 请编写程序，其功能是：以行为单位把字符串中的所有小写字母 o左边的字符串内容移到该串的右边存放，然后把小写字母 o删除，余下的字符串内容移到已处理字符串的左边存放，最后把已处理的字符串仍按行重新存入字符串数组 XX中，最后调用函数 write
28、dat()把结果 XX输出到文件 OUT5.DAT中。原始数据文件存放的格式是：每行的宽度均小于 80个字符，含标点符号和空格。函数# include “stdio.h“# include “string.h“# include “conio.h“# include “ctype.h“# include “mem.h“unsigned char xx5080 ;int maxline=0;int readdat (void) ;void writedat (void) ;/*将题目要求的字符串中所有小写字母。左边的字符串内容移到该串的右边存放，即将串中*/*“最后”一个字母 o左右两侧的内容互
29、换*/void StrOR (void)int i;char *p1, *p2 , t80;for (i=0;imaxline; i+)p2=xx i ;while (*p2) /*找到最后一个,o */if ( (1) ) p1=p2p2+;strcat (t,p1+1) ;strcat (t,xx i) ;p1=xxi;p2=t ;while(*p2) /*删符o*/jf( (2) )( (3) )=*p2;p2+;(4) ;void main ()clrscr () ;if (readdat () printf(“Cant open the file IN.DAT!/n“);return
30、;StrOR () ;writedat () ;int readdat (void)FILE *fp;int i=0;char *p;if (fp= fopen (“in.dat“ , “r“ =NULL)return 1;while (fgets (xx i , 80, fp)! =NULL)p=strchr (xx i, /n) ;if (p)i+;maxline= (5) ;fclose (fp) ;return 0;void writedat (void)FILE *fp;int i;fp=fopen (“in.dat “ , “w“) ;for (i=0; imaxline; i+)
31、printf(“%s/n“,xxi);fprintf(fp, “%s/n“,xxi) ;fclose (fp) ;（分数：15.00）填空项 1:_ （正确答案：*p2=o）解析：填空项 1:_ （正确答案：*p2!=o）解析：填空项 1:_ （正确答案：*p1+）解析：填空项 1:_ （正确答案：*p1=/0）解析：填空项 1:_ （正确答案：i）解析：解析 在主函数中，首先调用函数 readdat()，从文件 IN.DAT中读取一篇英文文章存入到字符串数组 XX中，用变量 maxline表示文章的行数，所以空(5)应填入“i”。函数 StrOR()的功能是将字符串中所有小写字母 o左边的字
32、符串内容移到该串的右边存放，即先将串中“最后”一个字母 o左右两侧的内容互换，再删去所有的小写字母o。第一个 while()循环的作用是让p1指向最后一个字母o，所以空(1)应填入“*p2=o“。第一个 strcat()函数的作用是将 p1以后的字符都放到新串 t中，第二个 strcat()函数的作用是将 p1以前的字符连接到新串 t的后面(注意：在此之前要让 p1所指的单元成为 p1前面字符串的结束位置*p1=t/0)。这时完成左右互换。最后一个 while()循环的作用是删除新串中的所有小写字母o，采用的删除方法为不是o的字母一律留下，否则不留(即相当于删除)，所以空(2)应填入“*p2!
33、=o“，而 p1指向这一行的开始，且每次赋值后值必须加 1，所以空(3)应填入“*p1+”。复制完所有不是o的字母后还要加一个字符串结束标记，所以空(4)应填入“*p1=/0”。最后通过调用函数 writedat()把结果 XX输出到文件中。五、试题五(总题数：1，分数：15.00)说明阅读下面程序，指出其中代码的错误及原因。C+程序01 #include iostream.h02 class employee03 private:04 short age;05 float salary ;06 friend void funcl () ;07 protected:08 char* name;
34、09 public:10 employee (char* nn, short ag, float salr) ;11 void print () const ;12 employee () ;13 ;14 manage:public employee15 char* department;16 /.17 public:18 void print () ;19 void setEmployee () ;20 /.21 22 /.23 void manage:print ()24 25 cout “name: “ nameendl;26 cout“salary: “salaryendl; /- (
35、1) 27 28 void manager:setEmployee(char* dept)29 30 employee:employee(char* nm,short ag,float salr) ; /- (2) /- (3) 31 department=dept;32 33 void funcl ()34 35 cout “department:“department 11- (4) 36 “,name: “nameendl;37 /.38 39 void main ()40 41 employee aemp; /- (5) 42 manager amngr (“ Kng “ , 35,
36、578. 9);43 /.44 （分数：15.00）填空项 1:_ （正确答案：私有基类成员在派生类中不可见）解析：填空项 1:_ （正确答案：构造函数不可继承）解析：填空项 1:_ （正确答案：没有定义复制构造函数）解析：填空项 1:_ （正确答案：友元关系不可继承）解析：填空项 1:_ （正确答案：一旦定义了构造函数，系统将不再生成默认构造函数）解析：解析 本题以 C+语言为载体，考查面向对象的对象设计中的几个重要概念，继承、友元和构造函数等。空(1)处直接引用了基类中的私有成员，这是不可以的，共有派生后，基类的私有成员在派生类中是不可见的，只能通过基类的共有函数来访问这些私有成员。空(2
37、)处对派生类的构造函数企图用基类的构造函数来定义，这是不可以的，构造函数不可以继承。空(3)处的这种定义是不可取的，这样并没有给派生类中的私有成员实现赋值。空(4)处其上的 funcl()是基类友元函数，它可以直接使用基类中的公有和保护成员，但友元函数没有继承性，它不可以使用派生类中的成员。空(5)处由于程序中自己定义了构造函数，那么系统将不再生成默认的构造函数，又由于类中定义的构造函数不是默认的，所以，在初始化对象时，必须给对象数据成员赋值。六、试题六(总题数：1，分数：15.00)说明下面程序输出一个矩形面积，以及矩形区域上的假想的作物产量。Java程序public class Mainj
38、ava public static void main(String args) Lot_size small = new Lot_size() ;Lot_size medium = new Lot_size();small.set (5,5,5,25) ;medium.set (10,10,10, 50) ;System.out.println(“For a small lot of area “+small.get_area () +“/n“);System.out.println(“the actual crops are $“+small.get_data2 () +“ /n“) ;S
39、ystem.out.println(“and ideal crops are $“+small.get_data () +“/n“) ;System.out.println(“For a medium lot of area“+medium.get_area () +“/n“);system.out.println (“the actual crops are $ “+medium.get_data2 () +“/n “);System.out.println (“and ideal crops are $“+medium.get_data () +“/n“);class Crop_asses
40、smentprivate int actual_crop;private int ideal_crop;public void set(int in_actual,int in_ideal) actual_crop = in_actual;ideal_crop = in_ideal;public int get_actual_crop () return (1) ; public int get_ideal_crop() return (2) ;class Lot_sizeprivate int length;private int width;private Crop_assessment
41、crop = (3) ;public void set(int 1,int w,int a,int i) length =1;width = w;crop.set (a,i) ;public int get_area () return lengt h*width; public int get_data() return (4) ; public int get_data2 () return (5) ;（分数：15.00）填空项 1:_ （正确答案：actual_crop）解析：填空项 1:_ （正确答案：ideal_crop）解析：填空项 1:_ （正确答案：new crop_asses
42、sment()）解析：填空项 1:_ （正确答案：crop.get_deal_crop()）解析：填空项 1:_ （正确答案：crop.get_actual_crop()）解析：解析 本题以 Java语言为载体，考查面向对象程序设计中的几个重要概念类的嵌套及函数的使用。本题的功能是通过已定义的粮食收成类定义了一个计算特定矩形域上粮食收成的类，在主函数中定义了两个对象，并调用了相应的函数，来输出理想和实际的粮食产量。首先，由于 Crop_assessment定义的成员数据默认为私有的，所以想要获得实际和理想的粮食产量，要通过两个共有成员函数，所以空(1)处应填入 actual_crop，空(2)处应填入 ideal_crop。其次，在类 Lot_size中，由于我们要反映矩形域上的粮食产量，所以我们在类中嵌套定义了一个类，Java中对象需要实例化，故空(3)应填入 new crop_assessment()。最后，由于我们想通过 Lot size类中的 get_data和 get_data2函数得到粮食产量，但由于这两个成员数据是私有函数，所以我们必须通过定义的对象调用它，所以空(4)应填入 crop.get_deal_crop()，空(5)应填入 crop.get_actual_crop()。
