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

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

● __(1)__（共15分）
閱讀以下說明和流程圖，填補(bǔ)流程圖中的空缺（1）~（5），將解答填入答題紙的對應(yīng)欄內(nèi)。
【說明】
求連續(xù)函數(shù)f(x)的根（方程f(x)=0的解）的最簡單方法是二分法。為此，首先需要在若干點上檢查函數(shù)值的符號，如果發(fā)現(xiàn)f(a)與f(b)符號相反(a 取該區(qū)間的中點m，如果f(m)=0，則根就是m。如果f(a)與f(m)符號相反，則根一定在區(qū)間(a， m)中；如果f(m)與f(b)符號相反，則根一定在區(qū)間(m， b)中。因此，根的范圍縮小了一半。
依此類推，將區(qū)間一半一半地分下去，當(dāng)區(qū)間的長度很?。ㄟ_(dá)到根的精度要求，例如0.001）時，或者當(dāng)區(qū)間中點處的函數(shù)值幾乎接近于0（即絕對值小于預(yù)先規(guī)定的微小量，例如0.001）時，近似計算就可以結(jié)束了。
以下流程圖描述了用二分法近似計算區(qū)間（a， b）中f(x)的根的過程。

【流程圖】

● __(2)__ （共15分）
閱讀以下說明和C函數(shù)，將應(yīng)填入（n） 處的字句寫在答題紙的對應(yīng)欄內(nèi)。
【說明1】
函數(shù)Counter(int n， int w[])的功能是計算整數(shù)n的二進(jìn)制表示形式中1的個數(shù)，同時用數(shù)組w記錄該二進(jìn)制數(shù)中1所在位置的權(quán)。
例如，十進(jìn)制數(shù)22的二進(jìn)制表示為10110。對于該二進(jìn)制數(shù)，1的個數(shù)為3，在w[0]中存入2（即2¹）、w[1]中存入4（即2²）、w[2]中存入16（即2⁴）。

【C函數(shù)1】

int Counter(int n， int w[]）

｛ int i＝0， k＝1;

while（（1） ）｛

if (n％2) w[i++]＝k;

n＝n／2; （2） ;

｝

return I;

｝

【說明2】

函數(shù)Smove(int A[]， int n)的功能是將數(shù)組中所有的奇數(shù)都放到所有偶數(shù)之前。其過程為：設(shè)置數(shù)組元素下標(biāo)索引i（初值為0）和j（初值為n-1），從數(shù)組的兩端開始檢查元素的奇偶性。若A[i]、A[j]都是奇數(shù)，則從前往后找出一個偶數(shù)，再與A[j]進(jìn)行交換；若A[i]，A[j]都是偶數(shù)，則從后往前找出一個奇數(shù)，再與A[i]進(jìn)行交換；若A[i]是偶數(shù)而A[j]是奇數(shù)，則交換兩者，直到將所有的奇數(shù)都排在所有偶數(shù)之前為止。

【C函數(shù)2】

void Smove(int A[]，int n)

{ int temp， i=0， j=n-1;

if（n＜2）return;

while（i＜j）｛

if（A[i]%2==1&&A[j]%2==1）｛（3） ;｝

else if（A[i]%2==0&&A[j]%2==0）｛（4） ;｝

else{

if（（5） ）｛

temp＝A[i];A[i]＝A[j];A[j]＝temp;

}

i++，j--;

}

}

}

● __(3)__ （共15分）
閱讀以下說明、C函數(shù)和問題，將解答寫入答題紙的對應(yīng)欄內(nèi)。

【說明1】

函數(shù)test fl (int m，int n)對整數(shù)m、n進(jìn)行某種運(yùn)算后返回一個整數(shù)值。

【C函數(shù)1】

int test_fl (int m， int n)

