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

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

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

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

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

【說明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分)
請(qǐng)根據(jù)說明2，填充C函數(shù)2中的空缺(1)和(2)。
【問題3]（3分）
用567，1234，56781234，62354879643分別作為實(shí)參調(diào)用函數(shù)reverse，對(duì)應(yīng)的返回值分別為765，4321，43218765，1357400630。請(qǐng)說明以62354879643作為實(shí)參調(diào)用函數(shù)reverse時(shí)返回結(jié)果出錯(cuò)的原因。

（）

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

【說明1】

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

【問題1】（6分）

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

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

【說明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分)

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

【問題3]（3分）

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

● __(3)__

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

【說明】

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

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

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

【問題1】(12分)

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

【問題2】（3分）

請(qǐng)說明函數(shù)CompactArr vl存在的缺點(diǎn)。

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

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

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

下面的Java代碼用于實(shí)現(xiàn)圖6-1所給出的設(shè)計(jì)思路，將其空缺處填充完整并編譯運(yùn)行，輸出結(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;

}

}