2012下半年程序员考试真题及答案-下午卷.doc

发布时间：2022-10-10 发布人：admin 分类：说明书资料大小：0.46M 资料格式：doc 举报版权申诉

第1页 / 共18页

第2页 / 共18页

第3页 / 共18页

第4页 / 共18页

第5页 / 共18页

第6页 / 共18页

第7页 / 共18页

第8页 / 共18页

【流程图】

【C函数】

2012 下半年程序员考试真题及答案-下午卷试题一【说明】本流程图用于计算菲波那契数列{a1=1，a2=1，…,an=an-1+an-2!n=3,4,…}的前 n 项（n>=2) 之和 S。例如，菲波那契数列前 6 项之和为 20。计算过程中，当前项之前的两项分别动态地保存在变量 A 和 B 中。【流程图】阅读说明和流程图，填补流程图中的空缺（1）〜（5） (1)2 或 A+B (2)n (3)A+B (4)B-A (5)S+B 菲波那契数列的特点是首 2 项都是 1，从第 3 项开始，每一项都是前两项之和。该数列的前几项为 1，1，2, 3，5，8，…。

在流程图中，送初始值 1—A，2—B 后，显然前 2 项的和 S 应等于 2,所以（1）处应填 2 (或 A+B)。此时 2→i (i 表示动态的项编号），说明已经计算出前 2 项之和。接着判断循环的结束条件。显然当 i=n 时表示已经计算出前 n 项之和，循环可以结束了。因此（2）处填 n。判断框中用“>”或“≥”的效果是一样的，因为随着 i 的逐步增 1，只要有 i=n 结束条件就不会遇到 i>n 的情况。不过编程的习惯使循环结束条件扩大些，以防止逻辑出错时继续循环。接下来 i+1→i 表示数列当前项的编号增 1，继续往下计算。原来的前两项值（分别在变量 A 和 B 中）将变更成新的前两项再放到变量 A 和 B 中。首先可以用 A+B—B 实现（原 A) + (原 B)—(新 B)，因此（3）处填 A+B。为了填新 A 值（原来的 B 值)，不能用 B—A，因为变量 B 的内容已经改变为（原 A) + (原 B)，而 B-A 正是（（原 A) + (原 B))-(原 A)=(原 B)，因此可以用 B-A—A 来实现新 A 的赋值。这样，（4）处填 B-A。最后应是前 n 项和值的累加（比原来的 S 值增加了新 B 值)，所以（5）处应填 S+B。填完各个空后，最好再用具体的数值来模拟流程图走几个循环检查所填的结果（这是防止逻辑上出错的好办法）。

试题二【说明】如果矩阵 A 中的元素 AW]满足条件：A[ij]是第 i 行中值最小的元素，且又是第 j 列中值最大的元素，则称之为该矩阵的一个马鞍点。一个矩阵可能存在多个马鞍点，也可能不存在马鞍点。下面的函数求解并输出一个矩阵中的所有马鞍点，最后返回该矩阵中马鞍点的个数。【C 函数】阅读说明和 C 函数，填充函数中的空缺。 (1)M

(2)minElem = a[row][0]或其等价形式 (3)N (4)a[i][k]或其等价形式 (5)M 本题考查 C 程序设计基本技术。题目中涉及的主要知识点为二维数组和程序控制逻辑。首先应认真阅读题目的说明部分，以了解函数代码的功能和大致的处理思路，然后理清代码的框架，明确各个变量(或数组元素）所起的作用，并以语句组分析各段代码的功能，从而完成空缺处的代码填充。由于矩阵屮的马鞍点 A[ij]是其所在行的最小元素，同时又是其所在列的最大元素，因此，对于矩阵中的每一行元素，先找出其最小者之值（用 minElem 表示），然后判断每一行的最小元素是否为其所在列的最大元素，若是则找到了一个马鞍点。显然，空（1)所在的表达式用于判断 M 行 N 列矩阵中的行数，因此应填入“M”。空（2)处应对变量 minElem 设置初始值。根据注释，minElem 用于表不第 row 行的最小元素值，其初值设为该行第 0 列的元素值，因此空（2)处应填入“minElem = a[row][0]”。空（3)所在的 for 语句用于找出一行中的最小元素，column 应索引至每行的最后一个元素，因此空（3)处应填入“N”。找出一行中的最小元素后，还要判断该元素是否为其所在列的最大元素。由于可能存在多个马鞍点，因此，一行中的最小元素可能不唯一，所以需要重新扫描该行的所有元素，一旦其等于最小元素值，则有可能成为马鞍点。实现该功能的代码如下：由于 k 的取值范围为[0，N),且 k 作为元素 a[r0w][k]的列下标（或第二下标)，因此当 “a[row][k]==minElem”时，即在第 row 行上找到了一个最小元素 a[row][k]，接下来就判

断它是否为所在列的最大元素了，空(4)所在的语句“for(i = 0;i

试题三【说明】函数 Insert_key(*root，key)的功能是将键值 key 插入到*root 指向根结点的二叉查找树中（二叉查找树为空时*root 为空指针）。若给定的二叉查找树中已经包含键值为 key 的结点，则不进行插入操作并返回 0;否则申请新结点、存入 key 的值并将新结点加入树中，返回 1。提示：二叉查找树又称为二叉排序树，它或者是一棵空树，或者是具有如下性质的二叉树: •若它的左子树非空，则其左子树上所有结点的键值均小于根结点的键值； •若它的右子树非空，则其右子树上所有结点的键值均大于根结点的键值； •左、右子树本身就是二叉查找树。设二叉查找树采用二叉链表存储结构，链表结点类型定义如下：【c 函数】

阅读说明和 C 函数，填充函数中的空缺。 (1)p 或 p!=NULL (2)p->left (3)p->right (4)sizeof(BiTnode) (5)*root = s 本题考查 c 程序设计基本技术及指针的应用。题目中涉及的考点主要有链表的査找、插入运算以及程序逻辑，分析程序时首先要明确各个变量所起的作用，并按照语句组分析各段代码的功能，从而完成空缺处的代码填充。在二叉排序树上插入结点时，首先应通过查找运算确定结点的插入位置。空（1)〜(3)所在代码段即用来实现二叉排序树的查找运算。根据说明，指针变量 p 的初始值设置为指向根结点（p = *r0ot)，在通过指针访问链表中的结点时，应确保 p 的值为非空指针才行，因此空（2)处应填入“p”或“p!=NULL”。若待查

找的键值 key 等于 p 指向结点的键值 key—value,则査找成功且 p 正指向所找到的结点；若 keykey__value，则应令 p 指向左子树结点，即空（2)处应填入“p->left”; 否则令 p 指向右子树结点，即空（3)处应填入“p->right”，从而根据待查找键值的大小进入了结点的子树。空（4)所在代码生成待插入键值所需结点，根据链表结点类型的定义，此处应填入 “sizeof(BiTnode)”。空（5)所在语句处理将新结点作为二叉查找树的根结点的情况，根据参数 root 的作用，此处应填入“*root = s”。

分享到：

赞收藏

资料库

2012下半年程序员考试真题及答案-下午卷.doc

相关推荐

程序员考试

热门标签

最新资料