上半年軟考程序員考試下午試卷及答案

1、2009年上半年軟考程序員考試下午試卷試題一（共15分）閱讀以下說明和流程圖，填補(bǔ)流程圖中的空缺（1）（5），將解答填入答題紙的對(duì)應(yīng)欄內(nèi)?！菊f明】下面的流程圖采用公式ex=1+x+x2/2!+x3/3!+x4/4!+xn/n!+計(jì)算的ex近似值。設(shè)x位于區(qū)間 （0,1）， 該流程圖的算法要點(diǎn)是逐步累積計(jì)算每項(xiàng)Xn/n!的值 （作為T），再逐步累加T 值得到所需的結(jié)果S。當(dāng)T 值小于10-5 時(shí)，結(jié)束計(jì)算?！玖鞒虉D】(1) S (2)x/n (3)T<0.00001 (4)S+T n+1n試題二（共15分）閱讀以下說明和C函數(shù)，將應(yīng)填入_處的字句寫在答題紙的對(duì)應(yīng)欄內(nèi)?！菊f明】C 語言常用整

2、型（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ù)）

3、保存在一維整型數(shù)組C 中?！綜 函數(shù)】void add_large_number(int A, int B, int C)int i, cf ;                  /*cf存放進(jìn)位*/int t, *p;                  /*

4、t為臨時(shí)變量，p為臨時(shí)指針*/cf =     （1）    ;for(i = 0; Ai>-1 && Bi>-1; i+) /*將數(shù)組A、B 對(duì)應(yīng)分組中的兩個(gè)整數(shù)進(jìn)行相加*/t =     （2）    ;Ci = t % 10000;cf =     （3）    ;if (     （4）  &

5、#160;   )    p = B;else    p = A;for( ; pi>-1; i+)           /*將分組多的其余各組整數(shù)帶進(jìn)位復(fù)制入數(shù)組C*/Ci = (pi + cf) %10000;    cf = (pi + cf) /10000;if ( cf > 0 )      Ci+ = cf;（5） 

6、;     = -1;                /*標(biāo)志"和數(shù)"的分組結(jié)束*/0 Ai+Bi+cf t/10000 Ai=-1或者Bi>-1 Ci試題三（共15分）閱讀以下說明、C 函數(shù)和問題，將解答填入答題紙的對(duì)應(yīng)欄內(nèi)?！菊f明】二叉查找樹又稱為二叉排序樹，它或者是一棵空樹，或者是具有如下性質(zhì)的二叉樹： 若它的左子樹非空，則其左子樹上所有結(jié)點(diǎn)的鍵值均小于根結(jié)點(diǎn)的鍵值； 若它的

7、右子樹非空，則其右子樹上所有結(jié)點(diǎn)的鍵值均大于根結(jié)點(diǎn)的鍵值； 左、右子樹本身就是二叉查找樹。 設(shè)二叉查找樹采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，鏈表結(jié)點(diǎn)類型定義如下：typedef struct BiTnodeint    key_value;                   /*結(jié)點(diǎn)的鍵值，為非負(fù)整數(shù)*/struct BiTnode *left,*right;   &#

8、160;        /*結(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;elseif (key = root-> key_v

9、alue)return     （2）    ;else if (key < root -> key_value)return     （3）    ;elsereturn     （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ù)取決于 

10、; （5）  。 root= NULL（root= =0 或！root） root find _key(root->left,key) find_key(root->right,key)關(guān)鍵字所在的結(jié)點(diǎn)的層數(shù)和二叉樹的高度試題四（共15 分）閱讀以下兩個(gè)說明、C 函數(shù)和問題，將解答寫入答題紙的對(duì)應(yīng)欄內(nèi)?！菊f明1】函數(shù) main()的功能旨在對(duì)輸入的一個(gè)正整數(shù) n，計(jì)算12+22+32+n2,但是對(duì)該函數(shù)進(jìn)行測(cè)試后沒有得到期望和結(jié)果?！綜函數(shù)1】1. 輸入5測(cè)試上述main函數(shù)時(shí)，顯示結(jié)果如下所示。2. 將行號(hào)為7的代碼修改為：printf("n = %dnres

11、ult: %dn", n, sum);  并再次輸入5測(cè)試main函數(shù)，顯示結(jié)果如下所示。 【問題1】（9 分）請(qǐng)給出上述main函數(shù)中需要修改的代碼行號(hào)，并給出修改后的整行代碼?！菊f明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á)式。問題1行號(hào) 修改后的整行代碼2int k,n, sun=0；或 int k,n,sum，su

12、m=0；4scanf("%d",&n);5for (k =1 ;k < =n; k+)問題2 str+ *str='a'從下列2道試題（試題五至試題六）中任選1道解答。如果解答的試題數(shù)超過1道，則題號(hào)小的1道解答有效。試題五（共15 分）閱讀以下說明和C+代碼，將應(yīng)填入 （n） 處的字句寫在答題紙的對(duì)應(yīng)欄內(nèi)?！菊f明】C+標(biāo)準(zhǔn)模板庫中提供了map模板類，該模板類可以表示多個(gè)“鍵-值”對(duì)的集合，其中鍵的作用與普通數(shù)組中的索引相當(dāng)，而值用作待存儲(chǔ)和檢索的數(shù)據(jù)。此外，C+模板庫還提供了pair模板類，該類可以表示一個(gè)“鍵-值”對(duì)。pair對(duì)象包含兩個(gè)屬

13、性：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。ma

14、p對(duì)象與員工對(duì)象之間的關(guān)系及存儲(chǔ)結(jié)構(gòu)如圖5-1所示?！綜+代碼】#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;str

15、ing phoneNumber;string address;int main( )map <int, employee*> employeeMap;typedef pair <int, employee*> employeePair;for (int employIndex = 1001; employIndex <= 1003; employIndex+)char temp10 ;               

16、/臨時(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-&quo

17、t;+tmp,"address-"+tmp); /將員工編號(hào)和員工信息插入到employeeMap對(duì)象中int employeeNo = 0;cout << "請(qǐng)輸入員工編號(hào):"（4）   >> employeeNo;                        /從標(biāo)準(zhǔn)輸入獲得員工

18、編號(hào)map<int,employee*>:const_iterator it;it =    （5）  .find(employeeNo);                   /根據(jù)員工編號(hào)查找員工信息if (it = employeeMap.end() cout << "該員工編號(hào)不存在 ！" << endl;retu

19、rn -1;cout << "你所查詢的員工編號(hào)為：" << it->first << endl;cout << "該員工姓名：" << it->second->name << endl;cout << "該員工電話：" << it->second->phoneNumber << endl;cout << "該員工地址：" << it->second

20、->address << endl;return 0; Ublic temp insert cin employeeMap試題六（共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代碼

21、中使用了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所示?！綣ava 代碼】import java.util.*;class employeeemployee(String name,String phoneNumber, String address) = name; this.phoneNumber = phoneNumber;this.ad

22、dress = 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,