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

>>>點擊進入軟考初級程序員歷年真題下載

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

（）（共15分）

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

【說明】

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

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

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

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

【C 函數(shù)】

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++) {

/*將數(shù)組

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

t = （2） ;

C[i] = t % 10000;

cf = （3） ;

}

if ( （4）)p = B;

elsep = A;

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

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

}

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

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

}

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

【函數(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】

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

【問題2】

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

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

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

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

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

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

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

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

【說明1】

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

【C函數(shù)1】

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

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

【問題1】（9 分）

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

【說明2】

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

【C函數(shù)2】

【問題2】（6 分）

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

（2）請指出可能導致函數(shù)f2_B 運行異常的表達式。

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

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

string tmp(（2）); //通過temp構(gòu)造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); //根據(jù)員工編號查找員工信息

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

)

); //將員工編號和員工信息插入到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 );

}

}