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;

}

}