1、计算机水平考试初级程序员 2012 年下半年下午真题及答案解析(总分：90.00，做题时间：150 分钟)一、问答题(总题数：6，分数：90.00)1.试题一(共 15 分) 阅读以下说明和流程图，填补流程图中的空缺(1)(5)，将解答填入答题纸的对应栏内。 说明 本流程图用于计算菲波那契数列a11，a2l，anan-1+an-2|n=3，4，)的前 n 项(n2)之和 S。例如，菲波那契数列前 6 项之和为 20。计算过程中，当前项之前的两项分别动态地保存在变量 A 和 B 中。 流程图 （分数：15.00）_2.试题二(共 15 分) 阅读以下说明和 C 函数，填充函数中的空缺，将解答填入
2、答题纸的对应栏内。 说明 如果矩阵 A 中的元素 Ai,j满足条件：Ai,j是第 i 行中值最小的元素，且又是第 j 列中值最大的元素，则称之为该矩阵的一个马鞍点。 一个矩阵可能存在多个马鞍点，也可能不存在马鞍点。下面的函数求解并输出一个矩阵中的所有马鞍点，最后返回该矩阵中马鞍点的个数。 C 函数 （分数：15.00）_3.试题三(共 15 分) 阅读以下说明和 C 函数，填充函数中的空缺，将解答填入答题纸的对应栏内。 说明 函数 Insert_key(*root，key)的功能是将键值 key 插入到*root 指向根结点的二叉查找树中(二叉查找树为空时*root 为空指针)。若给定的二叉查
3、找树中已经包含键值为 key 的结点，则不进行插入操作并返回0；否则申请新结点、存入 key 的值并将新结点加入树中，返回 1。 提示： 二叉查找树又称为二叉排序树，它或者是一棵空树，或者是具有如下性质的二叉树： 若它的左子树非空，则其左子树上所有结点的键值均小于根结点的键值； 若它的右子树非空，则其右子树上所有结点的键值均大于根结点的键值；左、右子树本身就是二叉查找树。 设二叉查找树采用二叉链表存储结构，链表结点类型定义如下： C 函数 （分数：15.00）_4.试题四(共 15 分) 阅读以下说明和 C 函数，填充函数中的空缺，将解答填入答题纸的对应栏内。 说明 已知两个整数数组 A 和
4、B 中分别存放了长度为 m 和 n 的两个非递减有序序列，函数Adjustment(A，B，m，n)的功能是合并两个非递减序列，并将序列的前 m 个整数存入 A 中，其余元素依序存入 B 中。 例如： 合并过程如下：从数组 A 的第一个元素开始处理。用数组 B 的最小元素 B0与数组 A 的当前元素比较，若 A 的元素较小，则继续考查 A 的下一个元素；否则，先将 A 的最大元素暂存入temp，然后移动 A 中的元素挪出空闲单元并将 B0插入数组 A，最后将暂存在 temp 中的数据插入数组 B的适当位置(保持 B 的有序性)。如此重复，直到 A 中所有元素都不大于 B 中所有元素为止。 C
5、函数 （分数：15.00）_5.试题五(共 15 分) 阅读以下说明和 C+代码，填充代码中的空缺，将解答填入答题纸的对应栏内。 说明 下面的程序用来计算并寻找平面坐标系中给定点中最近的点对(若存在多对，则输出其中的一对即可)。程序运行时，先输入点的个数和一组互异的点的坐标，通过计算每对点之间的距离，从而确定出距离最近的点对。例如，在图 5-1 所示的 8 个点中，点(1，1)与(2，05)是间距最近的点对。 C+代码 （分数：15.00）_6.试题六(共 15 分) 阅读以下说明和 Java 程序，填充程序中的空缺，将解答填入答题纸的对应栏内。 说明 下面的程序用来计算并寻找平面坐标系中给定
6、点中最近的点对(若存在多对，则输出其中的一对即可)。程序运行时，先输入点的个数和一组互异的点的坐标，通过计算每对点之间的距离，从而确定出距离最近的点对。例如，在图 6-1 所示的 8 个点中，点(1，1)与(2，05)是间距最近的点对。 java 代码 （分数：15.00）_计算机水平考试初级程序员 2012 年下半年下午真题答案解析(总分：90.00，做题时间：150 分钟)一、问答题(总题数：6，分数：90.00)1.试题一(共 15 分) 阅读以下说明和流程图，填补流程图中的空缺(1)(5)，将解答填入答题纸的对应栏内。 说明 本流程图用于计算菲波那契数列a11，a2l，anan-1+a
7、n-2|n=3，4，)的前 n 项(n2)之和 S。例如，菲波那契数列前 6 项之和为 20。计算过程中，当前项之前的两项分别动态地保存在变量 A 和 B 中。 流程图 （分数：15.00）_正确答案：( (1)2 或 A+B (2)n (3)A+B (4)B-A (5)S+B)解析： 菲波那契数列的特点是首 2 项都是 1，从第 3 项开始，每一项都是前两项之和。该数列的前几项为 1，1，2，3，5，8，。 在流程图中，送初始值 1A，2B 后，显然前 2 项的和 S 应等于 2，所以(1)处应填 2(或 A+B)。此时 2i(i 表示动态的项编号)，说明已经计算出前 2 项之和。接着判断循
8、环的结束条件。显然当 i=n 时表示已经计算出前 n 项之和，循环可以结束了。因此(2)处填 n。判断框中用“”或“”的效果是一样的，因为随着 i 的逐步增 1，只要有 in 结束条件，就不会遇到 in 的情况。不过编程的习惯使循环结束条件扩大些，以防止逻辑出错时继续循环。 接下来 i+1i 表示数列当前项的编号增 1，继续往下计算。原来的前两项值(分别在变量 A 和 B 中)将变更成新的前两项再放到变量 A 和 B 中。 2.试题二(共 15 分) 阅读以下说明和 C 函数，填充函数中的空缺，将解答填入答题纸的对应栏内。 说明 如果矩阵 A 中的元素 Ai,j满足条件：Ai,j是第 i 行中
9、值最小的元素，且又是第 j 列中值最大的元素，则称之为该矩阵的一个马鞍点。 一个矩阵可能存在多个马鞍点，也可能不存在马鞍点。下面的函数求解并输出一个矩阵中的所有马鞍点，最后返回该矩阵中马鞍点的个数。 C 函数 （分数：15.00）_正确答案：( (1)M (2)minElemarow0或其等价形式 (3)N (4)aik 或其等价形式 (5)M)解析： 本题考查 C 程序设计基本技术。 题目中涉及的主要知识点为二维数组和程序控制逻辑。首先应认真阅读题目的说明部分，以了解函数代码的功能和大致的处理思路，然后理清代码的框架，明确各个变量(或数组元素)所起的作用，并以语句组分析各段代码的功能，从而完
10、成空缺处的代码填充。 由于矩阵中的马鞍点 Ai,j是其所在行的最小元素，同时又是其所在列的最大元素，因此，对于矩阵中的每一行元素，先找出其最小者之值(用 minElem 表示)，然后判断每一行的最小元素是否为其所在列的最大元素，若是则找到了一个马鞍点。 显然，空(1)所在的表达式用于判断 M 行 N 列矩阵中的行数，因此应填入“M”。 空(2)处应对变量 minElem 设置初始值。根据注释，minElem 用于表示第 row 行的最小元素值，其初值设为该行第 0 列的元素值，因此空(2)处应填入“minElemarow0”。 空(3)所在的 for 语句用于找出一行中的最小元素，column
11、 应索引至每行的最后一个元素，因此空(3)处应填入“N”。 找出一行中的最小元素后，还要判断该元素是否为其所在列的最大元素。由于可能存在多个马鞍点，因此，一行中的最小元素可能不唯一，所以需要重新扫描该行的所有元素，一旦其等于最小元素值，则有可能成为马鞍点。实现该功能的代码如下： 3.试题三(共 15 分) 阅读以下说明和 C 函数，填充函数中的空缺，将解答填入答题纸的对应栏内。 说明 函数 Insert_key(*root，key)的功能是将键值 key 插入到*root 指向根结点的二叉查找树中(二叉查找树为空时*root 为空指针)。若给定的二叉查找树中已经包含键值为 key 的结点，则不
12、进行插入操作并返回0；否则申请新结点、存入 key 的值并将新结点加入树中，返回 1。 提示： 二叉查找树又称为二叉排序树，它或者是一棵空树，或者是具有如下性质的二叉树： 若它的左子树非空，则其左子树上所有结点的键值均小于根结点的键值； 若它的右子树非空，则其右子树上所有结点的键值均大于根结点的键值；左、右子树本身就是二叉查找树。 设二叉查找树采用二叉链表存储结构，链表结点类型定义如下： C 函数 （分数：15.00）_正确答案：( (1)p 或 p!=NULL (2)p-left (3)p-right (4)sizeof(BiTnode) (5)*root=s)解析： 本题考查 C 程序设计
13、基本技术及指针的应用。 题目中涉及的考点主要有链表的查找、插入运算以及程序逻辑，分析程序时首先要明确各个变量所起的作用，并按照语句组分析各段代码的功能，从而完成空缺处的代码填充。 在二叉排序树上插入结点时，首先应通过查找运算确定结点的插入位置。空(1)(3)所在代码段即用来实现二叉排序树的查找运算。 根据说明，指针变量 p 的初始值设置为指向根结点(p*root)，在通过指针访问链表中的结点时，应确保 p 的值为非空指针才行，因此空(2)处应填入“p”或“p!=NULL”。若待查找的键值 key 等于 p 指向结点的键值 key_value，则查找成功且 p 正指向所找到的结点：若 keyke
14、y_value，则应令 p 指向左子树结点，即空(2)处应填入“p-1eft”；否则令 p 指向右子树结点，即空(3)处应填入“p-right”，从而根据待查找键值的大小进入了结点的子树。 空(4)所在代码生成待插入键值所需结点，根据链表结点类型的定义，此处应填入“sizeof(BiTnode)”。 空(5)所在语句处理将新结点作为二叉查找树的根结点的情况，根据参数 root 的作用，此处应填入“*roots”。4.试题四(共 15 分) 阅读以下说明和 C 函数，填充函数中的空缺，将解答填入答题纸的对应栏内。 说明 已知两个整数数组 A 和 B 中分别存放了长度为 m 和 n 的两个非递减有
15、序序列，函数Adjustment(A，B，m，n)的功能是合并两个非递减序列，并将序列的前 m 个整数存入 A 中，其余元素依序存入 B 中。 例如： 合并过程如下：从数组 A 的第一个元素开始处理。用数组 B 的最小元素 B0与数组 A 的当前元素比较，若 A 的元素较小，则继续考查 A 的下一个元素；否则，先将 A 的最大元素暂存入temp，然后移动 A 中的元素挪出空闲单元并将 B0插入数组 A，最后将暂存在 temp 中的数据插入数组 B的适当位置(保持 B 的有序性)。如此重复，直到 A 中所有元素都不大于 B 中所有元素为止。 C 函数 （分数：15.00）_正确答案：( (1)A
16、m-1，或*(A+m-1)，或其等价表示 (2)ki，或其等价表示 (3)B0，或*B (4)tempBk，或 temp*(B+k)，或其等价表示 (5)temp)解析： 本题考查 C 程序设计基本技术。 题目中涉及的考点主要有一维数组及程序的运算逻辑，分析代码时首先要明确各个变量所起的作用，并按照语句组分析各段代码的功能，从而完成空缺处的代码。 根据题目中的说明和注释，此题的代码逻辑较为清楚。显然，A 的最大元素总是其最后一个元素，因此，空(1)处应填入“Am-1”。 空(2)所在语句从后往前移动 A 的元素，然后将来自 B 的最小元素插入 A 数组的适当位置，显然需要通过比较 B0与 A
17、中的元素来查找插入位置。 对于 B0与 A 中的元素的比较处理，其对应的语句如下： 5.试题五(共 15 分) 阅读以下说明和 C+代码，填充代码中的空缺，将解答填入答题纸的对应栏内。 说明 下面的程序用来计算并寻找平面坐标系中给定点中最近的点对(若存在多对，则输出其中的一对即可)。程序运行时，先输入点的个数和一组互异的点的坐标，通过计算每对点之间的距离，从而确定出距离最近的点对。例如，在图 5-1 所示的 8 个点中，点(1，1)与(2，05)是间距最近的点对。 C+代码 （分数：15.00）_正确答案：( (1)GPoint* (2)ComputeDistance* (3)numberOf
18、Points (4)distance(pointsi,pointsj) (5)shortestDistancetmpDistance)解析： 本题考查 C+语言程序设计的能力，涉及类、对象、函数的定义和相关操作。要求考生根据给出的案例和执行过程说明，认真阅读理清程序思路，然后完成题目。 先考察题目说明。计算平面或空间中点之间的距离是目前很多应用中需要的，如 GPS 计算等。本题目简化了点之间距离的要求，其主要任务是计算并寻找平面坐标系中给定点中最近的点对(若存在多对，则输出其中的一对即可)。数轴上两点之间的距离等于相应两数差的绝对值，而平面坐标系中两点之间的距离等于相应两点的横坐标差和纵坐标差
19、的平方和的算数平方根。假设平面左边系中的两点 和 ，两者之间的距离 。如题中图 5-1 所示的 8 个点中，点(1，1)和(2,0.5)之间的距离为6.试题六(共 15 分) 阅读以下说明和 Java 程序，填充程序中的空缺，将解答填入答题纸的对应栏内。 说明 下面的程序用来计算并寻找平面坐标系中给定点中最近的点对(若存在多对，则输出其中的一对即可)。程序运行时，先输入点的个数和一组互异的点的坐标，通过计算每对点之间的距离，从而确定出距离最近的点对。例如，在图 6-1 所示的 8 个点中，点(1，1)与(2，05)是间距最近的点对。 java 代码 （分数：15.00）_正确答案：( (1)GPoint (2)newGPoint() (3)points.length 或 numberOfPoints (4)getDistance(pointsi,pointsj) (5)shortestDistancetmpDistance)解析：
