2009上半年程序员考试真题及答案-下午卷.doc-资料库

第1页 / 共16页

第2页 / 共16页

第3页 / 共16页

第4页 / 共16页

第5页 / 共16页

第6页 / 共16页

第7页 / 共16页

第8页 / 共16页

2009 上半年程序员考试真题及答案-下午卷试题一设 x 位于区间（0, 1)，该流程图的算法要点是逐步累积计算每项的值（作为 T),再逐步累加 T 值得到所需的结果 S。当 T 值小于 10-5 时，结束计算。【流程图】 (1) S (2) x/n (3) T<0.00001 (4) S+T (5) n+1—n 本题属于简单的数值计算应用。人们经常需要近似计算初等函数的值。在计算机内部，近似计算初等函数的值最常用的方法就是将初等函数按幂级数展开，再计算前若干项的和，直到计算误差满足要求为止。在设计算法时应考虑，对于自变量的大致范围，如何展开级数，使级数收敛的速度比较快，在计算过程中，怎样估计计算的误差是否己经满足要求。由于初等函数在计算机中需要频繁使用，因此设计髙效率的算法非常重要。这种精益求

精的设计是全世界许多专家己经反复探索并实现了的。对于一般程序员来说，只要求基本的、正确的算法设计，并实现编程就可以了。本题中，为了计算指数函数 e x 的值，已经给出了基本的算法，以及计算过程中控制误差终止计算的方法。本题主要的重点是如何设计计算流程，实现级数前若干项的求和，以及判断终止计算的条件。级数求和通常采用逐项累加的方法。设 S 为累加的结果，T 为动态的项值，那么，S+T —S 就能完成各项的累加。由于本题中 T=x n/n!，如果每次都直接计算该项的值，则计算量会很大。这种项的特殊性表明，后一项与前一项有简单的关充分利用前项的计算结果则会大大减少计算量。这是程序员需要掌握的基本技巧。本题的流程图中，一开始先输入自变量 X，接着对一些变量赋初值。变量 n 与 T 需要赋初值，对变量 S 也应赋初值。级数项号 n 的初值为 1，逐次进行累积的 T 也应有初值 1，逐次进行累加的 S 则应有初值 0 或级数第 1 项的值 1。从随后的流程看，S 应有初值 1,本题中（1)处应填 S。项值 T 的累积公式应是 T，所以本题中（2)处应填 x/n。流程图中（3)处为判断计算过程结束的条件，按照题中的要求，当 T<10-5 时计算过程结束，因此，（3)处应填 T<0.00001。流程图中（4)处需要累加 S，实现 S+T---S，因此，（4)处应填 S+T。流程图中（5)处应对级数的项号 n 进行自增，因此，（5)处应填 n+1—n。

试题二【说明】 C 语言常用整型（int)或长整型（long)来说明需要处理的整数，在一般情况下可以满足表示及运算要求，而在某些情况下，需要表示及运算的整数比较大，即使采用更长的整型（例如，longlong 类型，某些 C 系统会提供）也无法正确表示，此时可用一维数组来表示一个整数。假设下面要处理的大整数均为正数，将其从低位到高位每 4 位一组进行分组（最后—组可能不足 4 位)，每组作为 1 个整数存入数组。例如，大整数 2543698845679015847 在数组 A 中的表示如下（特别引入-1 表示分组结束)：在上述表示机制下，函数 add_large+mimbert(A、B、C)将保存在一维整型数组 A 和 B 中的两个大整数进行相加，结果（和数）保存在一维整型数组 C 中。【问题 1】【C 函数】

(1) 0 (2) A[i]+B[i] + cf,或其等价形式 (3) t/ 10000,或（A[i]+B[i] + cf)/10000,或其等价形式 (4) A[i]=-1,或 B[i]>-1，或其等价形式 (5) C[i],或其等价形式本题考査 C 程序设计基本能力。用整型数组表示大整数时，一个数组元素可以表示整数的一位，也可以表示多位，为提高存储空间的利用率并提高运算速度，本题中采用一个数组元素表示 4 位的整数。在这种表示方式下进行两个大整数的相加运算时，主要考虑进位的处理。题目中用变量 cf 来表示进位情况，显然，开始相加前尚未产生进位，所以 cf 的初始值为 0, 因此空（1)处应填入 0。由于相加时需要对齐，并且根据程序中 c[i] = t % 10000 对 t 的使用，空（2)处应填入 A[i]+B[i] + cf。该运算同时产生下一步运算需要使用的进位值 cf，因此空（3)处应填入 t /10000 或(A[i]+ B[i] + cf)/10000o 参与相加运算的两个整数位数不一定相同，因此，尚有剩余的那个整数的其余位数应带进位记录下来，程序中设置的临时指针 p 指向保存这个整数的数组。根据题中设置的标志若数组 A 表示的整数已经结束，则满足 A[i]=-1，否则满足 B[i]=-1，因此考查 if 语句的逻辑后，空（4)处应填入 A[i]=-1，或 B[i]>-1。另外，当两个整数相加后产生进位，此时可能需要将此进位结果作为和数来记录，以 9999 9999 4567 与 5555 相加为例说明，和数 1 0000 0000 0122 比 9999 9999 4567 还要多 1 位，并且在数组中表示时的分组数也多 1 个。if 语句 if ( cf > 0 ) C[i++] = cf; 即用来处理这种情况。空（5)处的语句用于为表示和数的数组设置标志，因此应填入 C[i]。若要输出用数组表示的整数，则可用以下程序段：

