试题二（共 15分）

阅读以下说明和C函数，将应填入 （n） 处的字句写在答题纸的对应栏内。

【说明 1】

函数Counter(int n, int w[])的功能是计算整数n的二进制表示形式中1的个数，同时用数组w记录该二进制数中1所在位置的权。

例如，十进制数22的二进制表示为10110。对于该二进制数，1的个数为3，在w[0]中存入2（即 ）、w[1]中存入4（即 ）、w[2]中存入16（即 ）。

1

2 2

2 4

2

【C函数 1】

int Counter(int n, int w[])

{ int i = 0, k = 1;  

     while (  （1）   ) {

        if (n % 2) w[i++] = k;

       n = n / 2;     （2）  ;

    }

return i;

}

【说明 2】

函数 Smove(int A[], int n)的功能是将数组中所有的奇数都放到所有偶数之前。其过程为：设置数组元素下标索引i（初值为0）和j（初值为n-1），从数组的两端开始检查元素的奇偶性。若 A[i]、A[j]都是奇数，则从前往后找出一个偶数，再与 A[j]进行交换；若 A[i]、A[j]都是偶数，则从后往前找出一个奇数，再与A[i]进行交换；若 A[i]是偶数而A[j]是奇数，则交换两者，直到将所有的奇数都排在所有偶数之前为止。

【C函数 2】

void Smove(int A[], int n)

{   int temp, i = 0, j = n-1;

     if ( n< 2 ) return;

     while ( i< j ) {

           if ( A[i] % 2 == 1 && A[j] % 2 == 1 )   {  （3）  ; } 

     else if ( A[i] % 2 == 0 && A[j] % 2 == 0 )   {  （4）  ; } 

  else {

    if (  （5）   ) {

                 temp = A[i]; A[i] = A[j]; A[j] = temp;

            }

          i++, j--;

        }

  }

}

试题六（共 15分）

阅读以下说明和Java代码，将应填入 （n） 处的字句写在答题纸的对应栏内。

【说明】

 已知类 LinkedList 表示列表类，该类具有四个方法：addElement()、lastElement()、

numberOfElement()以及removeLastElement()。四个方法的含义分别为：

 void addElement(Object): 在列表尾部添加一个对象；

 Object lastElement(): 返回列表尾部对象；

int numberOfElement(): 返回列表中对象个数；

void removeLastElement(): 删除列表尾部的对象。

   现需要借助LinkedList来实现一个Stack栈类， Java代码1和Java代码2分别采用继承

和组合的方式实现。

【Java代码1】

public class Stack extends LinkedList{

 public void push(Object o){ //压栈

 addElement(o);

 }

 public Object peek(){     //获取栈顶元素

 return  （1）  ;

 }

 public boolean isEmpty(){ //判断栈是否为空

   return numberOfElement() == 0;

 }

 public Object pop(){ //弹栈

 Object o = lastElement();

    （2）  ;

 return o;

 }

}

【Java代码2】

public class Stack {

 private  （3）  ;

 public Stack(){

 list = new LinkedList();

 }

 public void push(Object o){

 list.addElement(o);

 }

 public Object peek(){//获取栈顶元素

 return list. （4）  ;

 }

 public boolean isEmpty(){//判断栈是否为空

 return list.numberOfElement() == 0;

 }

 public Object pop(){ //弹栈

 Object o = list.lastElement();

 list.removeLastElement();

 return o;

 }

}

【问题】

若类LinkedList新增加了一个公有的方法removeElement(int index)，用于删除列表中第index个元素，则在用继承和组合两种实现栈类Stack的方式中，哪种方式下Stack对象可访问方法removeElement(int index)？ （5） （A. 继承 B. 组合）

试题五（共 15分）

阅读以下说明和C++代码，将应填入 （n） 处的字句写在答题纸的对应栏内。

【说明】

 已知类 LinkedList 表示列表类，该类具有四个方法：addElement()、lastElement()、

numberOfElement()以及removeLastElement()。四个方法的含义分别为：

 void addElement(Object): 在列表尾部添加一个对象；

 Object lastElement(): 返回列表尾部对象；

int numberOfElement(): 返回列表中对象个数；

void removeLastElement(): 删除列表尾部的对象。

现需要借助LinkedList来实现一个Stack栈类，C++代码1和C++代码2分别采用继承和组合的方式实现。

【C++代码 1】

class Stack :public LinkedList{

public:

 void push(Object o){ addElement(o); }; //压栈

 Object peek(){ return  （1）  ; }; //获取栈顶元素

 bool isEmpty(){  //判断栈是否为空

   return numberOfElement() == 0;

 };

 Object pop(){  //弹栈

 Object o = lastElement();

    （2）  ;

  return o;

 };

};

【C++代码 2】

class Stack {

private:

   （3）  ;

public:

 void push(Object o){ //压栈

 list.addElement(o);

 };

 Object peek(){  //获取栈顶元素

 return list. （4）  ;

 };

 bool isEmpty(){ //判断栈是否为空

 return list.numberOfElement() == 0;

 };

 Object pop(){//弹栈

 Object o = list.lastElement();

 list.removeLastElement();

 return o;

 };

};

【问题】

若类LinkedList新增加了一个公有的方法removeElement(int index)，用于删除列表中第index个元素，则在用继承和组合两种实现栈类Stack的方式中，哪种方式下Stack对象可访问方法removeElement(int index)？ （5） （A. 继承 B. 组合）

试题四（共 15分）

阅读以下说明和C函数，将解答填入答题纸的对应栏内。

【说明】

函数del_substr(S,T)的功能是从头至尾扫描字符串 S， 删除其中与字符串T相同的所有子串，其处理过程为：首先从串 S 的第一个字符开始查找子串 T，若找到，则将后面的字符向前移动将子串T覆盖掉，然后继续查找子串T，否则从串S的第二个字符开始查找，依此类推，重复该过程，直到串S的结尾为止。该函数中字符串的存储类型 SString

