1、初级程序员下午试题-101 及答案解析(总分：150.00，做题时间：90 分钟)一、试题一(总题数：1，分数：15.00)流程图说明下列流程图用于从数组 K中找出一切满足：K(I)+K(J)=M 的元素对(K(I)，K(J)(1IJN)。假定数组K中的 N个不同的整数已按由小到大的顺序排列，M 是给定的常数。流程图（分数：15.00）填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_二、试题二(总题数：1，分数：15.00)1说明函数 int circle(int n，int d)判定正整数 n的 d进制表示形式是否是回文数。函数 2.1int circle(int n,
2、int d)int s=0,m=n;while (m)(1) ; m/=d;return (2) ;函数 2.2说明函数 int trans(unsigned n，int d，char s)将一个无符号整数转换为任意 d进制数(2d16)。函数 2.2#define M sizeof(unsigned int)*8int trans (unsigned n,int d,char s)static char digits=“0123 456789ABCDEF“;char buf M+1; int j，i=M;if (d2 |d16)s0=/0;return 0;(3) ;do(4) ;n/=d;
3、 while (n) ;for( (5) ); (s(j)=bufj!=/0;j+);return j;（分数：15.00）填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_三、试题三(总题数：1，分数：15.00)说明函数 print (BinTreeNode *t; DateType x)的功能是在二叉树中查找值为 x的结点，并打印该结点所有祖先结点。在此算法中，假设值为 x的结点不多于一个。此算法采用后序的非递归遍历形式。函数中使用栈 ST保存结点指针 ptr以及标志 tag，Top 是栈顶指针。函数void print (BinTreeNode * t; DateT
4、ype x) stack ST;int i,top;top=0; /置空栈while (t ! =NULL t-data ! =x | top ! =0)while (t!=NULL t-data !=x)/寻找值为 x的结点(1) ; ST top.ptr=t;STtop.tag=0;(2) ;if(t!=Null t-data=x) /找到值为 x的结点for(i=1; (3) ; i+)printf(“%d“, ST top.ptr-data);else while( (4) )top-;if(top0)ST top .tag=1;(5) ;（分数：15.00）填空项 1:_填空项 1:
5、_填空项 1:_填空项 1:_填空项 1:_四、试题四(总题数：1，分数：15.00)说明下面的程序是通过双链结构来查找学生的信息程序的一部分，即创建双向链表部分。函数#include stdio.h#define N 10typedef struct nodechar name 20;struct node *llink,*rlink;stud; /*双链表的结构定义*/*双链表的创建*/stud * creat (int n)stud *p,*h,*s;int i;if (h= (stud *) malloc (sizeof (stud) =NULL)printf (“cannot fin
6、d space! /n“) ;exit (0) ;h-name0=/0;h-llink=NULL;h-rlink=NULL;p=h;for(i=0; in; i+)if(s= (stud *) malloc (sizeof (stud)=NULL)printf (“cannot find space! /n“) ;exit (0) ;(1) ;printf(“Please input the %d mans name: “;i+1) ;scanf(“%s“, s-name) ;(2) ;(3) ;p=s ;(4) ;(5) ;return (h) ;（分数：15.00）填空项 1:_填空项 1
7、:_填空项 1:_填空项 1:_填空项 1:_五、试题五(总题数：1，分数：15.00)说明下面程序是一个小型公司工资管理的程序。该公司主要有 4类人员：经理、兼职技术人员、销售员和销售经理。基类为 employee，由它派生出 technician类，manager 类，salesman 类，最后由 manager类和salesman类派生出 salesmanager类。月工资计算办法是：经理拿固定月薪 8000;兼职技术人员按每小时100元领取月薪; 销售按当月销售额的 4%提成; 销售经理既拿固定月工资也领取销售提成，固定月工资5000元，销售提成为所管辖部门当月销售总额的 0.5%。C
8、+程序#includeiostream.h#includestring.hclass employeeprotected:int no;char name 10 ;float salary;public :employee ()cout “职工编号: “ ;cinno ;cout“职工姓名:“;cinname ;salary= 0 ;void pay () void display () ;class technician:public employeeprivate :float hourlyrate;int workhours;public :technician() hourlyrate
9、=100; void pay ()coutname 本月工作时数: “ ;cinworkhours ;salary=hourlyrate*workhours;void display ()cout“兼职技术人员“name“(编号为“no/“)“本月工资：“salaryendl;class salesman: (1) protected:float commrate;float sales;public：salesman() commrate=0.04;void pay()coutname“本月销售额：“; cinsales;salary= (2) ;void display()cout“销售额
10、“name“(编号“no/“)“本月工资：“salaryendl; class manager: (3) protected:float monthlypay;public：manager()monthlypay=8000;void pay()salary=monthlypay;void display()cout“经理“name“(编号为“no/“)“本月工资：“salaryendl; class salesmanager: (4) public：salesmanager()monthlypay=5000;commrate=0.005;void pay()coutname“所管部门月销售量：
11、“; cinsales：salary= (5) ; void display()cout“销售经理“name“(编号为“no/“)“本月工资：“salaryendl;（分数：15.00）填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_六、试题六(总题数：1，分数：75.00)说明以下程序的功能是计算三角形、矩形和正方形的面积并输出，程序由 5个类组成：AreaTest 是主类，类Trianlge、Rectangle 和 Square分别表示三角形、矩形和正方形，抽象类 Figure提供了一个计算面积的抽象方法。程序public class AreaTest public
12、static void main(String args ) Figure figures= new Triangle (2,3,3) ,new Rectangle (5,8) ,new Square (5) ;for (int i=0; 1 figures .length; i+) System. out .println (figures i +“area=“ +figures i. getArea ();public abstract class Figurepublic abstract double getArea() ;public class Rectangle extends
13、(1) double height;double width;public Rectangle(double height, double width) this .height=height;this.width=width;public String toString () return “Rectangle: height= “+height+“ , width= “+width+“:“;public double getArea () return (2) ;class Square extends (3) public Square(double width) (4) ;public
14、 string toString () return “Square: width= “+width+“ : “ ;class Triangle extends (5) double la;double lb;double lc;public Triangle(double la,double lb, double lc) this.la=la; this.lb=lb; this.lc=lc;public String toString() return “Triangle : sides= “+la+“ , “+lb+“ , “ +lc+“ : “ ;public double getAre
15、a () double s= (la+lb+lc)/2.0;return Math. sqrt (s* (s-la) * (s-lb) * (s-lc) ;（分数：75.00）填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_初级程序员下午试题-101 答案解析(总分：150.00，做题时间：90 分钟)一、试题一(总题数：1，分数：15.00)流程图说明下列流程图用于从数组 K中找出一切满足：K(I)+K(J)=M 的元素对(K(I)，K(J)(1IJN)。假定数组K中的 N个不同的整数已按由小到大的顺序排列，M 是给定的常数。流程图（分数：15.00）填空项 1:_ （
16、正确答案：）解析：填空项 1:_ （正确答案：）解析：填空项 1:_ （正确答案：1+1I）解析：填空项 1:_ （正确答案：J-1J）解析：填空项 1:_ （正确答案：N/2）解析：解析 本题算法的思路是：设置了两个变量 I和 J，初始时分别指向数组 K的第一个元素和最后一个元素。如果这两个元素之和等于 M时，输出结果，并且这两个指针都向中间移动; 如果小于 M，则将指针 I向中间移动(因为数组 K已按由小到大的顺序排列); 如果大于 M，则将指针 J向中间移动(因为数组 K已按由小到大的顺序排列)。当 IJ 时，说明所有的元素都搜索完毕，退出循环。根据上面的分析，空(1)和空(2)要求填写
17、循环结束条件，显然，空(1)处应填写“”，空(2)处应填写“”。这里主要要注意 I=J的情况，当 I=J时，说明两个指针指向同一元素，应当退出循环。空(3)在流程图中有两处，一处是当 K(I)+K(J)=M时，另一处是当 K(I)+K(J)M 时，根据上面分析这两种情况都要将指针 I向中间移动，即“I+1I”。同样的道理，空(4)处应填写“J-1J”。比较“K(I)+K(J):M”最少执行次数发生在第 1元素与第 N个元素之和等于 M、第 2元素与第 N-1个元素之和等于 M、，这样每次比较，两种指针都向中间移动，因此最小执行次数约为“N/2”。二、试题二(总题数：1，分数：15.00)1说明
18、函数 int circle(int n，int d)判定正整数 n的 d进制表示形式是否是回文数。函数 2.1int circle(int n,int d)int s=0,m=n;while (m)(1) ; m/=d;return (2) ;函数 2.2说明函数 int trans(unsigned n，int d，char s)将一个无符号整数转换为任意 d进制数(2d16)。函数 2.2#define M sizeof(unsigned int)*8int trans (unsigned n,int d,char s)static char digits=“0123 456789ABCD
19、EF“;char buf M+1; int j，i=M;if (d2 |d16)s0=/0;return 0;(3) ;do(4) ;n/=d; while (n) ;for( (5) ); (s(j)=bufj!=/0;j+);return j;（分数：15.00）填空项 1:_ （正确答案：s=s*d+m%d）解析：填空项 1:_ （正确答案：s=n）解析：填空项 1:_ （正确答案：bufi=/0）解析：填空项 1:_ （正确答案：buf-i=digitsn%d）解析：填空项 1:_ （正确答案：j=0）解析：解析 回文数就是顺着看和倒着看相同的数。例如，n=232，它的十进制表示回文数
20、; n=27，它的二进制表示 11011是回文数; n=851，它的十六进制表示 353是回文数。设判断是否为回文数的函数为circle(int n，int d)，它有两个参数 n和 d。其中 n为要判定是否为回文数的整数，d 指将 n转成 d进制表示。为判定 n是否是 d进制表示形式中的回文教，一种办法是：首先顺序译出 n的 d进制的各位数字，然后把译出的各位数字将低位当高位按 d进制的转换方法译成一个整数，若 n是回文数，则转换所得的整数应与 n相等; 否则，n 不是回文数。求 n整除 d的余数，就能得到 n的 d进制数的最低位数字，重复上述步骤，直至 n为 0，依次得到 n的 d进制数表
21、示的最低位至最高位数字。由各位数字取出相应字符，就能得到 n的 d进制的字符串。三、试题三(总题数：1，分数：15.00)说明函数 print (BinTreeNode *t; DateType x)的功能是在二叉树中查找值为 x的结点，并打印该结点所有祖先结点。在此算法中，假设值为 x的结点不多于一个。此算法采用后序的非递归遍历形式。函数中使用栈 ST保存结点指针 ptr以及标志 tag，Top 是栈顶指针。函数void print (BinTreeNode * t; DateType x) stack ST;int i,top;top=0; /置空栈while (t ! =NULL t-d
22、ata ! =x | top ! =0)while (t!=NULL t-data !=x)/寻找值为 x的结点(1) ; ST top.ptr=t;STtop.tag=0;(2) ;if(t!=Null t-data=x) /找到值为 x的结点for(i=1; (3) ; i+)printf(“%d“, ST top.ptr-data);else while( (4) )top-;if(top0)ST top .tag=1;(5) ;（分数：15.00）填空项 1:_ （正确答案：top+）解析：填空项 1:_ （正确答案：t=t-leftChild）解析：填空项 1:_ （正确答案：i=t
23、op）解析：填空项 1:_ （正确答案：top0 STtop.tag=1）解析：填空项 1:_ （正确答案：t=STtop.ptr-rightChild）解析：解析 这个程序是一个典型二叉树后序遍历非递归算法的应用。算法的实现思路是：先扫描根结点的所有左结点并入栈; 当找到一个结点的值为 x时，则输入出栈里存放的数据，这些数据就是该结点所有祖先结点; 然后判断栈顶元素的右子树是否已经被后序遍历过，如果是，或者右子树为空，将栈顶元素退栈，该子树已经全部后序遍历过，如果不是，则对栈顶结点的右子树进行后序遍历，此时应把栈顶结点的右子树的相应结点放入栈中。再重复上述过程，直至遍历过树中所有结点。空(1
24、)和空(2)所在循环就是扫描根结点的所有左结点并入栈，根据程序中的栈的定义，栈空时 top=0，因此在入栈时，先将栈顶指针加 1，因此空(1)处应填写“top+”或其等价形式，空(2)是取当前结点的左子树的根结点，因此应填写“t=t-leftChild”。空(3)所在循环是处理找到值为 x的结点，那么该结点的所有祖先结点都存放在栈中，栈中的栈底是二叉树的根，而栈顶元素是该结点的父结点，因此，空(3)处应填写“i=top”。空(4)所在循环是判断栈顶元素的右子树是否已经被后序遍历过，如果是，或者右子树为空，将栈顶元素退栈，这里要填写判断条件。tag=0 表示左子树，tag=1 表示右子树，因此，
25、空(4)处应填写“top0 STtop.tag=1”。空(5)所在语句块是处理栈顶元素的右子树没有被后序遍历的情况，则将右子树入栈，因此空(5)处应填写“t=STtop.ptr-rightChild”。四、试题四(总题数：1，分数：15.00)说明下面的程序是通过双链结构来查找学生的信息程序的一部分，即创建双向链表部分。函数#include stdio.h#define N 10typedef struct nodechar name 20;struct node *llink,*rlink;stud; /*双链表的结构定义*/*双链表的创建*/stud * creat (int n)stud
26、 *p,*h,*s;int i;if (h= (stud *) malloc (sizeof (stud) =NULL)printf (“cannot find space! /n“) ;exit (0) ;h-name0=/0;h-llink=NULL;h-rlink=NULL;p=h;for(i=0; in; i+)if(s= (stud *) malloc (sizeof (stud)=NULL)printf (“cannot find space! /n“) ;exit (0) ;(1) ;printf(“Please input the %d mans name: “;i+1) ;s
27、canf(“%s“, s-name) ;(2) ;(3) ;p=s ;(4) ;(5) ;return (h) ;（分数：15.00）填空项 1:_ （正确答案：p-rlink=s）解析：填空项 1:_ （正确答案：s-llink=p）解析：填空项 1:_ （正确答案：s-rlink=NULL）解析：填空项 1:_ （正确答案：h-llink=s）解析：填空项 1:_ （正确答案：p-rlink=h）解析：解析 双向链表有两条方向不同的链，即每个结点中除 next域存放后继结点地址外，还增加一个指向其直接前驱的指针域 prioro这样在查找过程中，当指针处在中间某个结点时不仅可以像单链表那样向
28、后查找，而且可以返回之前找过的结点。本题考察双向链表的构造，程序中首先构造了一个头结点，并将头结点的左右指针都设为空; 然后构造新的结点，让头结点的右指针指向该结点，即空(1)填 p-rlink=s，该结点的左指针指向头结点，即空(2)填 s-llink=p，以此类推，最后将头结点的左指针指向最后一个结点，最后一个结点的右指针指向头结点，形成一个环，即空(4)和空(5)分别填入 h-llink=s 和 p-rlink=h。五、试题五(总题数：1，分数：15.00)说明下面程序是一个小型公司工资管理的程序。该公司主要有 4类人员：经理、兼职技术人员、销售员和销售经理。基类为 employee，由
29、它派生出 technician类，manager 类，salesman 类，最后由 manager类和salesman类派生出 salesmanager类。月工资计算办法是：经理拿固定月薪 8000;兼职技术人员按每小时100元领取月薪; 销售按当月销售额的 4%提成; 销售经理既拿固定月工资也领取销售提成，固定月工资5000元，销售提成为所管辖部门当月销售总额的 0.5%。C+程序#includeiostream.h#includestring.hclass employeeprotected:int no;char name 10 ;float salary;public :employe
30、e ()cout “职工编号: “ ;cinno ;cout“职工姓名:“;cinname ;salary= 0 ;void pay () void display () ;class technician:public employeeprivate :float hourlyrate;int workhours;public :technician() hourlyrate=100; void pay ()coutname 本月工作时数: “ ;cinworkhours ;salary=hourlyrate*workhours;void display ()cout“兼职技术人员“name
31、“(编号为“no/“)“本月工资：“salaryendl;class salesman: (1) protected:float commrate;float sales;public：salesman() commrate=0.04;void pay()coutname“本月销售额：“; cinsales;salary= (2) ;void display()cout“销售额“name“(编号“no/“)“本月工资：“salaryendl; class manager: (3) protected:float monthlypay;public：manager()monthlypay=800
32、0;void pay()salary=monthlypay;void display()cout“经理“name“(编号为“no/“)“本月工资：“salaryendl; class salesmanager: (4) public：salesmanager()monthlypay=5000;commrate=0.005;void pay()coutname“所管部门月销售量：“; cinsales：salary= (5) ; void display()cout“销售经理“name“(编号为“no/“)“本月工资：“salaryendl;（分数：15.00）填空项 1:_ （正确答案：vir
33、tual public employee）解析：填空项 1:_ （正确答案：sales*commrate）解析：填空项 1:_ （正确答案：virtual public employee）解析：填空项 1:_ （正确答案：public manager,public salesman）解析：填空项 1:_ （正确答案：monthlypay+commrate*sales）解析：解析 本题以 C+语言为载体，考查面向对象的对象设计中的重要概念虚基类。根据题意，salesmanager 是 manager和 salesman派生来的，当某类的部分或全部直接基类是从另一个共同基类派生而来时，这些直接基类
34、中从上一级基类继承来的成员就拥有相同的名称。在派生类的对象中，同名成员在内存中同时拥有多个副本，可以使用作用域分辨符来唯一标识并分别访问它们，也可以将直接基类的共同基类设置为虚基类。所以空(1)和空(3)应该分别填入 virtual public employee和 virtual public employee，空(4)应该填入 public manager，public salesman，根据题目中的条件，可以填写出销售员和销售经理的月薪公式，空(2)和空(5)应该分别填入 sales*commrate和monthlypay+commrate*sales。六、试题六(总题数：1，分数：75
35、.00)说明以下程序的功能是计算三角形、矩形和正方形的面积并输出，程序由 5个类组成：AreaTest 是主类，类Trianlge、Rectangle 和 Square分别表示三角形、矩形和正方形，抽象类 Figure提供了一个计算面积的抽象方法。程序public class AreaTest public static void main(String args ) Figure figures= new Triangle (2,3,3) ,new Rectangle (5,8) ,new Square (5) ;for (int i=0; 1 figures .length; i+) Sy
36、stem. out .println (figures i +“area=“ +figures i. getArea ();public abstract class Figurepublic abstract double getArea() ;public class Rectangle extends (1) double height;double width;public Rectangle(double height, double width) this .height=height;this.width=width;public String toString () retur
37、n “Rectangle: height= “+height+“ , width= “+width+“:“;public double getArea () return (2) ;class Square extends (3) public Square(double width) (4) ;public string toString () return “Square: width= “+width+“ : “ ;class Triangle extends (5) double la;double lb;double lc;public Triangle(double la,doub
38、le lb, double lc) this.la=la; this.lb=lb; this.lc=lc;public String toString() return “Triangle : sides= “+la+“ , “+lb+“ , “ +lc+“ : “ ;public double getArea () double s= (la+lb+lc)/2.0;return Math. sqrt (s* (s-la) * (s-lb) * (s-lc) ;（分数：75.00）填空项 1:_ （正确答案：Figure）解析：填空项 1:_ （正确答案：height*width）解析：填空项
39、 1:_ （正确答案：Rectangle）解析：填空项 1:_ （正确答案：super(width, width)）解析：填空项 1:_ （正确答案：Figure）解析：解析 本题考查的是 Java面向对象程序设计中继承、抽象类的概念和应用。由题意可知，题中程序的功能是计算不同图形的面积。题中已指明类 Figure是抽象类，所以 Figure只能作为基类。因此，空(1)处应填：Figure。分析一下程序可知，类 Rectangle直接继承类 Figure，将实现Figure中的抽象方法 getArea()，长方形的面积是长宽，显然，空(2)处应填：height*width。空(3)处填的是类
40、Square的直接父类的类名，类 Figure和类 Rectangle均有可能是类 Square的直接父类，仔细研究一下程序可发现，类 Square没有给出方法 getArea()的新的定义，所以 Figure不可能是其直接父类，因此空(3)处应填 Rectangle。空(4)处是计算正方形的面积，显然此处是要调用其父类的 getArea()方法，类 Rectangle中的 getArea()方法需两个参数，故需将正方形的边长分别赋值给长方形的长和宽，此时还需借助 Java中 super函数，利用 super函数可将类 Square中的 width传递给 Rectangle中的 height和width，所以空(4)处应填：super(width，width)。空(5)处应填类 Triangle的直接父类的类名，程序中类 Triangle已给出 getArea()的新的定义，故 Triangle的直接父类是 Figureo所以空(5)处应填：Figureo经如上分析后，四个类的继承关系便很显然了。类 Figure.类 Rectangle、类 Square、类Triangle的继承关系如图 6-1所示。
