1、初级程序员下午试题-47 及答案解析(总分：90.00，做题时间：90 分钟)一、试题一(总题数：1，分数：15.00)1.【说明】为了减少直接插入排序关键字的比较次数，本算法使用了二分(折半)插入法对一个无序数组 R1n进行排序。排序思想是对一个待插入元素，先通过二分法(折半)找到插入位置，后移元素后将该元素插入到恰当位置。(假设 R中的元素互不相同)算法1变量声明X: Data Typei,j,low, high,mid,r:0n2每循环一次插入一个 Ri循环：i 以 1为步长，从 2到 n，反复执行。(1)准备XRi; (1) ; highi-1;(2)找插入位置循环：当 (2) 时，反
2、复执行。(3) 若 X.keyRmid.key则 highmid-1;否则 (4) (3)后移循环：j 以-1 为步长，从 (5) ，反复执行。Rj+1Rj(4)插入RlowX3算法结束（分数：15.00）_二、试题二(总题数：1，分数：15.00)2.【函数 2.1说明】将一个正整数分解质因数。例如：输入 90，打印出 90=2*3*3*5。【函数 2.1】Fun1 (int n)int i;for(i=2;i=n;i+)while ( (1) )if (n%i=0)printf(“%d*“,i);(2) ;elsebreak;printf(“%d“,/n);【函数 2.2说明】下面程序的功
3、能是：海滩上有一堆桃子，5 只猴子来分。第 1只猴子把这堆桃子平均分为 5份，多了一个，这只猴子把多的一个扔入海中，拿走了一份。第 2只猴子把剩下的桃子又平均分成 5份，又多了一个，它同样把多的一个扔入海中，拿走了一份。第 3、4、5 只猴子都是这样做的，问海滩上原来最少有多少个猴子?【函数 2.2】main()int i,m,j,k,count;for(i=4;i10000;i+=4)count=0;(3) ;for(k=0;k5;k+) (4) ;i=j;if(j%4=0)(5) ;elsebreak;i=m;if(count=4)printf(“%d/n“,count);break;（分
4、数：15.00）_三、试题三(总题数：1，分数：15.00)3.【说明】下面的程序构造一棵以二叉链表为存储结构的二叉树。【函数】BitTree *createbt(BitTree *bt)BitTree *q;struct node *s30;int j,i;char x;printf(“i,x=“);scant(“%d,%c“,while(i!=0 /生成一个结点(1) ;q-lchild=NULL;q-rchild=NULL;(2) ;if ( (3) )j=i/2; / j为 i的双亲结点if(i%2=0)(4) ; /i为 j的左孩子else(5) ; /i为 j的右孩子printf(
5、“i,x=“);scanf(“%d,%c“,return si;（分数：15.00）_四、试题四(总题数：1，分数：15.00)4.【说明】本程序从正文文件 text.in中读入一篇英文短文，统计该短文中不同单词及出现次数，并按词典编辑顺序将单词及出现次数输出到正文文件 word.out中。程序用一棵有序二叉树存储这些单词及其出现的次数，边读入边建立，然后中序遍历该二叉树，将遍历经过的二叉树上的结点内容输出。【函数】# include stdio.h# include malloc.h# include ctype.h# include string.h# define INF “text.i
6、n“# define OUTF “word.ourtypedef struct treenode char *word;int count;struct treenode *left, *right;BNODE;int getword(FILE *fpt, char *word)char c;c=fgetc(tpt);if (c=EOF)return 0;while(!(tolower(c)= a if (c=EOF)return 0;/* 跳过单词间的所有非字母字符 */while(tolower(c)= a c=fgetc(fpt);*word=/0;return 1;void binar
7、y_tree(BNODE *t, char *word)BNODE *ptr, *p; int compres;p=NULL;(1) ;while (ptr) /* 寻找插入位置 */compres=strcmp(word, ptr-word);/* 保存当前比较结果 */if (!compres)(2) ; return;elsep=ptr;ptr=compres0 ? ptr-right: ptr-left;ptr=(BNODE *)malloc(sizeof(BNODE);ptr-left=ptr-right=NULL;ptr-word=(char *)malloc(strlen(wor
8、d)+1);strcpy(ptr-word, word);(3) ;if (p=NULL)*t=ptr;else if (compres0)p-right=ptr;elsep-left=ptr;void midorder(FILE *fpt, BNODE *t)if (t=NULL)return;midorder(fpt, (4) );fprintf(fpt, “%s %d/n“, t-word, t-count);midorder(fpt, t-right);void main()FILE *fpt; char word40;BNODE *root=NULL;if (fpt=fopen(IN
9、F, “r“)=NULL)printf(“Cant open file %s/n“, INF);return;while(getword(fpt, word)=1)binary_tree( (5) );fclose(fpt);fpt=fopen(OUTF, “w“);if (fpt=NULL)printf(“Cant open fife %s/n“, OUTF);return;midorder(fpt, root);fclose(fpt);（分数：15.00）_五、试题五(总题数：1，分数：15.00)5.【说明】进行两个整数之间的比较，由考生通过输入窗口分别输入两个整数，程序比较出结果。例如
10、：先后输入的两个数分别为 25和 36。比较结果显示：25!=36253625=36 【Java 代码】import javax.swing.JOptionPane;public class Java3public static void main(String args)String (1) / 用户输入第 1个字符串secondNumber, / 用户输入第 2个字符串result; / 包含输出int number1, / 比较的第 1个数number2; / 比较的第 2个数/ 用户输入的第 1个字符串firstNumber =JOptionPane. (2) (“Enter firs
11、t integer:“);/读用户输入的第 2个字符串secondNumber =JOptionPane.showlnputDialog(“Enter second integer:“);将字符串类型转换成整数类型number1= Integer. (3) (firstNumber);number2= Integer.parselnt(secondNumber);result= “:if ( (4) )result=number1+“=“+number2;if (number1 != number2)result=number1+“!=“+number2;if (number1number2)
12、result=result+“/n“+number1+“+ number2;if (number1number2)result=result+“/n“+number1+“+number2;if (number1=number2)result=result+“/n“+number1+“=“+number2;if (numbed=number2)result=result+“/n“+number1+“=“+number2;/显示结果JOptionPane. (5) .(null, result, “Comparison Results“,JOptionPane. INFORMATION_MESSA
13、GE);/程序正常退出System.exit(0);（分数：15.00）_六、试题六(总题数：1，分数：15.00)6.【说明】本程序的功能是根据矩形左上角和右下角顶点坐标生成一个矩形对象，然后输出该矩形 4个顶点的坐标，计算并输出该矩形的面积。【C+代码】#includeiostreamusing namespace std;class MyPoint( /表示平面坐标系中的点的类double x;double y;public:MyPoint (double x,double y)this-x=x;this-y=y;double getX()const (1) ;double getY()
14、const return y;void show()const cout(x,y);class MyRectangle /表示矩形的类MyPoint upleft; /矩形的左上角顶点MyPoint down right; /矩形的右下角顶点public:MyRectangle(MyPoint upleft,MyPoint downright);MyPoint getUpLeft()constreturn up_left; /返回左上角坐标MyPoint getDownRight()constreturn down_right; /返回右下角坐标MyPoint getUpRight()cons
15、t; /返回右上角坐标MyPoint getDownLeft()const; /返回左下角坐标double area()const; /返回矩形的面积;MyRectangle: MyRectangle( (2) ):up left(p1),down_right(p2)MyPoint MyRectangle:getUpRight()constreturn MyPoint(down_right.getX(),up_left.getY();MyPoint MyRectangle:getDownLeft()constreturn MyPeint( (3) );double (4) :area()con
16、streturn (getUpLeft(),getX()-getDownRight().getX()*(getDownRight().getY()-getUpLeft().getY();int main( )MyRectangle r(MyPoint(0,2),MyPoint(2,0);r.getUpLeft(),show();r.getUpRight().show();r.getDown Right().show();(5) ;coutr.area()end1;return 0;（分数：15.00）_初级程序员下午试题-47 答案解析(总分：90.00，做题时间：90 分钟)一、试题一(总题
17、数：1，分数：15.00)1.【说明】为了减少直接插入排序关键字的比较次数，本算法使用了二分(折半)插入法对一个无序数组 R1n进行排序。排序思想是对一个待插入元素，先通过二分法(折半)找到插入位置，后移元素后将该元素插入到恰当位置。(假设 R中的元素互不相同)算法1变量声明X: Data Typei,j,low, high,mid,r:0n2每循环一次插入一个 Ri循环：i 以 1为步长，从 2到 n，反复执行。(1)准备XRi; (1) ; highi-1;(2)找插入位置循环：当 (2) 时，反复执行。(3) 若 X.keyRmid.key则 highmid-1;否则 (4) (3)后移
18、循环：j 以-1 为步长，从 (5) ，反复执行。Rj+1Rj(4)插入RlowX3算法结束（分数：15.00）_正确答案：(1)low1 (2)low=high (3)midint(low+high)/2)(4)lowmid+1 (5)i-1 到 low)解析：分析本题考查使用二分插入法对无序数组排序的伪码实现。在做题前，我们需要先大概明白二分插入法的基本思想和步骤，其基本思想是(设 Rlow，high是当前的插入区间)：(1)将要插入的数取出放在 X中；(2)确定区间的中点位置：mid=(low+high)/2；(3)确定插入位置，将待插入的 k值与 Rmid.key比较，具体方法如下：
19、若 Rmid.keyk，则由排序后表的有序性可知 Rmid,，n.key 均大于 k，因此，插入区间是左子表 Rlow,，high，其中 high=mid-1。 若 Rmid.keyk，则要插入的 k必在 mid的右子表 Rmid+1，high中，其中 low=mid+1。(4)在上面的过程中，low 逐步增加，而 high逐步减少，直到 highlow，则找到插入位置为 low，然后循环移动位置 low后面的元素，再插入数值。(5)重复上述过程，直到所有数都被插入。有了上面的分析，我们再来看程序伪代码，第(1)空处在准备阶段，准备阶段要完成的任务是给变量赋初值，highi-1 将数组中的最后
20、一个位置赋给了插入指针 high，因为插入的范围是数组的整个范围，那么第(1)空应该用来将数组的第一个位置赋给插入指针 low，因此答案为 low1。第(2)空是找插入位置用的循环条件，根据我们上面的分析，要直到 highlow 时，才能确定插入的位置；而在 low=high 时，循环一直执行，结合程序的内容，知道此空答案为 low=high。第(3)空很明显是用来确定区间的中间位置，但 mid有可能为小数，在程序中我们用取整的方法来去掉小数部分，因此，此空答案为 mid-int(low+high)/2)。第(4)空是条件 X.keyRmid.key 不成立的情况下执行的语句，如果条件为假，则
21、说明要插入的数大于中间位置的数，应该在其右区间里进行插入，根据分析知道，这时左指针 low应该改变，这个空就是用来实现这个功能的，因此，答案为 lowmid+1。第(5)空在后移的循环操作中，作为后移的循环判断条件，在找到插入位置后，进行插入前，我们需要一个空间来存放插入的值。从程序中不难看出，是将待插入位置后面的所有元素向后移动一位，而待插入位置存放在 low中，因此，此空答案为 i-1到 low。二、试题二(总题数：1，分数：15.00)2.【函数 2.1说明】将一个正整数分解质因数。例如：输入 90，打印出 90=2*3*3*5。【函数 2.1】Fun1 (int n)int i;for
22、(i=2;i=n;i+)while ( (1) )if (n%i=0)printf(“%d*“,i);(2) ;elsebreak;printf(“%d“,/n);【函数 2.2说明】下面程序的功能是：海滩上有一堆桃子，5 只猴子来分。第 1只猴子把这堆桃子平均分为 5份，多了一个，这只猴子把多的一个扔入海中，拿走了一份。第 2只猴子把剩下的桃子又平均分成 5份，又多了一个，它同样把多的一个扔入海中，拿走了一份。第 3、4、5 只猴子都是这样做的，问海滩上原来最少有多少个猴子?【函数 2.2】main()int i,m,j,k,count;for(i=4;i10000;i+=4)count=0
23、;(3) ;for(k=0;k5;k+) (4) ;i=j;if(j%4=0)(5) ;elsebreak;i=m;if(count=4)printf(“%d/n“,count);break;（分数：15.00）_正确答案：(1)n!=i (2)n=n/i (3)m=i(4)j=i/4*5+1 (5)count+)解析：分析 本题考查 C语言中正整数分解质因数算法和猴子分桃算法的实现。在程序 2.1中，要求将一个正整数分解质因数。我们先来了解一下质因数的概念，一个自然数的因数中，为质数的因数叫做这个数的质因数。把一个合数，用质因数相乘的形式表示出来，叫做分解质因数。如90=2*3*3*5，其中
24、 2，3，5 都是质数。在对数 n进行分解质因数时，应先找到一个最小的质数 i，然后按下述步骤完成：(1)判断这个质数 i是否等于 n，如果相等，则说明分解质因数的过程已经结束，打印出结果即可。(2)如果 ni，但 n能被 i整除，则 i是 n的质因数，应打印出 i的值，并用 n除以 i 的商，作为新的正整数 n。(3)如果 n不能被 i整除，则用 i+1作为 i的值，重复执行第(1)步。通过代码我们已经知道了最小的质数为 2，第(1)空是循环的判断条件，结合我们上面的分析，应该是判断质数 i是否等于 n，因此，此空答案为 n!=i。第(2)空在条件判断语句下，条件 n%i=0成立，说明 n能
25、被 i整除，根据分析，应打印出 i的值，并用 n除以 i的商，作为新的正整数 n。代码中已经实现了对 i的输出，第(2)空的任务是用 n除以 i的商，作为新的正整数 n，因此，答案为 n=n/i。在程序 2.2中，要求我们求出原来海滩上的桃子数，这个数的特点是除以 5余 1，且减去它的商和余数后再除以 5又余 1，一直这样下去，直到最后一次。要求这样一个有特点的数，我们可以在一个较大的范围里编程去找具有这种性质的数。结合代码我们知道，程序设计是从 4到 10000这个范围里去找具有这种特征的数的基数。第(3)空所在位置是第一层循环下面，应该是给变量赋初值阶段，结合后面的程序，可以发现 m是用来
26、临时存放当前求的基数乙因此，此空答案为 m=i。第(4)空在第二层循环下面，这个循环的作用是利用当前的基数 i来求桃子数，那么求解的过程肯定是分桃过程的逆向过程。即此空的答案为 i=i/4*5+1。第(5)空在条件判断语句下面，如果条件成立，则执行此语句。我们接着看下面的程序，发现程序中有语句 if(count=4)，而在程序中一直没有出现变量 count的值改变的语句，而它的初值是 0，因此，此空肯定用来改变 count的值的，再结合猴子分桃的特性，可以得到此空的答案为 count+。三、试题三(总题数：1，分数：15.00)3.【说明】下面的程序构造一棵以二叉链表为存储结构的二叉树。【函数
27、】BitTree *createbt(BitTree *bt)BitTree *q;struct node *s30;int j,i;char x;printf(“i,x=“);scant(“%d,%c“,while(i!=0 /生成一个结点(1) ;q-lchild=NULL;q-rchild=NULL;(2) ;if ( (3) )j=i/2; / j为 i的双亲结点if(i%2=0)(4) ; /i为 j的左孩子else(5) ; /i为 j的右孩子printf(“i,x=“);scanf(“%d,%c“,return si;（分数：15.00）_正确答案：(1)q-data=x (2)
28、si=q (3)i!=1(4)sj-lchild=q (5)sj-rchild=q)解析：分析本题考查二叉树的构造。题目要求构造一棵二叉树，而二叉树的性质如下：如果对一棵有 n个结点的完全二叉树的结点按层序编号(从第 1层到第log 2n+1层，每层从左到右)，则对任一结点 i(1in)，有：(1)如果 i=1，则结点 i无双亲，是二叉树的根；如果 i1，则其双亲是结点i/2。(2)如果 2in，则结点 i为叶子结点，无左孩子：否则，其左孩子是结点 2i。(3)如果 2i+1n，则结点 i无右孩子；否则，其右孩子是结点 2i+1。下面我们来看程序。程序中声明了一个结点指针数组，用来保存生成的树
29、中结点。用从键盘输入的方式来确定要插入的字符 x和此结点在二叉树中的位置 i(这个位置是指在完全二叉树中编号的位置)。第(1)空是在生成一个新结点后的操作，生成了一个新结点后，自然要将从键盘输入的字符 x值存放进来，以及修改结点的两个指针域。程序中指针域都赋了空，因此，第(1)空的任务应该是将字符 x写进来，因此，此空答案为 q-data=x。第(2)空是在对结点完成操作后的操作，根据题目意思，生成的结点应该要保存到数组 s中，此数组是一个指针数组，保存结点时，是将结点的地址保存进数组中相应的位置，因此，此空答案为 sil=q。第(3)空是条件判断语句的条件，结合下面的程序可以知道，此条件语句
30、用来判断当前结点是不是根结点，如果不是，才执行条件语句中的内容。根据上面的分析，如果 i=1，则结点 i无双亲，是二叉树的根，因此，此空的答案为 i!=1。第(4)空处后面有注释，说明 i是 j的左孩子结点，这个时候我们应该让 j结点的左孩子指针指向结点i，此空就是要实现这一功能。而结点，j 被存放在数组 s中的第 j个位置，因此，此空答案为 si-lchild=q。从程序中很容易看出，第(5)空与第(4)空功能相似，只是说 i是 j的右孩子结点，因此，让 j结点的右孩子指针指向结点乙此空答案为 sj-rchild=q。四、试题四(总题数：1，分数：15.00)4.【说明】本程序从正文文件 t
31、ext.in中读入一篇英文短文，统计该短文中不同单词及出现次数，并按词典编辑顺序将单词及出现次数输出到正文文件 word.out中。程序用一棵有序二叉树存储这些单词及其出现的次数，边读入边建立，然后中序遍历该二叉树，将遍历经过的二叉树上的结点内容输出。【函数】# include stdio.h# include malloc.h# include ctype.h# include string.h# define INF “text.in“# define OUTF “word.ourtypedef struct treenode char *word;int count;struct tre
32、enode *left, *right;BNODE;int getword(FILE *fpt, char *word)char c;c=fgetc(tpt);if (c=EOF)return 0;while(!(tolower(c)= a if (c=EOF)return 0;/* 跳过单词间的所有非字母字符 */while(tolower(c)= a c=fgetc(fpt);*word=/0;return 1;void binary_tree(BNODE *t, char *word)BNODE *ptr, *p; int compres;p=NULL;(1) ;while (ptr)
33、/* 寻找插入位置 */compres=strcmp(word, ptr-word);/* 保存当前比较结果 */if (!compres)(2) ; return;elsep=ptr;ptr=compres0 ? ptr-right: ptr-left;ptr=(BNODE *)malloc(sizeof(BNODE);ptr-left=ptr-right=NULL;ptr-word=(char *)malloc(strlen(word)+1);strcpy(ptr-word, word);(3) ;if (p=NULL)*t=ptr;else if (compres0)p-right=pt
34、r;elsep-left=ptr;void midorder(FILE *fpt, BNODE *t)if (t=NULL)return;midorder(fpt, (4) );fprintf(fpt, “%s %d/n“, t-word, t-count);midorder(fpt, t-right);void main()FILE *fpt; char word40;BNODE *root=NULL;if (fpt=fopen(INF, “r“)=NULL)printf(“Cant open file %s/n“, INF);return;while(getword(fpt, word)=
35、1)binary_tree( (5) );fclose(fpt);fpt=fopen(OUTF, “w“);if (fpt=NULL)printf(“Cant open fife %s/n“, OUTF);return;midorder(fpt, root);fclose(fpt);（分数：15.00）_正确答案：(1)ptr=*t (2)ptr-count+ (3)ptr-count=1(4)t-left (5)public class Java3public static void main(String args)String (1) / 用户输入第 1个字符串secondNumber,
36、 / 用户输入第 2个字符串result; / 包含输出int number1, / 比较的第 1个数number2; / 比较的第 2个数/ 用户输入的第 1个字符串firstNumber =JOptionPane. (2) (“Enter first integer:“);/读用户输入的第 2个字符串secondNumber =JOptionPane.showlnputDialog(“Enter second integer:“);将字符串类型转换成整数类型number1= Integer. (3) (firstNumber);number2= Integer.parselnt(secon
37、dNumber);result= “:if ( (4) )result=number1+“=“+number2;if (number1 != number2)result=number1+“!=“+number2;if (number1number2)result=result+“/n“+number1+“+ number2;if (number1number2)result=result+“/n“+number1+“+number2;if (number1=number2)result=result+“/n“+number1+“=“+number2;if (numbed=number2)re
38、sult=result+“/n“+number1+“=“+number2;/显示结果JOptionPane. (5) .(null, result, “Comparison Results“,JOptionPane. INFORMATION_MESSAGE);/程序正常退出System.exit(0);（分数：15.00）_正确答案：(1)firstNumber (2)showInputDialog (3)parseInt(4)number1=number2 (5)showMessageDialog)解析：分析本题考查 Java中的语法结构和两个数大小比较的实现。题目要求由考生通过输入窗口分别
39、输入两个整数，比较其大小并输出结果。下面来分析程序代码，程序中定义了一个类 Java3，在这个类中实现题目要求的功能。第(1)空所在代码行的注释是用户输入第 1个字符串，但这在程序的开始，没有进行输入操作，应该是声明一个字符串型变量用来存放用户输入的第 1个字符串，而在这个空的前面有一个关键字 String用来表明所声明的变量是字符串型的，结合后面的程序，我们知道用来存放输入的第 1个字符串的变量是firstNumber，因此，此空答案为 firstNumber。根据注释，第(2)空所在代码行的作用是读用户输入的第 1个字符串，而实现这个功能的是 JOptionPane包中的 showlnpu
40、tDialog()函数，结合后面的程序，我们不难找出此空的答案，为 showlnputDialog。再根据注释，我们知道第(3)空所在代码行的作用是将第 1个字符串类型的内容转换成整数类型，在 Java中，一般通过类型对象的 parseInt()方法，结合后面的程序，我们也不难找出此空的答案，为parseInt。第(4)空是条件判断语句中的条件，根据整个程序，我们不难发现变量 result中存放的是要输出的结果，而语句 result=number1+“+number2 是将 number1=number2这样一个结果存放到 result中，那么只有当 number1等于 number2时，才输
41、出这个结果，因此，第(4)空的作用应该是确定 number1等于number2。所以，此空答案为 number1=number2。第(5)空在注释显示结果下面，从上面的程序中我们知道，变量 result中存放的是要输出的结果，根据下面的程序，很明显是要调用包 JOptionPane中的某个方法来实现输出。此方法应该是showMessageDialog()，因此，此空答案为 showMessageDialog。六、试题六(总题数：1，分数：15.00)6.【说明】本程序的功能是根据矩形左上角和右下角顶点坐标生成一个矩形对象，然后输出该矩形 4个顶点的坐标，计算并输出该矩形的面积。【C+代码】#i
42、ncludeiostreamusing namespace std;class MyPoint( /表示平面坐标系中的点的类double x;double y;public:MyPoint (double x,double y)this-x=x;this-y=y;double getX()const (1) ;double getY()const return y;void show()const cout(x,y);class MyRectangle /表示矩形的类MyPoint upleft; /矩形的左上角顶点MyPoint down right; /矩形的右下角顶点public:MyR
43、ectangle(MyPoint upleft,MyPoint downright);MyPoint getUpLeft()constreturn up_left; /返回左上角坐标MyPoint getDownRight()constreturn down_right; /返回右下角坐标MyPoint getUpRight()const; /返回右上角坐标MyPoint getDownLeft()const; /返回左下角坐标double area()const; /返回矩形的面积;MyRectangle: MyRectangle( (2) ):up left(p1),down_right(
44、p2)MyPoint MyRectangle:getUpRight()constreturn MyPoint(down_right.getX(),up_left.getY();MyPoint MyRectangle:getDownLeft()constreturn MyPeint( (3) );double (4) :area()constreturn (getUpLeft(),getX()-getDownRight().getX()*(getDownRight().getY()-getUpLeft().getY();int main( )MyRectangle r(MyPoint(0,2),
45、MyPoint(2,0);r.getUpLeft(),show();r.getUpRight().show();r.getDown Right().show();(5) ;coutr.area()end1;return 0;（分数：15.00）_正确答案：(1)return x(2)MyPoint p1，MyPoint p2(3)up_left.getX()，down_right.getY()(4)MyRectangle(5)r.getDownLeft().show()解析：分析本题考查 C+语言的基本语法结构和计算矩形面积。题目要求根据矩形左上角和右下角顶点(已知)坐标生成一个矩形对象，然后输出该矩形 4个顶点的坐标，计算
