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

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

● __(1)__
閱讀以下說明和流程圖，填補流程圖中的空缺(1)～(5)，將解答填入答題紙的對應欄內。
【說明】
下面的流程圖可在正文字符串T(1：L)中計算關鍵詞字符串K(1：m)出現的次數（用n表示）。其中，L為字符串T的長度，m為字符串K的長度(m<L)。為便于模糊查找，關鍵詞中的字符“?”可以匹配任意一個字符。
在該流程圖中，先從T中取出長度為m的子串存入A中，再將A與K進行逐個字符的比較（其中，K可以包含字符“？”）。注意：從正文字符串中取出的關鍵詞字符串不允許交叉。例如，“aaaaaa”中有3個關鍵詞字符串“aa”。【流程圖】

● __(2)__
閱讀以下說明和C函數，回答問題l至問題3，將解答寫在答題紙的對應欄內。
【說明1】
函數substring(const char str[]，int index，int length)的功能是求出字符串str中指定序號index開始且長度為length的子串，并返回所取出的子串。以字符串“China today”為例，其第一個字符“C”的序號為1(而其在字符數組str中的下標為0)，從序號5開始且長度為3的子串為“at”。

【問題1】（6分）
函數substring中有兩處錯誤，請指出這些錯誤所在代碼的行號，并在不增加和刪除
代碼行的情況下進行修改，寫出修改正確后的完整代碼行（有注釋時，注釋可省略）。

【說明2】
在C函數2中，reverse(unsigned intn的功能是求出并返回n的反序數。例如，1234
的反序數是4321，其求解過程如下：
(1)由1234除以10得到商123和余數4，O乘以10再加上4得到4；
(2)由123除以10得到商12和余數3，4乘以10再加上3得到43;
(3)由12除以10得到商l和余數2，43乘以10再加上2得到432;
(4)由1除以10得到商0和余數1，432乘以10再加上1得到4321。
【C函數2】
unsigned int reverse(unsigned int n)
{
unsigned int result=0；
while( (1) ){
result= result *10+ n%10，
n=(2)__；
}
retum result，
}
【問題2] (6分)
請根據說明2，填充C函數2中的空缺(1)和(2)。
【問題3]（3分）
用567，1234，56781234，62354879643分別作為實參調用函數reverse，對應的返回值分別為765，4321，43218765，1357400630。請說明以62354879643作為實參調用函數reverse時返回結果出錯的原因。

（）

閱讀以下說明和C函數，回答問題l至問題3，將解答寫在答題紙的對應欄內。

【說明1】

函數substring(const char str[]，int index，int length)的功能是求出字符串str中指定序號index開始且長度為length的子串，并返回所取出的子串。以字符串“China today”為例，其第一個字符“C”的序號為1(而其在字符數組str中的下標為0)，從序號5開始且長度為3的子串為“at”。

【問題1】（6分）

函數substring中有兩處錯誤，請指出這些錯誤所在代碼的行號，并在不增加和刪除

代碼行的情況下進行修改，寫出修改正確后的完整代碼行（有注釋時，注釋可省略）。

【說明2】

在C函數2中，reverse(unsigned intn的功能是求出并返回n的反序數。例如，1234

的反序數是4321，其求解過程如下：

(1)由1234除以10得到商123和余數4，O乘以10再加上4得到4；

(2)由123除以10得到商12和余數3，4乘以10再加上3得到43;

(3)由12除以10得到商l和余數2，43乘以10再加上2得到432;

(4)由1除以10得到商0和余數1，432乘以10再加上1得到4321。

【C函數2】

unsigned int reverse(unsigned int n)

{

unsigned int result=0；

while( (1) ){

result= result *10+ n%10，

n=(2)__；

}

retum result，

}

【問題2] (6分)

請根據說明2，填充C函數2中的空缺(1)和(2)。

【問題3]（3分）

用567，1234，56781234，62354879643分別作為實參調用函數reverse，對應的返回值分別為765，4321，43218765，1357400630。請說明以62354879643作為實參調用函數reverse時返回結果出錯的原因。

● __(3)__

閱讀以下說明和C函數，回答問題l和問題2，將解答填入答題紙的對應欄內。

【說明】

對于具有n個元素的整型數組a，需要進行的處理是刪除a中所有的值為0的數組元素，并將a中所有的非O元素按照原順序連續地存儲在數組空間的前端。下面分別用函數CompactArr_v1和CompactArr v2來實現上述處理要求，函數的返回值為非零元素的個數。

函數CompactArr_vl(int a[]，int n)的處理思路是：先申請一個與數組a的大小相同的動態數組空間，然后順序掃描數組a的每一個元素，將遇到的非O元素依次復制到動態數組空間中，最后再將動態數組中的元素傳回數組a中。

函數CompactArr_v2(int a[]，int n)的處理思路是：利用下標i（初值為0）順序掃描數組a的每一個元素，下標k（初值為0）表示數組a中連續存儲的非0元素的下標。掃描時，每遇到一個數組元素，i就增1，而遇到非0元素并將其前移后k才增1。

【問題1】(12分)

請根據說明中函數CompactArr_v1的處理思路填補空缺(1)～(3)，根據CompactArr_v2的處理思路填補空缺(4)。

【問題2】（3分）

請說明函數CompactArr vl存在的缺點。

