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

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

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

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

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

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

（）

閱讀以下說明和C函數(shù)，回答問題l至問題3，將解答寫在答題紙的對應(yīng)欄內(nèi)。

【說明1】

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

【問題1】（6分）

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

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

【說明2】

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

的反序數(shù)是4321，其求解過程如下：

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

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

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

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

【C函數(shù)2】

unsigned int reverse(unsigned int n)

{

unsigned int result=0；

while( (1) ){

result= result *10+ n%10，

n=(2)__；

}

retum result，

}

【問題2] (6分)

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

【問題3]（3分）

用567，1234，56781234，62354879643分別作為實參調(diào)用函數(shù)reverse，對應(yīng)的返回值分別為765，4321，43218765，1357400630。請說明以62354879643作為實參調(diào)用函數(shù)reverse時返回結(jié)果出錯的原因。

● __(3)__

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

【說明】

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

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

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

【問題1】(12分)

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

【問題2】（3分）

請說明函數(shù)CompactArr vl存在的缺點。

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

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

下面的C++代碼用于實現(xiàn)圖5-1所給出的設(shè)計思路，將其空缺處填充完整并編譯運行，輸出結(jié)果為：
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)，將解答寫在答題紙的對應(yīng)欄內(nèi)。
【說明】
已知對某幾何圖形繪制工具進行類建模的結(jié)果如圖6.1所示，其中Shape為抽象(abstract)類，表示通用圖形，Box（矩形）、Ellipse（橢圓）和Line（線條）繼承(extends)了Shape類，其中，Circle表示圓（即特殊的橢圓）。

下面的Java代碼用于實現(xiàn)圖6-1所給出的設(shè)計思路，將其空缺處填充完整并編譯運行，輸出結(jié)果為：
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{∥繪制現(xiàn)狀示意代碼

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) { []關(guān)閉圖，刪除所繪制圖形

(5) ；

}

}

public static void main(String[] args){

Diagram diagram= (6) ；

diagram.drawShapes0;

diagram.close0;

}

}