银符考试题库-在线练习-初级程序员下午试题模拟55

试题一
阅读下列说明和流程图，将应填入 (n) 处的字句写在对应栏内。
[流程图说明]
下列流程图用于从数组K中找出一切满足：K(I)+K(J)=M的元素对(K(I)，K(J))(1≤I≤J≤N)。假定数组K中的N个不同的整数已按由小到大的顺序排列，M是给定的常数。
[流程图]

此流程图中，比较“K(I)+K(J):M”最少执行次数约为。

1.

≥

2.

＜

3.

1+1→I

4.

J-1→J

5.

N/2

[解析] 本题算法的思路是：设置了两个变量I和J，初始时分别指向数组K的第一个元素和最后一个元素。如果这两个元素之和等于M时，输出结果，并且这两个指针都向中间移动; 如果小于M，则将指针I向中间移动(因为数组K已按由小到大的顺序排列); 如果大于M，则将指针J向中间移动(因为数组K已按由小到大的顺序排列)。当I≥J时，说明所有的元素都搜索完毕，退出循环。
根据上面的分析，空(1)和空(2)要求填写循环结束条件，显然，空(1)处应填写“≥”，空(2)处应填写“＜”。这里主要要注意I=J的情况，当I=J时，说明两个指针指向同一元素，应当退出循环。
空(3)在流程图中有两处，一处是当K(I)+K(J)=M时，另一处是当K(I)+K(J)＜M时，根据上面分析这两种情况都要将指针I向中间移动，即“I+1→I”。同样的道理，空(4)处应填写“J-1→J”。
比较“K(I)+K(J):M”最少执行次数发生在第1元素与第N个元素之和等于M、第2元素与第N-1个元素之和等于M、……，这样每次比较，两种指针都向中间移动，因此最小执行次数约为“N/2”。

试题二
阅读以下函数说明和C语言函数，将应填入 (n) 处的字句写在对应栏内。
1说明]
函数int circle(int n，int d)判定正整数n的d进制表示形式是否是回文数。
[函数2.1]
int 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进制数(2≤d≤16)。
[函数2.2]
#define M sizeof(unsigned int)*8
int trans (unsigned n,int d,char s[])
{ static char digits[]="0123 456789ABCDEF";
char buf [M+1];
int j，i=M;
if (d＜2 ||d＞16)
{
s[0]='\0';
return 0;
}
3 ;
do
{
4 ;
n/=d;
}while (n) ;
for( 5 ); (s(j)=buf[j]!='\0';j++);
return j;
}

1.

s=s*d+m%d

2.

s==n

3.

buf[i]='\0'

4.

buf[--i]=digits[n%d]

5.

j=0

[解析] 回文数就是顺着看和倒着看相同的数。例如，n=232，它的十进制表示回文数; 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进制数表示的最低位至最高位数字。由各位数字取出相应字符，就能得到n的d进制的字符串。

试题三
阅读下列函数说明和C代码，将应填入 (n) 处的字句写在对应栏内。
[说明]
函数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-＞data ! =x || top ! =0)
{ while (t!=NULL ＆＆ t-＞data !=x)
{
//寻找值为x的结点
1 ;
ST [top].ptr=t;
ST[top].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(top＞0)
{
ST [top] .tag=1;
5 ;
}
}
}

1.

top++

2.

t=t-＞leftChild

3.

i=top

4.

top＞0 ＆＆ ST[top].tag=1

5.

t=ST[top].ptr-＞rightChild

[解析] 这个程序是一个典型二叉树后序遍历非递归算法的应用。
算法的实现思路是：先扫描根结点的所有左结点并入栈; 当找到一个结点的值为x时，则输入出栈里存放的数据，这些数据就是该结点所有祖先结点; 然后判断栈顶元素的右子树是否已经被后序遍历过，如果是，或者右子树为空，将栈顶元素退栈，该子树已经全部后序遍历过，如果不是，则对栈顶结点的右子树进行后序遍历，此时应把栈顶结点的右子树的相应结点放入栈中。再重复上述过程，直至遍历过树中所有结点。空(1)和空(2)所在循环就是扫描根结点的所有左结点并入栈，根据程序中的栈的定义，栈空时top=0，因此在入栈时，先将栈顶指针加1，因此空(1)处应填写“top++”或其等价形式，空(2)是取当前结点的左子树的根结点，因此应填写“t=t-＞leftChild”。空(3)所在循环是处理找到值为x的结点，那么该结点的所有祖先结点都存放在栈中，栈中的栈底是二叉树的根，而栈顶元素是该结点的父结点，因此，空(3)处应填写“i=top”。空(4)所在循环是判断栈顶元素的右子树是否已经被后序遍历过，如果是，或者右子树为空，将栈顶元素退栈，这里要填写判断条件。tag=0表示左子树，tag=1表示右子树，因此，空(4)处应填写“top＞0 ＆＆ ST[top].tag=1”。空(5)所在语句块是处理栈顶元素的右子树没有被后序遍历的情况，则将右子树入栈，因此空(5)处应填写“t=ST[top].ptr-＞rightChild”。

试题四
阅读以下函数说明和C语言函数，将应填入 (n) 处的字句写在对应栏内。
[说明]
下面的程序是通过双链结构来查找学生的信息程序的一部分，即创建双向链表部分。
[函数]
#include ＜stdio.h＞
#define N 10
typedef struct node
{
char 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 find space! \n") ;
exit (0) ;
}
h-＞name[0]='\0';
h-＞llink=NULL;
h-＞rlink=NULL;
p=h;
for(i=0; i＜n; i++)
{
if((s= (stud *) malloc (sizeof (stud)))==NULL)
{
printf ("cannot find space! \n") ;
exit (0) ;
}
1 ;
printf("Please input the %d man's name: ";i+1) ;
scanf("%s", s-＞name) ;
2 ;
3 ;
p=s ;
}
4 ;
5 ;
return (h) ;
}

