2009年下半年《程序员》下午试题(标准答案＋解析版)

如果您发现本试卷没有包含本套题的全部小题，请尝试在页面顶部本站内搜索框搜索相关题目，一般都能找到。

试题六（共 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)的根的过程。
点击查看答案