温故而知新，下笔如有神最近两上半年程序员考试专项考题训练及答案-下午卷试题一下面的流程图可在正文字符串T(1:L)中计算关键词字符串K(l:m)出现的次数（用n表示)。其中，L为字符串T的长度，m为字符串K的长度(mL时，即当iL-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中。 如果一直到比较结束，发现两个数组中对应的各个字符都是一致的，那么，就找到了一处关键词。此时，找到关键词的计数器n应增l(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)处应填 j+1。试题二函数 substring(const char str, int index, int length)的功能是求出字符串 str 中指定序号index开始且长度为length的子串，并返回所取出的子串。以字符串“China today” 为例，其第一个字符“C”的序号为1 (而其在字符数组str中的下标为0)，从序号5开始且长度为3的子串为“at”。 【问题1】函数substring中有两处错误，请指出这些错误所在代码的行号，并在不增加和删除代码行的情况下进行修改，写出修改正确后的完整代码行（有注释时，注释可省略)。本问题考查字符串运算及常见编程错误的处理。求子串运算substring的原型如下：根据题目说明，参数index为子串的位置序号（从1开始)，length为子串的长度。 显然，在函数substring中，首先应判断参数的合理性，即index应不小于1，length应不小于0，同时，从index开始可以得到长度为length的子串，即index+length-1应不大于 最后一个字符的序号。因此，第6行的代码是正确的。第7行申请动态内存块的语句是正确的。第9行的代码判断内存申请是否成功，其中，判断指针tptr的表达式tptr = 0有错误，即误用了 “=”与“=”，导致无论内存申请操作是否成功，在此都将tptr赋值为空指针，造成内存泄漏。第10、11行代码用于从字符串str中复制子串，代码是正确的。第12行的代码设置 字符串的结束标志，为错误代码。由于所获得字符串的长度为length，其在动态数组tptr 的下标从0开始，因此，下标length-1为最后一个字符的下标，tptrlength-l = 0会导致 丢失最后一个字符，因此该语句中tptr的下标应为length。【问题2】请根据说明2,填充C函数2中的空缺（1)和（2)。 (1) n!=0 或 n0(2) n/10 本问题考查整数运算。从题中给出的运算过程可知，在所运算的整数不为0时，运算过程会继续，因此空(1)处应填入“11!=0”。除以10后要丢掉个位数的处理则由空（2)处进行，即填入“n/10”。【问题3】请说明以62354879643作为实参调用函数reverse时返回结果出错的原因。运算结果溢出（或超出范围，或其他含义相近的描述)。本问题考查溢出问题。由于程序语言提供的基本数据类型都有其表示范围的限制，因此在运算过程中需要 注意是否发生溢出。通过分析，上面的运算过程并没有问题，而且前三个数据的处理结果都是正确的，因此最后一个数据出错的原因是其超出整型的表示范围造成的。试题三对于具有n个元素的整型数组a，需要进行的处理是删除a中所有值为0的数组元素，并将a中所有非0元素按照原顺序连续地存储在数组空间的前端。下面分别用函数CompactArr_vl和CompactArr_v2来实现上述处理要求，函数的返回值为非零元素的个数。函数CompactArr_vl(int a, intn)的处理思路是：首先申请一个与数组a的大小相同的动态数组空间，然后顺序扫描数组.a的每一个元素，将遇到的非0元素依次复制到动态数组空间中，最后再将动态数组中的元素传回数组a中。函数CompaetArr_v2(int a, intn)的处理思路是：利用下标i (初值为0)顺序扫描数组a的每一个元素，下标k (初值为0)表示数组a中连续存储的非0元素的下标。扫描时，每遇到一个数组元素，i就增1，而遇到非0元素并将其前移后k才增1。【问题1】请根据说明中函数CompactArr_vl的处理思路填补空缺(1)(3)，根据CompactArr_ v2的处理思路填补空缺（4)。 (1) sizeof(int)(2) tempk+ 或 *(temp+k+)或等价表示(3) ik 或等价表示(4) ak+ 或*(a+k+)或等价本问题考査C程序结构、数组及运算的应用知识。根据题目中对函数CompactArr_vl的处理思路描述，空（1)处应填入sizeof(int)。 以下代码将数组a中的非0元素复制到动态数组temp中。显然，k应作为temp的下标索引变量使用，因此空（2)处应填入tempk+，当该 循环语句结束后，k的值也就是a中非0元素的个数。据此，空（3)处应填入ik。【问题2】请说明函数CompactArr_vl存在的缺点。可能由于动态内存申请操作失败而导致函数功能无法实现，没有释放动态数组空间 (存在内存泄漏问题)，时间和空间效率低。本问题考查程序分析基本能力。解决同一个问题会有多种不同的方法，务种方法都有其特点。在本问题中，相比于函数CompactArr_v2, CompactArr vl的处理思路容易理解，由于数组a的数据需要复制 给temp,然后再复制回来，因此需要更多的空间支持，处理速度时间也更长。另外，其 代码执行时也可能由于申请内存空间的要求得不到满足，从而导致函数的功能不能实现， 虽然发生这种情况的概率很低，但也有可能发生。此外，数结束前也没有释放所申请 的内存块。试题四假设一个算术表达式中可以包含以下三种括号：“(”和“)”、“”和“”及和 “”，并且这三种括号可以按照任意的次序嵌套使用。下面仅考虑表达式中括号的匹配关系，其他问题暂时忽略。例如，表达式 a-(b-5)*c中的括号是完全匹配的，而表达式a-(b-5)*c中的括号不是完全匹配的， 因为“(”与“”不能匹配，而且多了一个“)”，即缺少一个与“)”相匹配的“(”。函数ifMatched (char expr)的功能是用栈来判断表达式中的括号是否匹配，表达式 以字符串的形式存储在字符数组expr中。若表达式中的括号完全匹配，则该函数的返回 值为Matched,否则返回值为Mismatched。该函数的处理思路如下：(1) 设置一个初始为空的栈，从左至右扫描表达式。(2) 若遇上左括号，则令其入栈；若遇上右括号，则需要与栈顶的左括号进行匹配。(3) 若所遇到的右括号能与栈顶的左括号配对，则令栈顶的左括号出栈 然后继续匹配过程；否则返回Mismatched，结束判断过程。(4) 若表达式扫描结束，同时栈变为空，则说明表达式中的括号能完全匹配，返回 Matched o函数ifMatched中用到了两种用户自定义数据类型BOOL和STACK,其中，BOOL 类型的定义如下：填补C函数中的空缺（1)（5)(1) cptrH- 或 +cptr 或 cptr +=1 或 cptr = cptr+-l(2) Push(&S, *cptr)(3) Top(S)(4) Pop(&S)(5) IsEmpty(S)本题考查c程序设计基本能力。由于已经将表达式以字符串的形式存入字符数组expr,因此指针cptr就用于指示表 达式中的每个字符。显然，以下for语句用于扫描expr中的每个字符：for (cptr = expr; *cptr!= 10; (1)因此，空（1)处应填入cpti+或其等价形式。空（2)处进行处理的前提是遇到了左括号，因此，根据题目中对函数ifMatched的 处理思路描述，这时应进行压栈操作，即应填入Push(&S，*cptr),这里要注意函数调用 时实参的形式。由于弹栈操作不能返回栈顶元素，因此根据注释，空（3)处需要读取栈顶元素， 即应填入Top(S)，空（4)处填入Pop(&S)。由于表达式扫描结束且同时栈变为空，才说明表达式中的括号能完全匹配，因此， for语句的条件表达式*cptr!=W不成立时表达式结束，此时控制流可以到达空（5)所在 语句，在此需要判断栈的状态来决定括号是否完全匹配，即空（5)处应填入IsEmpty(S)。 试题五已知对某几何图形绘制工具进行类建模的结果如图5-1所示，其中Shape为抽象类 (应至少包含一个纯虚拟（virtual)函数)，表示通用图形，Box表示矩形，Ellipse表示椭圆，Circle表示圆（即特殊的椭圆），Line表示线条。下面的C+代码用于实现图5-1所给出的设计思路，将其空缺处填充完整并编译运行，输出结果为：填补C+代码中的空缺（1)（5)(1) virtual(2) : public Shape(3) : public Ellipse(4) new Diagram(5) delete本题考查C+语言程序设计的能力，涉及类和抽象类、对象、函数和虚函数的定义和相关操作，以及继承关系。要求考生根据给出的案例和执行过程说明，认真阅读理清程序思路，然后完成题目。先考查类图整体结构。本题中根据类图定义了类