银符考试题库-在线练习-初级程序员2012下半年下午试题

试题一

1. 阅读以下说明和流程图，填补流程图中的空缺。
[说明]
本流程图用于计算菲波那契数列{a₁=1，a₂=1，a_n=a_n-1+a_n-2,n=3,4,…}的前n项(n≥2)之和S。例如，菲波那契数列前6项之和为20。计算过程中，当前项之前的两项分别动态地保存在变量A和B中。

2或A+B或等价形式
(2)n
(3)A+B或等价形式
(4)B-A或等价形式
(5)S+B或等价形式

[解析] 本题考查菲波那契数列，菲波那契数列的特性就是a_n=a_n-1+a_n-2,要求这个数列之和，只需从第一项开始，逐步累加，直到累加到第n项。
在本题给出的程序流程图中，第一空是要给变量S赋值，从后面的内容我们不难看出S当中存放的是前m项的和，在初始时，应该存放第一项和第二项的和，因此第一空填“A+B”。
第二空是判断的条件，如果条件为真，则输出S，而i是循环变量，那么只有求了n项的和之后才会输出S，当i的值大于等于n时，就求出了前n项的和，因此第二空填“n”。第3空是给B赋值，随着i的值加1，整个计算过程往后移动，如果初始是第一和第二个元素，那么接下来就应该考虑第3个元素，存放在变量B中，而第3个元素等于第一个和第二个元素之和，因此第3空应该填“A+B”，而这个时候为了方便求解第4个元素，故应该将第二个元素值保存到变量A中，因此第4空的答案是“B-A”。而第5空是将当前项纳入求和，应该是将S+B赋值给S。

试题二

1. 阅读以下说明和C函数，填充函数中的空缺。
[说明]
如果矩阵A中的元素A[i,j]满足条件：A[i,j]是第i行中值最小的元素，且又是第i列中值最大的元素，则称之为该矩阵的一个马鞍点。
一个矩阵可能存在多个马鞍点，也可能不存在马鞍点。下面的函数求解并输出一个矩阵中的所有马鞍点，最后返回该矩阵中马鞍点的个数。
【C函数】
Int findSaddle(int a[][N],int M),
{,/^*a表示M行N列矩阵,N是宏定义符号常量^*/
int row,column,i,k;
int minElem;
int count=0;/^*count用于记录矩阵中马鞍点的个数^*/
for(row=0;row＜______;row++){
/^*minElem用于表示第row行的最小元素值,其初值设为该行第0列的元素值^*/
______;
for(column=1;column＜______;column++)
if(minElem＞a[row][column]){
minElem=a[row][column];
}
for(k=0;k＜N;k++)
if(a[row][k]==minElem){
/^*对第row行的每个最小元素,判断其是否为所在列的最大元素^*/
for(j=0;i＜M;i++)
if(______＞minElem)break;
if(i＞=______){
printf("(%d,%d):%d\n",row,k,minElem);/^*输出马鞍点^*/
count++;
}/^*if^*/
}/^*if^*/
}/^*for^*/
return count;
}/^*findSaddle^*/

M
(2)minElem=a[row][0]或其等价形式
(3)N
(4)a[i][k]或其等价形式
(5)M

[解析] 根据题目描述，我们不难知道，要求出所以马鞍点，需要遍历矩阵中所有元素，并分别判断每个元素是否是马鞍点。要判断一个点是否是马鞍点，根据题目给出的马鞍点的定义进行即可。
在本题中，第一空是for循环的循环条件，结合后面的程序我们不难看出，这个循环是要找出每行中值最小的元素，因此需要遍历每一行，而总共有M行，下标从0开始，因此第一空答案为“M”。第二空是要给变量minElem赋值，而根据题目注释，其初值设为该行第0列的元素值，因此第二空答案为“minElom=a[row][0]”。
第3空是第二重for循环的条件，很明显，这个循环是对某一行进行操作，遍历行中的所有元素，找出该行中最小值的元素，根据题目意思，每一行有N个元素，下标从0开始，因此本空答案为“N”。
从上面的分析，我们找出了每一行中值最小的元素，接下来就要判断这些元素是否是所在列值最大的元素。第4空是在一个循环下面，该循环的作用是判断某个元素是否是本列最大值，即如果该列中有元素值大于minElem，即循环结束。因此第4空答案为“a[i][k]”。
第5空是输出马鞍点的判定条件，那么在求出minElem是某列最大值时，即可输出该点，因为该点就是马鞍点，那么这个时候i>=M。