定义如下：

typedef struct {

char *ch;        /*串空间的首地址*/

int length;      /*串长*/

}SString;

【C函数】

void del_substr(SString *S, SString   T)

{

  int i, j;

     if ( S->length< 1 || T.length< 1 || S->length< T.length )  

return;

  i = 0;                        /* i为串S中字符的下标 */

  for ( ; ; ) {

     j = 0;                    /* j为串T中字符的下标 */ 

           while ( i< S->length && j< T.length ) {   /* 在串S中查找与T相同的子串 */

 if ( S->ch[i]==T.ch[j] )   {

     i++; j++;

                }

            else {

i =  （1）  ; j = 0;   /* i值回退，为继续查找T做准备 */

}

     }

     if (  （2）   ) {         /* 在S中找到与T相同的子串 */ 

         i =  （3）  ;         /* 计算S中子串T的起始下标 */

for(k = i+T.length; klength; k++) /* 通过覆盖子串T进行删除 */

S->ch[ （4）  ] = S->ch[k];

         S->length =  （5）  ;  /* 更新S的长度 */

     }

     else break;             /* 串S中不存在子串T*/

  }  

}

试题三（共 15分）

阅读以下说明、C函数和问题，将解答写入答题纸的对应栏内。

【说明 1】

函数test_f1(int m, int n)对整数 m、n进行某种运算后返回一个整数值。

【C函数 1】

int test_f1(int m, int n)

{ int k;

k = m >n ? m : n;

for(;(k%m!=0) || (k%n!=0);k++);

return k;

}

【问题 1】（5分）

（1）请写出发生函数调用test_f1(9,6)时，函数的返回值；

（2）请说明函数test_f1的功能。

【说明 2】

设在某 C 系统中为每个字符分配 1 个字节，为每个指针分配 4 个字节，sizeof(x)计

算为x分配的字节数。

函数test_f2()用于测试并输出该C系统为某些数据分配的字节数。

【C函数 2】

void test_f2( )

{ char str[] = "NewWorld";          char *p = str;            char i = '\0';       

        void *ptr  = malloc(50);

printf("%d\t", sizeof(str));   printf("%d\n", sizeof(p));  

printf("%d\t", sizeof(i));  printf("%d\n ", sizeof(ptr));

}

【问题 2】（4分）

请写出函数test_f2()的运行结果。

【说明 3】

函数 test_f3(char s[])的功能是：将给定字符串 s 中的所有空格字符删除后形成的串保存在字符数组tstr中（串s的内容不变），并返回结果串的首地址。

【C函数 3】

char *test_f3 (const char s[])

{   char tstr[50]={'\0'};  unsigned int i, k = 0;

    for(i=0; i

       if (s[i] != ' ') tstr[k++] = s[i];

    return tstr;

}

【问题 3】（6分）

函数test_f3()对返回值的处理有缺陷，请指出该缺陷并说明修改方法。

试题二（共 15分）

阅读以下说明和C函数，将应填入 （n） 处的字句写在答题纸的对应栏内。

【说明 1】

函数Counter(int n, int w[])的功能是计算整数n的二进制表示形式中1的个数，同时用数组w记录该二进制数中1所在位置的权。

例如，十进制数22的二进制表示为10110。对于该二进制数，1的个数为3，在w[0]中存入2（即 ）、w[1]中存入4（即 ）、w[2]中存入16（即 ）。

1

2 2

2 4

2

【C函数 1】

int Counter(int n, int w[])

{ int i = 0, k = 1;  

     while (  （1）   ) {

        if (n % 2) w[i++] = k;

       n = n / 2;     （2）  ;

    }

return i;

}

【说明 2】

函数 Smove(int A[], int n)的功能是将数组中所有的奇数都放到所有偶数之前。其过程为：设置数组元素下标索引i（初值为0）和j（初值为n-1），从数组的两端开始检查元素的奇偶性。若 A[i]、A[j]都是奇数，则从前往后找出一个偶数，再与 A[j]进行交换；若 A[i]、A[j]都是偶数，则从后往前找出一个奇数，再与A[i]进行交换；若 A[i]是偶数而A[j]是奇数，则交换两者，直到将所有的奇数都排在所有偶数之前为止。

【C函数 2】

void Smove(int A[], int n)

{   int temp, i = 0, j = n-1;

     if ( n< 2 ) return;

     while ( i< j ) {

           if ( A[i] % 2 == 1 && A[j] % 2 == 1 )   {  （3）  ; } 

     else if ( A[i] % 2 == 0 && A[j] % 2 == 0 )   {  （4）  ; } 

  else {

    if (  （5）   ) {

                 temp = A[i]; A[i] = A[j]; A[j] = temp;

            }

          i++, j--;

        }

  }

}

试题一（共 15分）

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

【说明】

求连续函数 f(x)的根（方程 f(x)=0 的解）的最简单方法是二分法。为此，首先需要在若干点上检查函数值的符号，如果发现 f(a)与f(b)符号相反（a取该区间的中点 m，如果 f(m)=0，则根就是 m。如果 f(a)与 f(m)符号相反，则根一定在区间(a，m)中；如果 f(m)与 f(b)符号相反，则根一定在区间(m，b)中。因此，根的范围缩小了一半。 依此类推，将区间一半一半地分下去，当区间的长度很小（达到根的精度要求，例如0.001）时，或者当区间中点处的函数值几乎接近于0（即绝对值小于预先规定的微小量，例如0.001）时，近似计算就可以结束了。

   以下流程图描述了用二分法近似计算区间（a，b）中f(x)的根的过程。