2018年5月 程序员 下午题答案及解析

一、问答题

1、阅读以下说明和流程图，填补流程图中的空缺，将解答填入答题纸的对应栏内。
[说明]
下面流程图的功能是：在给定的两个字符串中查找最长的公共子串，输出该公共子串的长度L及其在各字符串中的起始位置(L=0时不存在公共字串)。例如，字符串"The light is not bright tonight"与"Tonight the light is not bright"的最长公共子串为"he 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的指定字符串是否完全相同(该过程的流程略)。
[流程图]

参考答案：

N或rnin(M，N)
M-L+1
N-L+1
L-1
L，I，J

解析：

本题考查对算法流程图的理解和绘制能力。本题的算法用于查找两个字符串中的最长公共子串，并输出其长度及在各自字符串中的起始位置。

根据说明和流程图的分析，我们可以得出以下解释：

1. 由于字符串A和B的长度分别为M和N，且M≥N≥1，所以它们的公共子串长度L必然小于或等于N。因此，初始时，应将min(M，N)或N送L，表示开始查找的最大可能的公共子串长度。所以(1)处填写N或min(M，N)。
2. 对于A串，长度为L的子串的起始下标可以从1开始直到M-L+1。因此，(2)处应填写M-L+1或其等价形式。
3. 对于B串，同样的逻辑，长度为L的子串的起始下标可以从1开始直到N-L+1。所以，(3)处应填写N-L+1或其等价形式。
4. 如果两个子串比较的结果不匹配，则需要继续执行循环。此时需要减小L的值，所以(4)处应填写L-1。
5. 如果找到了匹配的子串，即找到了最长公共子串，此时应输出公共子串的长度L以及在A、B串中的起始位置I和J。所以，(5)处应填写L，I，J（顺序不分先后）。

综上所述，答案应为：N或min(M，N)；M-L+1；N-L+1；L-1；L，I，J。

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= ______;  
 s= ______;

    term=s/n;

    }

    return  pi*4;

    }

[C函数2]

    long fun(char
*str)

    {

    int i=0;

    long num: 0;

    char *p = str;

    while ( i＜8 && ______)  {

    if  (
 *p ＞=  '0'
 && *p ＜=  '9'
 )  {

    num= ______ + *p -
'0';

    ++i;

    }

    ______;

    }

    return  num;

    }

参考答案：

n+2
-s或-1*s
*p!='\0'或等价形式
num*10或等价形式
p++或等价形式

解析：

对于函数f(double eps)，其功能是计算π的近似值。根据题目中的说明和公式，我们知道在循环中需要不断更新n和s的值以保证计算的准确性。其中n每次递增2，因此空(1)处应填入n+2；由于公式中的各项正负交替，所以空(2)处应填入-s或等价形式来实现正负交替的计算；关于最后的返回值，函数返回的是π的近似值，因此需要乘以4，即返回pi*4。对于函数fun(char *str)，其功能是从字符串中提取数字字符并组合成一个整数。根据题目的要求和函数的逻辑，我们知道在循环中需要判断字符串是否结束或已经读取了8位数字字符，因此空(3)处应填入相应的条件判断语句；在提取数字字符时需要将当前数字字符转换为整数，因此空(4)处应填入将当前数字字符转换为整数的操作；最后需要更新指针p以获取下一个字符，因此空(5)处应填入指针p的更新操作。

3、阅读以下说明和C代码，填补代码中的空缺，将解答填入答题纸的对应栏内。
[说明]
下面的程序代码根据某单位职工的月工资数据文件(名称为Salary.dat，文本文件)，通过调用函数GetIncomeTax计算出每位职工每月需缴纳的个人所得税额并以文件(名称为IncomeTax.dat，文本文件)方式保存。
例如，有4个职工工资数据的Salary.dat内容如下，其中第一列为工号(整数)，第2列为月工资(实数)。
1030001  6200.00
1030002  5800.00
2010001  8500.00
2010010  8000.00
相应地，计算所得IncomeTax.dat的内容如下所示，其中第3列为个人所得税额：
1030001 6200.00 47.20
1030002 5800.00 35.94
2010001 8500.00 233.50
2010010 8000.00 193.00
针对工资薪金收入的个人所得税计算公式为：
个人所得税额=应纳税所得额×税率-速算扣除数
其中，应纳税所得额=月工资-三险一金-起征点
税率和速算扣除数分别与不同的应纳税所得额对应，如下表所示。

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

