201505程序员下午真题

第 1 题

阅读以下说明和流程图，填补流程图中的空缺，将解答填入答题纸的对应栏内。
【说明】
下面流程图的功能是：在给定的两个字符串中查找最长的公共子串，输出该公共子串的长度 L 及其在各字符串中的起始位置（L=0时不存在公共字串）。例如，字符串"The light is not bright tonight ” 与“ Tonight the light is not bright ”的最长公共子串为 "The light is not bright”，长度为22，起始位置分别为2和10。
设A[1:M]表示由M个字符A[1]，A[2],…，A[M]依次组成的字符串；B[1:N]表示由N个字符B[1], B[2],…，B[N]依次组成的字符串，M≥N≥1。
本流程图采用的算法是：从最大可能的公共子串长度值开始逐步递减，在A、B字符串中查找是否存在长度为L的公共子串，即在A、B字符串中分别顺序取出长度为L的子串后，调用过程判断两个长度为L的指定字符串是否完全相同（该过程的流程略）。

【流程图】

答案与解析

• 试题难度：较难
• 知识点：流程图>流程图
• 试题答案：（1）N 或 min(M，N)      
  （2）M-L+1
  （3）N-L+1   
  （4）L-1
  （5）L，I， J
  
• 试题解析：

  本题考查对算法流程图的理解和绘制能力。这是程序员必须具有的技能。
  本题的算法可用来检查某论文是否有大段抄袭了另一论文。"the light is not bright tonight" 是著名的英语绕口令，它与 "Tonight the light is not bright" 大同小异。
  由于字符串 A 和 B 的长度分别为 M 和 N ，而且M≥N≥1，所以它们的公共子串长度L 必然小于或等于 N。题中采用的算法是，从最大可能的公共子串长度值L 开始逐步递减，在 A、B 字符串中查找是否存在长度为 L 的公共子串。因此，初始时，应将 min (M，N) 送L，或直接将 N 送 L。 （1） 处应填写 N 或 min（M，N），或其他等价形式。
  对每个可能的 L 值，为查看 A、B 串中是否存在长度为 L 的公共子串，显然需要执行双重循环。A 串中，长度为 L 的子串起始下标可以从 1 开始直到 M-L+1 （可以用实例来检查其正确性）；B 串中，长度为 L 的子串起始下标可以从 1 开始直到 N-L+1。因此双重循环的始值和终值就可以这样确定，即 （2）处应填 M-L+1 ，或等价形式；（3）处 应填 N-L+1 或等价形式（注意循环的终值应是最右端子串的下标起始值）。
  A 串中从下标 1开始长度为 L 的子串可以描述为 A[I:I+L-1]； B 串中从下标J开始 长度为 L 的子串可以描述为 A[J：J+L-1]。因此，双重循环体内，需要比较这两个子串（题中采用调用专门的函数过程或子程序来实现）。
  如果这两个子串比较的结果相同，那么就已经发现了 A、B 串中最大长度为 L 的公共子串，此时，应该输出公共子串的长度值 L、在A 串中的起始下标 I、在B 串中的起始下标 J。因此，（5） 处应填L，I， J （可不计顺序）。
  如果这两个子串比较的结果不匹配，那么就需要继续执行循环。如果直到循环结束仍然没有发现匹配子串时，就需要将 L 减少 1 （（4）处填L-1或其等价形式）。只要 L 非 0，则还可以继续对新的L 值执行双重循环。如果直到 L=0，仍没有发现子串匹配， 则表示 A、B 两串没有公共子串。
  

第 2 题

阅读以下说明和 C   函数，填补函数代码中的空缺，将解答填入答题纸的对应栏内。
【说明 1】
函数 f(double eps) 的功能是:利用公式计算并返回 π 的近似值。

