1、2012年下半年软件水平考试（初级）程序员下午（应用技术）真题试卷及答案与解析 1 阅读以下说明和流程图，填补流程图中的空缺 (1) (5)，将解答填入答题纸的对应栏内。 【说明】 本流程图用于计算菲波那契数列 a1=1， a2=1， ， an=an-1+an-2， |n=3， 4， 的前 n项 (n2)之和 S。例如，菲波那契数列前 6项之和为 20。计算过程中，当前项之前的两项分别动态地保存在变量 A和 B中。 【流程图】 2 阅读以下说明和 C函数，填充函数中的空缺，将解答填入答题纸的对应栏内。 【说明】 如果矩阵 A中的元素 Ai， j满足条件： Ai， j是第 i行中值最小的元素，且
2、又是第 j列中值最大的元素，则称之为该矩阵的一个马鞍点。 一个矩阵可能存在多个马鞍点，也可能不存在马鞍点。下面的函数用来求解并输出一个矩阵中的所有马鞍点，最后返回该矩阵中马鞍点的个数。 【 C函数】 Int findSaddle(int aN， int M)， *a表示 M行 N列矩阵， N是宏定义符号常量 * int row， column， i， k； int minElem： int COUrtt=0； *count用于记录矩阵中马鞍点的个数 * for(row= 0； row (1) ； row+) *minElem用于表示第 row行的最小元素值，其初值设为该行第 0列的元素值 *
3、(2) ： for(column= 1； columN (3) ； column+) if(minElemarowcolumn) minElem= arowcolumn； for(k=0； k N； k+) if(arowk= =minElem) *对第 row行的每个最小元素，判断其是否为所在列的最大元素 * for(i=0； i M； i+) if( (4) minElem)break； if(i= (5) ) printf(”( d， d)： d n”， row， k， minElem)； *输出马鞍点 * count+： * if * * if * * for * return cou
4、nt * findSaddle * 3 阅读以下说明和 C函数，填充函数中的空缺，将解答填入答题纸的对应栏内。 【说明】 函数 Insert_key(*root， key)的功能是将键值 key插入到 *root指向根结点的二叉查找树中 (二叉查找树为空时 *root为空指针 )。若给定的二叉查找树中已经包含键值为key的结点，则不进行插入操作并返回 0；否则申请新结点、存入 key的值并将新结点加入树中，返回 1。 提示： 二叉查找树又称为二叉排序树，它或者是一棵空树，或者是具有如下性质的二叉树： .若它的左子树非空，则其左子树上所有结点的键值均小于根结点的键值； .若它的右子树非空，则其右
5、子树上所有结点的键值均大于根结点的键值； .左、右子树本身就是二叉查找树。 设二叉查找树采用二叉链表存储结构，链表结点类型定义如下： typedef struct BiTnode int key_value； *结点的键值，为非负整数 * struct BiTnode * left， * right； *结点的左、右子树指 针 * BiTnode， *BSTree； 【 C函数】 int Insert_key(BSTree * root， int key) BiTnode * father=NULL， * p= * root， * s； while( (1) &key!=p-key_value
6、) *查找键值为 key的结点 * father=p； if(key p-key_value)p= (2) ； *进入左子树 * else p= (3) ； *进入右子树 * if(p)return 0； *二叉查找树中已存在键值为 key的结点，无须再插入 * s=(BiTnode*)malloc( (4) )； *根据结点类型生成新结点 * if(!s)return-1； s-key_value=key； s-left=NULL； s-right=NULL； if( ! father) (5) ； *新结点作为二叉查找树的根结点 * else *新结点插入二叉查找树的适当位置 * if(k
7、eykey_value)father-left=s： else father-right=s； return 1： 4 阅读以下说明和 C函数，填充函数中的空缺，将解答填入答题纸的对应栏内。 【说明】 已知两个整数数组 A和 B中分别存放了长度为 m和 n的两个非递减有序序列，函数 Adjustment(A， B， m， n)的功能是合并两个非递减序列，并将序列的前 m个整数存入 A中，其余元素依序存入 B中。例如： 合并过程如下：从数组 A的第一个元素开始处理。用数组 B的最小元素 B0与数组 A的当前元素比较，若 A的元素较小，则继续考查 A的下一个元素；否则，先将 A的最大元素暂存入 t
8、emp，然后移动 A中的元素挪出空闲单元并将 B0插入数组 A，最后将暂存在 temp中的数据插入数组 B的适当位置 (保持 B的有序性 )。如此重复，直到 A中所有元素都不大于 B中所有元素为止。 【 C函数】 void Adjustment(int A， int B， int m， int n) *数组 A有 m个元素，数组 B有 n个元素 * int k， temp； for(i=0； i 5 阅读以下说明和 C+代码，填充代码中的空缺，将解答填入答题纸的对应栏内。 【说明】 下面的程序用来计算并寻找平面坐标系中给定点中最近的点对 (若存在多对，则输出其中的一对即可 )。程序运行时，先输
9、入点的个数和一组互异的点的坐标，通过计算每对点之间的距离，从而确定出距离最近的点对。例如，在下图所示的 8个点中，点 (1， 1)与 (2， 0 5)是间距最近的点对。 【 C+代码】 #include#includeusing namespace std； class GPointprivate： double x， y； public： void setX(double x)this-x=x； void setY(double y)this-y=y； double getX()return this-x； double getY()return this-y； ； class Comput
10、eDistancepublic： double distance(GPoint a， GPoint b)return sqrt(a getX() - b getX()*(a getX() - b getX() +(a getY() - b getY()*(a getY() - b getY()； ； int main() int i， j， numberOfPoints=0； coutnumbeOfPoints： (1) points=new GPointnumberOfPoints；创建保存 点坐标的数组 memset(points， 0， Sizeof(points)； couttmpxt
11、mpy；， pointsi setX(tmpx)； pointsi setY(tmpy)； (2) computeDistance= new ComputeDistance()； int p1=0， p2=1； p1和 p2用于表示距离最近的点对在数组中的下标 double shortestDistance=computeDistance-distance(pointsp1，pointsp2)； 计算每一对点之间的距离 for(i=0； i numberOfPoints；i+)for(j=i+1； j (3) ； j+) double tmpDistance=computeDistance-
12、(4) ； if( (5) ) p1=i； p2=j； shortestDistance= tmpDistance； cout 6 阅读以下说明和 Java程序，填充程序中的空缺，将解答填入答题纸的对应栏内。 【说明】 下面的程序用来计算并寻找平面坐标系中给定点中最近的点对 (若存在多对，则输 出其中的一对即可 )。程序运行时，先输入点的个数和一组互异的点的坐标，通过计算每对点之间的距离，从而确定出距离最近的点对。例如，在下图所示的 8个点中，点 (1， 1)与 (2， 0 5)是问距最近的点对。 Java代码】 import java util Scanner； class GPointpr
13、ivate 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 FindNearestPoints public static void main(Stringargs) Scanner input=new Scanner(System in)； System out print(”输入点的个数： ”)； int nu
14、mberOfPoints=input nextInt()： (1) points=new GPointnumberOfPoints； 创建保存点坐标的数组 System out print(”请输入 ”+numberOfPoints+”个点的坐标 ”)； for(int i=0； i points 1ength；i+) pointsi= (2) ； pointsi setX(input nextDouble()； pointsi setY(input nextDouble()； FindNearestPoints fnp=new FindNearestPoints()： int p1=0， p
15、2： 1； p1和 p2用于表示距离最近的点对在数组中的下标 double shortestDistance=fnp getDistance(pointsp1， pointsp2)； 计算 每一对点之间的距离 for(int i=0； i 2012年下半年软件水平考试（初级）程序员下午（应用技术）真题试卷答案与解析 1 【正确答案】 (1)2或 A+B或其等价形式 (2)n (3)A+B或其等价形式 (4)B A或其等价形式 (5)S+B或其等价形式 【试题解析】 本问题考查考生设计和阅读流程图的能力。 从题目给出的流程图可以看出， (1)需要为 S赋值。由于在初始时， S为前两项之和，因此，
16、 (1)处应填入 A+B或 2。 (2)处需要设置一个循环 条件。本流程图用于计算菲波那契数列的前 n项 (n2)之和 S，显然，当循环变量值小于 ”时会一直循环进行求和，当循环变量值大于获等于 ”时循环结束，并输出和 S的结果。因此， (2)处应填入 n。 (3) (5)处分别用于计算 B、 A和 S的值。根据题目的描述，汁算过程中，当前项之前的两项分别动态地保存在变量 A和 B中。因此， (3)处应填入 A+B。 (4)处 A为 B的前一项，因此应填入 B A。 (5)处计算 S的值，应在上次和的基础上再加上数列中下一项的值，因此应输入 S+B。 2 【正确答案】 (1)M (2)minE
17、lem=arow0或其等价形式 (3)N (4)aik或其等价形式 (5)M 【试题解析】 本题考查考生综合运用 C语言的知识解决实际问题的能力。 根据题目的描述，马鞍点 Ai， j为矩阵第 i行中值最小的元素，且又是第 j列中值最大的元素。 (1)处的 for循环实现对所有行进行遍历，而矩阵 a共有 M行，因此， (1)处应填入 M。 根据程序段中提供的注释， (2)处用于设置第 roW行的最小元素值，且其初值设为该行第 0列的元素值。因此， (2)处应填入 minElem=arow0。 类似的思路， (3)处的 for循环实现对所有列进行遍历，而矩阵 a共有 N行，因此， (3)处应填入
18、N。 根据程序段中提供的注释， (4)和 (5)处实现对第 row行的每个最小元素，判断其是否为所在列的最大元素，因此， (4)处应填入 aik。 (5)处所在的 if判断条件用于判断行是否比较结束，因此应填入 M。 3 【正确答案】 (1)p!=NULL (2)p-left (3)p-right (4)sizeof(BiTnode) (5)*root=s 【试题解析】 本题考查数据结构中二叉查找树的实现，题目中涉及的考点主要有链表运算和程序逻辑。考生应理解二又查找树的性质，分析程序时首先要明确各个变量所其的作用和代表的含义，并按照语句组分析各段代码的功能，从而完成空缺处的代码填写。 根据程序
19、段中的注释， whiIe循环所在的程序段用于查找键值为 key的结点。此时的循环条件应满足二叉查找树非空。因此， (1)处应填入 p!=NuLL或其等价形式。 根据二叉查找树的性质，若它的左子树非空，则其左子树上所有结点的键值均小于根结点 的键值。因此，若插入的键值 key小于当前结点的键值，则应将其添加到其左子树中。因此， (2)处应填入 p-1eft。类似的思路， (3)处应填入 p-right使其进入右子树。 根据程序段中的注释， (4)处用于根据结点类型生成新结点。由于需申请的结点的类型为 BiTnode，因此， (4)处应填入 sizeof(BiTnode)，指定申请空间的大小。 若
20、该二叉查找树为空，新结点应作为二叉查找树的根结点进行插入， (5)处即实现该功能，应填入 *root=s。 4 【正确答案】 (1)Am 1或 *(A+m 1)或其等价表示 (2)k i (3)B0或 *B (4)temp BEk或其等价表示 (5)temp 【试题解析】 本题考查 C语言中数组的基本概念和应用。 根据程序段中的注释， (1)处将数组 A中的最大元素备份至 temp。由于 A中存放了长度为 m的非递减有序序列，其最大元素为第 m个元素，因此， (1)处应填入Am一 1或其等价表示。 程序段接下来的 for循环实现从后往前依次考查 A的元素，移动 A的元素并将来自 B的最小元素插
21、入 A中。由于 B的最小元素 捕入到 Ai和 Am一 1之间，因此， (2)处的循环控制条件应填入 ki。 (3)处将 B的最小元素 b0插入到适当的位置，因此应填入 B0或其等价表示。 程序段的最后一个 for循环实现将备份在 temp的数据插入数组 B的适当位置。在将 temp插入到 B中时，须保持 B的有序性，因此， (4)处应填入 tempBk。 (5)处实现将 letup插入到 B中，因此应填入 temp。 5 【正确答案】 (1)Gpoint* (2)ComputeDistance * (3)number()tPoints (4)distance(pointsi， pointsj)
22、 (5)shortestDistance2 tmpDistance 【试题解析】 本题考查考生使用 C+语言进行面向对象程序设计的能力。首先要理解清楚题目中有关最近点对的概念和计算方法，然后阅读程序以实现该功能。 (1)处显示创建保存点坐标的数组。这里的 new运算符用于开辟数组空间，其语法规则为： new类型 初值 。 (1)处需要填入一类型修饰符，因此应填入 GPoint*。类似的思路， (2)处应填入 ComputeDistance*。 根据程序段中的注释， (3)和 (4)处实现计算每一对点 之间的距离。 (3)处为循环控制变量，因为要计算所有对点间的距离，因此应填入numberOtP
23、oints。 (4)处应调用 computeDistance类的 distance函数计算每一对点pointsi和 pointsj之间的距离，因此应填入 distance(pointsi， pointsj)。 (5)处应填入一个判断条件，以输出距离最小的点对。这可通过比较shortestDistance和 tmpDistance来实现。因此， (5)处应填入shortestDistancetmpDistance。 6 【正确答案】 (1)GPoint (2)new GPoint (3)points length (4)getDistance(pointsi， pointsj) (5)short
24、estDistancetmpDistance 【试题解析】 本题考查考生使用 Java语青进行面向对象程序设计的能力。首先要理解清楚题目中有关最近点对的概念和计算方法，然后阅读 程序以实现该功能。 (1)处显示创建保存点坐标的数组。这里的 new运算符用于开辟数组空间，其语法规则为： new类型 初值 。 (1)处需要填入一类型修饰符，因此应填入 GPoint。类似的思路， (2)处考查 Java语言中用 new初始化数组，应填入 new GPoint。 根据程序段中的注释， (3)和 (4)处实现计算每一对点之间的距离。 (3)处为循环控制变量，因为要计算所有对点间的距离，因此应填入 points 1ength。 (4)处应调用 computeDistance类的 distance函数计算 每一对点 pointsi和 pointsj之间的距离，因此应填入 getDistance(pointsi， pointsj)。 (5)处应填入一个判断条件，以输出距离最小的点对。这可通过比较shortestDistance和 tmpDistance来实现。因此， (5)处应填入shortestDistancetmpDistance。
