1、2011年上半年软件水平考试（初级）程序员下午（应用技术）试题真题试卷及答案与解析 1 阅读以下说明和流程图，填补流程图中的空缺 (1) (5)，将解答填入对应栏内。 说明 下面的流程图可在正文字符串 T(1:L)中计算关键词字符串 K(1:m)出现的次数 (用 n表示 )。其中， L为字符串 T的长度， m为字符串 K的长度 (m L)。为便于模糊查找，关键词中的字符 “?”可以匹配任意一个字符。 在该流程图中，先从 T中取出长度为 m的子串存入 A中，再将 A与 K进行逐个字符的比较 (其中， K可以包含字符 “?”)。注意：从正文字符 串中取出的关键词字符串不允许交叉。例如，“aaaaa
2、a”中有 3个关键词字符串 “aa”。 流程图 1 阅读以下说明和 C函数，回答问题 1至问题 3，将解答写在对应栏内。 说明 1 函数 substring(const char str， int index， int length)的功能是求出字符串 str中指定序号 index开始且长度为 length的子串，并返回所取出的子串。以字符串 “China today”为例，其第一个字符 “C”的序号为 1(而其在字符数组 str中的下标为 0)，从序号 5开始且长度为 3的子 串为 “at”。 C函数1说明 2 在 C函数 2中， reverse(unsigned int n)的功能是求出并
3、返回 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=r
4、esult *10+n%10; n= (2) ; return result; 2 请根据说明 2，填充 C函数 2中的空缺 (1)和 (2)。 3 用 567， 1234， 56781234， 62354879643分别作为实参调用函数 reverse，对应的返回值分别为 765， 4321， 43218765， 1357400630。请说明以 62354879643作为实参 调用函数 reverse时返回结果出错的原因。 3 阅读以下说明和 C函数，回答问题 1和问题 2，将解答填入对应栏内。 说明 对于具有 n个元素的整型数组 a，需要进行的处理是删除 a中所有值为 0的数组元素，并将
5、a中所有非 0元素按照原顺序连续地存储在数组空间的前端。 下面分别用函数 compactArr_v1和 compactArr_v2来实现上述处理要求，函数的返回值为非零元素的个数。 函数 CompactArr(int a， int n)的处理思路是：首先申请一个与数组 a的大小相同的动态 数组空间，然后顺序扫描数组 a的每一个元素，将遇到的非 0元素依次复制到动态数组空间中，最后再将动态数组中的元素传回数组 a中。 函数 CompactArr_v2(int a， int n)的处理思路是：利用下标 i(初值为 0)顺序扫描数组 a的每一个元素，下标 k(初值为 0)表示数组 a中连续存储的非
6、0元素的下标。扫描时，每遇到一个数组元素， i就增 1，而遇到非 0元素并将其前移后 k才增 1。 C函数 1 int CompactArr vl(int a， int n) int i, k; int *temp=(int*)malloc(n* (1) ); if(!temp) return-1; for(i=0, k=0; i n; i+) if(ai!=0) (2) =ai; for(i=0; (3) ; i+) ai=tempi; return k; C函数 2 intCompactArr v2(inta， intn) int i, k; for(i=0, k=0; i n; i+)
7、if(ai!=0) (4) =ai; return k; 4 请根据说明中函数 CompactArr_v1的处理思路填补空缺 (1) (3)，根据CompactArr_v2的处理思路填补空缺 (4)。 5 请说明函数 CompactArr_v1存在的缺点。 6 阅读以下说明和 C函数，填补 C函数中的空缺 (1) (5)，将解答写在对应栏内。 说明 假设一个算术表达式中可以包含 以下三种括号： “(”和 “)”、 “”和 “”及 “”和 “”，并且这三种括号可以按照任意的次序嵌套使用。 下面仪考虑表达式中括号的匹配关系，其他问题暂时忽略。例如，表达式 a-(b-5)*c中的括号是完全匹配的，而
8、表达式 a-(b-5)*c中的括号不是完全匹配的，因为 “(”与 “”不能匹配，而且多了一个 “)”，即缺少一个与 “)”相匹配的 “(”。 函数 if Matched(char expr)的功能是用栈来判断表达式中的括号是否匹配，表达式以字符串的形式存储在字符数组 expr中。若 表达式中的括号完全匹配，则该函数的返回值为 Matched，否则返回值为 Mismatched。 该函数的处理思路如下： (1)设置一个初始为空的栈，从左至右扫描表达式。 (2)若遇上左括号，则令其入栈；若遇上右括号，则需要与栈顶的左括号进行匹配。 (3)若所遇到的右括号能与栈顶的左括号配对，则令栈顶的左括号出栈，
9、然后继续匹配过程；否则返回 Mismatched，结束判断过程。 (4)若表达式扫描结束，同时栈变为空，则说明表达式中的括号能完全匹配，返回Matched。 函数 if Matched中用到了两种用户白定义数据类型 BOOL和 STACK，其中，BOOL类型的定义如下： typedef enum Mismatched, Matched BOOL; STACK(即栈类型 )的定义省略，栈的基本操作的函数原型说明如下： void InitStack(STACK*S)：初始化一个空栈。 void Push(STACK*S. char e)：将一个字符压栈，栈中元素数目增 1。 void Pop(ST
10、ACK*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=) | *
11、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; 7 阅读下列说明、图和 C+代码，填补 C+代码中的空缺 (1) (5)，将解答写在对应栏内。 说明 已知对某几何图
12、形绘制工具进行类建模的结果如图 5-1所示，其中Shape为抽象类 (应至少包含一个纯虚拟 (virreal)函数 )，表示通用图形， 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)
13、m_name=name; Shape() (1) void paint()=0; string getName()const return m_name; private: string m_name; ; /Box和 Line类的定义与 Ellipse类似，其代码略 class Ellipse (2) public: Ellipse(const String name): Shape(name)cout “E1lipse“ end1; void paint() cout getName() end1; ; class Circle (3) public: Circle(const strin
14、g name): Ellipse(name)(cout “Circle“ end1; ; class Diagram public: void drawAShap(Shape* shape) shape- paint(); void drawShapeS() shapes0=new Circle(“C“); shapes1=new Ellipse(“E“); for (int i=0; i 2; +1) drawAShap(Shapesi); void close()( /*N除形状，代码略 $/) private: Shape* shapes2; ; int main() Diagram*
15、diagram= (4) ; diagram- drawShapes(); diagram-close(); (5) diagram; 8 阅读以下说明和 Java代码，填补 Java代码中的空缺 (1) (6)， 将解答写在对应栏内。 说明 已知对某几何图形绘制工具进行类建模的结果如图 6-1所示，其中Shape为抽象 (abstract)类，表示通用图形， Box(矩形 )、 Ellipse(椭圆 )和 Line(线条 )继承 (extends)了 Shape类，其中， Circle表示圆 (即特殊的椭圆 )。下面的 Java代码用于实现图 6-1所给出的设计思路，将其空缺处填充完整并编译
16、运行，输出结果为： 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 pa
17、int() /绘制现状示意代码 System.out.println(getName(); ; class Circle (4) public Circle(String name) super(name); System.out.println(“Circle“); ; class Diagram private Shape shapes=new Shape2; public void drawAShape(Shape shape) shape.paint(); void eraseAShape(Shape shape) /删除形状，代码略 void drawShapes() shapes0
18、=new Circle(“C“); shapes1=new Ellipse(“E“); for(int i=0; i 2; +i) drawAShap(shapesi); /绘制形状 void close() for(int i=0; i 2; +i) /关闭图，删除所绘制图形 (5) ; public static void main(String args) Diagram diagram= (6) ; diagram.drawShapes(); diagram.close(); 2011年上半年软件水平考试（初级）程序员下午（应用技术）试题真题试卷答案与解析 1 【正确答案】 L-m+1
19、或等价表示 i+m-1或等价表示 i+1或等价表示 n+1或等价表示 A(j)=K(j)或等价表示 【试题解析】 根据题意，正文字符串中的各个字符依次存放在 T(1)， T(2)， ，T(L)中，关键词字符串中的各个字符依次存放在 K(1)， K(2)， ， K(m)中。显然i是字符数组 T的动态下标指针。为了与关键词字符串进行比较，题中需要每次从数组 T中连续取出 m个元素放在数组 A中。第 1次将 T(1:m)存入 A(1:m)，第 2次将 T(2:m+1)存入 A(1:m)， ，第 i次就应将 T(i:m+i-1)存入 A(1:m)，最后一次应将 T(L-m+1:L)存入 A(1:m)。
20、因此，流程图的 (2)中应填 m+i-1。由于 m+i-1必须小于或等于 L。当 m+i-1 L时，即当 i L-m+1时，就不应该再取子串了。因此流程图的 (1)处应填 L-m+1。 流程图右下方一片描述了字符数组 A(i)， A(i+1)， ， A(i+m-1)与字符数组K(1)， K(2)， ， K(m)的比较过程。题中用 j表示数组 K的动态下标指针， j=1，2， ， m。显然，数组 A的动态下标指针为 i+j-1(j=1， 2， ， m)。两个字符数组都从左到逐个字符地进行比较，如果发现有不一致的字 符，就结束比较，将 i增1后准备继续从数组 T中取新的子串放在 A中。如果一直到比
21、较结束，发现两个数组中对应的各个字符都是一致的，那么，就找到了一处关键词。此时，找到关键词的计数器 n应增 1(n+1n) 。因此，流程图的 (4)处应填 n+1。 字符数组 A与 K的比较过程关键是逐个字符 A(j)与 K(j)的比较。由于允许模糊查找，即 K(j)中的字符 “?”可以与任何字符匹配。因此，比较操可以写成判断“A(j)=K(j) or K(j)=“?“”是否为真。只要 K(j)=“?“，比较结果就一定为真。因此，流程图的 (5)处应 填 A(j)=K(j)。如果比较结果为真，则还需要执行 j+1j ，准备继续往下比较。因此流程图的 (3)处应填 i+1。 2 【正确答案】 (
22、1)n!=0或 n 0 (2)n/10 3 【正确答案】 运算结果溢出 (或超出范围，或其他含义相近的描述 )。 4 【正确答案】 sizeof(int) tenlpk+ 或 *(temp+k+) 或等价表示 i k 或等价表示 ak+ 或 *(a+k+) 或等价表示 【试题解析】 本题考查 C程序设计和分析能力。 本 问题考查 C程序结构、数组及运算的应用知识。 根据题目中对函数 CompactArr_v1的处理思路描述，空 (1)处应填入 sizeof(int)。 以下代码将数组 a中的非 0元素复制到动态数组 temp中。 for(i=0, k=0; i n; i+) if(ai!=0)
23、 (2) =ai; 显然， k应作为 temp的下标索引变量使用，因此空 (2)处应填入 tempk+，当该循环语句结束后， k的值也就是 a中非 0元素的个数。据此，空 (3)处应填入 ik。 根据题目中对函数 CompactArr_v2的处理思路描述，空 (4)处应填入 ak+。 5 【正确答案】 可能由于动态内存申请操作失败而导致函数功能无法实现，没有释放动态数组空间 (存在内存泄漏问题 )，时问和空间效率低。 【试题解析】 本问题考查程序分析基本能力。 解决同一个问题会有多种不同的方法，各种方法都有其特点。在本问题中，相比于函数 CompactArr v2， CompactArr_v1
24、的处理思路容易理解，由于数组 a的数据需要复制给 temp，然后再复制回来，因此需要更多的空间支 持，处理速度时间也更长。另外，其代码执行时也可能由于申请内存空间的要求得不到满足，从而导致函数的功能不能实现，虽然发生这种情况的概率很低，但也有可能发生。此外，函数结束前也没有释放所申请的内存块。 6 【正确答案】 cptr+ 或 +cptr 或 cptr+=1 或 cptr=cptr+1 Push( S， *cptr) Top(S) Pop( S) IsEmpty(S) 【试题解析】 本题考查 C程序设计基本能力。 由于已经将表达式以字符串的形式存入字符数组 expr，因此指针 cptr就用于指
25、示表达式中的每个字符。显然，以下 for语句用于扫描 expr中的每个字符： for(cptr=expr; *cptr!=0; (1) ) 因此，空 (1)处应填入 cptr+或其等价形式。 空 (2)处进行处理的前提是遇到了左括号，因此，根据题目中对函数 if Matched的处理思路描述，这时应进行压栈操作，即应填入 Push(&S， *cptr)，这里要注意函数调用时实参的形式。 由于弹栈操作不能返回栈顶元素，因此根据注释，空 (3)处需要读取栈项元素，即应填入 Top(S)，空 (4)处填入 Pop( S)。 由于表达式扫描结束且同时栈变为空，才说明表达式中的括号能完全匹配，因此， f
26、or语句的条件表达式 *cptr!=0不成立时表达式结束，此时控制流可以到达空 (5)所在语句，在此需要判断栈的状态来决定括号是否完全匹配，即空 (5)处应填入 IsEmpty(S)。 7 【正确答案】 virtual public Shape public Ellipse new Diagram delete 【试题解析】 本题考查 C+语言程序设计的能力，涉及类和抽象类、对象、函 数和虚函数的定义和相关操作，以及继承关系。要求考生根据给出的案例和执行过程说明，认真阅读理清程序思路，然后完成题目。 先考查类图整体结构。本题中根据类图定义了类： Diagram、 Shape、 Box、Elli
27、pse、 Line和 Circle。其中 Shape为抽象类，表示通用图形，抽象类中应至少包含一个纯虚拟 (virtual)函数。 Box表示矩形， Ellipse表示椭圆， Line表示线条，三者都是 Shape的子类，继承了 Shape类， Circle表示圆 (即特殊的椭圆 )，继承了Ellipse。 抽象类 Shape的定义中，需要通过使用 virtual标识虚函数， void paint()=0；表示 paint()是纯虚函数，其定义前必须添加 virtual进行表示。类 Ellipse为 Shape的子类， Circle为 Ellipse的子类，需要在代码中体现出继承。另外，在子类
28、的构造函数中，调用父类的构造函数，所以继承的权限为 public。其语法为： public后加类名。 类 Diagram中没有定义构造函数，编译器生成一个缺省的构造函数，调用是采用 new关键字加类名。使用完成之后，通过 delete进行释放。 因此空 (1)需要表现出 paint()函数为纯虚函数，即为 virtual；空 (2)和空 (3)处添加继承父类，并且权限为 public，即为： public Shape和 :public Ellipse；空 (4)处补充通过使用编译器生成的缺省构造函数创建对象，即 ilew Diagram；空 (5)处通过delete释放 new创建的对象 di
29、agram。 8 【正确答案】 abstract或 public abstract abstract或 public abstract或 protected abstract extends Shape extends Ellipse eraseAShape(shapesi) new Diagram() 【试题解析】 本题考查 Java语言程序设计的能力，涉及类和抽象类、对象、方法和抽象方法的定义和相关操作，以及继承关系。要求考生根据给出的案例和执行过程说明，认真阅读理清程序思路，然后完成题目。 先考查类图整体结构。本题中根据类图定义了类： Diagram、 Shape、 Box、Ellips
30、e、 Line和 Circle。其中 Shape为抽象类，表示通用图形，抽象类中应至少包含一个抽 象 (abstract)方法。 Box表示矩形， Ellipse表示椭圆， Line表示线条，三者都是 Shape的子类，继承了 Shape类， Circle表示圆 (即特殊的椭圆 )，继承了Ellipse。 抽象类 Shape的定义中，需要通过使用 abstract标识抽象方法，方法 void paint()；没有实现体，表示 paint()是抽象方法，其定义前必须添加 abstract进行表示。类 Ellipse为 Shape的子类， Circle为 Ellipse的子类，需要在代码中体现出继
31、承。另外，在子类的构造方法中，需调用父类 的构造方法，而在父类中没有不带参数的构造方法，必须使用 super关键字显式地进行调用。在 Java中，继承的语法为 extends后加类名。 类 Diagram中没有定义构造方法，编译器生成一个缺省的构造方法，调用时采用 new关键字加缺省构造器方法。 因此空 (1)和 (2)需要表现出 Shape为抽象类， paint()方法为抽象方法，即为abstract；和 (3)处添加继承父类 Shape，即 extends Shape；空 (4)处补充继承父类Ellipse，即 extends Ellipse；空 (5)处删除图 形，即 eraseAShape(shapesi)，调用空(6)通过使用编译器生成的缺省构造方法创建对象，即 new Diagram()。