1.

p-＞rlink=s

2.

s-＞llink=p

3.

s-＞rlink=NULL

4.

h-＞llink=s

5.

p-＞rlink=h

[解析] 双向链表有两条方向不同的链，即每个结点中除next域存放后继结点地址外，还增加一个指向其直接前驱的指针域prioro这样在查找过程中，当指针处在中间某个结点时不仅可以像单链表那样向后查找，而且可以返回之前找过的结点。本题考察双向链表的构造，程序中首先构造了一个头结点，并将头结点的左右指针都设为空; 然后构造新的结点，让头结点的右指针指向该结点，即空(1)填p-＞rlink=s，该结点的左指针指向头结点，即空(2)填s-＞llink=p，以此类推，最后将头结点的左指针指向最后一个结点，最后一个结点的右指针指向头结点，形成一个环，即空(4)和空(5)分别填入h-＞llink=s和p-＞rlink=h。

试题五
阅读以下说明和C++程序，将应填入 (n) 处的字句写在对应栏内。
[说明]
下面程序是一个小型公司工资管理的程序。该公司主要有4类人员：经理、兼职技术人员、销售员和销售经理。基类为employee，由它派生出technician类，manager类，salesman类，最后由manager类和salesman类派生出salesmanager类。月工资计算办法是：经理拿固定月薪8000;兼职技术人员按每小时100元领取月薪; 销售按当月销售额的4%提成; 销售经理既拿固定月工资也领取销售提成，固定月工资5000元，销售提成为所管辖部门当月销售总额的0.5%。
[C++程序]
#include＜iostream.h＞
#include＜string.h＞
class employee
{
protected:
int no;
char name [10] ;
float salary;
public :
employee ()
{
cout＜＜ "职工编号: " ;
cin＞＞no ;
cout＜＜"职工姓名:";
cin＞＞name ;
salary= 0 ;
}
void pay () {}
void display () {}
};
class technician:public employee
private :
float hourlyrate;
int workhours;
public :
technician() {hourlyrate=100; }
void pay ()
{
cout＜＜name本月工作时数: " ;
cin＞＞workhours ;
salary=hourlyrate*workhours;
}
void display ()
{
cout＜＜"兼职技术人员"＜＜name＜＜"(编号为"＜＜no\
＜＜")"＜＜"本月工资："＜＜salary＜＜endl;
}
};
class salesman: 1
{
protected:
float commrate;
float sales;
public：
salesman() {commrate=0.04;}
void pay()
{
cout＜＜name＜＜"本月销售额：";
cin＞＞sales;
salary= 2 ;
}
void display()
{
cout＜＜"销售额"name＜＜"(编号"＜＜no＜＜\
＜＜")"＜＜"本月工资："＜＜salary＜＜endl;
}
};
class manager: 3
{
protected:
float monthlypay;
public：
manager(){monthlypay=8000;}
void pay(){salary=monthlypay;}
void display()
{
cout＜＜"经理"＜＜name＜＜"(编号为"＜＜no\
＜＜")"＜＜"本月工资："＜＜salary＜＜endl;
}
};
class salesmanager: 4
{
public：
salesmanager()
{
monthlypay=5000;
commrate=0.005;
}
void pay()
{
cout＜＜name＜＜"所管部门月销售量：";
cin＞＞sales：
salary= 5 ;
}
void display()
{
cout＜＜"销售经理"＜＜name＜＜"(编号为"＜＜no\
＜＜")"＜＜"本月工资："＜＜salary＜＜endl;
}
};

1.

virtual public employee

2.

sales*commrate

3.

virtual public employee

4.

public manager,public salesman

5.

monthlypay+commrate*sales

[解析] 本题以C++语言为载体，考查面向对象的对象设计中的重要概念——虚基类。
根据题意，salesmanager是manager和salesman派生来的，当某类的部分或全部直接基类是从另一个共同基类派生而来时，这些直接基类中从上一级基类继承来的成员就拥有相同的名称。在派生类的对象中，同名成员在内存中同时拥有多个副本，可以使用作用域分辨符来唯一标识并分别访问它们，也可以将直接基类的共同基类设置为虚基类。所以空(1)和空(3)应该分别填入virtual public employee和virtual public employee，空(4)应该填入public manager，public salesman，根据题目中的条件，可以填写出销售员和销售经理的月薪公式，空(2)和空(5)应该分别填入sales*commrate和monthlypay+commrate*sales。

试题六
阅读以下说明及程序，将应填入 (n) 处的字句写在对应栏内。
[说明]
以下程序的功能是计算三角形、矩形和正方形的面积并输出，程序由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++) {
System. out .println (figures [i] +"area=" +figures [i]. getArea ());
}
}
}
public abstract class Figure{
public 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 () {
return "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,double 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)) ;
}
}

1.

Figure

2.

height*width

3.

Rectangle

4.

super(width, width)

5.

Figure

[解析] 本题考查的是Java面向对象程序设计中继承、抽象类的概念和应用。
由题意可知，题中程序的功能是计算不同图形的面积。题中已指明类Figure是抽象类，所以Figure只能作为基类。因此，空(1)处应填：Figure。分析一下程序可知，类Rectangle直接继承类Figure，将实现Figure中的抽象方法getArea()，长方形的面积是长×宽，显然，空(2)处应填：height*width。空(3)处填的是类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所示。

考生在解答此类题型时，应搞清楚类的继承关系，这是题目的难点，也是关键点。继承关系可从抽象类、方法的实现等角度来判断。