● __(4)__
閱讀以下說明和C函數，填補C函數中的空缺(1)～(5)，將解答寫在答題紙的對應欄內。
【說明】
假設一個算術表達式中可以包含以下三種括號：“（”和“）”、"[”和“]”、“{”和“}”，并且這三種括號可以按照任意的次序嵌套使用。
下面僅考慮表達式中括號的匹配關系，其他問題暫時忽略。例如，表達式“[a．(b．5)】*c【{}】”中的括號是完全匹配的，而表達式“【a-(b-5]))*c”中的括號不是完全匹配的，因為“（”與“】”不能匹配，而且多了一個“）”，即缺少一個與“）”相匹配的“(”。
函數ifmatched (char expr[])的功能是用棧來判斷表達式中的括號是否匹配，表達式以字符串的形式存儲在字符數組expr中。若表達式中的括號完全匹配，則該函數的返回值為Matched，否則返回值為Mismatched。
該函數的處理思路如下：
(1)設置一個初始為空的棧，從左至右掃描表達式。
(2)若遇上左括號，則令其入棧；若遇上右括號，則需要與棧頂的左括號進行匹配。
(3)若所遇到的右括號能與棧頂的左括號配對，則令棧頂的左括號出棧，然后繼續匹配過程；否則返回Mismatched，結束判斷過程。
(4)若表達式掃描結束，同時棧變為空，則說明表達式中的括號能完全匹配，返回Matched。
函數ifMatched中用到了兩種用戶自定義數據類型BOOL和STACK，其中，BOOL類型的定義如下：
typedef enum {Mismatched， Matched}BOOL;STACK（即棧類型）的定義省略，棧的基本操作的函數原型說明如下：
void InitStack(STACK *S):初始化一個空棧。
void Push(STACK *S，char e):將一個字符壓棧，棧中元素數目增1。
void Pop(STACK *S)：棧頂元素出棧，棧中元素數目減1。
char Top(STACK S)：返回非空棧S的棧頂元素值，棧中元素數目不變。
int IsEmpty(STACK S)：若S是空棧，則返回1，否則返回0。

● __(5)__
閱讀以下說明、圖和C++代碼，填補C++代碼中的空缺(1)～(5)，將解答寫在答題紙的對應欄內。
【說明】
已知對某幾何圖形繪制工具進行類建模的結果如圖5.1所示，其中Shape為抽象類(應至少包含一個純虛擬( virtual)函數），表示通用圖形，Box表示矩形，Ellipse表示橢圓，Circle表示圓（即特殊的橢圓），Line表示線條。

下面的C++代碼用于實現圖5-1所給出的設計思路，將其空缺處填充完整并編譯運行，輸出結果為：
Ellipse
Circle
Ellipse
C
E

【C++代碼】

#include <string>

#include <iostream>

using namespace std;

class Shape{

public:

Shape(const string& name){

m_name= name;

}

~Shape0{}

(1) void paintO = 0;

stringgetNameOconst {

retumm name;

}

Private;

string m_name;

};

//Box和 Line類的定義與 Ellipse類似，其代碼略

classEllipse (2) {

public:

Ellipse(const string& name) : Shape(name){ cout<<"Ellipse" <<endl; }

voidpaintO { cout<<getNameO<<endl;}

};

classCircle (3) {

public:

Circle(const string& name) : Ellipse(name){ cout<<"Circl"<<endl; }

};

class Diagram {

public:

void drawAShap(Shape* shape){ shape->paint0; }

void drawShapes0 {

shapes[0] = new Circle("C");

shapes[l] = new Ellipse("E");

for (int i=O;i<2; ++1) {

drawAShap(shapes[i]);

}

}

void close O{ /*刪除形狀，代碼略 */ }

private:

Shape* shapes[2];

};

int main( )

{

Diagram* diagram = (4)

diagram->drawShapes0;

diagram->close O;

(5) diagram;

}

● __(6)__
閱讀以下說明、圖和Java代碼，填補Java代碼中的空缺(1)～(6)，將解答寫在答題紙的對應欄內。
【說明】
已知對某幾何圖形繪制工具進行類建模的結果如圖6.1所示，其中Shape為抽象(abstract)類，表示通用圖形，Box（矩形）、Ellipse（橢圓）和Line（線條）繼承(extends)了Shape類，其中，Circle表示圓（即特殊的橢圓）。

下面的Java代碼用于實現圖6-1所給出的設計思路，將其空缺處填充完整并編譯運行，輸出結果為：
Ellipse
Circle
Ellipse
C
E【Java代碼】

(1) class Shape{

public Shape(String name){

this.name= name;

}

(2) void paint0;

String getName(){

retum this.name;

}

final String name;

}；

//Box和Line類似下面Ellipse，其代碼略

class Ellipse (3) {

public Ellipse(String name){

super(name);

System.out.println("Ellipse");

}

Void paintO{∥繪制現狀示意代碼

System.out.println(getName0);

}

}；

class Circle(4) {

public Circle(String name){

super(name);

System.out.println("Circle");

}

}；

class Diagram{

private Shape shapes[]= new Shape[2];

public void draw A Shape(Shape shape){

shape.paint0;

}

void erase A Shape(Shape shape){

∥刪除形狀，代碼略

}

void drawShapes0{

shapes[0]= new Circle("C”);

shapes[l]= new Ellipse("E");

for (int i=O; i<2;++i) {

draw A Shap (shapes[i]);／／繪制形狀

}

}

void close0{

for (int i=O;i<2; ++1) { []關閉圖，刪除所繪制圖形

(5) ；

}

}

public static void main(String[] args){

Diagram diagram= (6) ；

diagram.drawShapes0;

diagram.close0;

}

}