2009年上半年程序员下午试卷案例

设x位于区间（0, 1)，该流程图的算法要点是逐步累积计算每项

的值（作为 T),再逐步累加T值得到所需的结果S。当T值小于10^-5时，结束计算。

问题：1.1 【流程图】

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

在上述表示机制下，函数add_large+mimbert(A、B、C)将保存在一维整型数组A和B中的两个大整数进行相加，结果（和数）保存在一维整型数组C中。

问题：2.1 【C函数】

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

若它的左子树非空，则其左子树上所有结点的键值均小于根结点的键值；
若它的右子树非空，则其右子树上所有结点的键值均大于根结点的键值；
左、右子树本身就是二叉查找树。

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

函数find_key(root, key)的功能是用递归方式在给定的二叉查找树(root指向根结点) 中查找键值为key的结点并返回结点的指针；若找不到，则返回空指针。

问题：3.1 【C函数】

问题：3.2 若某二叉查找树中有n个结点，则查找一个给定关键字时，需要比较的结点个数取决于（5)。

【说明1】
函数main()的功能旨在对输入的—个正整数n，计算1²+2²+3²+…+n²,但是对该函数进行测试后没有得到期望的结果。

问题：4.1 请给出上述main函数中需要修改的代码行号，并给出修改后的整行代码。

问题：4.2 【说明2】
函数test_f2()编译时系统报告有错，修改后得到函数f2_B()。对函数f2_B()进行编译时顺利通过，在某些C系统中执行时却由于发生异常而不能正确结束。

【C函数2】

【问题】
(1) 请指出函数test_f2中不能通过编译的表达式；
(2) 请指出可能导致函数f2_B运行异常的表达式。

【说明】
C++标准模板库中提供了map模板类，该模板类可以表示多个“键-值”对的集合，其中键的作用与普通数组中的索引相当，而值用作待存储和检索的数据。此外，C++模板库还提供了pair模板类，该类可以表示一个“键-值”对。pair对象包含两个属性：first 和second,其中first表示“键-值”中的“键”，而second表示“键-值”中的“值”。
map类提供了 insert方法和find方法，用于插入和查找信息。应用时，将一个pair 对象插入（insert)到map对象后，根据“键”在map对象中进行査找（find)，即可获得一个指向pair对象的迭代器。
下面的C++代码中使用了 map和pair模板类，将编号为1001、1002、1003的员工信息插入到map对象中，然后输入一个指定的员工编号，通过员工编号来获取员工的基本信息。员工编号为整型编码，员工的基本信息定义为类employee。map对象与员工对象之间的关系及存储结构如图5-1所示。

问题：5.1 阅读以下说明和C++代码，将应填入（n)处的字句写在答题纸的对应栏内。
【C++代码】

【说明】
java.util包中提供了HashMap模板类，该模板类可以表示多个“键-值”对的集合，其中“键”的作用与普通数组中的索引相当，而“值”用作待存储和检索的数据。HashMap 实现了 Map接口。在Map接口中定义了put和get方法，put方法表示Map对象中加入一个“键-值”对，get方在则通过“键”来获取其对应的“值”。
下面的Java代码中使用了HashMap模板类，将编号为1001、1002、1003的员工信息插入到HashMap对象中，然后输入一个指定的员工编号，通过员工编号来获取员工的基本信息。员工编号为整型编码，而员工的基本信息定义为类employee。
HashMap对象与员工对象之间的关系及存储结构如下图所示。

问题：6.1