【C 函数 1】
double f(double eps)
{
     double   n  =  1.0，s  =  1.0，term  =  1.0  ，pi  =  0.0  ;
     while   (  fabs(term)  >=  eps  ) {
            pi  =  pi  +  term；
            n =  (1)   ;   s =   (2)    ;
            term = s /  n ；
     }
     return    pi4;
}
【说明 2】
函数fun(char str)的功能是:自左至右顺序取出非空字符串 str中的数字字符，形成一个十进制整数(最多 8 位)。例如，若 str中的字符串为 "iyt?67kp f3g8d5.j4ia2e3p12"， 则函数返回值为 67385423。
【C 函数 2】
long fun(char  str)
{
     int  i =  0;
     long num  =  0;
     char  p  =  str;
 
     while   (   i<8  &&      （3）        )   {
          if  (   p  >=  '0' &&   p  <=  '9' )    {
               num =       （4）      +*p-‘0';
               ++i;
          }
               （5）    ；
     }
     return  num;
}

答案与解析

• 试题难度：较难
• 知识点：C程序设计>C程序设计
• 试题答案：(1)n+2
  (2)-s 或-1s
  (3) p!= ' \ 0'或等价形式
  (4) num*10 或等价形式
  (5) p++或等价形式
  
• 试题解析：本题考查 C 语言程序设计基本技能。考生需认真阅读题目中的说明，从而确定代码的运算逻辑，在阅读代码时，还需注意各变量的作用。
  函数f(double eps)  的功能是计算 π 的近似值。观察题中给出的计算公式，可知在循环中n每次递增2，因此空(1)处应填入"n+2"。由于公式中的各项是正负交替的，因此结合表达式 "term = s / n"可知变量 s 就是起此作用的。空 (2) 处应填入" -s"或"-1s"。
  对于函数 fun(char str)，从字符序列中取出数字并组合为一个整数时，对于每个数字，只需将之前获取的部分乘以10再加上该数字的值即可。
  以 67385423 为例。
  67385423 = (((((((0+6)10+7)10+3) 10+8)10+5)10+4)10+2)10+3
  函数中的变量 i是用来计算位数的， num 用来计算所获得的整数值。显然，最多读取字符序列中的前 8 个数字，或者到达字符序列的末尾(p!= ' \ 0')时，计算也需结束。因此，空(3)处应填入“ (p!= ' \ 0')”。
  根据 num 的作用，空 (4) 处应填入 "num10"。
  根据指针 p 的作用，空 (5) 处的代码应使得 p 指向下一个字符，因此应填入 "p++"。
  

第 3 题

阅读以下说明和 C 代码，填补代码中的空缺，将解答填入答题纸的对应栏内。
【说明】
下面的程序代码根据某单位职工的月工资数据文件（名称为 Salary.dat，文本文件） ，通过调用函数 GetIncomeTax计算出每位职工每月需缴纳的个人所得税额并以文件（名称为IncomeTax.dat ，文本文件）方式保存。
例如，有 4 个职工工资数据的 Salary.dat 内容如下，其中第一列为工号（整数），第2 列为月工资（实数）。

针对工资薪金收入的个人所得税计算公式为：
个人所得税额=应纳税所得额×税率－速算扣除数
其中，应纳税所得额=月工资－三险一金－起征点
税率和速算扣除数分别与不同的应纳税所得额对应，如表 3-1 所示。

设三险一金为月工资的  19%，起征点为3500元。
 例如，某人月工资为 5800元，按规定 19%缴纳三险一金，那么：
其应纳税所得额 X=5800- 5800x19%－3500=1198 元，对应税率和速算扣除数分别
为 3%和 0 元，因此，其个人所得税额为 1198X3%－0=35.94 元。