{ int k;

k=m>n?m:n;

for(;(k%m!=0)||(k%n!=0);k++);

return k;

｝

【問題1】（5分）

（1）請寫出發(fā)生函數(shù)調(diào)用test_fl(9，6)時，函數(shù)的返回值；

（2）請說明函數(shù)test_fl的功能。

【說明2】

設(shè)在某C系統(tǒng)中為每個字符分配1個字節(jié)，為每個指針分配4個字節(jié)，sizeof(x)計算為x分配的字節(jié)數(shù)。

函數(shù)test_f2()用于測試并輸出該C系統(tǒng)為某些數(shù)據(jù)分配的字節(jié)數(shù)。

【C函數(shù)2】

void test_f2()

{ char str[]="NewWorld"; char *p＝str; char i=‘\0’;

void *ptr=malloc(50);

printf("%d\t"，sizeof(str)); printf("%d\n"，sizeof(p))；

printf("%d\t"，sizeof(i)); printf("%d\n”，sizeoqptr))，

}

【問題2】（4分）

請寫出函數(shù)test_f2()的運(yùn)行結(jié)果。

【說明3】

函數(shù)test_f3(char s[])的功能是：將給定字符串s中的所有空格字符刪除后形成的串保存在字符數(shù)組tstr中（串s的內(nèi)容不變），并返回結(jié)果串的首地址。

【C函數(shù)3】

char *test_f3 (const char s[])

｛ char tstr[50]＝{‘\0’}; unsigned int i，k=0;

for(i=0;i<strlen(s);i++)

if（s[i]!=‘ ’）tstr[k++]＝s[i];

return tstr;

｝

【問題3】（6分）

函數(shù)test_f3()對返回值的處理有缺陷，請指出該缺陷并說明修改方法。

● __(4)__ （共15分）
閱讀以下說明和C函數(shù)，將解答填入答題紙的對應(yīng)欄內(nèi)。
【說明】
函數(shù)del_substr(S，T)的功能是從頭至尾掃描字符串S，刪除其中與字符串T相同的所有子串，其處理過程為：首先從串S的第一個字符開始查找子串T，若找到，則將后面的字符向前移動將子串T覆蓋掉，然后繼續(xù)查找子串T，否則從串S的第二個字符開始查找，依此類推，重復(fù)該過程，直到串S的結(jié)尾為止。該函數(shù)中字符串的存儲類型SString定義如下：
typedef struct｛
char *ch; ／*串空間的首地址*／
int length; ／*串長*／
｝SString;

【C函數(shù)】

void del substr(SString*S， SString T)

｛

int i， j;

if（S->length＜1||T.length＜1||S->length＜T.length）

return;

i=0; ／* i為串S中字符的下標(biāo) *／

for（;;）｛

j=0; ／* j為串T中字符的下標(biāo) *／

while（i＜S->length&&j＜T.length）｛ ／* 在串S中查找與T相同的子串 *／

if（S->ch[i]==T.ch[j]）｛

i++; j++;

}

else｛

i=（1） ; j=0; ／* i值回退，為繼續(xù)查找T做準(zhǔn)備 *／

｝

｝

if（（2） ）｛ ／* 在S中找到與T相同的子串 *／

i=（3） ; ／* 計算S中子串T的起始下標(biāo) *／

for(k=i+T.length; k<S->length; k++) ／* 通過覆蓋子串T進(jìn)行刪除 *／

S->ch[（4） ]=S->ch[k];

S->length=（5） ; ／* 更新S的長度*／

｝

else break; ／* 串S中不存在子串T */

｝

｝

● __(5)__ （共15分）
閱讀以下說明和C++代碼，將應(yīng)填入（n） 處的字句寫在答題紙的對應(yīng)欄內(nèi)。
【說明】
已知類LinkedList表示列表類，該類具有四個方法：addElement__(6)__、lastElement__(7)__、numberOfElement__(8)__以及removeLastElement__(9)__。四個方法的含義分別為：
void addElement(Object)：在列表尾部添加一個對象；
Object lastElement__(10)__：返回列表尾部對象；
int numberOfElement__(11)__：返回列表中對象個數(shù)；
void removeLastElement__(12)__：刪除列表尾部的對象。
現(xiàn)需要借助LinkedList來實現(xiàn)一個Stack棧類，C++代碼1和C++代碼2分別采用繼承和組合的方式實現(xiàn)。
【C++代碼1】

class Stack :public LinkedList{

public:

void push(Object o)｛addElement(o);｝; //壓棧

Object peek()｛return （1） ;｝; //獲取棧頂元素

bool isEmpty()｛ //判斷棧是否為空

return numberOfElement()==0;

｝;

Object pop() { //彈棧

Object o＝lastElement();

（2） ;

return o；

｝;

｝;

【C++代碼2】

class Stack｛

private:

（3） ;

public:

void push(Object o)｛ //壓棧

list.addElement(o);

｝;

Object peek(){ //獲取棧頂元素

return list.（4） ;

｝;

bool isEmpty() { //判斷棧是否為空

return list.numberOfElement()==0;

｝;

Object pop()｛ //彈棧

Object o＝list.lastElement();

list.removeLastElement();

return o;

｝;

｝;

【問題】

若類LinkedList新增加了一個公有的方法removeElement(int index)，用于刪除列表中第index個元素，則在用繼承和組合兩種實現(xiàn)棧類Stack的方式中，哪種方式下Stack對象可訪問方法removeElement(int index)?（5） （

（5）A．繼承B．組合）

● __(6)__ （共15分）
閱讀以下說明和Java代碼，將應(yīng)填入（n） 處的字句寫在答題紙的對應(yīng)欄內(nèi)。
【說明】
已知類LinkedList表示列表類，該類具有四個方法：addElement__(7)__、lastElemen__(8)__、numberOfElement__(9)__以及removeLastElement__(10)__。四個方法的含義分別為：
void addElement(Object)：在列表尾部添加一個對象；
Object lastElement__(11)__：返回列表尾部對象；
int numberOfElement__(12)__：返回列表中對象個數(shù)；
void removeLastElement__(13)__：刪除列表尾部的對象。
現(xiàn)需要借助LinkedList來實現(xiàn)一個Stack棧類，Java代碼1和Java代碼2分別采用繼承和組合的方式實現(xiàn)。
【Java代碼1】

public class Stack extends LinkedList｛

public void push(Object o)｛ //壓棧

addElement(o);

｝

public Object peek()｛ //獲取棧頂元素

return （1） ;

｝

public boolean isEmpty(){ //判斷棧是否為空

return numberOfElement()=0;

}

public Object pop()｛ //彈棧

Object o＝lastElement();

（2） ;

return o;

｝

｝

【Java代碼2】

public class Stack｛

private（3） ;

public Stack()｛

list＝new LinkedList();

｝

public void push(Object o)｛

list.addElement(o);

}

public Object peek｛ //獲取棧頂元素

return list.（4） ;

｝

public boolean isEmpty()｛ //判斷棧是否為空

return list.numberOfElement()==0;

｝

public Object pop()｛ //彈棧

Object o＝list． lastElement();

list.removeLastElemento;

return o;

｝

｝

【問題】

若類LinkedList新增加了一個公有的方法removeElement(int index），用于刪除列表中第index個元素，則在用繼承和組合兩種實現(xiàn)棧類Stack的方式中，哪種方式下Stack對象可訪問方法removeElement(int index）？（5） （

（6）A．繼承B．組合）