试题三

1. 阅读以下说明和C函数，填充函数中的空缺。
[说明]
函数Insert_key(^*root，key)的功能是将键值key插入到^*root指向根结点的二叉查找树中(二叉查找树为空时^*root为空指针)。若给定的二叉查找树中已经包含键值为key的结点，则不进行插入操作并返回0；否则申请新结点、存入key的值并将新结点加入树中，返回1。
提示：
二叉查找树又称为二叉排序树，它或者是一棵空树，或者是具有如下性质的二叉树：
◎若它的左子树非空，则其左子树上所有结点的键值均小于根结点的键值。
◎若它的右子树非空，则其右子树上所有结点的键值均大于根结点的键值。
◎左、右子树本身就是二叉查找树。
设二叉查找树采用二叉链表存储结构，链表结点类型定义如下：
typedef struct BiTnode{
int key_value;/^*结点的键值,为非负整数^*/
struct BiTnode^*left,^*ight; /^*结点的左、右子树指针^*/
}BiTnode,^*BSTree;
【C函数】
int Insert_key(BSTree^*root,int key)
{
BiTnode^*father=NULL,^*p=^*root,^*s;
while(______&&key!=p-＞key_value){/^*查找键值为key的结点^*/
father=p;
if(key＜p-＞key_value)p=______,/^*进入左子树^*/
else p=______;/^*进入右子树^*/
}
if(p)return 0;/^*二叉查找树中已存在键值为key的结点,无需再插入^*/
s=(BiTnode^*)malloc(______);/^*根据结点类型生成新结点^*/
if(!s)return-1;
s-＞key_value=key; s-＞left=NULL;s-＞right=NULL;
if(!fiather)
______; /^*新结点作为二叉查找树的根结点^*/
else /^*新结点插入二叉查找树的适当位置^*/
If(key＜father-＞key_value)father-＞left=s;
elsefather-＞right=s;
retum 1;
}

