2012年下半年程序员考试下午真题

2012年下半年程序员考试下午真题：

>>>点击进入软考初级程序员历年真题下载

● 阅读以下说明和流程图，填补流程图中的空缺(1)~(5)，将解答填入答题纸的对应栏内。
【说明】
本流程图用于计算菲波那契数列 {a₁=1，a₂=1，…，a_n=a_n-1+n_n-2|n=3，4，…}的前n 项 ( n≥2) 之和 S。例如，菲波那契数列前6 项之和为 20。计算过程中，当前项之前的两项分别动态地保存在变量 A 和 B 中。
【流程图】

● 阅读以下说明和C函数，填充函数中的空缺，将解答填入答题纸的对应栏内。
【说明】
如果矩阵A中的元素A[i,j]满足条件: A[i,j]是第i行中值最小的元素，且又是第j列中值最大的元素，则称之为该矩阵的一个马鞍点。
一个矩阵可能存在多个马鞍点，也可能不存在马鞍点。下面的函数求解并输出一个矩阵中的所有马鞍点，最后返回该矩阵中马鞍点的个数。

● 阅读以下说明和C函数，填充函数中的空缺，将解答填入答题纸的对应栏内。
【说明】
函数Insert_key(*root ，key)的功能是将键值 key 插入到*boot指向根结点的二叉查找树中(二叉查找树为空时 *root 为空指针)。若给定的二叉查找树中已经包含键值为 key 的结点，则不进行插入操作井返回 0；否则申请新结点、存入 key 的值并将新结点加入树中，返回1。
提示:

·二叉查找树又称为二叉排序树，它或者是一棵空树，或者是具有如下性质的二叉树：

·若它的左子树非空，则其左子树上所有结点的键值均小于根结点的键值；

·若它的右子树非空，则其右子树上所有结点的键值均大于根结点的键值；

·左、右子树本身就是二叉查找树。

设二叉查找树采用二叉链表存储结构，链表结点类型定义如下:

● 阅读以下说明和 C 函数，填充函数中的空缺，将解答填入答题纸的对应栏内。
【说明】
己知两个整数数组 A 和 B 中分别存放了长度为 m 和 n 的两个非递减有序序列，函数 Adjustment(A,B，m，n)的功能是合并两个非递减序列，并将序列的前m个整数存入A中，其余元素依序存入 B 中。
例如：

合并过程如下:从数组 A 的第一个元素开始处理。用数组 B 的最小元素 B[O]与数组 A 的当前元素比较，若 A 的元素较小，则继续考查 A 的下一个元素；否则，先将A的最大元素暂存入temp ，然后移动A中的元素挪出空闲单元并将 B[O]插入数组 A ，最后将暂存在temp 中的数据插入数组B的适当位置(保持 B的有序性)。如此重复，直到A中所有元素都不大于B中所有元素为止。

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

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