试题四（共15分）

阅读以下说明和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。

试题六（共15分）

阅读以下说明、图和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(){

           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 drawAShape(Shape shape){

          shape.paint();

    }

    void erase A Shape(Shape shape){

         ∥删除形状，代码略

    }

    void drawShapes(){

         shapes*0+= new Circle("C”);

          shapes[l]= new Ellipse("E");

           for (int   i=O; i<2;++i) {

              drawAShap(shapes[i]);／／绘制形状 

      }

 }

void close(){

    for (int i=0;i<2; ++1) { []关闭图，删除所绘制图形

             (5)      ；

    }

 }

 public static void main(String[] args){

      Diagram diagram=   (6)    ；

      diagram.drawShapes();

diagram.close();

    }

}

  从下列2道试题（试题五至试题六）中任选 1道解答。如果解答的试题数超过1道，则题号小的1道解答有效。

试题五（共15分）

    阅读以下说明、图和C++代码，填补C++代码中的空缺(1)～(5)，将解答写在答题纸的对应栏内。

【说明】

    已知对某几何图形绘制工具进行类建模的结果如图5.1所示，其中Shape为抽象类(应至少包含一个纯虚拟( virtual)函数），表示通用图形，Box表示矩形，Ellipse表示椭圆，Circle表示圆（即特殊的椭圆），Line表示线条。

 下面的C++代码用于实现图5-1所给出的设计思路，将其空缺处填充完整并编译运行，输

出结果为：

    Ellipse

    Circle

    Ellipse

    C

    E

【C++代码】

#include

#include

using namespace std;

class Shape{

public:

     Shape(const string& name){

    m_name= name;

    }

~Shape(){}

             (1)      void paint() = 0;

          stringgetName()const {

            retumm name;

        }

 Private:

     string m_name;

};

 //Box和 Line类的定义与 Ellipse类似，其代码略

 classEllipse   (2)   {

 public:

       Ellipse(const string& name) : Shape(name){ cout<<"Ellipse"<

     Voidpaint() { cout<

  };

  classCircle   (3)  {

   public: 

        Circle(const string& name) : Ellipse(name){ cout<<"Circl"<

  };

  class Diagram {

public:

      void drawAShap(Shape* shape){ shape->paint(); }

      void drawShapes() {

          shapes[0] = new Circle("C");

          shapes[l] = new Ellipse("E");

          for (int i=O;i<2; ++1)     {

drawAShap(shapes[i]);

          }

        }

       void close (){ /*删除形状,代码略  */ }

 private:

       Shape* shapes[2];

 };

 int main( )

 {

   Diagram* diagram =     (4)   

diagram->drawShapes();

   diagram->close ();

      (5)   diagram;

}

试题四（共15分）

阅读以下说明和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。

试题二（共15分）

阅读以下说明和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

时返回结果出错的原因。

试题三（共15分）

阅读以下说明和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存在的缺点。  

试题一（共15分）

阅读以下说明和流程图，填补流程图中的空缺(1)～(5)，将解答填入答题纸的对应栏内。

【说明】

下面的流程图可在正文字符串T(1： L)中计算关键词字符串K(1： m)出现的次数（用 n表示）。其中，L为字符串 T的长度，m为字符串K的长度(m

“?”可以匹配任意一个字符。 在该流程图中，先从T中取出长度为m的子串存入A中，再将 A与 K进行逐个字符的比较（其中，K可以包含字符“？”）。注意：从正文字符串中取出的关键词字符串不允许交叉。

例如，“aaaaaa”中有3个关键词字符串“aa”。

【流程图】