1、初级程序员下午试题-93 及答案解析(总分：105.00，做题时间：90 分钟)一、试题一(总题数：1，分数：15.00)【算法说明】某商务交流中心共有 N 间客房。每间客房的房间号、房间等级、床位数及占用状态分别存放在数组ROOM、RANK、NBED 和 STATUS 中。房间等级值为 1、2 或 3。房间的状态值为 0(空闲)或 1(占用)。客房是以房间(不是床位)为单位出租的。程序流程图(见图 2-11)所反映的算法是，根据几个散客的要求预订一间空房。程序的输入为：人数 M，房间等级要求尺(R=0 表示任意等级都可以)。程序的输出为：所有可供选择的房间号。（分数：15.00）_二、试题二
2、(总题数：1，分数：15.00)1.【说明】以下【C 程序】能将自然数 1，2，N 2按蛇形方式逐个存入 N 阶矩阵。换言之，程序从 anO开始到 aOn。为止(n=N-1)顺序填入自然数，交替地对每一斜列从左上元素向右下元素或从右下元素向左上元素存数。例如，当 N=5 时，程序输出结果如图 2-12 所示；当 N=8 时，程序输出结果如图 2-13 所示。（分数：15.00）_三、试题三(总题数：1，分数：15.00)2.【说明】某超市集团为发展业务向社会公开招聘 N 个工种的工作人员，每个工种各有不同的编号(1 至 M)和计划招聘人数。每位应聘者需申报两个工种，并参加集团组织的考试。该集团
3、公司将按应聘者的成绩从高分至低分的顺序进行排队录取。具体录取原则是：从高分到低分依次对每位应聘者先按其第一志愿录取；当不能按其第一志愿录取时，便将他的成绩扣去 5 分后，重新排队，并按其第二志愿录取。以下 C 程序为输出各工种实际招聘的应聘人员，每个工种都保留一个录取者的有序队列。录取处理循环直至招聘额满或已对全部应聘者都作了录取处理后跳出。C 程序中，类型 STU 包含有应聘者的基本信息：编号、成绩、志愿、排队成绩和录取志愿号。数组 rzl)的每个元素对应一个工种，包含有计划招聘人数和已录取的人数。【C 程序】#include#define N 36#define EDMARK 5typed
4、ef struct stu int no, total, z2, sortm, zi;struct stu *next;STU;struct rznode int lmt, count;STU *next;rz N;STU *head = NULL, *over = NULL;int allFILE *fp;char dataf = “zp2008.dat“ ;print(STU *p)for (;p!=NULL; p = p-next)printf( “%d(%d) /t“ , p-no, p-totalinsert(STU *p, STU *u)STU *v, *q;for (q = *p
5、;q != NULL; v = q , (1) )if (q- sortm u-sortm)break;if ( q = *p)(2) ;else(3) ;u-next = q ;main ( )int zn, i, no, total, zl, z2 ;STU *p, *v, *q;fp = fopen(dataf, “r“ );if (fp = NULL)printf (“Cant open file %s.kn“ ,dataf);exit (0);fscanf (fp, “%d“ ,for (all = 0, i = 1; i = zn; i+)fscanf (fp, “%d“, rzi
6、.count = 0;rzi.next = NULL;all += (4) ;for (;)if ( fscanf(fp, “%d%d%d%d“ ,p = ( STU *) malloc (sizeof (STU);p-no = no;p-total = p-sortm = total;p-zi = 0;p-z0 = z1;p-z1 = z2;(5) ;fclose (fp);for (;all )p = head;head = head-next;if (rzp-zp-zi.count (6) )rzp-zp-zi.count +;insert(all-;continue;if (p-zi
7、= 1 )p-next = over;over = p;continue;p-sortm -= DEMARK;(7) ;insert(for (i = 1; i = zn; i+ )printf(“%d:/n“ ,i);print( rzi .next);printf(“ /n“);printf( “over:/n“ );print(head);print(over);printf(“ /n“);（分数：15.00）_四、试题四(总题数：1，分数：15.00)3.【说明】【C 程序 1】用回溯算法来产生由 0 或 1 组成的 2m个二进位串，使该串满足以下要求。视串为首尾相连的环，则由 m 位
8、二进制数字组成的 2m个子序列，每个可能的子序列都互不相同。例如，如果 m=3，在串 11101000 首尾相连构成的环中，由 3 位二进制数字组成的每个可能的子序列都在环中恰好出现一次，它们依次是 111，110，101，010，100，000，001，011，如图 2-14 所示。（分数：15.00）_五、试题五(总题数：1，分数：15.00)【说明】某机动车驾驶员模拟考试系统的“交通禁令标志识别”窗体中，共有 1 个按钮(CmdTest)、6 个标签、 1个包含 10 个单选按钮的控件数组(OptPicture)，如图 2-15 所示。其中，标签(LblPrompt1)“禁令标志”与标签
9、(LblTest)相对应，标签(LblPrompt2)“图片答案”与标签(LblAnswer)相对应，标签(LblEvaluate)为结果提示。窗体(Frm001)对象和单选按钮控件数组(OptPicture)对象的部分属性及属性值如表 2-15 所示。表 2-15 窗体、单选按钮控件数组的部分属性及属性值对 象 属 性 属性值(名称) Frm001Icon 变通标识MaxButton (1)窗体MinButton (2)(名称) optPictureIndex (3)Style 1-Graghics单选按钮控件数组Picture (装入相应图片)该程序运行时，单击【测试】按钮(CmdTest
10、)，在标签(LblTest)中随机显示一个交通禁令标志名称，用户单击控件数组(OptPicture)相应单选按钮后，程序在标签(LblAnswer)给出用户所击单选按钮对应的交通禁令标志名称，在标签(LblEvaluate)给出正确或错误的提示结果，如图 2-15 和图 2-16 所示。（分数：15.00）_六、试题六(总题数：1，分数：15.00)4.【说明】以下【C+程序】实现一个简单的小型复数类 MiniComplex，该复数类能进行输入、输出、复数的加法、减法、乘法和除法运算，还可以进行复数的相等比较。【C+程序】#ifndef H_MiniComplex#define H_MiniC
11、omplex#include iostreamusing namespace std;class MiniComplexpublic: /重载流插入和提取运算符(1) ostreamreturn osObject;(2) istreamisObject complex.realPartchcomplex.imagPartch;return isObject;MiniComplex(double real=0,double imag=0); /构造函数MiniComplex operator+(const MiniComplex /重载运算符+MiniComplex operator-(cons
12、t MiniComplex /重载运算符-MiniComplex operator*(const MiniComplex /重载运算符*MiniComplex operator/(const MiniComplex /重载运算符/bool operator=(const MiniComplex /重载运算符=private :double (3) ;double imagPart;#end if#include “MiniComplex.h“bool MiniComplex:operator=(const MiniComplexMiniComplex:MiniComplex(double re
13、al,double imag)realPart= real; imagPart=imagPart;MiniComplex MiniComplex:operator+(const MiniComplextemp.realPart = realPart+ortherComplex. realPart;temp.imagPart = imagPart +ortherComplex. imagPart;return temp;(4) MiniComplex temp;temp.realPart= realPart-ortherComplex. realPart;temp.imagPart = imag
14、Part-ortherComplex. imagPart;return temp;MiniComplex MiniComplex:operator*(const MiniComplextemp.realPart = (realPart*ortherComplex. realPart)-(imagPart *ortherComplex.imagPart);temp.imagPart = (realPart*ortherComplex. imagPart)+(imagPart *ortherComplex.realPart);return temp;MiniComplex MiniComplex:
15、operator/(const MiniComplexfloat tt;tt=1/(ortherComplex.realPart*ortherComplex.realPart+ortherComplex.imagPart *ortherComplex. imagPart);temp.realPart=(realPart*ortherComplex, realPart)+(imagPart *ortherComplex. imagPart)*tt;temp.imagPart =(imagPart *ortherComplex. realPart)-(realPart*ortherComplex.
16、 imagPart)*tt;return temp;#include iostream#include MiniComplex.husing namespace std;int main()MiniComplex numl(23, 34),num2(56, 35);cout“Initial Value of num1=“num1“/n Initial Value of num2=“num2end1;coutnum1“+“num2“=“num1+num2end1; /使用重载的加号运算符coutnum1“-“num2“=“num1-num2end1; /使用重载的减号运算符coutnum1“*“
17、num2“=“num1*num2end1; /使用重载的乘号运算符coutnum1“/“num2“=“num1/num2end1; /使用重载的除号运算符(5) ;（分数：15.00）_七、试题七(总题数：1，分数：15.00)5.【说明】Stack 类是 java. ntil 包中专门用来实现栈的工具类。以下 Java 程序是一个不使用库函数而实现字符串反转的程序。例如，输入：123456，则输出：654321：输入：asdfeg，则输出：gefdsa。【Java 程序】import java.applet.Applet;import java.awt.*;import java.awt.e
18、vent.*;import java.util.*;public class UseStack extends Applet implements ActionListenerStack MyStack;Label prompt=new Label(“输入要反转字符:“);Button pushBtn=new Button(“压栈“);Button popBtn=new Button(“弹栈“); /反转TextField input=new TextField(5);int DrawStack =new int10; /记录堆栈中数据int PoppedOut=new int20; /记录被
19、弹出的数据int StackCnt=0; /记录模拟堆栈的数组中的数据个数String msg=“ “;public void init()MyStack=new Stack();add(prompt);add(input);add(pushBtn);add(popBtn);pushBtn.addActionListener(this);(1) public void paint(Graphics g)for (int i=10; iStackCnt; i+) /模拟显示堆栈内部的数据排列情况g.drawRect(50,200-i*20,80,20);g.drawString(Integer.
20、toString(DrawStacki),80,215-i*20);for (int i=0; (2) ) /显示被弹出的数据g.drawString(Integer.toString(PoppedOuti),200+i*20,100);g.drawString(“堆栈“,70,236);g.drawString(“栈底“,135,225);g.drawString(“栈顶“,160,225-StackCnt*20);g.drawString(msg,200,140);public void actionPerformed( (3) )if (e.getAct ionCommand () =
21、“压栈“) /压栈操作if(StackCnt10)MyStack.push(new Integer( (4) );DrawStackStackCnt+=Integer.parseInt(input.getText() );input.setText (“ “);elsemsg=“输入数据过多，请先弹栈!“else if (e.getActionCommand () = “弹栈“) /弹栈操作if( (5) )StackCnt-;PoppedOutPopCnt+=(Integer)(MyStack.pop().intValue();elsemsg=“堆栈已空，不能再弹栈!“;repaint();
22、（分数：15.00）_初级程序员下午试题-93 答案解析(总分：105.00，做题时间：90 分钟)一、试题一(总题数：1，分数：15.00)【算法说明】某商务交流中心共有 N 间客房。每间客房的房间号、房间等级、床位数及占用状态分别存放在数组ROOM、RANK、NBED 和 STATUS 中。房间等级值为 1、2 或 3。房间的状态值为 0(空闲)或 1(占用)。客房是以房间(不是床位)为单位出租的。程序流程图(见图 2-11)所反映的算法是，根据几个散客的要求预订一间空房。程序的输入为：人数 M，房间等级要求尺(R=0 表示任意等级都可以)。程序的输出为：所有可供选择的房间号。（分数：15
23、.00）_正确答案：(1)房间未被占用，即 STATUS(I)=02)房间的床铺要足够，即 NBED(I)=M3)若客人要求特定的房间等级 R(R!=0)，则 RANK(I)R，否则 RANK(I)的值不做考虑)解析：要点解析 在程序流程图(见图 2-11)中，I 表示房间序号(需注意不是房间的编号)。当 IN 时表示所有的房间都检查过了，若 STATUS(I)0，表示房间已被占用，则检查下一个房间；否则查看房间的床铺是否足够。着 NBED(I)M 表示房间床铺不够，则检查下一个房间：若床铺足够，则需看客人对房间等级是否有要求。若 R!=0，表示客人对房间等级有要求，则检查 RANK(I)是否
24、等于尺。若不等于，则检查下一个房间；若 RANK(I)=R 或者 R=0，分别表示房间等级满足要求和客人对房间等级无要求，则当前的房间 I 满足所有的条件。接着可将房间 I 的房间编号 ROOM(1)存放到 RM(J)中，然后检查下一个房间。综合以上分析结果，某个房间 I 要满足下列条件才可被选中：1)房间未被占用，即 STATUS(I)=0：2)房间的床铺要足够，即 NBED(I)=M；3)若客人要求特定的房间等级 R(R!=0)，则 RANK(I)=2R，否则 RANK(I)的值不做考虑。_正确答案：(1)1101 1202 1302(2)1201)解析：要点解析 当输入 M=3，R=0
25、时，表示客人的人数为 3，对房间的等级没有要求，因此，只要房间的床铺足够且房间未被占用即可满足要求。换言之，在表 2-14 中 NBED 列中的值大于等于 3，STATUS 列中的值为 0 即可满足条件，因此输出的结果为：1101 1202 1302。当输入 M=2，R=1 时，表示客人的人数为 2，要求房间的等级为 1 级，因此，在房间的床铺足够且房间未被占用时，还要求房间的等级为 1 级才可满足要求。换言之，表 2-14 中 RANK 列中的值等于 1，NBED 列中的值大于等于 2，STATUS 列中的值为 0 即可满足条件，因此，输出的结果为：1201。_正确答案：(3)RATE(RA
26、NK(I)*M-DAYRENT(J)解析：要点解析 结合常识可知，由于房间的费用是根据房间的等级和房间所住客人的数量决定的，因此在等级为了的房间每人每天的住宿费为 RATE(r)的前提下，为使该算法在输出每个候选的房间号 RM(J)后，再输出这批散客每天所需的总住宿费 DAYRENT(J)，在图 2-11 中“ROOM(1)RM(J)”之后应增加的处理语句如下。RATE(RANK(I)*MDAYRENT(J)_正确答案：(4)I，N|J=K，或其他等价形式)解析：要点解析 如果要限制该算法最多输出 K 个可供选择的房间号，则必须知道已经选择的房间的个数。由于变量 J 的值代表了满足条件的房间数
27、量，因此在图 2-11 中判断语句“IN”应修改为：IN|J=K。二、试题二(总题数：1，分数：15.00)1.【说明】以下【C 程序】能将自然数 1，2，N 2按蛇形方式逐个存入 N 阶矩阵。换言之，程序从 anO开始到 aOn。为止(n=N-1)顺序填入自然数，交替地对每一斜列从左上元素向右下元素或从右下元素向左上元素存数。例如，当 N=5 时，程序输出结果如图 2-12 所示；当 N=8 时，程序输出结果如图 2-13 所示。（分数：15.00）_正确答案：(1)row_startrow_end?1：-1 或(row end-row start)0)*2-1 或其他等价的代码形式(2)(
28、row-end-i)*sign=0 或其等价的代码形式(3)2*n+1 或其等价的代码形式(4)n，d-1，n+1-d(5)n+1-d，0，n(6)2*n-d+1，n，0(7)0，d n-1，2*n-d+1)解析：要点解析这是一道要求读者掌握二维数组应用的程序设计题。本题的解答思路如下。本程序由主函数 main、函数 makeline 和函数 makeArray 组成。函数 makeArray 通过对函数 makeline 的调用，每次形成矩阵的一条斜线，直到完成整个矩阵。主函数 main 通过调用函数 makeArray 分别形成了1 阶至 10 阶(由常量 SIZE 决定)的蛇形矩阵，并将
29、其输出。函数 makeline 的 3 个参数分别为起点的行号、列号及终点的行号。sing 是行列号的增量。当从人上到右下方填数时，变量 sing 值为 1，此时终点行号(row_end)大于起点行号(row_start)；当从右下方到左上方填数时，变量 sing 值为-1，此时终点行号小于起点行号。(1)空缺处所填写内容的功能是对变量 sing赋值，应填入“row_startrow_end?1:-1”，或“(row_end-row_start)0)*2-1”，或其他等价的代码形式。函数 makeline 中的 for 循环是对斜线的元素进行赋值。(2)空缺处是循环的结束条件，所填入的内容是“
30、(row_end-i)*sign=0”。函数 makeArray 通过多次调用 makeline 形成矩阵的各条斜线。顺序是从左下角填起，第奇数条斜线从右下方向左上方填写，第偶数条斜线从左上方向右下方填。对于第 d 条斜线，如果在主对角线左下(即 d=n)，其左上角的行号、列号分别为 n+1-d 和 0，右下角的行号、列号分别为 n 和 d-1。而(4)、(5)空缺处所填写的语句是处理主对角线左下的各条斜线，根据斜线方向和起止位置，应分别填入“n，d-1， n+1-d”和“n+1-d，0，n”。如果在主对角线右上，其左上角的行号、列号分别为 0 和 d-n-1，右下角的行号、列号分别为 2*n
31、 -d+1和 n。(6)、(7)空缺处所填写的语句是处理主对角线右上的各条斜线。根据斜线方向利起止位置，应分别填入“2*n-d+1，n，0”和“0，d-n-1，2*n-d+1”。需要注意的是：函数 makeArray 中的 n 不是阶数 N，而是 N-1。函数 makeArray 通过调用函数 makeline 形成矩阵的 2*n+1 条斜线。而(3)空缺处是控制 for 循环的终值，其所填写的内容是“2*n+1”。三、试题三(总题数：1，分数：15.00)2.【说明】某超市集团为发展业务向社会公开招聘 N 个工种的工作人员，每个工种各有不同的编号(1 至 M)和计划招聘人数。每位应聘者需申报
32、两个工种，并参加集团组织的考试。该集团公司将按应聘者的成绩从高分至低分的顺序进行排队录取。具体录取原则是：从高分到低分依次对每位应聘者先按其第一志愿录取；当不能按其第一志愿录取时，便将他的成绩扣去 5 分后，重新排队，并按其第二志愿录取。以下 C 程序为输出各工种实际招聘的应聘人员，每个工种都保留一个录取者的有序队列。录取处理循环直至招聘额满或已对全部应聘者都作了录取处理后跳出。C 程序中，类型 STU 包含有应聘者的基本信息：编号、成绩、志愿、排队成绩和录取志愿号。数组 rzl)的每个元素对应一个工种，包含有计划招聘人数和已录取的人数。【C 程序】#include#define N 36#d
33、efine EDMARK 5typedef struct stu int no, total, z2, sortm, zi;struct stu *next;STU;struct rznode int lmt, count;STU *next;rz N;STU *head = NULL, *over = NULL;int allFILE *fp;char dataf = “zp2008.dat“ ;print(STU *p)for (;p!=NULL; p = p-next)printf( “%d(%d) /t“ , p-no, p-totalinsert(STU *p, STU *u)STU
34、 *v, *q;for (q = *p;q != NULL; v = q , (1) )if (q- sortm u-sortm)break;if ( q = *p)(2) ;else(3) ;u-next = q ;main ( )int zn, i, no, total, zl, z2 ;STU *p, *v, *q;fp = fopen(dataf, “r“ );if (fp = NULL)printf (“Cant open file %s.kn“ ,dataf);exit (0);fscanf (fp, “%d“ ,for (all = 0, i = 1; i = zn; i+)fs
35、canf (fp, “%d“, rzi.count = 0;rzi.next = NULL;all += (4) ;for (;)if ( fscanf(fp, “%d%d%d%d“ ,p = ( STU *) malloc (sizeof (STU);p-no = no;p-total = p-sortm = total;p-zi = 0;p-z0 = z1;p-z1 = z2;(5) ;fclose (fp);for (;all )p = head;head = head-next;if (rzp-zp-zi.count (6) )rzp-zp-zi.count +;insert(all-
36、;continue;if (p-zi = 1 )p-next = over;over = p;continue;p-sortm -= DEMARK;(7) ;insert(for (i = 1; i = zn; i+ )printf(“%d:/n“ ,i);print( rzi .next);printf(“ /n“);printf( “over:/n“ );print(head);print(over);printf(“ /n“);（分数：15.00）_正确答案：(1)q=q-next 或 q=v-next 或其等价的代码形式(2)*p=u 或其等价的代码形式(3)v-next=u 或其等价
37、的代码形式(4)rzi.1mt(5)insert(class MiniComplexpublic: /重载流插入和提取运算符(1) ostreamreturn osObject;(2) istreamisObject complex.realPartchcomplex.imagPartch;return isObject;MiniComplex(double real=0,double imag=0); /构造函数MiniComplex operator+(const MiniComplex /重载运算符+MiniComplex operator-(const MiniComplex /重载运
38、算符-MiniComplex operator*(const MiniComplex /重载运算符*MiniComplex operator/(const MiniComplex /重载运算符/bool operator=(const MiniComplex /重载运算符=private :double (3) ;double imagPart;#end if#include “MiniComplex.h“bool MiniComplex:operator=(const MiniComplexMiniComplex:MiniComplex(double real,double imag)rea
39、lPart= real; imagPart=imagPart;MiniComplex MiniComplex:operator+(const MiniComplextemp.realPart = realPart+ortherComplex. realPart;temp.imagPart = imagPart +ortherComplex. imagPart;return temp;(4) MiniComplex temp;temp.realPart= realPart-ortherComplex. realPart;temp.imagPart = imagPart-ortherComplex
40、. imagPart;return temp;MiniComplex MiniComplex:operator*(const MiniComplextemp.realPart = (realPart*ortherComplex. realPart)-(imagPart *ortherComplex.imagPart);temp.imagPart = (realPart*ortherComplex. imagPart)+(imagPart *ortherComplex.realPart);return temp;MiniComplex MiniComplex:operator/(const Mi
41、niComplexfloat tt;tt=1/(ortherComplex.realPart*ortherComplex.realPart+ortherComplex.imagPart *ortherComplex. imagPart);temp.realPart=(realPart*ortherComplex, realPart)+(imagPart *ortherComplex. imagPart)*tt;temp.imagPart =(imagPart *ortherComplex. realPart)-(realPart*ortherComplex. imagPart)*tt;retu
42、rn temp;#include iostream#include MiniComplex.husing namespace std;int main()MiniComplex numl(23, 34),num2(56, 35);cout“Initial Value of num1=“num1“/n Initial Value of num2=“num2end1;coutnum1“+“num2“=“num1+num2end1; /使用重载的加号运算符coutnum1“-“num2“=“num1-num2end1; /使用重载的减号运算符coutnum1“*“num2“=“num1*num2en
43、d1; /使用重载的乘号运算符coutnum1“/“num2“=“num1/num2end1; /使用重载的除号运算符(5) ;（分数：15.00）_正确答案：(1)friend(2)friend(3)RealPart(4)MiniComplex MiniComplex:operator-(const MiniCompleximport java.awt.*;import java.awt.event.*;import java.util.*;public class UseStack extends Applet implements ActionListenerStack MyStack;Label prompt=new Label(“输入要反转字符:“);Button pushBtn=new Button(“压栈“);Button popB
