2009年上半年程序员考试下午真题：

>>>点击进入软考初级程序员历年真题下载

● __(1)__（共15分）
阅读以下说明和流程图，填补流程图中的空缺（1）～（5），将解答填入答题纸的对应栏内。
【说明】
下面的流程图采用公式 计算 的近似值。
设x位于区间 （0，1）， 该流程图的算法要点是逐步累积计算每项Xⁿ/n!的值 （作为T），再逐步累加T 值得到所需的结果S。当T 值小于10^-5时，结束计算。

（）（共15分）

阅读以下说明和流程图，填补流程图中的空缺（1）～（5），将解答填入答题纸的对应栏内。

【说明】

下面的流程图采用公式 计算 的近似值。

设x位于区间 （0，1）， 该流程图的算法要点是逐步累积计算每项Xⁿ/n!的值 （作为T），再逐步累加T 值得到所需的结果S。当T 值小于10^-5时，结束计算。

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

在上述表示机制下，函数add_large_number(A，B，C)将保存在一维整型数组A和B中的两个大整数进行相加，结果（和数）保存在一维整型数组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; A[i]>-1 && B[i]>-1; i++) {

/*将数组

（2）A．B 对应分组中的两个整数进行相加*/

t = （2） ;

C[i] = t % 10000;

cf = （3） ;

}

if ( （4）)p = B;

elsep = A;

for( ; p[i]>-1; i++) {/*将分组多的其余各组整数带进位复制入数组C*/

C[i] = (p[i] + cf) %10000;cf = (p[i] + cf) /10000;

}

if ( cf > 0 )C[i++] = cf;

（5）= -1;/*标志"和数"的分组结束*/

}

● __(3)__（共15分）
阅读以下说明、C 函数和问题，将解答填入答题纸的对应栏内。
【说明】
二叉查找树又称为二叉排序树，它或者是一棵空树，或者是具有如下性质的二叉树：
若它的左子树非空，则其左子树上所有结点的键值均小于根结点的键值；
若它的右子树非空，则其右子树上所有结点的键值均大于根结点的键值；
左、右子树本身就是二叉查找树。
设二叉查找树采用二叉链表存储结构，链表结点类型定义如下：
typedef struct BiTnode{
intkey_value; /*结点的键值，为非负整数*/
struct BiTnode *left，*right;/*结点的左、右子树指针*/
}*BSTree;
函数find_key(root， key)的功能是用递归方式在给定的二叉查找树（root指向根结点）中查找键值为key的结点并返回结点的指针；若找不到，则返回空指针。

【函数】

BSTree find_key(BSTree root， int key)

{

if (（1） )

return NULL;

else

if (key == root-> key_value)

return （2） ;

else if (key < root -> key_value)

return （3） ;

else

return （4） ;

}

【问题1】

请将函数find_key中应填入（1）～（4）处的字句写在答题纸的对应栏内。

【问题2】

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

● __(4)__（共15 分）
阅读以下两个说明、C 函数和问题，将解答写入答题纸的对应栏内。
【说明1】
函数 main__(5)__的功能旨在对输入的一个正整数 n，计算1²+2²+3²+...+n²，但是对该函数进行测试后没有得到期望的结果。
【C函数1】

1. 输入5测试上述main函数时，显示结果如下所示。

2. 将行号为7的代码修改为：printf("n = %d\nresult: %d\n"， n， sum);并再次输入5测试main函数，显示结果如下所示。

【问题1】（9 分）
请给出上述main函数中需要修改的代码行号，并给出修改后的整行代码。 行号修改后的整行代码

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

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

阅读以下两个说明、C 函数和问题，将解答写入答题纸的对应栏内。

【说明1】

函数 main()的功能旨在对输入的一个正整数 n，计算 ，但是对该函数进行测试后没有得到期望的结果。

【C函数1】

1. 输入5测试上述main函数时，显示结果如下所示。

2. 将行号为7的代码修改为：printf("n = %d\nresult: %d\n"， n， sum);并再次输入5测试main函数，显示结果如下所示。

【问题1】（9 分）

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

【说明2】

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

【C函数2】

【问题2】（6 分）

（1）请指出函数test_f2中不能通过编译的表达式；

（2）请指出可能导致函数f2_B 运行异常的表达式。

● __(5)__ （共15 分）
阅读以下说明和C++代码，将应填入（n） 处的字句写在答题纸的对应栏内。
【说明】
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所示。


【C++代码】

#include <iostream>

#include <map>

#include <string>

using namespace std ;

class employee{

（1）:

employee(string name，string phoneNumber， string address){

this->name = name;

this->phoneNumber = phoneNumber;

this->address = address;

}

string name;

string phoneNumber;

string address;

};

int main( )

{

map <int， employee*> employeeMap;

typedef pair <int， employee*> employeePair;

for (int employIndex = 1001; employIndex <= 1003; employIndex++){

char temp[10] ;//临时存储空间

_itoa(employIndex，temp，10); //将employIndex转化为字符串存储在temp中

string tmp(（2）); //通过temp构造string对象

employeeMap. （3）( employeePair ( employIndex，

new employee("employee-" + tmp，

"85523927-"+tmp，

"address-"+tmp)

)

); //将员工编号和员工信息插入到employeeMap对象中

}

int employeeNo = 0;

cout << "请输入员工编号:";

（4） >> employeeNo;//从标准输入获得员工编号

map<int，employee*>::const_iterator it;

it =（5）.find(employeeNo); //根据员工编号查找员工信息

if (it == employeeMap.end()) {

cout << "该员工编号不存在 ！" << endl;

return -1;

}

cout << "你所查询的员工编号为：" << it->first << endl;

cout << "该员工姓名：" << it->second->name << endl;

cout << "该员工电话：" << it->second->phoneNumber << endl;

cout << "该员工地址：" << it->second->address << endl;

return 0;

}

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



【Java 代码】

import jav

（6）A．util.*;

class employee{

employee(String name，String phoneNumber， String address){

this.name = name;

this.phoneNumber = phoneNumber;

this.address = address;

}

String name;

String phoneNumber;

String address;

};

public class javaMain {

public static void main(String[] args) {

Map<Integer， employee> employeeMap = new HashMap<Integer， employee>();

for (Integer employIndex = 1001; employIndex <= 1003; employIndex++){

String tmp = employIndex.（1）();

employeeMap.（2）(employIndex，（3）("employee-"+tmp，

"85523927-"+tmp，

"address-"+tmp

)

); //将员工编号和员工信息插入到employeeMap对象中

}

int employeeNo = 0;

System.out.print("请输入员工编号:");

Scanner s= new Scanner(System.in);

employeeNo = s.nextInt();//从标准输入获得员工编号

employee result = employeeMap.（4）(employeeNo);

if (（5） == null)

{

System.out.println("该员工编号不存在 ！");

return;

}

System.out.println("你所查询的员工编号为：" + employeeNo);

System.out.println("该员工姓名：" + result.name);

System.out.println("该员工电话：" + result.phoneNumber);

System.out.println("该员工地址：" + result.address );

}

}