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