1、初级程序员下午试题-104 及答案解析(总分：90.00，做题时间：90 分钟)一、试题一(总题数：1，分数：15.00)说明下面的流程图，用来完成计算一组数组中的中值，其方法是：将数组中的一个值与其他值比较，并计算大于等于被比较数的数值的个数，以及小于等于被比较数的数值的个数，如果两数都大于 n/2，则已经找到了中值，否则继续之前的步骤。注：流程中循环开始的说明按照“循环变量：循环初值，循环终值，增量”格式描述。（分数：15.00）填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_二、试题二(总题数：1，分数：15.00)函数 2.1说明编制一个字符替换函数 rep(ch
2、ar *s，char *s1，char *s2)，实现将已知字符串 s中所有属于字符串 s1中的字符都用字符串 s2中的对应字符代替。函数 2,1#include stdio.h#define MAX 50rep(char *s,char *s1,char *s2)char *p;for(; *s; s+)for (p=s1; *p (1) ; p+); /*检查当前字符是否在字符串 s1中出现*/if(*p) (2) ; /*当前字符在字符串 s1中出现，用字符串 s2中的对应字符代替 s中的字符*/函数 2.2说明函数 Insert_Sort(int n)是一个直接插入排序的程序。其基本思
3、想是，假设待排序的记录存放在数组R1n中。初始时，R1自成一个有序区，无序区为 R2n。从 i=2起直至 i=n为止，依次将 Ri插入当前的有序区 R1i-1中，生成含 n个记录的有序区。函数 2.2#define MAX 255int RMAX; void Insert_Sort(int n)int i，j ;for(i=2; i=n; i+)if( (3) )R0=Ri; j=i-1; /*R0是哨兵，且是 Ri的副本*/do /*从右向左在有序区 R1i-1中查找 Ri的插入位置*/(4) ; /*将关键字大于 Ri的记录后移*/j-;while( (5) ); /*当 RiRj时终止*
4、/Rj+1=R0j /*Ri插入到正确的位置上*/（分数：15.00）填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_三、试题三(总题数：1，分数：15.00)说明函数 Node*difference(A，B)用于求两个集合之差 C=A-B，即当且仅当 e是 A中的一个元素，但不是 B中的元素时，e 是 C中的元素。集合用有序链表实现，用一个空链表表示一个空集合，表示非空集合的链表根据元素之值按递增排列。执行 C=A-B之后，表示集合 A和 B的链表不变，若结果集合 C非空，则表示其链表根据元素之值按递增排列。函数 append()用于在链表中添加结点。函数typedef
5、 struct nodeint element;struct node *link;Node; Node *A, *B, *C; Node *append(last,e)Node *last;int e; last-link= (Node *)malloc (sizeof (Node);last-link-element=e;return(last-link);Node *difference (A,B)Node *A, *B;Node *c, *last;C=last= (Node *)malloc(sizeof (Node);while( (1) )if(A-element B-eleme
6、nt)last=append (last,A-element);A=A-link;else if( (2) ) A=A-link;B=B-link;else(3) ;while( (4) ) last=append(last,A-element);A=A-link;(5) ; last=C;C=C-link;free(last); return (C); （分数：15.00）填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_四、试题四(总题数：1，分数：15.00)说明八皇后问题是指求解如何在国际象棋 8*8棋盘上无冲突地放置八枚皇后棋子。因为在国际象棋里，皇后的移动方式是
7、横竖交叉，所以在任意一个皇后所在位置的水平、竖赢和斜 45。线上都不能有其他皇后棋子的存在。一个完整无冲突的八皇后棋子分布称为八皇后问题的一个解。本程序实现了八枚皇后棋子在 8*8棋盘上无冲突的放置。函数#includemath. h#includestdio.h#define MAX 8 /*棋子数及棋盘大小 MAX*MAX*/int board MAX;/*印出结果*/void show_result()int i;for (i=0;iMAX;i+)printf(“(%d, %d)“,i,board i);printf(“/n“); /*检查是否在同一直横斜线上有其他棋子*/int che
8、ck_cross (int n)int i;for(i=0; in; i+)if( (1) )return 1; return 0;/*放棋子到棋盘上*/void put_chess (int n)int i;for (i=0; iMAX; i+)board n =i;if( (2) )if( (3) )show_result();/*找到其中一种放法了，印出结果*/else (4) ; void main()clrscr(); puts(“The possible placements are:“);(5) ;puts(“/n Press any key to quit“);getch();
9、 return：（分数：15.00）填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_五、试题五(总题数：1，分数：15.00)说明设计一程序，输入 16个整数到一个数组中，将数组位序颠倒重新排序，使每个数字不再按原 j的顺序排列，而是按 j的二进制数颠倒后得出的数排列，例如，将第 1个(0001)数与第 8个(1000)数交换，将第 3个数(0011)与第 12个数(1100)交换。C+程序#includeiostream.h#define SIZE 16#define SWAP (a,b) temper=(a); (a)= (b); (b) =temper;void m
10、aln()int dataSIZE; int n：cout“请输入“SIZE“个整数：“;for (n=0;nSIZE;n+)(1) ; int j=0,m;for (int i=0; in; i+)if(ji)(2) ; (3) ; while( (4) ) j=m)j-=m;m=1：(5) ; coutendl“排序后：“; for(n=0;nSIZE;n+)coutdata n; “ “; （分数：15.00）填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_六、试题六(总题数：1，分数：15.00)1.说明已知类 SubClass的 getSum方法返回其父类成员
11、i与类 SubClass成员 j的和，类 SuperClass中的getSum为抽象函数，程序中的第 14行有错误，请修改该错误并给出修改后的完整结果，然后完善程序中的空缺，当程序运行到第 22行且尚未执行第 22行语句时成员变量 i的值，最后给出程序运行后的输出结果。Java代码行号 代码01 public class Mainjava02 public static void main(String args) 03 SuperClass s = new SubClass () ;04 System. out .println (s. getValue () ;05 System. out
12、 .println (s.getSum () ;06 07 08 abstract class SuperClass09 private int i;10 public SuperClass () i= 5; 11 public int getValue () 12 return i;13 14 public final abstract int getSum();15 16 class SubClass extends SuperClass17 int j;18 public SubClass () 19 this (-3);20 21 public SubClass (int j) 22
13、(1) .j=j;23 24 public int getValue () return j; 25 public int getSum() 26 return (2) . getValue() + j;27 28 （分数：15.00）填空项 1:_初级程序员下午试题-104 答案解析(总分：90.00，做题时间：90 分钟)一、试题一(总题数：1，分数：15.00)说明下面的流程图，用来完成计算一组数组中的中值，其方法是：将数组中的一个值与其他值比较，并计算大于等于被比较数的数值的个数，以及小于等于被比较数的数值的个数，如果两数都大于 n/2，则已经找到了中值，否则继续之前的步骤。注：流程中
14、循环开始的说明按照“循环变量：循环初值，循环终值，增量”格式描述。（分数：15.00）填空项 1:_ （正确答案：j=-1;）解析：填空项 1:_ （正确答案：xj=xi;）解析：填空项 1:_ （正确答案：count_lower+,）解析：填空项 1:_ （正确答案：count_lower(n/2.0)|count_higher(n/2.0);）解析：填空项 1:_ （正确答案：xj;）解析：解析 本题目考查流程图。算法描述在题目中已经详细给出，通过阅读题目可知 j用来定位数组中一个被比较的数，i 用来循环遍历数组中所有的数。j 应该从第 0个数开始，又由于要执行一步 j=j+1，所以空(1
15、)中应填入 j=-1，count_higher+说明，遍历的数比被比较的数大，即空(2)中应填入 xj=xi，相应的，空(3)中就应填入 count_lower+，题目说明中已经指出，当 count_lower和 count higher都大于 n/2时，就说明找到了中值，所以空(4)应当填入 count_lower(n/2.0)|count_higher(n/2.0)，最后，如果循环结束，则 xj就应该是中值，空(5)中应填入 xj。二、试题二(总题数：1，分数：15.00)函数 2.1说明编制一个字符替换函数 rep(char *s，char *s1，char *s2)，实现将已知字符串
16、s中所有属于字符串 s1中的字符都用字符串 s2中的对应字符代替。函数 2,1#include stdio.h#define MAX 50rep(char *s,char *s1,char *s2)char *p;for(; *s; s+)for (p=s1; *p (1) ; p+); /*检查当前字符是否在字符串 s1中出现*/if(*p) (2) ; /*当前字符在字符串 s1中出现，用字符串 s2中的对应字符代替 s中的字符*/函数 2.2说明函数 Insert_Sort(int n)是一个直接插入排序的程序。其基本思想是，假设待排序的记录存放在数组R1n中。初始时，R1自成一个有序区
17、，无序区为 R2n。从 i=2起直至 i=n为止，依次将 Ri插入当前的有序区 R1i-1中，生成含 n个记录的有序区。函数 2.2#define MAX 255int RMAX; void Insert_Sort(int n)int i，j ;for(i=2; i=n; i+)if( (3) )R0=Ri; j=i-1; /*R0是哨兵，且是 Ri的副本*/do /*从右向左在有序区 R1i-1中查找 Ri的插入位置*/(4) ; /*将关键字大于 Ri的记录后移*/j-;while( (5) ); /*当 RiRj时终止*/Rj+1=R0j /*Ri插入到正确的位置上*/（分数：15.00
18、）填空项 1:_ （正确答案：*p!=*s）解析：填空项 1:_ （正确答案：*s=*(p-s1+s2)）解析：填空项 1:_ （正确答案：RiRi-1）解析：填空项 1:_ （正确答案：Rj+1Rj）解析：填空项 1:_ （正确答案：R0Rj）解析：解析 假设字符串分别如下，char s=“ABCABC”，s1=“AC”，s2=“xy”; 则调用函数rep(s，s1，s2)将使字符串 s的内容变为“xByxBy”。为实现题目中的要求，可用一个循环访问字符串 s中的字符，并检查该字符是否在字符串 s1中出现，若不在字符串 s1中出现，则略过该字符，所以空(1)填入*p!=*s; 若在字符串 s
19、1中出现，则用字符串 s2中的对应字符代替 s中的字符，所以空(2)填入*s=*(p-s1+s2)。根据题目中的注释，直接插入排序的具体做法是这样的，将待插入记录 Ri的关键字从右至左依次与有序区中记录 Rj(j=i-1，i-2，.，1)的关键字进行比较：若 Rj的关键字大于 Ri的关键字，则将Rj后移一个位置，所以空(4)处填入 Rj+1Rj; 若 Rj的关键字小于或等于 Ri的关键字，则查找过程结束，j+1 即为 Ri的插入位置，所以空(5)处填入 R0Rj，如果 Ri大于等于有序区中所有的 R，则 Ri应在原有位置上，所以空(3)填入 RiRi-1。三、试题三(总题数：1，分数：15.0
20、0)说明函数 Node*difference(A，B)用于求两个集合之差 C=A-B，即当且仅当 e是 A中的一个元素，但不是 B中的元素时，e 是 C中的元素。集合用有序链表实现，用一个空链表表示一个空集合，表示非空集合的链表根据元素之值按递增排列。执行 C=A-B之后，表示集合 A和 B的链表不变，若结果集合 C非空，则表示其链表根据元素之值按递增排列。函数 append()用于在链表中添加结点。函数typedef struct nodeint element;struct node *link;Node; Node *A, *B, *C; Node *append(last,e)Node
21、 *last;int e; last-link= (Node *)malloc (sizeof (Node);last-link-element=e;return(last-link);Node *difference (A,B)Node *A, *B;Node *c, *last;C=last= (Node *)malloc(sizeof (Node);while( (1) )if(A-element B-element)last=append (last,A-element);A=A-link;else if( (2) ) A=A-link;B=B-link;else(3) ;while(
22、 (4) ) last=append(last,A-element);A=A-link;(5) ; last=C;C=C-link;free(last); return (C); （分数：15.00）填空项 1:_ （正确答案：B-link）解析：填空项 1:_ （正确答案：A-element=B-element）解析：填空项 1:_ （正确答案：B=B-link）解析：填空项 1:_ （正确答案：A-link!=NULL）解析：填空项 1:_ （正确答案：last-link=NULL）解析：解析 本题用链表表示集合，通过比较链表的元素值判断集合的元素之间关系。第一个 while循环的条件是链
23、表 B指针不指向空，即空(i)应填 B-link。由于 A和 B两集合都是按递增排列的，则如果A中的元素小于 B中的元素，A 中元素直接放入集合 C中，集合 A指向其下一个元素; 如果 A中的元素等于 B中的元素，集合 A和 B分别指向下一个元素，即空(2)填 A-element=B-element;如果 A中的元素大于 B中的元素，集合 B指向其下一个元素，即空(3)填 B=B-link。第二个循环的条件是链表 A指针不指向空时，将 A中元素直接加入到 C中，即空(4)填 A-link!=NULL。将链表 C最后结点指针指向空，即空(5)填 last-link=NULL。四、试题四(总题数：
24、1，分数：15.00)说明八皇后问题是指求解如何在国际象棋 8*8棋盘上无冲突地放置八枚皇后棋子。因为在国际象棋里，皇后的移动方式是横竖交叉，所以在任意一个皇后所在位置的水平、竖赢和斜 45。线上都不能有其他皇后棋子的存在。一个完整无冲突的八皇后棋子分布称为八皇后问题的一个解。本程序实现了八枚皇后棋子在 8*8棋盘上无冲突的放置。函数#includemath. h#includestdio.h#define MAX 8 /*棋子数及棋盘大小 MAX*MAX*/int board MAX;/*印出结果*/void show_result()int i;for (i=0;iMAX;i+)print
25、f(“(%d, %d)“,i,board i);printf(“/n“); /*检查是否在同一直横斜线上有其他棋子*/int check_cross (int n)int i;for(i=0; in; i+)if( (1) )return 1; return 0;/*放棋子到棋盘上*/void put_chess (int n)int i;for (i=0; iMAX; i+)board n =i;if( (2) )if( (3) )show_result();/*找到其中一种放法了，印出结果*/else (4) ; void main()clrscr(); puts(“The possibl
26、e placements are:“);(5) ;puts(“/n Press any key to quit“);getch(); return：（分数：15.00）填空项 1:_ （正确答案：boardi=boardn|(n-i)=abs(boardi-boardn)）解析：填空项 1:_ （正确答案：!check_cross(n)）解析：填空项 1:_ （正确答案：n=MAX-1）解析：填空项 1:_ （正确答案：put_chess(n+1)）解析：填空项 1:_ （正确答案：put_chess(0)）解析：解析 程序使用了回溯的方法来解决八皇后问题，也就是逐次试探的方法。这个方法通过函
27、数put-chess()对自身的递归调用来实现。运行程序后，主函数调用 put_chess()函数在棋盘第一行第一列上放置棋子，开始向下一行递归，所以空(5)处填入 put_chess(0)。每一步递归中，首先检测待做位置有没有冲突出现。如果没有冲突就放下棋子，并进入下一行递归，否则检测该行的下一个位置，所以空(2)处填入!check_cross(n)， 空(1)处填入 boardi=boardn|(n-i)=abs(boardi-boardn)。如果整个一行中没有可以放置的位置，就退回上一层递归，所以空(4)处填入 put_chess(n+1)。最后，如果本次放置成功，并且递归调用深度为 7
28、，就打印输出结果，所以空(3)处填入 n=MAX-1。五、试题五(总题数：1，分数：15.00)说明设计一程序，输入 16个整数到一个数组中，将数组位序颠倒重新排序，使每个数字不再按原 j的顺序排列，而是按 j的二进制数颠倒后得出的数排列，例如，将第 1个(0001)数与第 8个(1000)数交换，将第 3个数(0011)与第 12个数(1100)交换。C+程序#includeiostream.h#define SIZE 16#define SWAP (a,b) temper=(a); (a)= (b); (b) =temper;void maln()int dataSIZE; int n：c
29、out“请输入“SIZE“个整数：“;for (n=0;nSIZE;n+)(1) ; int j=0,m;for (int i=0; in; i+)if(ji)(2) ; (3) ; while( (4) ) j=m)j-=m;m=1：(5) ; coutendl“排序后：“; for(n=0;nSIZE;n+)coutdata n; “ “; （分数：15.00）填空项 1:_ （正确答案：cindatan）解析：填空项 1:_ （正确答案：SWAP(dataj,datai)）解析：填空项 1:_ （正确答案：m=SIZE/2）解析：填空项 1:_ （正确答案：m=2）解析：填空项 1:_
30、（正确答案：j+=m）解析：解析 本题考查的是用 C+程序编程。题目要求将数组中的数按照位序倒序重新排列，根据给出的语句，并经过分析我们可知，程序首先是读入了一个数组，所以空(1)应填入 cindatan。接着求从 0到 SIZE-1住序倒序后的值，并将对应的数组中的两数交换，这里多了一项比较，只有求出的位序倒序数大于本身时才做交换，而小于本身时说明已经作了一次交换，而不再交换，所以，空(2)应填入 SWAP(dataj,datai)。while 循环内是求位序倒序数的主要部分，空(3)处应填入 m=SIZE/2。由于 m要进行右移一位的操作，也就是除 2，那么 m就必须大于等于 2，因此空(
31、4)应填入 m=2。最后，在对 m进行过移位操作后，要将其变化反映到 j上，所以，空(5)处应填 j+=m。六、试题六(总题数：1，分数：15.00)1.说明已知类 SubClass的 getSum方法返回其父类成员 i与类 SubClass成员 j的和，类 SuperClass中的getSum为抽象函数，程序中的第 14行有错误，请修改该错误并给出修改后的完整结果，然后完善程序中的空缺，当程序运行到第 22行且尚未执行第 22行语句时成员变量 i的值，最后给出程序运行后的输出结果。Java代码行号 代码01 public class Mainjava02 public static void
32、 main(String args) 03 SuperClass s = new SubClass () ;04 System. out .println (s. getValue () ;05 System. out .println (s.getSum () ;06 07 08 abstract class SuperClass09 private int i;10 public SuperClass () i= 5; 11 public int getValue () 12 return i;13 14 public final abstract int getSum();15 16 c
33、lass SubClass extends SuperClass17 int j;18 public SubClass () 19 this (-3);20 21 public SubClass (int j) 22 (1) .j=j;23 24 public int getValue () return j; 25 public int getSum() 26 return (2) . getValue() + j;27 28 （分数：15.00）填空项 1:_ （正确答案：程序 14行的错误改为：public abstract int getSum();(1) this(2) super程
34、序 22行未执行前成员变量 i的值为 5。程序运行结果为-3，2。）解析：解析 本题考查的是用 Java程序编程。程序 14行中定义了公有抽象方法 getSum()，而抽象方法就是用来继承的，以实现多态，不能定义为final，故应改为“public abstract int getSum()”。Java中对自身的引用为 this，而函数中的局部变量会屏蔽外部变量，故空(1)处应填 this。SubClass 的getSum方法是返回其父类成员 i与类 SubClass成员 j的和，而对父类的引用为 super，故空(2)应填super。继承类的初始化顺序是先初始化基类再初始化继承类。程序 22行的首次调用是通过 SubClass类的默认构造函数中的调用 this(-3)，而此时基类已通过默认构造函数构造，故基类的变量 i的值为 50初始化完成后，i 的值为 5，j 的值为-3，故 getSum()方法应返回 2。所以，程序运行结果为：-3, 2。
