温故而知新，下笔如有神近几上半年程序员考试专题习题训练及答案-下午卷试题一设x位于区间（0, 1)，该流程图的算法要点是逐步累积计算每项的值（作为 T),再逐步累加T值得到所需的结果S。当T值小于10-5时，结束计算。 【流程图】 (1) S (2) x/n (3) T0.00001 (4) S+T (5) n+1n本题属于简单的数值计算应用。人们经常需要近似计算初等函数的值。在计算机内部，近似计算初等函数的值最常用的方法就是将初等函数按幂级数展开，再计算前若干项的和，直到计算误差满足要求为止。在设计算法时应考虑，对于自变量的大致范围，如何展开级数，使级数收敛的速度比较快，在计算过程中，怎样估计计算的误差是否己经满足要求。由于初等函数在计算机中需要频繁使用，因此设计髙效率的算法非常重要。这种精益求精的设计是全世界许多专家己经反复探索并实现了的。对于一般程序员来说，只要求基本的、正确的算法设计，并实现编程就可以了。本题中，为了计算指数函数e x的值，已经给出了基本的算法，以及计算过程中控制误差终止计算的方法。本题主要的重点是如何设计计算流程，实现级数前若干项的求和，以及判断终止计算的条件。级数求和通常采用逐项累加的方法。设S为累加的结果，T为动态的项值，那么，S+TS就能完成各项的累加。由于本题中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)处为判断计算过程结束的条件，按照题中的要求，当T10-5时计算过程结束，因此，（3)处应填T-1，或其等价形式(5) Ci,或其等价形式 本题考査C程序设计基本能力。用整型数组表示大整数时，一个数组元素可以表示整数的一位，也可以表示多位，为提高存储空间的利用率并提高运算速度，本题中采用一个数组元素表示4位的整数。 在这种表示方式下进行两个大整数的相加运算时，主要考虑进位的处理。题目中用变量cf来表示进位情况，显然，开始相加前尚未产生进位，所以cf的初始值为0,因此空（1)处应填入0。由于相加时需要对齐，并且根据程序中ci = t % 10000对t的使用，空（2)处应填入Ai+Bi + cf。该运算同时产生下一步运算需要使用的进位值cf，因此空（3)处应填入 t /10000 或(Ai+ Bi + cf)/10000o参与相加运算的两个整数位数不一定相同，因此，尚有剩余的那个整数的其余位数应带进位记录下来，程序中设置的临时指针p指向保存这个整数的数组。根据题中设置的标志若数组A表示的整数已经结束，则满足Ai=-1，否则 满足Bi=-1，因此考查if语句的逻辑后，空（4)处应填入Ai=-1，或Bi-1。另外，当两个整数相加后产生进位，此时可能需要将此进位结果作为和数来记录，以9999 9999 4567 与5555相加为例说明，和数1 0000 0000 0122 比9999 9999 4567 还要多1位，并且在数组中表示时的分组数也多1个。if语句if ( cf 0 ) Ci+ = cf;即用来处理这种情况。空（5)处的语句用于为表示和数的数组设置标志，因此应填入Ci。若要输出用数组表示的整数，则可用以下程序段：试题三【说明】二叉查找树又称为二叉排序树，它或者是一棵空树，或者是具有如下性质的二叉树：若它的左子树非空，则其左子树上所有结点的键值均小于根结点的键值；若它的右子树非空，则其右子树上所有结点的键值均大于根结点的键值；左、右子树本身就是二叉查找树。设二叉查找树采用二叉链表存储结构，链表结点类型定义如下：函数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函数中需要修改的代码行号，并给出修改后的整行代码。本表中的解答无次序要求。注：在第3行、第4行中增加语句SUm=0;，或者将sum=0加在第5行的正确位置 也可以，即for( k = 1，sum = 0; k=n; k+)或者 for(sum = 0, k = 1; k=n; k+).本题考查C程序的调试和排错能力。【分析】程序中的错误可分为语法错误和语义错误，其中语义错误又分为静态语义错误和动态语义错误。语法错误和静态语义错误可在编译时检测出，动态语义错误则 在程序运行时才能表现出来。C函数1所示代码已经通过编译，而运行结果不对。虽然直接的运行结果为输出变量sum的值，但其计算过程却与n和k的值相关。因此，可以从每个变量初始值的设定、修改方式和引用方式考査。对于变量k，其初始值由语句表达式k=l确定，修改方式为k+,引用处为循环条件k=n和sum+=k*k，没有不当之处。对于变量n，其初始值由scanf(%d，n)确定，引用处为循环条件k=n，得到初始值后不再进行修改。然而从第2次测试main函数时显示的结果可知，n的值并不是为其输入的值5,显然对n值的设定有误，仔细检查scanf函数的调用可知，其中的n之前缺少了取地址运算符号&，正确的函数调用为scanf(%d，&n)。对于变量sum,其修改和引用处分别为sum += k*k、printf(result: %dn, sum),没 有对其进行初始化，而是在一个未知的数值上开始累加，因此，sum最后的结果无法符合预期的值。另外，函数中还有一个比较隐蔽的错误，就是语句结束符号“;”的不当使用，导致循环语句for( k = 1; k=n; k+)只是将k的值从1递增到n+1，没有产生实质的运算结果，使得sum的值不会随着sum+=k*k发生变化。【问题2】【说明2】函数test_f2()编译时系统报告有错，修改后得到函数f2_B()。对函数f2_B()进行编译时顺利通过，在某些C系统中执行时却由于发生异常而不能正确结束。【C函数2】【问题】(1) 请指出函数test_f2中不能通过编译的表达式；(2) 请指出可能导致函数f2_B运行异常的表达式。(1) strf+(2) *str = a .本题考查C程序的调试和排错能力。【分析】函数teSt_f2()编译时系统报告有错，检査其函数体，其中的char str =test string;表明str是一位数组名，因此，*str表示str0，通过*str = a;为str0赋值 显然是允许的。出错的地方是strf+，在C语言中，数组名是指针（地址）常量，是不允许修改的，strf+试图修改指针常量str，因此编译时会报告错误。若将str修改为指针变量，即在函数f2_B()中定义为char *str = test string，则可以通过strH修改str的值，使得str可以指向f同的字符对象。使某些C系统执行f2_B0时发生异常的表达式是*str =