p
(2)p-＞left
(3)p-＞right
(4)sizeof(BiTnodel
(5)^*root=s

[解析] 根据题目描述，要插入结点，首先要找树中是否有该键值的结点，有则返回0，如果没有则申请新结点、存入key的值并将新结点加入树中，返回1。
在本题中，第一空是在while循环的循环条件中，根据题目注释知道该循环是查找键值为key的结点，需要遍历整棵树，因此应该是P不为空，所以该空的答案是“P”。
第二空是要给变量P赋值，而根据题目注释，可以知道这里是要进入左子树，因此是要让p指向左子树的根结点，因此是将p=p-＞left。同样的道理可以得出第3空的答案为“p=p-＞right”。
根据题目意思，第4空是要动态分配新结点，那么根据动态分配空间的函数malloc可知，本空应该填“sizeof(BiTnode)”。
而根据题目注释和程序可知，第5空处是原来二叉查找树为空的情况，这时要将新结点作为二叉查找树的根结点，那么只要将s赋值给^*root即可。

试题三

1. 阅读以下说明和C函数，填充函数中的空缺。
[说明]
已知两个整数数组A和B中分别存放了长度为m和n的两个非递减有序序列，函数Adjustment(A，B，m，n)的功能是合并两个非递减序列，并将序列的前m个整数存入A中，其余元素依序存入B中。
例如：

	合并前	合并后
数组A的内容	1，9，28	1，4，7
数组B的内容	4，7，12，29，37	9，12，28，29，37

合并过程如下：从数组A的第一个元素开始处理。用数组B的最小元素B[0]与数组A的当前元素比较，若A的元素较小，则继续考查A的下一个元素；否则，先将A的最大元素暂存入temp，然后移动A中的元素挪出空闲单元并将B[0]插入数组A，最后将暂存在temp中的数据插入数组B的适当位置(保持B的有序性)。如此重复，直到A中所有元素都不大于B中所有元素为止。
【C函数】
void Adjustment(int A[],int B[],int m,int n)
{ /^*数组A有m个元素,数组B有n个元素^*/
int i,k,temp;
for(i=0;i＜m;i++)
{
if(A[i]＜=B[0])continue,
temp=______;/^*将A中的最大元素备份至temp^*/
/^*从后往前依次考查A的元素,移动A的元素并将来自B的最小元素插入A中^*/
for(k=m-1; ______;k-)
A[k]=A[k-1];
A[i]=______;
/^*将备份在temp的数据插入数组B的适当位置^*/
for(k=1;______＆＆k＜n;k++)
B[k-1]=B[k];
B[k-1]=______;
}
}

A[m-1]，或^*(A+m-1)，或其等价表示
(2)k＞i，或其等价表示
(3)B[0]，或^*B
(4)temp＞B[k]，或temp＞^*(B+k)，或其等价表示
(5)temp

[解析] 在题目描述中，已经将合并的过程描述的非常清楚了，本题就是要我们实现题目描述的算法。在程序中，第1空是给变量temp赋值，根据注释和题目意思，我们可以知道，这条语句将A中的最大元素备份至temp，而A是一个非递减有序序列，那么其最大元素是最后一个元素，因为数组下标从0开始，因此第一空填应该填“A[m-1]”。
根据题目注释知道该循环是查找键值为key的结点，需要遍历整棵树，因此应该是P不为空，所有这空的答案是P。
第2空是for循环的条件，根据题目注释和程序，可以知道for循环这里是要移动A中i及后面的元素，因此移动的结束条件就是k＞i。
第3空是给A[i]赋值，其实这个时候，A[i]的值为空，给它赋值就是将B的最小元素插入A中下标为i的位置，因此第3空应该填“B[0]”。
第4空是for循环的条件，从程序和注释我们可以知道，该for循环是要将B中的元素移动，找到temp插入的适当位置，因此只要temp＞B[k]为真，循环就当继续，而第5空就非常简单了，找到了合适的插入位置，直接将temp插入即可，因此第5空填“temp”。

试题四

1. 阅读以下说明和C++代码，填充代码中的空缺。
[说明]
下面的程序用来计算并寻找平面坐标系中给定点中最近的点对(若存在多对，则输出其中的一对即可)。程序运行时，先输入点的个数和一组互异的点的坐标，通过计算每对点之间的距离，从而确定出距离最近的点对。例如，在图中所示的8个点中，点(1，1)与(2，0.5)是间距最近的点对。

【C++代码】
#include＜iostream＞
#include＜cmath＞
using namespace std;
class GPoint{
private;
doublex,y;
public;
void setX(doubte x){this-＞x=x;}
void setY(double y){this-＞y=y;}
double getX(){return this-＞x;}
double getY(){return this-＞y;}
};
class ComputeDistance{
public;
double distance(GPoint a,GPoint b){
retum sqrt＜＜a.getX()-b.getX())^*(a.getX()-b.getX())+(a.getY()-b.getY())^*(a.getY()-b.getY());
}
};
int main()
{
int i,j,numberOfPoints=0;
cout＜＜"输入点的个数:";
cin＞＞numberOfPoints;
______ points=new GPoint[numberOfPoints]; //创建保存点坐标的数组
memset(points,0,sizeof(points));
cout＜＜"输入"＜＜numberOfPoints＜＜"个点的坐标:";
for(i=0;i＜numberOfPoints;i++){
double tmpx,tmpy;
cin＞＞tmpx＞＞tmpy;
points[i].setX(tmpx);
points[i].setY(tmpy);
}
______ computeDistance=new ComputeDistance();
int p1=0,p2=1;//p1和p2用于表示距离最近的点对在数组中的下标
double shortestDistance=computeDistance-＞distance(points[p1],points[p2]);
//计算每一对点之间的距离
for(i=0;i＜numberOfPoints;i++){
for(j=i+1;j＜______;j++){
double tmpDistance=computeDistance-＞______;
if(______){
p1=i;p2=j;
shortestDistance=tmpDistance;
}
}
}
cout＜＜"距离最近的点对是:(";
cout＜＜"points[p1].getX()＜＜","＜＜points[p1].getY()＜＜")和(";
cout＜＜points[p2].getX()＜＜","＜＜points[p2].getY()＜＜")"＜＜"endl;
delete computeDistance;
return 0;
}

