201105程序员下午真题
第 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”。
【流程图】
答案与解析
- 试题难度：较难
- 知识点：流程图>流程图
- 试题答案：
(1) L-m+1 或等价表示
(2) i+m-1 或等价表示
(3) j+1 或等价表示
(4) n+1 或等价表示
(5)A(j)=K(j)或等价表示 - 试题解析：
首先取m长度的字符串与K进行比较。所以第2空应填i+m-1，然后将两个字符串进行比较，如果相等，将序号往下移一位，如果不等，i的值增1.在这里，要求序号不能大于m.
第 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，0乘以10再加上4得到4；
(2)由123除以10得到商12和余数3，4乘以10再加上3得到43;
(3)由12除以10得到商1和余数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)__；
}
retun result，
}
【问题2] (6分)
请根据说明2，填充C函数2中的空缺(1)和(2)。
【问题3]（3分）
用567，1234，56781234，62354879643分别作为实参调用函数reverse，对应的返回值分别为765，4321，43218765，1357400630。请说明以62354879643作为实参调用函数reverse时返回结果出错的原因。
答案与解析
- 试题难度：较难
- 知识点：C程序设计>C程序设计
- 试题答案：
【问题1】
【问题2】
(1)n！=0或n>0
(2) n/10
【问题3】
运算结果溢出（或超出范围，或其他含义相近的描述）。
”=”一般为赋值号，而非等号。序号length才是其末尾序号，而非length。
循环的要求是n>0，执行完后要使n变成n/10。
数据太大，计算机参生溢出。
第 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存在的缺点。
答案与解析
- 试题难度：较难
- 知识点：C程序设计>C程序设计
- 试题答案：
【问题1】
(1) sizeof(int)
(2)temp[k++] 或*(temp+k++)或等价表示
(3) i＜k 或等价表示
(4)a[k++] 或*（a+k++）或等价表示
【问题2】
可能由于动态内存申请操作失败而导致函数功能无法实现，时间和空间效率低。
- 试题解析：
申请数组a大小的空间，a为一整型数组，所以我们可以用求sizeof的方式来达到目的。复制完后将k的值增1，数组需要下移一位。将数组元素传回a中，使用for循环来达到目得，循环的条件是i<k。
遇到非0元素并将其前移后k才增1，所以形式为a[k++]而非a[++k]。
函数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。
【C 函数】
BOOL ifMatched (char expr[ ])
{
char *cptr; /* cptr 指向表达式中的字符*/
STACK S;
char e;
InitStack(&S} ; /*构造一个空栈*/
for(cptr = expr; *cptr!= '\0' （1） {
if ( *cptr== ' (' || *cptr ==' [' ， || *cptr ==' {' )
（2）;
else
if ( *cptr==')' || *cptr== ']' || *cptr=='}' ) {
if (IsEmpty (S) )
return Mismatched;
e =（3） ; /*取栈顶的左括号*/
if ( *cptr ==')' ，&& e!=' (' ) return Mismatched;
if ( *cptr ==']' && e!=' [' ) return Mismatched;
if ( *cptr ==')' && e!='{' )return Mismatched;
（4） ; /*梭顶的左括号出校*/
}
}
if (（5）) return Matched;
return Mismatched;
}
答案与解析
- 试题难度：较难
- 知识点：C程序设计>C程序设计
- 试题答案：
(1) cptr++或++cptr 或cptr +=1 或cptr = cptr+1
(2) Push(&S，*cptr)
(3) Top(S)
(4)Pop(&S)
(5) Is Empty(S) - 试题解析：
当没有遇到字符结束符\0时，指针下移一位继续扫描。遇到左括号时，将其压入栈中。取栈顶的左括号为Top(s)，左括号出栈为pop(&s)，最后判断，如果是空栈，则返回1，否则返回0
第 5 题
阅读以下说明、图和C++代码，填补C++代码中的空缺(1)～(5)，将解答写在答题纸的对应栏内。
【说明】
已知对某几何图形绘制工具进行类建模的结果如图5.1所示，其中Shape为抽象类(应至少包含一个纯虚拟( virtual)函数），表示通用图形，Box表示矩形，Ellipse表示椭圆，Circle表示圆（即特殊的椭圆），Line表示线条。
图6-1 类图
下面的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;
}
~Shape( ){}
(1) void paint( ) = 0;
stringgetName( )const {
return m_name;
}
private;
string m_name;
};
//Box和 Line类的定义与 Ellipse类似，其代码略
class Ellipse (2) {
public:
Ellipse(const string& name) : Shape(name){ cout<<"Ellipse" <<end1; }
void paint( ) { cout<<getName( )<<end1;}
};
class Circle (3) {
public:
Circle(const string& name) : Ellipse(name){ cout<<"Circl"<<end1;
};
class Diagram {
public:
void drawAShap(Shape* shape){ shape->paint( ); }
void drawShapes( ) {
shapes[0] = new Circle("C");
shapes[l] = new Ellipse("E");
for (int i=0;i<2; ++i) {
drawAShap(shapes[i]);
}
}
void close ( ){ /*删除形状，代码略 */ }
private:
Shape* shapes[2];
};
int main( )
{
Diagram* diagram = (4) ;
diagram->drawShapes( );
diagram->close ( );
(5) diagram;
}
答案与解析
- 试题难度：较难
- 知识点：C++程序设计>C++程序设计
- 试题答案：
（[answer]）
(1) virtual
(2)：public Shape
(3): public Ellipse
(4) new Diagram或new Diagram()
(5) delete - 试题解析：本题考查C++语言程序设计的能力，涉及类和抽象类、对象、函数和虚函数的定义和相关操作，以及继承关系。要求考生根据给出的案例和执行过程说明，认真阅读理清程序思路，然后完成题目。
先考查类图整体结构。本题中根据类图定义了类：Diagram 、Shape、Box 、Ellipse 、Line 和 Circ1e。其中Shape 为抽象类，表示通用图形，抽象类中应至少包含一个纯虚拟（virtual）函数。Box表示矩形，Ellipse表示椭圆，Line表示线条，三者都是Shape的子类，继承了Shape类，Circ1e 表示圆（即特殊的椭圆），继承了Ellipse。
抽象类 Shape的定义中，需要通过使用 virtual标识虚函数，void paint()= 0; 表示 paint()是纯虚函数，其定义前必须添加 virtual 进行表示。类 Ellipse为 Shape 的子类，Circ1e为 Ellipse的子类，需要在代码中体现出继承。另外，在子类的构造函数中，调用父类的构造函数，所以继承的权限为public。其语为：public 后加类名。
类Diagram中没有定义构造函数，编译器生成一个缺省的构造函数，调用是采用 new关键字加类名。使用完成之后，通过 delete 进行释放。
因此空（1）需要表现出 paint()函数为纯虚函数，即为virtual；空（2）和空（3）处添加继承父类，并且权限为public，即为:public Shape 和:public Ellipse；空（4）处补充通过使用编译器生成的缺省构造函数创建对象，即 new Diagram；空（5）处通过 delete释放 new 创建的对象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 paint( );
String getName( ){
return this.name;
}
final String name;
}；
//Box和Line类似下面Ellipse，其代码略
class Ellipse (3) {
public Ellipse(String name){
super(name);
System.out.println("Ellipse");
}
Void paint( ){ //绘制现状示意代码
System.out.println(getName( ));
}
}；
class Circle (4) {
public Circle(String name){
super(name);
System.out.println("Circle");
}
}；
class Diagram{
private Shape shapes[ ]= new Shape[2];
public void drawAShape(Shape shape) {
shape.paint( );
}
void eraseAShape(Shape shape) {
//删除形状，代码略
}
void drawShapes( ) {
shapes[0]= new Circle("C”);
shapes[1]= new Ellipse("E");
for (int i=0; i<2;++i) {
drawAShap (shapes[i]); //绘制形状
}
}
void close( ){
for (int i=0;i<2; ++i) { //关闭图，删除所绘制图形
(5) ；
}
}
public static void main(String[ ] args) {
Diagram diagram= (6) ；
diagram.drawShapes( );
diagram.close( );
}
}
答案与解析
- 试题难度：较难
- 知识点：Java程序设计>Java程序设计案例
- 试题答案：
(1) abstract或public abstract
(2) abstract或public abstract或protected abstract
(3) extends Shape
(4) extends Ellipse
(5) erase A Shape (shapes[i])
(6) new Diagram()
- 试题解析：本题考查Java语言程序设计的能力，涉及类和抽象类、对象、方法和抽象方法的定义和相关操作，以及继承关系。要求考生根据给出的案例和执行过程说明，认真阅读理清程序思路，然后完成题目。
先考查类图整体结构。本题中根据类图定义了类：Diagram、Shape、Box、Ellipse、Line和 Circle。其中Shape为抽象类，表示通用图形，抽象类中应至少包含一个抽象（abstract）方法。Box表示矩形，Ellipse表示椭圆，Line表示线条，三者都是 Shape的子类，继承了Shape类，Circle表示圆（）即特殊的椭圆，继承了Ellipse。
抽象类 Shape的定义中，需要通过使用 abstract标识抽象方法，方法void paint()；没有实现体，表示 paint()是抽象方法，其定义前必须添加 abstract进行表示。类 Ellipse为Shape的子类，Circle为 Ellipse的子类，需要在代码中体现出继承。另外，在子类的构造方法中，需调用父类的构造方法，而在父类中没有不带参数的构造方法，必须使用 super关键字显式地进行调用。在 Java中，继承的语法为 extends 后加类名。
类Diagram 中没有定义构造方法，编译器生成一个缺省的构造方法，调用时采用 new关键字加缺省构造器方法。
因此空（1）和（2）需要表现出 Shape 为抽象类，paint()方法为抽象方法，即为 abstract; 和（3）处添加继承父类 Shape ，e.p extends Shape；空（4）处补充继承父类 Ellipse，即 extends Ellipse；空（5）处删除图形，即 eraseAShape( shapes[i]) ，调用空（6）通过使用编译器生成的缺省构造方法创建对象，即 new Diagram()。