【计算机类职业资格】初级程序员下午试题-47及答案解析.doc
《【计算机类职业资格】初级程序员下午试题-47及答案解析.doc》由会员分享,可在线阅读,更多相关《【计算机类职业资格】初级程序员下午试题-47及答案解析.doc(17页珍藏版)》请在麦多课文档分享上搜索。
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
- 1.请仔细阅读文档,确保文档完整性,对于不预览、不比对内容而直接下载带来的问题本站不予受理。
- 2.下载的文档,不会出现我们的网址水印。
- 3、该文档所得收入(下载+内容+预览)归上传者、原创作者;如果您是本文档原作者,请点此认领!既往收益都归您。
下载文档到电脑,查找使用更方便
5000 积分 0人已下载
下载 | 加入VIP,交流精品资源 |
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算机 职业资格 初级 程序员 下午 试题 47 答案 解析 DOC