（1） double GetIncomeTax(double salary"或 double GetlncomeTax(double)
（2） !fin 或 fin==NULL 或 fin==0
（3） !fout 或fout==NULL 或fout==0
（4） &id，&salary
（5） GetIncomeTax(salary)
（6） salary *(l-RATE)或等价形式
注： RATE 可替换为 0.19

本题考查 C 语言程序设计基本技能。考生需认真阅读题目中的说明，以便理解问题并确定代码的运算逻辑，在阅读代码时，还需注意各变量的作用。
根据注释，空（1）处应填入 "double GetIncomeTax(double salary)" 或"double GetIncomeTax(double)"，对函数GetIncomeTax进行声明。
空（2）、（3）处所在的代码是判断文件打开操作是否成功，因此应分别填入"!fin"、 "!fout"。
根据说明可知，变量 id 和 salary分别表示工号和月工资数。
空（4）处所在语句为从文件中读取数据的操作，从 fscanf 的格式控制串可知读取的两个数是整数和双精度浮点数，则输入表列的两个变量分别为接收整数值的变量 id 和接收整数值的变量 salary ，因此空（4）应填入"&id，&salary"
空（5）处所在代码向fout 关联的文件写入计算出的所得税额，显然需调用函数GetlncomeTax 来计算，因此应填入" GetIncomeTax(salary)" 。
空 （6）处的代码计算应纳税所得额，根据说明中给出的计算公式及三险一金的计算方法：
应纳税所得额=月工资－三险一金－起征点
空 （6） 处应填入" salary *(1-RATE) "。

第 4 题

阅读以下说明和 C 函数，填补代码中的空缺，将解答填入答题纸的对应栏内。
【说明】
函数 Combine(LinkList La，LinkList Lb)的功能是：将元素呈递减排列的两个含头结点单链表合并为元素值呈递增（或非递减）方式排列的单链表，并返回合并所得单链表的头指针。例如，元素递减排列的单链表 La 和 Lb 如图 4-1 所示，合并所得的单链表如图 4-2 所示。 

图 4-1  合并前的两个链表示意图

设链表结点类型定义如下：
 
typedef  struct Node{
               int data;
               struct Node  next;
}Node ,LinkList;
 
【C 函数】
LinkList  Combine(LinkList   La ，LinkList   Lb)
{    //La 和 Lb 为含头结点且元素呈递减排列的单链表的头指针
     //函数返回值是将 La 和 Lb 合并所得单链表的头指针
     //且合并所得链表的元素值呈递增（或非递减)方式排列
 
    （1）      Lc ,tp ,pa ,pb;;  //Lc 为结果链表的头指针 ，其他为临时指针
 
     if  (!La)  return NULL;
     pa  =  La->next;                  //pa 指向 La 链表的第一个元素结点
 
     if  (!Lb)  return NULL;
     pb  =  Lb->next;                               //pb 指向 Lb 链表的第一个元素结点
 
     Lc  =  La;                                          //取 La  链表的头结点为合并所得链表的头结点
     Lc->next  =  NULL;
 
     while (    （2）    ){ //pa 和 pb 所指结点均存在(即两个链表都没有到达表尾)
          //令tp指向 pa 和 pb 所指结点中的较大者
          if (pa->data > pb->data) {
          tp = pa;       pa = pa->next;
     }
     else{
           tp = pb;     pb = pb->next;
      }
        （3）    =  Lc->next;       //tp 所指结点插入 Lc 链表的头结点之后
      Lc->next =  （4）     ;
  }
  tp =  (pa)? pa : pb;   //设置 tp 为剩余结点所形成链表的头指针
 
  //将剩余的结点合并入结果链表中， pa 作为临时指针使用
  while (tp) {
     pa = tp->next;
     tp->next = Lc->next;
     Lc->next = tp;
             （5）    ;
   }
  
return Lc;
}

答案与解析

• 试题难度：一般
• 知识点：C程序设计>C程序设计
• 试题答案：

  （1）LinkList
  （2）pa&&pb
  （3）tp->next
  （4）tp
  （5）tp=pa
  

• 试题解析：

  本题考查数据结构应用及 C 语言实现。链表运算是 C 程序设计题中常见的考点，需熟练掌握。考生需认真阅读题目中的说明，以便理解问题并确定代码的运算逻辑，在阅读代码时，还需注意各变量的作用。
  根据注释，空（1）所在的代码定义指向链表中结点的指针变量，结合链表结点类 型的定义，应填入"LinkList"。
  由于 pa 指向La链表的元素结点、pb 指向 Lb 链表的元素结点，空 （2）所在的while语句中，是将 pa 指向结点的数据与 pb 所指向结点的数据进行比较，因此空 （2）处应填 入 "pa &&pb"，以便运算“pa->data > pb->data”中的 pa 和 pb 为非空指针 。
  从空（3）所在语句的注释可知，需将 tp 所指结点插入 Lc 链表的头结点之后，空（3）处应填入"tp->next"，空（4）处应填入 “tp”如下图所示。
  

  
  空 (5) 所在的 while 语句处理还有剩余结点的链表， pa 是保存指针的临时变量，循环中的下面 4 条语句执行后的链表状态如下图所示。
  
  空（5）处应填入 "tp= pa"，以继续上述的重复处理过程。

第 5 题

阅读下列说明和 C++代码，填补代码中的空缺，将解答填入答题纸的对应栏内。
【说明】
设计 RGB 方式表示颜色的调色板，进行绘图，其类图如图 5-1 所示。该程序的 C++代码附后。

图5-1  类图

【C++代码】

include <iostream>

include <stdlib.h>

include <ctime>

using namespace  std;
class MyColor{
private:
     int red; int green;  int blue;
public:
     MyColor() {red =  0;  green  =  0;  blue  =  0;   }
     ～MyColor() { }
     MyColor(int   red ，int  green ，int  blue)    {
     this->red = red;  this->green  = green;  this->blue = blue;}
//其他方法略
     void  print()   {
         cout<<"Red:  " << red <<  "\tGreen: " << green << "\tBlue " << blue
         <<  endl;
     }
};
class  Palette  {
private:
     int number; MyColor palette;
public:
     Palette() {   number   =  256;   palette  =   (MyColor)malloc
     (sizeof(MyColor) *number);   }
   ～Palette () {
         for  (int i = 0;   i <  number;  i++) { delete palette[i];  }
                  （1）     ;
     }
     Palette(MyColor pale ，int  number)   {
             （2）        = number;
         palette = (MyColor*)malloc(sizeof(MyColor)number) ;
         memcpy(palette ，pale ，sizeof(pale)number);
     }
//其他方法略
    void  print ()    {
         for  (int i =  0;   i <  number;   i++) {
             cout <<  i <<  "  : " ;
             palette[i]->print();
         }
     }
};
class Drawing{
     public:
           （3）         int COLORNUMBER = 16;
     public:
         ～Drawing ()  {  }
         void  draw()   (
             Palette palette;
             int red ，green ，blue;
             MyColor   color[COLORNUMBER];
             srand((unsigned)time(O));
             for (int i = 0; i < COLORNUMBER;  i++)  {
                  red=rand ()% 256; green =  rand() % 256; blue = rand ()% 256;
                  color [i]  =      （4）    (red ，green ，blue);
             }
             palette = new Palette(color ，COLORNUMBER);
             palette->print();
             for  (int i =  0; i < COLORNUMBER;  i++)
                  delete color[i];
         }
     };
     int main   () {
         Drawing  * d  =   （5）   ;
         d->draw();
         delete  d;
}

答案与解析

• 试题难度：较难
• 知识点：C++程序设计>C++程序设计
• 试题答案：

  （1）free(palette)
  （2）this->number
  （3）static const
  （4）new MyColor
  （5）new Drawing()
  

• 试题解析：

  本题考查 C++程序设计的能力，涉及类、对象、方法定义和相关操作。要求考生根据给出的案例和代码说明，认真阅读并理清程序思路，然后完成题目。
  先考查题目说明。本题目中涉及到颜色、调色板、绘图等类以及初始化和调色相关等操作。根据说明进行设计。
  类图中给出三个类 Drawing 、Palette 和 MyColor 及其之间的关系。Drawing 与 Palette、 MyColor 之间具有关联关系， Palette 与 MyColor 之间是聚合关系。
  MyColor为以 RGB 方式表示颜色，由属性 red、green 和 blue 表示，每个MyColor
  对象即为一个 RGB 颜色。 MyColor 具有两个构造器，缺省构造器将 RGB 颜色均初始化为 0；带参数的构造方法将当前对象的 RGB 值设置为调用构造方法时消息中所传递的参数值。Print()用来输出当前对象的 RGB 值供测试使用。
  Palette类用于表示调色板，其调色板颜色数量，用 int 型 number 表示，其 MyColor对象指针数组，用指向指针的指针 MyColor** palette 表示。 Palette的缺省构造方法中，将 number 设置为 256 色，并将 palette 指向动态申请存储 256 色 MyColor 对象指针的空间。另一个构造方法 Palette(MyColor** pale，int number) 中参数有指向 MyColor 对象指针数组的指针 pale 以及颜色数量 number。该构造方法设置当前调色板对象的颜色数量，用 this->number 表示当前对象的 number 属性，动态申请该数量对应的 MyColor 指针类型的 number 个存储空间，并将此存储空间复制给属性 palette 。析构方法先用delete 删除用 new 创建的每个 MyColor 对象，并用 free 释放采用 malloc 函数动态申请的存放 MyColor 对象指针的存储空间。 print()方法用来打印 pale配中每个颜色对象的颜色，供测试使用。 在 print()函数体内部，为每个数组元素调用当前对象的 print ()打印一个 RGB 颜色。
  Drawing 类属性 int COLORNUMBER 定义绘画时所用的颜色数量（本例中设置为16 表示基于 16 色绘图） 0 void 世aw() 方法声明调色板 Palette palette 、定义 COLORNUMBER 色 MyColor 对象指针数组 color ，随机生成RGB 颜色并根据此颜色创 建 COLORNUMBER 个 MyColor 对象，即循环 COLORNUMBER 次，每次循环生成随 机的 RGB 颜色后调用 MyColor 的带参数构造器创建 MyColor 对象，即：
  color[i) = new MyColor(red ，green ，blue);
  所有颜色数组创建完成后，基于所创建的 COLORNUMBER 个 MyColor 对象指针数 组创建调色板，即：
  palette = new Palette(color ，COLORNUMBER);
  调用调色板的 print()方法进行打印（模拟给图）。最后将 MyColor 对象指针元素进行删除。由于 COLORNUMBER 的作用是绘图的颜色数量，在创建 MyColor 对象指针数组时作为元素个数，所以，需要是 static const 静态常量。
  主控逻辑代码在 main 函数中实现。在 main() 函数中，创建 Drawing 对象指针 d ，即生成一个绘图对象：
  Drawing * d = new Drawing();
  并进行绘图，即调用 d 的创w()方法，实现绘图功能。在使用完对象之后，需要对new 出的对象采用 delete 操作进行释放对象，对 d 对象进行删除，即 delete d;，释放内存。
  综上所述，空（1）需要表示释放 malloc 函数申请的动态内存的函数，即free(palette);
  空 （2）需要表示当前对象的 number 属性，即 this->number; 空（3）需要修饰COLORNUMBER 为静态常量，即 static const; 空（4）需要调用 MyColor 的构造方法创建 MyColor 对象，即 new MyColor; 空 （5）处为创建 Drawing 类的对象指针 d 的 new Drawing()。
  

第 6 题

阅读以下说明和 Java 代码，填补代码中的空缺，将解答填入答题纸的对应栏内。
【说明】
设计 RGB 方式表示颜色的调色板，进行绘图。其类图如图 6-1 所示。该程序的 Java代码附后。

图6-1  类图

【Java 代码】

//颜色类
class MyColor{
private int red , green , blue;

public MyColor() {
red = 0; green = 0; blue = 0;
}

public MyColor(int red , int green , int blue) {
this.red = red;
this.green = green;
this.blue = blue;
}
//其他方法略
public String toString() {
return "Red: " + red + "\tGreen:" + green + "\tBlue" + blue;
}
}
//调色板类
class Palette {
public int number; //颜色数
private （  1  ） palette; //颜色表
public Palette() {
number = 256;
palette = new MyColor[number];
}
public Palette(MyColor[] palette , int number) {

（  2 ） 

</span>= number;

（  3  ）

</span>= palette;
}
//其他方法略
public String toString() {
String str = "";
for (int i = 0; i < number; i++) {
str +=i + " : " + palette[i] + "\n"; }
return str;
}
}

//绘图类
class Drawing {
public （  4  ）

int COLORNUMBER = 16;

public static void main(String[] args) {
Palette palette;
int red , green , blue;
MyColor[] color = new MyColor[COLORNUMBER];
for (int i = 0; i < COLORNUMBER; i++) {
red = (int) (Math.random() 256);
green = (int) (Math.random() 256);
blue = (int) (Math.random() * 256);
color [i] =  （  5  ）

(red , green , blue);
}
palette = new Palette(color , COLORNUMBER);
System.out.println(palette);
}
}
</p>

答案与解析

• 试题难度：较难
• 知识点：Java程序设计>Java程序设计案例
• 试题答案：

  （1）MyColor[]
  （2）this.number
  （3）this.palette
  （4）static final
  （5）new MyColor
  

• 试题解析：

  本题考查 Java 语言程序设计的能力，涉及类、对象、方法的定义和相关操作。要求考生根据给出的案例和代码说明，认真阅读并理清程序思路，然后完成题目。
  先考查题目说明。本题目中涉及到颜色、调色板、绘图等类以及初始化和调色相关等操作。根据说明进行设计。
  类图中给出三个类 Drawing 、Palette 和 MyColor 及其之间的关系。Drawing 与 Palette、MyColor 之间具有关联关系，Palette 与 MyColor 之间是聚合关系。
  MyColor 为以 RGB 方式表示颜色，由属性 red 、green 和 blue 表示，每个 MyColor对象即为一个 RGB 颜色。 MyColor 具有两个构造器，缺省构造器将 RGB 颜色均初始化为0；带参数的构造方法将当前对象的 RGB 值设置为调用构造方法时消息中所传递的参数值。 toString()用来构造并返回当前对象的 RGB 值的字符串供测试使用。
  

  Palette 类用于表示调色板，有调色板颜色数，用 int 型 number 表示，有 MyColor 对象数组，用 MyColor[] palette表示。 Palette 的缺省构造方法中，将 number 设置为 256 色，并将 palette初始化成 256 色 MyColor 数组。另一个构造方法 Palette(MyColor[] pale，int number) 中参数有 MyColor 对象数组 pale 以及颜色数量 number 。该构造方法设置当前调 色板对象的颜色数量，用 this.number 表示当前对象的 number 属性，将参数 palette数组赋值给当前对象的 palette，用 this.palette表示当前对象的 palette属性。 toString()方法用来构造并返回 palette中每个颜色对象的颜色的字符串，供测试使用。在toString()方法体内部，构造字符串时用+进行拼接 palette[i]时，每个数组元素调用当前对象的toString()构造并返回一个 RGB 颜色的字符串。
  

  Drawing 类属性int COLORNUMBER 定义绘画时所用的颜色数量(本例中设置为 16 表示基于 16 色绘图)。 Main()方法声明调色板 Palette palette 、定义COLORNUMBER 色 MyColor 对象数组 color ，即：
  MyColor[] color = new MyColor[COLORNUMBER];
  随机生成 RGB 颜色并根据此颜色创建 COLORNUMBER 个 MyColor 对象，即循环 COLORNUMBER 次，每次循环生成随机的 RGB 颜色后调用 MyColor 的带参数构造器 创建 MyColor 对象，即：
  color[i] = new MyColor(red ，green ，blue);
  所有颜色数组创建完成后，基于所创建的 COLORNUMBER 个 MyColor 对象数组创建调色板，即：
  palette = new Palette(color ，COLORNUMBER);
  采用 System.out.println(palette);进行打印（模拟绘图），其中会自动调用调色板的 toString（）方法。由于 COLORNUMBER 的作用是绘图的颜色数量，在创建 MyColor 对象数组时作为元素个数，所以，需要是 static fmal 静态常量。
  综上所述，空（1）需要表示 MyColor 对象数组，即 MyColor[]; 空 （2）需要表示当前对象的 number 属性，即 this.number; 空（3）需要当前对象的 palette属性，即 this.palette;空 （4）需要表示 COLORNUMBER 为静态常量，即 static fmal; 空 （5）处
  为创建 MyColor 类的对象，即 newMyColor 。