2009年上半年程序員考試下午真題：

>>>點(diǎn)擊進(jìn)入軟考初級(jí)程序員歷年真題下載

● __(1)__（共15分）
閱讀以下說明和流程圖，填補(bǔ)流程圖中的空缺（1）～（5），將解答填入答題紙的對(duì)應(yīng)欄內(nèi)。
【說明】
下面的流程圖采用公式 計(jì)算 的近似值。
設(shè)x位于區(qū)間 （0，1）， 該流程圖的算法要點(diǎn)是逐步累積計(jì)算每項(xiàng)Xⁿ/n!的值 （作為T），再逐步累加T 值得到所需的結(jié)果S。當(dāng)T 值小于10^-5時(shí)，結(jié)束計(jì)算。

（）（共15分）

閱讀以下說明和流程圖，填補(bǔ)流程圖中的空缺（1）～（5），將解答填入答題紙的對(duì)應(yīng)欄內(nèi)。

【說明】

下面的流程圖采用公式 計(jì)算 的近似值。

設(shè)x位于區(qū)間 （0，1）， 該流程圖的算法要點(diǎn)是逐步累積計(jì)算每項(xiàng)Xⁿ/n!的值 （作為T），再逐步累加T 值得到所需的結(jié)果S。當(dāng)T 值小于10^-5時(shí)，結(jié)束計(jì)算。

● __(2)__（共15分）
閱讀以下說明和C 函數(shù)，將應(yīng)填入（n）處的字句寫在答題紙的對(duì)應(yīng)欄內(nèi)。
【說明】
C 語言常用整型（int）或長(zhǎng)整型（long）來說明需要處理的整數(shù)，在一般情況下可以滿足表示及運(yùn)算要求，而在某些情況下，需要表示及運(yùn)算的整數(shù)比較大，即使采用更長(zhǎng)的整型（例如，long long類型，某些C系統(tǒng)會(huì)提供）也無法正確表示，此時(shí)可用一維數(shù)組來表示一個(gè)整數(shù)。
假設(shè)下面要處理的大整數(shù)均為正數(shù)，將其從低位到高位每4位一組進(jìn)行分組（最后一組可能不足4位），每組作為1個(gè)整數(shù)存入數(shù)組。例如，大整數(shù)2543698845679015847在數(shù)組A 中的表示如下（特別引入-1表示分組結(jié)束）：

在上述表示機(jī)制下，函數(shù)add_large_number(A，B，C)將保存在一維整型數(shù)組A和B中的兩個(gè)大整數(shù)進(jìn)行相加，結(jié)果（和數(shù)）保存在一維整型數(shù)組C 中。

【C 函數(shù)】

void add_large_number(int A[]， int B[]， int C[])

{

int i， cf ;/*cf存放進(jìn)位*/

int t， *p;/*t為臨時(shí)變量，p為臨時(shí)指針*/

cf = （1） ;

for(i = 0; A[i]>-1 && B[i]>-1; i++) {

/*將數(shù)組

（2）A．B 對(duì)應(yīng)分組中的兩個(gè)整數(shù)進(jìn)行相加*/

t = （2） ;

C[i] = t % 10000;

cf = （3） ;

}

if ( （4）)p = B;

elsep = A;

for( ; p[i]>-1; i++) {/*將分組多的其余各組整數(shù)帶進(jìn)位復(fù)制入數(shù)組C*/

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

}

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

（5）= -1;/*標(biāo)志"和數(shù)"的分組結(jié)束*/

}

● __(3)__（共15分）
閱讀以下說明、C 函數(shù)和問題，將解答填入答題紙的對(duì)應(yīng)欄內(nèi)。
【說明】
二叉查找樹又稱為二叉排序樹，它或者是一棵空樹，或者是具有如下性質(zhì)的二叉樹：
若它的左子樹非空，則其左子樹上所有結(jié)點(diǎn)的鍵值均小于根結(jié)點(diǎn)的鍵值；
若它的右子樹非空，則其右子樹上所有結(jié)點(diǎn)的鍵值均大于根結(jié)點(diǎn)的鍵值；
左、右子樹本身就是二叉查找樹。
設(shè)二叉查找樹采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，鏈表結(jié)點(diǎn)類型定義如下：
typedef struct BiTnode{
intkey_value; /*結(jié)點(diǎn)的鍵值，為非負(fù)整數(shù)*/
struct BiTnode *left，*right;/*結(jié)點(diǎn)的左、右子樹指針*/
}*BSTree;
函數(shù)find_key(root， key)的功能是用遞歸方式在給定的二叉查找樹（root指向根結(jié)點(diǎn)）中查找鍵值為key的結(jié)點(diǎn)并返回結(jié)點(diǎn)的指針；若找不到，則返回空指針。

