1、2009年上半年软件水平考试（初级）程序员下午（应用技术）试题真题试卷及答案与解析 1 阅读以下说明和流程图，填补流程图中的空缺 (1)一 (5)，将解答填入答题纸的对应栏内。【说明】下面的流程图采用公式 ex=1+x+x2 2 1+x3 3 1+x4 4 1+x n n!+计算 ex的近似值。设 x位于区间 (0， 1)，该流程图的算法要点是逐步累积计算每项 xx n!的值 (作为 T)，再逐步累加 T值得到所需的结果 s。当 T值小于 10-5时，结束计算。【流程图】 2 阅读以下说明和 c函数，将应填入 (n) 处的 字句写在答题纸的对应栏内。【说明】 c语言常用整型 (int)或长整型
2、 (1ong)来说明需要处理的整数，在一般情况下可以满足表示及运算要求，而在某些情况下，需要表示及运算的整数比较大，即使采用更长的整型 (例如， long long类型，某些 c系统会提供 )也无法正确表示，此时可用一维数组来表示一个整数。假设下面要处理的大整数均为正数，将其从低位到高位每 4位一组进行分组 (最后一组可能不足 4位 )，每组作为 1个整数存人数组。例如，大整数 2543698845679015847在数组 A中的表示如下 (特别引入 -1表示分组结束 )： 在上述表示机制下，函数 add_large_number(A， B， c)将保存在一维整型数组 A和 B中的两个大整数进
3、行相加，结果 (和数 )保存在一维整型数组 c中。【 c函数】 Void add_large_number(int A， int B， int c)int i， cf； *cf存放进位 * int t，*p； *t为临时变量， p为临时指针 * cf= ( 1) ； for(i=0 ； Ai-l Bi-1；i+) *将数组 A、 B对应分组中的两个整数进行相加 * t=(2) ； Ci=t i0000；cf= (3) ； if( (4)P=B； else P=A； for(； Pi-1； i+) *将分组多的其余各组整数带进位复制入数组 C* Ci=(pi+cf) i0000； cf=(pi+
4、cf) 10000； if(cf0) Ci+=cf； (5)=-1； *标志 ”和数 ”的分组结束 * 3 阅读以下说明、 C函数和问题，将解答填入答题纸的对应栏内。 【说明】 二叉查找树又称为二叉排序树，它或者是一棵空树，或者是具有如下性质的二叉树： 若它的左子树非空，则其 左子树上所有结点的键值均小于根结点的键值； 若它的右子树非空，则其右子树上所有结点的键值均大于根结点的键值； 左、右子树本身就是二叉查找树。 设二叉查找树采用二叉链表存储结构，链表结点类型定义如下： typedef struct BiTnode int key_value； *结点的键值，为非负整数 * struct B
5、iTnode*left， *right； *结点的左、右子树指针 * *BSTree； 函数 findkey(root， key)的功能是用递归方式在给定的二叉查找树 (root指向根结点 )中查找键值为 key的结点并返回结点的指针；若找不到，则返回空指针。 【 C函数】 BSTree find_key(BSTree root， int key) if ( (1) ) return NULL； else if(key=root-key_valuel return (2) ； else if(keyname=name； this-phoneNumber=phoneNumber ； this-a
6、ddress=address； string name； string phoneNumber； string address； )； int main()mapemployeeMap； typedef pairemployeeNo； 从标准输入获得员工编号 map： const_iterator it； it= (5) find(employeeNo)； 根据员工编号查找员工信息if(it=employeeMap end()coutfirstsecond一 nafae(phoneNumbersecond-address 6 阅读以下说明和 Java代码，将应填人 (n) 处的字句写在答题纸的
7、对应栏内。【说明 】 Java.util包中提供了 HashMap模板类，该模板类可以表示多个 “键一值 ”对的集合，其中 “键 ”的作用与普通数组中的索引相当，而 “值 ”用作待存储和检索的数据。HashMap实现了 Map接口。在 Map接口中定义了 put和 get方法， put方法表示Map对象中加入一个 “键 -值 ”对， get方法则通过 “键 ”来获取其对应的 “值 ”。下面的Java代码中使用了 HashMap模板类，将编号为 1001、 1002、 1003的员工信息插入到 HashMap对象中，然后输入一个指定的员工编号，通过员工编号来获取员工的基本信息。 员工编号为整型编
8、码，而员工的基本信息定义为类 employee。HashMap对象与员工对象之间的关系及存储结构如图 52所示。【 Java代码】import Java.util *； class employeeemployee(String name， String phoneNumber，String address)this name=name； thi s phoneNumber=phoneNumber ；this address=address； String name； String phoneNumber； String address； ； publ ic class jaVaMainpub
9、lic static void main(Stringargs)MapemployeeMap=new HashMap(Integer， employee()； for(Integer employIndex=1001； employIndex 2009年上半年软件水平考试（初级）程序员下午（应用技术）试题真题试卷答案与解析 1 【正确答案】 (1)S (2)x n (3)Tn 【试题解析】 在题目中已经给出了指数函数 ex的公式，即基本算法，另外也给出了计算过程中控制误差终止计算的方法。本题主要的重点是如何设计计算流程，实现级数前若干项的求和，以及判断计算终止的条件。级数求和一般都是采用逐项累
10、加的方法。从流程图我们可以看出 s为累加结果， T为动态的项值，最后通过s+T-S 来完成各项的累加。已知 T=xnx n!，如果每次都直接计算 T 的值，计算量会比较大。从 ex的公式中我们可以看出每一项都一个共同点，就是后一项和前一项有简单的关系 Tn=T(n-i)*x n，我们可以充分利用前项的计算结果来计算后一项，这样就会大大减少计算量。这也是程序员需要掌握的基本技巧。在流程图中，一开始先输入变量 x，接着对其他变量赋初值。级数项号 n 的初始值为 1，逐次进行累积的 T 的初始值为 1，根据后面的流程推断可以看出逐次进行累加的 s应该有初始值 l的 (在输入的 x满足条件直接退出循环
11、的时候根据公式输出的值为D，所以空 (1)的答案为 “S”。从前面分析直到 e。的公式中后一项和前一项有简单的关系 Tn=T(n-i)*x n，所以空 (2)的答案为 “x n”。空 (3)处是判断计算过程结束的条件，按照题目中的要求 “当 T值小于 lO-5时，结束计算。 ”所以空 (3)的答案为“Ts，所以空 (4)的答案为 “S+T”。流程走到空 (5)的时候已经求出第 n项的值 Tn，并累加到 s中，根据算法下一步应该计算第 n+1项的值，所以这里需要对级数的项号 n进行自增，空 (5)的答案可以为 “n+=1”或者 n+，但是根据流程图以上的书写风格写为 “n+1-n”应该是最佳答案
12、。 2 【正确答案】 (1)0 (2)Ai+Bi+cf (3)t 10000 (4)Ai=-l或 Bi-1(5)Ci 【试题解析】 题目用整型数组表示大数组，一个数组元素表示 4位的整数。在这种表示方式下进行两个大整数的相加运算时，需要对进位的处理多加考虑。已知cf 表示进位情况，那么在开始进行相加之前， cf 的初始值应该为 O，所以空 (1)的答案为 “O”。大家都知道在进行加法操作的时候，需要从个位开始进行对齐然后从末位进行相加。对于保存在整型数组中的大整数，我们从最低位 A0和 B0开始相加，并且根据程序中 ci=t 10000对 t的使用，可以推断出 空 (2)的答案为“Ai+Bi+
13、cf”。需要注意的是，在进行运算的同时，需要对前面相加产生的进位cf 进行相加，同时也要计算出此次相加产生的进位，所以空 (3)进位的计算的答案应该为 “t 10000”。但是每次进行相加的两个整数的位数不一定相同，对于位数比较长的那个整数，我们应该把相加之后剩余的位数连带进位记录下来，保存到数组 c中的对应位置，从程序中可以看出临时指针 p 指向的是位数比较长的这个数组。根据题目中的两个 for循环设置的满足循环的条件可以看出如果数组中的整数已经相加结束，肯定满足 Ai=-1否 则 Bi=-1，所以空 (4)处的判断条件应该为“Ai： =-1”或者 “Bi-l”。当两个整数相加之后会产生进位
14、，新的数据的位数可能会比原来的长，这时候我们就需要把多出来的这一位 (即最后一次相加产生的进位 )作为和数来进行处理。函数在最后用一个 if语句对这种情况进行了处理，而空 (5)的语句应该是对存放相加之和的数组设置结束标志，所以空 (5)的答案为 ci。 3 【正确答案】 (1)!root或 rool=NuLL (2)root (3)find_key(root-。 left，key)(4)find_key(root-fight， key)(5)该关键字对应结点在该二叉查找树所在层次 (数 )或位置，或者该二叉树中从根结点到该关键字对应结点的路径长度。 【试题解析】 根据 “说明 ”中对二叉查找
15、树的定义可以知道在对二叉查找树进行查找时，应该按照以下步骤来进行。 (1)首先判断二叉查找树是否为空，如果为空，直接返回 NuLL；否则，继续向下走。 (2)判断键值 key与树根结点的键值比较的大小。 (3)如果相等，则返回树根结点。 (4)如果大于树根结点，则以树根结点的右子树为根结点，从步骤 (1)开始继续循环查找 。 (5)如果小于树根结点，则以树根结点的左子树为根结点，从步骤 (1)开始继续循环查找。 (6)递归调用查找函数，如果给定的二叉查找树上不存在与给定的键值相等的结点，则必然进入某一个结点的空的子树时结束。从以上的步骤分析可以看出空 (1)处应该是判断 root是否为空，故答
16、案为 “root=NuLL”或 !root；空 (2)的时候查找到与 key相等的键值，返回该节点指针，故答案为 “root”；空 (3)处 key的值小于根结点的键值，则应该以该根结点的左子树为根结点重新查找，故答案为 “find_key(root-1eft， key)”；空 (4)处则是处理剩下的最后一种情况，即 key的值大于根结点的键值，这时候应该以该根结点的右子树为根结点，递归调用函数，所以答案为 “find_key(root-fight，key)”。根据上面的二叉查找树的查找过程中可以看出，查找成功其实是走了一条从根结点到达所找结点的路径。例如要从下面的二叉查找树中查找 75，则需
17、要依次与 50、 67、 89、 75进行比较，可以看出在树中查找一个关键字，需要比较的结点的个数取决于该关键字对应结点在该二叉查找树中所在层数或位置，或者是该二叉查找树从根结点到该关键 字的对应结点的路径长度。 4 【正确答案】 问题 (1)： 以上的答案仅供参考，并没有先后顺序。另外对 sum进行初始化的 “sum=O； ”也可以加在第 3行，第 4行以及第 5行的适当的位置。问题 (2)： (1)str+ (2) str： a 【试题解析】 问题 (1)解析：程序中的错误可以分为语法错误和语义错误，其中语义错误又可以分为静态语义错误和动态语义错误。语法错误和静态语义错误可以在编译的时候发
18、现，而动态的语义错误只有在程序运行的结果中才能表现出来。 C函数 1中的 main 函数通过编译但是运行结果不对 ，虽然输出的是 sum的值，但是在 for循环中 sum的值的得到与 k以及 n的值是相关的，因此我们需要从 n、 k、sum的定义和初始化查起。首先来看 k，在定义的时候没有被初始化，但是在 for循环进行使用的时候被初始化为 1，后面通过 k+进行改变的，这一部分是正确的。接下来看 n， n 在定义的时候也没有被初始化， n 的值是通过 scanf(“ d”， n)取得的，由第二次测试的显示结果可以看出， n 的值并不是我们的输入值 5，很显然 n 的值设定不对，回头仔细检查
19、scanf函数的调用才发现 n 的前面缺少取地址运算符 “ ”，作为一名程序员 都应该知道 scanf中的变量使用的是地址，所以正确的写法为 “scanI。 (“ d”， &m)； ”；再来看 sum， sum的值主要是通过 for循环中的语句 “sum+=k*k”来改变的。 “sum+=k*k”实际上等同于 “sum=sum+k*k”，可是我们知道 sum在定义的时候并没有初始化，那么在我们第一次进入 for循环的时候 sum的值是不确定的，在这种情况下执行语句 “sum+=k*k”得到的值自然也就无法预料了，所以我们需要在 sum使用之前对其进行初始化 “sum=0”。另外，在程序中还有一
20、处就是第 5行，可以看到在句 末有一个分号，这样就等于 for循环语句的循环体为空， “sum+=k * k”语句并没有被包含到 for循环语句中，只是在循环结束后执行一次，最后输出地结果 sum是等于 n * n，不符合题目要求的结果(12+22+32+n 2)，正确的做法就是删除第 5行末位的分号。问题 (2)的解析：函数 test 12()编译时系统报错，检查函数能够发现 “char str =“test string”； ”定义了字符数组 str，并进行了初始化，因此 str就是数组名，也是数组在内存中的首地址， *str则表示的是 strO， 通过 “* str=a”改变 strO的
21、值是对的，但是“str+”就不对了，在 c语言中 str是数组名是地址常量，是不能修改的，所以系统在编译的时候会报告错误。如果我们将 str定义为一个 char类型的指针的话，则可以通过 str+来修改 str的值，使它指向不同字符对象，但是在函数 f2_B()中定义 “char *str=test string； ”的时候，直接对指针 str用常量进行了初始化，使得str为一个指针常量，这样即使我们可以通过 str+取得字符串中的任何一个字符，但是却不能够通过 “*str=a”修改 *str的值，所以在运行的时候就会发生异常不能够正常结束。 5 【正确答案】 (1)public (2)tem
22、p (3)insert (4)cin (5)employeeMap 【试题解析】 在 c+中，在生成类的对象的时候需要调用类的构造函数，因此employee的构造函数应该是公有函数，在代码中的空 (1)处的答案为 “public ”；在空 (2)所在行通过注释可以看出来在这一行我们需要把 char型的数组 temp 转换成string型的对象，所以空 (2)的答案为 “temp”；在空 (3)所在的代码行我们构造了一个新的员工对象，并将其插入 Pair对象中，按照代码注释的意思需要将这个 Pair对象添加到 employeeMap 对象中，在题目前面的说明中已经给出了 Map 类的使用方法，可
23、以直接通过调用 Map 类中的 insert函数实现这一功能，所以空 (3)的答案为 “insert”；空 (4)处需要从标准输入获得员工编号， c+的标准类库中已经提供了标准输入函数 cin，所以这里的答案为 “cin”；空 (5)处根据注释我们知道是要根据员工编号查找员工信息，这里我们可以直接调用 Map 类的 find函数来实现，因而之前员工编号和员工信息都是通过调用 Map 类的 insert函数存储在 Map 类的实例 employeeMap 中，所以空 (5)的答案为 “employeeMap”。 6 【正确答案】 (1)toString (2)put (3)new employe
24、e (4)get (5)result 【试题解析】 在空 (1)我们可以看到 trap 是 String类型的，而 employlndex 是Integer类型的，很显然这里是要把 employIndex 转换为 String 类型赋值给临时变量 tmp，所以可以使用整型数 的 “toString方法；空 (2)和空 (3)所在的行根据注释可以看出是希望构造一个新的员工对象，并将这个新对象以及其编号加入HashMap 类的实例 employee-Map 中，而我们从前面的说明可以知道 HashMap 类中的 put函数可以直接实现加入这一功能，所以空 (2)的答案为 “put”，而空 (3)处需要使用。 new 构造一个新的 employee对象，所以答案为 “new employee”；空 (4)处我们得到了一个员工编号，根据题意这里主要是使用 HashMap类的 get函数来查询对应员工编号的员工信息，并将 其存放到 result中，如果没有查到 result将为空，并输出提示语句提示该员工编号不存在，所以空 (4)的答案为 “get”，空 (5)的答案为 “result”。