[C代码] 

    #include ＜stdio.h＞ 

    #define BASE 3500
               //起征点 

    #define RATE 0.19
              //三险一金比例 

    ______;  
                     
    //声明函数GetIncomeTax


    int main() 

    { 

    int id; 

    double salary; 

    FILE *fin,*fout; 

    fin =
fopen("Salary.dat","r"); 

    if  (______)
 return 0; 

    fout =
fopen("IncomeTax.dat","w"); 

    if (______)
 return 0; 

    while (!feof(fin))
 { 

    if
 (fscanf(fin,"%d%if", ______) !=2) break; 

  
 fprintf(fout,"%d\t%.21f\t%.21f\n",id, salary, ______); 

    } 

    fclose(fin); 

    fclose(fout); 

    return 0; 

    } 

    double
GetIncomeTax(double salary) 

    { 

    double yns_sd; 

    yns_sd = ______ -
BASE;        /*计算应纳税所得额*/ 

    if  (yns_sd＜=0)       return  0.0; 

    else  if
 (yns_sd＜=1500)
     return yns_sd*0.03; 

    else  if
 (yns_sd＜=4500)
     return yns_sd*0.1-105; 

    else  if
 (yns_sd＜=9000)
     return yns_sd*0.2-555; 

    else  if
 (yns_sd＜=35000)
    return yns sd*0.25-1005; 

    else  if
 (yns_sd＜=55000)
    return yns_sd*0.3-2755; 

    else if(yns_sd＜=80000)  return yns_sd*0.35-5505; 

    return
yns_sd*0.45-13505; 

    }

参考答案：

double GetIncomeTax(double salary)或double GetIncomeTax(double)
!fin或fin=NULL或fin==0
!fout或fout==NULL或fout==0
&id.&salary
GetIncomeTax(salary)
salary*(1-RATE)或等价形式
注：RATE可替换为0.19

解析：

本题考查C语言程序设计中的文件操作、函数声明与定义以及数学计算。根据题目描述和提供的代码，具体分析如下：

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

设链表结点类型定义如下：

typedef Struct Node{

    int data;

    struct Node*next;

    }Node,*LinkList;

    [C函数]

    LinkList
Combine(LinkList La,LinkList Lb)

    {  //La和Lb为含头结点且元素呈递减排列的单链表的头指针

    //函数返回值是将La和Lb合并所得单链表的头指针

    //且合并所得链表的元素值呈递增(或非递减)方式排列

    ______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(______)
 {  //pa和pb所指结点均存在(即两个链表都没有到达表尾)

    //令tp指向pa和pb所指结点中的较大者

    if(pa-＞data＞pb-＞data){

    tp=pa;  
 pa=pa-＞next;

    }

    else{

    tp=pb;  
 pb=pb-＞next;

    }

    ______ =Lc-＞next;    //tp所指结点插入Lc链表的头结点之后

    Lc-＞next=______;

    }

    tp=(pa)?pa:pb;
   //设置tp为剩余结点所形成链表的头指针

    //将剩余的结点合并入结果链表中,pa作为临时指针使用

    while  (tp)
 {

    pa=tp-＞next;

    tp-＞next=Lc-＞next;

    Lc-＞next=tp;

    ______;

    }

    return Lc;

    }

参考答案：

LinkList
pa&&pb
tp-＞next
tp
tp=pa

解析：

本题考查数据结构应用及C语言实现。链表运算是C程序设计题中常见的考点，需熟练掌握。考生需仔细阅读题目中的说明和注释，理解问题并确定代码的运算逻辑。

空(1)所在的代码定义指向链表中结点的指针变量，根据链表结点类型的定义，应填入"LinkList"。

空(2)所在的while语句中，需要将pa指向的结点的数据与pb所指向的结点的数据进行比较。因此，空(2)处应填入"pa&&pb"，确保在比较两个链表元素时，两个指针都不为空。

空(3)和空(4)根据注释，需将tp所指结点插入Lc链表的头结点之后。因此，空(3)处应填入"tp->next"，表示将tp所指向的下一个结点作为插入位置；空(4)处应填入"tp"，表示将tp所指向的结点插入到链表中。