【函數(shù)】

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】

請(qǐng)將函數(shù)find_key中應(yīng)填入（1）～（4）處的字句寫在答題紙的對(duì)應(yīng)欄內(nèi)。

【問題2】

若某二叉查找樹中有n個(gè)結(jié)點(diǎn)，則查找一個(gè)給定關(guān)鍵字時(shí)，需要比較的結(jié)點(diǎn)個(gè)數(shù)取決于（5）。

● __(4)__（共15 分）
閱讀以下兩個(gè)說明、C 函數(shù)和問題，將解答寫入答題紙的對(duì)應(yīng)欄內(nèi)。
【說明1】
函數(shù) main__(5)__的功能旨在對(duì)輸入的一個(gè)正整數(shù) n，計(jì)算1²+2²+3²+...+n²，但是對(duì)該函數(shù)進(jìn)行測(cè)試后沒有得到期望的結(jié)果。
【C函數(shù)1】

1. 輸入5測(cè)試上述main函數(shù)時(shí)，顯示結(jié)果如下所示。

2. 將行號(hào)為7的代碼修改為：printf("n = %d\nresult: %d\n"， n， sum);并再次輸入5測(cè)試main函數(shù)，顯示結(jié)果如下所示。

【問題1】（9 分）
請(qǐng)給出上述main函數(shù)中需要修改的代碼行號(hào)，并給出修改后的整行代碼。 行號(hào)修改后的整行代碼

【說明2】
函數(shù)test_f2__(6)__編譯時(shí)系統(tǒng)報(bào)告有錯(cuò)，修改后得到函數(shù)f2_B__(7)__。對(duì)函數(shù)f2_B__(8)__進(jìn)行編譯時(shí)順利通過，在某些C 系統(tǒng)中執(zhí)行時(shí)卻由于發(fā)生異常而不能正確結(jié)束。
【C函數(shù)2】

【問題2】（6 分）
（1）請(qǐng)指出函數(shù)test_f2中不能通過編譯的表達(dá)式；
（2）請(qǐng)指出可能導(dǎo)致函數(shù)f2_B 運(yùn)行異常的表達(dá)式。
（）（共15 分）

閱讀以下兩個(gè)說明、C 函數(shù)和問題，將解答寫入答題紙的對(duì)應(yīng)欄內(nèi)。

【說明1】

函數(shù) main()的功能旨在對(duì)輸入的一個(gè)正整數(shù) n，計(jì)算 ，但是對(duì)該函數(shù)進(jìn)行測(cè)試后沒有得到期望的結(jié)果。

【C函數(shù)1】

1. 輸入5測(cè)試上述main函數(shù)時(shí)，顯示結(jié)果如下所示。

2. 將行號(hào)為7的代碼修改為：printf("n = %d\nresult: %d\n"， n， sum);并再次輸入5測(cè)試main函數(shù)，顯示結(jié)果如下所示。

【問題1】（9 分）

請(qǐng)給出上述main函數(shù)中需要修改的代碼行號(hào)，并給出修改后的整行代碼。 行號(hào)修改后的整行代碼

【說明2】

函數(shù)test_f2()編譯時(shí)系統(tǒng)報(bào)告有錯(cuò)，修改后得到函數(shù)f2_B()。對(duì)函數(shù)f2_B()進(jìn)行編譯時(shí)順利通過，在某些C 系統(tǒng)中執(zhí)行時(shí)卻由于發(fā)生異常而不能正確結(jié)束。

【C函數(shù)2】

【問題2】（6 分）

（1）請(qǐng)指出函數(shù)test_f2中不能通過編譯的表達(dá)式；

（2）請(qǐng)指出可能導(dǎo)致函數(shù)f2_B 運(yùn)行異常的表達(dá)式。