GPoint^*
(2)ComputeDistance^*
(3)numberOfPoims
(4)distance(points[i]，points[j])
(5)shortestDistance＞tmpDistance

[解析] 本题是用C++来实现题目要求的功能。根据程序我们不难看出第一空是要定义一个保存点坐标对象的数组，调用的是Gpoint构造函数，那么其对象类型为Gpoint，因此第一空的答案为“GPoint^*”。第二空是要定义一个ComputeDistance的对象指针，因此其答案为“ComputeDistance^*”。
第3、4、5空都在双重for循环中，根据题目意思，该双重for循环是要实现计算每一对点之间的距离。其中第3空是循环的条件，循环继续的条件是i小于点的个数，因此第3空填“numberOfPoints”。而第4空很明显是要用computeDistance对象指针来调用其计算两点间距离的函数distance，而这里是要求点i和点i间的距离，因此第4空答案应填“distance(points[i],points[j])”。第5空是if语句的条件，如果条件成立，则p1=i,p2=j，说明i和j点间的距离比当前最短距离更短，因此第5空是“shortestDistance＞tmpDistance”。

试题五

1. 阅读以下说明和Java程序，填充程序中的空缺。
[说明]
下面的程序用来计算并寻找平面坐标系中给定点中最近的点对(若存在多对，则输出其中的一对即可。程序运行时，先输入点的个数和一组互异的点的坐标，通过计算每对点之间的距离，从而确定出距离最近的点对。例如，在图中所示的8个点中，点(1，1)与(2，0.5)是间距最近的点对。

【Java代码】
import java.util.Scanner;
class GPoint
{
private double x,y;
public void setX(aouble x){this.x=x;}
public void setY(double Y){this.y=y;}
public double getX() {return this.x;)
public double getY() {return this.y;
}
class FindNearestPotnts{
public static void main(String[]args){
Scanner input=new Scanner(System.in);
System.out.print("输入点的个数:");
int numberOfPoints=input.nextlnt();
______ points=new GPoint[numberOfPoints];//创建保存点坐标的数组
System.out.print("请输入"+numberOfPoints+"个点的坐标");
for(int i=0;i＜points.length;i++){
points[i]=______;
points[i].setX(input.nextDouble());
points[i].setY(input.nextDouble());
}
FindNearestPoints fop=new FindNearestPoints();
int p1=0,p2=1;//p1和p2用于表示距离最近的点对在数组中的下标
double shortestDistance=fnp.getDistance(points[p1],points[p2]);
//计算每一对点之间的距离
for(int i=0;i＜points.length;i++)
{
for(intj=i+1;j＜______;j++)
{
double tmpDistance=fnp.______;//计算两点间的距离
if(______)
{
p1=i;
p2=j;
shortestDistance=tmpDistance;
}
}
}
System.out.pdntln("距离最近的点对是("+
points[p1].getX()+","+points[p1].getY()+")和("+
points[p2].getX()+","+points[p2].getY()+")");
}
public double getDistance(GPoint pt1,GPoint pt2)
{
retum Math.sqrt((pt2.getX()-pt1.getX())^*(pt2.getX()-pt1.getX())
+(pt2.getY()-pt1.getY())^*(pt2.getY()-pt1.getY());
}
}

GPoint
(2)new GPoint()
(3)points.length
(4)getDistance(points[i]，points[j])
(5)shortestDistance＞tmpDistance

[解析] 本题是用Java来实现题目要求的功能。根据程序注释，我们不难看出第一空是要定义一个创建保存点坐标的数组，调用的是Gpoint构造函数，那么其对象类型为Gpoint，因此第一空的答案为“GPoint”。第二空是要给数组中定义具体的每个点对象，那么应该用“new GPoint()”。
第3、4、5空都在双重for循环中，根据题目意思，该双重for循环是要实现计算每一对点之间的距离。其中第3空是循环的条件，循环继续的条件是j小于点的个数，因此第3空填“points.length”。而第4空很明显是要计算两点间距离，结合程序，我们不难看出，调用fnp的函数getDistance即可，而这里是要求点i和点j间的距离，因此第4空答案应填“getDistance(points[i]，points[j])”。第5空是if语句的条件，如果条件成立，则p1=i，p2=j，说明i和j点间的距离比当前最短距离更短，因此第5空是“shortestDistance＞tmpDistance”。