试题三【说明】二叉查找树又称为二叉排序树，它或者是一棵空树，或者是具有如下性质的二叉树：若它的左子树非空，则其左子树上所有结点的键值均小于根结点的键值；若它的右子树非空，则其右子树上所有结点的键值均大于根结点的键值；左、右子树本身就是二叉查找树。设二叉查找树采用二叉链表存储结构，链表结点类型定义如下：函数 find_key(root, key)的功能是用递归方式在给定的二叉查找树(root 指向根结点) 中查找键值为 key 的结点并返回结点的指针；若找不到，则返回空指针。【问题 1】【C 函数】

(1) !root,或 root==0，或 root=NULL (2) root (3) find_keyj(root->left,key) (4) find_key(root->right, key) 本题考查数据结构的应用、指针和递归程序设计。根据二叉查找树的定义，在一棵二叉查找树上进行查找时，首先用给定的关键字与树根结点的关键字比较，若相等，则查找成功：若给定的关键字小于树根结点的关键字，则接下来到左子树上进行查找，否则接下来到右子树上进行查找。如果在给定的二叉查找树上不存在与给定关键字相同的结点，则必然进入某结点的空的子树时结束查找。因此，空（1)处填入 !root 表明进入了空树；空（ 2) 处填入 root 表明返回结点的指针；空 (3) 处填入 find_key(root->left ， key) 表明下一步到左子树上继续查找；空（ 4) 处填入 find_key(root->right, key)表明下一步到右子树上继续查找。显然，在二叉排序树上进行查找时，若成功，则查找过程是走了一条从根结点到达所找结点的路径。例如，在下图所示的二叉排序树中査找 62,则依次与 46、54、101 和 62 作了比较。因此，在树中查找一个关键字时，需要比较的结点个数取决于该关键字对应结点在该二叉査找树所在层次（数）或位置。【问题 2】若某二叉查找树中有 n 个结点，则查找一个给定关键字时，需要比较的结点个数取决于（5)。（5）该关键字对应结点在该二叉査找树所在层次（数）或位置，或者该二叉树中从根结点到该关键字对应结点的路径长度

本题考查数据结构的应用、指针和递归程序设计。根据二叉查找树的定义，在一棵二叉查找树上进行查找时，首先用给定的关键字与树根结点的关键字比较，若相等，则查找成功：若给定的关键字小于树根结点的关键字，则接下来到左子树上进行查找，否则接下来到右子树上进行查找。如果在给定的二叉查找树上不存在与给定关键字相同的结点，则必然进入某结点的空的子树时结束查找。因此，空（1) 处填入!root 表明进入了空树；空（2)处填入 root 表明返回结点的指针；空(3)处填入 find_key(root->left ， key) 表明下一步到左子树上继续查找；空（ 4) 处填入 find_key(root->right, key)表明下一步到右子树上继续查找。显然，在二叉排序树上进行查找时，若成功，则查找过程是走了一条从根结点到达所找结点的路径。例如，在下图所示的二叉排序树中査找 62,则依次与 46、54、101 和 62 作了比较。因此，在树中查找一个关键字时，需要比较的结点个数取决于该关键字对应结点在该二叉査找树所在层次（数）或位置。

试题四【说明 1】函数 main()的功能旨在对输入的—个正整数 n，计算 12+22+32+…+n2,但是对该函数进行测试后没有得到期望的结果。【问题 1】请给出上述 main 函数中需要修改的代码行号，并给出修改后的整行代码。本表中的解答无次序要求。

资料库

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

相关推荐

程序员考试

热门标签

最新资料