● __(5)__ （共15 分）
閱讀以下說明和C++代碼，將應(yīng)填入（n） 處的字句寫在答題紙的對(duì)應(yīng)欄內(nèi)。
【說明】
C++標(biāo)準(zhǔn)模板庫中提供了map模板類，該模板類可以表示多個(gè)“鍵-值”對(duì)的集合，其中鍵的作用與普通數(shù)組中的索引相當(dāng)，而值用作待存儲(chǔ)和檢索的數(shù)據(jù)。此外，C++模板庫還提供了pair模板類，該類可以表示一個(gè)“鍵-值”對(duì)。pair對(duì)象包含兩個(gè)屬性：first和second，其中first表示“鍵-值”中的“鍵” ，而second表示“鍵-值”中的“值”。
map 類提供了 insert 方法和 find 方法，用于插入和查找信息。應(yīng)用時(shí)，將一個(gè) pair對(duì)象插入（insert）到 map 對(duì)象后，根據(jù)“鍵”在 map 對(duì)象中進(jìn)行查找（find），即可獲得一個(gè)指向pair對(duì)象的迭代器。
下面的 C++代碼中使用了 map和 pair 模板類，將編號(hào)為 1001、1002、1003 的員工信息插入到map對(duì)象中，然后輸入一個(gè)指定的員工編號(hào)，通過員工編號(hào)來獲取員工的基本信息。員工編號(hào)為整型編碼，員工的基本信息定義為類employee。
map對(duì)象與員工對(duì)象之間的關(guān)系及存儲(chǔ)結(jié)構(gòu)如圖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] ;//臨時(shí)存儲(chǔ)空間

_itoa(employIndex，temp，10); //將employIndex轉(zhuǎn)化為字符串存儲(chǔ)在temp中

string tmp(（2）); //通過temp構(gòu)造string對(duì)象

employeeMap. （3）( employeePair ( employIndex，

new employee("employee-" + tmp，

"85523927-"+tmp，

"address-"+tmp)

)

); //將員工編號(hào)和員工信息插入到employeeMap對(duì)象中

}

int employeeNo = 0;

cout << "請(qǐng)輸入員工編號(hào):";

（4） >> employeeNo;//從標(biāo)準(zhǔn)輸入獲得員工編號(hào)

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

it =（5）.find(employeeNo); //根據(jù)員工編號(hào)查找員工信息

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

cout << "該員工編號(hào)不存在 ！" << endl;

return -1;

}

cout << "你所查詢的員工編號(hào)為：" << it->first << endl;

cout << "該員工姓名：" << it->second->name << endl;

cout << "該員工電話：" << it->second->phoneNumber << endl;

cout << "該員工地址：" << it->second->address << endl;

return 0;

}

● __(6)__（共15 分）
閱讀以下說明和Java代碼，將應(yīng)填入（n） 處的字句寫在答題紙的對(duì)應(yīng)欄內(nèi)。
【說明】
java.util包中提供了HashMap模板類，該模板類可以表示多個(gè)“鍵-值”對(duì)的集合，其中 “鍵” 的作用與普通數(shù)組中的索引相當(dāng)，而 “值” 用作待存儲(chǔ)和檢索的數(shù)據(jù)。 HashMap實(shí)現(xiàn)了Map接口。在Map接口中定義了put和get方法，put方法表示Map對(duì)象中加入一個(gè)“鍵-值”對(duì)，get方法則通過“鍵”來獲取其對(duì)應(yīng)的“值” 。
下面的Java代碼中使用了HashMap模板類，將編號(hào)為1001、1002、1003的員工信息插入到HashMap對(duì)象中，然后輸入一個(gè)指定的員工編號(hào)，通過員工編號(hào)來獲取員工的基本信息。員工編號(hào)為整型編碼，而員工的基本信息定義為類employee。
HashMap對(duì)象與員工對(duì)象之間的關(guān)系及存儲(chǔ)結(jié)構(gòu)如圖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

)

); //將員工編號(hào)和員工信息插入到employeeMap對(duì)象中

}

int employeeNo = 0;

System.out.print("請(qǐng)輸入員工編號(hào):");

Scanner s= new Scanner(System.in);

employeeNo = s.nextInt();//從標(biāo)準(zhǔn)輸入獲得員工編號(hào)

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

if (（5） == null)

{

System.out.println("該員工編號(hào)不存在 ！");

return;

}

System.out.println("你所查詢的員工編號(hào)為：" + employeeNo);

System.out.println("該員工姓名：" + result.name);

System.out.println("該員工電話：" + result.phoneNumber);

System.out.println("該員工地址：" + result.address );

}

}