空(5)所在的while语句处理的是还有剩余结点的链表。在这个循环中，通过不断将剩余的结点插入到已合并的链表中，最终实现两个链表的合并。因此，空(5)处应填入"tp=pa"，以便在循环结束后继续处理剩余的结点。

综上所述，完整的答案应为：LinkList pa&&pb tp->next tp tp=pa。

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

类图

[C++代码]

    #include＜iostream＞

    #include ＜stdlib. h＞

    #include ＜crime＞

    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];  }

    ______;

    }

    Palette(MyColor**
pale,  int number)  {

    ______ = 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:

    ______ int
COLORNUMBER = 16;

    public:

    ～Drawing()  {  }

    void draw()
 {

    Palette* palette;

    int red,
 green,  blue;

    MyColor*
color[COLORNUMBER];

    srand ((unsigned)
time (0));

    for (int i=0; i＜COLORNUMBER; i++)    {

    red=rand()  %
256; green = rand()  % 256; blue = rand() % 256;

    color[i] = ______
(red,  green, blue);

    }

    palette = new
Palette (color,  COLORNUMBER);

    palette-＞print ();

    for  (int
i=0; i ＜
COLORNUMBER; i++)

    delete color[i];

    }

    };

    int main  ()
{

    Drawing * d =
______;

    d-＞draw ();

    delete d;

    }

参考答案：

free(palette)
this-＞number
static const
new MyColor
new Drawing()

解析：

这道题目是关于类与对象的定义与操作的题目。根据题目给出的说明和代码，我们需要完成一些空缺的填写。以下是详细的解析：

首先，关于Palette类的析构函数中的内存释放问题。在析构函数中，我们需要释放使用malloc函数动态分配的内存空间。因此，第一个空应该填写释放动态内存的函数，即free(palette)。

其次，关于Palette类的构造函数中的属性赋值问题。在构造函数中，我们需要设置当前对象的number属性，所以第二个空应该填写this->number。

接着，关于Drawing类中COLORNUMBER的定义问题。为了保证COLORNUMBER在程序运行期间不发生改变，我们需要将其定义为静态常量，所以第三个空应该填写static const。

然后，关于Drawing类的draw()方法中创建MyColor对象的问题。在这个方法中，我们需要创建MyColor对象，所以第四个空应该填写调用MyColor的构造方法创建MyColor对象的语句，即new MyColor(red, green, blue)。

最后，关于main()函数中创建Drawing对象的问题。在main函数中，我们需要创建一个Drawing类的对象指针d，所以第五个空应该填写创建Drawing类对象的构造函数，即new Drawing()。

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

类图

[Java代码]

    //颜色类

    class MyColor {

    private int red,
 green, blue;

    public MyColor()
 {

    red = 0; green = O;
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 ______
palette;    //颜色表

    public Palette()
 {

    number = 256;

    palette = new
MyColor[number];

    }

    public
Palette(MyColor[] palette,  int number)

    ______ = number;

    ______ = palette;

    }

    //其他方法略

    public String
toString()  {

    String  str =
 "";

    for (int i = 0; i ＜ number; i++)  {

    str +=
i+":" + palette[i] + "\n";

    }

    return str;

    }

    }

    //绘图类

    class Drawing
 {

    public ______ 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]  =
______ (red,  green, blue);

    }

    palette = new
Palette (color, COLORNUMBER);

    System.out.println
(palette);

    }

    }

参考答案：

MyColor[]
this.number
this.palette
static final
new MyColor

解析：

本题考查Java语言中的类设计和对象创建。根据题目描述和给出的代码片段，我们可以逐一解析填空部分：

1. 在Palette类中，表示颜色表的变量应该是一个MyColor类型的数组，所以第一个空应填写为MyColor[] palette;。

2. 在Palette的构造函数中，需要设置当前调色板对象的颜色数量，使用关键字this引用当前对象的number属性，并赋值参数number，所以第二个空应填写为this.number = number;。

3. 同样在Palette的构造函数中，需要将参数palette数组赋值给当前对象的palette属性，所以第三个空应填写为this.palette = palette;。

4. 在Drawing类中，COLORNUMBER表示绘画时所用的颜色数量，这是一个静态常量，因此应填写为static final。

5. 在创建MyColor对象时，需要使用new MyColor(red, green, blue)来创建新的MyColor对象。

综上，答案为：MyColor[] palette;、this.number = number;、this.palette = palette;、static final、new MyColor(red, green, blue)。

喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！