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

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

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

【流程圖】

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

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

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

【C函數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函數和問題，將解答寫入答題紙的對應欄內。

【說明1】

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

【C函數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）請寫出發生函數調用test_fl(9，6)時，函數的返回值；

（2）請說明函數test_fl的功能。

【說明2】

設在某C系統中為每個字符分配1個字節，為每個指針分配4個字節，sizeof(x)計算為x分配的字節數。

函數test_f2()用于測試并輸出該C系統為某些數據分配的字節數。

【C函數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分）

請寫出函數test_f2()的運行結果。

【說明3】

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

【C函數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分）

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

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

【C函數】

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中字符的下標 *／

for（;;）｛

j=0; ／* j為串T中字符的下標 *／

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

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

i++; j++;

}

else｛

i=（1） ; j=0; ／* i值回退，為繼續查找T做準備 *／

｝

｝

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

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

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

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

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

｝

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

｝

｝

● __(5)__ （共15分）
閱讀以下說明和C++代碼，將應填入（n） 處的字句寫在答題紙的對應欄內。
【說明】
已知類LinkedList表示列表類，該類具有四個方法：addElement__(6)__、lastElement__(7)__、numberOfElement__(8)__以及removeLastElement__(9)__。四個方法的含義分別為：
void addElement(Object)：在列表尾部添加一個對象；
Object lastElement__(10)__：返回列表尾部對象；
int numberOfElement__(11)__：返回列表中對象個數；
void removeLastElement__(12)__：刪除列表尾部的對象。
現需要借助LinkedList來實現一個Stack棧類，C++代碼1和C++代碼2分別采用繼承和組合的方式實現。
【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個元素，則在用繼承和組合兩種實現棧類Stack的方式中，哪種方式下Stack對象可訪問方法removeElement(int index)?（5） （

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

● __(6)__ （共15分）
閱讀以下說明和Java代碼，將應填入（n） 處的字句寫在答題紙的對應欄內。
【說明】
已知類LinkedList表示列表類，該類具有四個方法：addElement__(7)__、lastElemen__(8)__、numberOfElement__(9)__以及removeLastElement__(10)__。四個方法的含義分別為：
void addElement(Object)：在列表尾部添加一個對象；
Object lastElement__(11)__：返回列表尾部對象；
int numberOfElement__(12)__：返回列表中對象個數；
void removeLastElement__(13)__：刪除列表尾部的對象。
現需要借助LinkedList來實現一個Stack棧類，Java代碼1和Java代碼2分別采用繼承和組合的方式實現。
【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個元素，則在用繼承和組合兩種實現棧類Stack的方式中，哪種方式下Stack對象可訪問方法removeElement(int index）？（5） （

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