2016年上半年程序员下午题答案及解析

一、问答题

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

【说明】

设整型数组A[1：N]每个元素的值都是1到N之间的正整数。一般来说，其中会有一些元素的值是重复的，也有些数未出现在数组中。下面流程图的功能是查缺查重，即找出A[1：N]中所有缺的或重复的整数，并计算其出现的次数（出现次数为0时表示缺）。流程图中采用的算法思想是将数组A的下标与值看作是整数集[1：N]加上的一个映射，并用数组C[1：N]记录各整数出现的次数，需输出所有缺少的或重复的数及其出现的次数。

【流程图】

【问题】

如果数组A[1：5]的元素分别为{3，2，5，5，1}，则算法流程结束后输出结果为：

(5) 输出格式为：缺少或重复的元素，次数（0表示缺少）

参考答案：

(1)A[i]

(2)C[k]+1

(3)1

(4)k

和C[k]

(5)4,{1,1,1,0,2}

解析：

(1) 根据说明，算法需要遍历数组A的每个元素，因此空白处应填写表示数组元素的值，即 A[i]。

(2) 在遍历过程中，对于数组A中的每个元素A[i]，需要在数组C中对应的元素C[A[i]]上计数。因此空白处应填写增加计数的表达式，即 C[k]+1，其中k代表A[i]的值。

(3) 在初始化数组C的环节，需要将所有元素初始化为0，表示对应的整数在数组A中未出现。因此空白处填写0，即初始值为1。

(4) 在计数完成后，需要遍历数组C，找出不等于初始值的元素，这些元素对应的值即为在数组A中出现过但次数不为初始值的整数。因此空白处应填写变量k和C[k]，表示当前遍历到的数组C中的元素和其对应的值。此时还需要记录这些元素的原始下标，用于输出缺少或重复的元素的位置信息。由于数组下标从1开始，因此这里应该填写当前元素的下标即可。由于原始下标已经丢失，无法直接获取，因此需要通过其他方式记录或计算。此处暂不涉及具体实现细节。

(5) 根据题目给出的数组A[1：5]的元素为{3，2，5，5，1}，经过算法处理后，得到缺少的元素为无（因为数组中的元素都是完整的），重复的元素为5（出现了两次）。因此输出格式为缺少或重复的元素及其出现次数，即{无, 5, 2}。注意此处应为数字本身和出现次数的组合，而非下标和出现次数的组合。

2、

阅读以下说明和C代码，填补代码中的空缺，将解答填入答题纸的对应栏内。

【说明1】

递归函数is_elem(char ch, char *set)的功能是判断ch中的字符是否在set表示的字符集合中，若是，则返回1，否则返回0。

【C代码1】

int is_elem (char ch ,char*set)
{
     If(*set==‘\0’)
         return 0;
     else
        If((1))
     return 1;
       else
        return is_elem((2))
}

【说明2】

函数char*combine(char* setA,char *setB)的功能是将字符集合A（元素互异，由setA表示）和字符集合B（元素互异，由setB表示）合并，并返回合并后的字符集合。

【C代码2】

char*combine(char *setA, char*setB)
{
    int i，lenA, lenB, lenC；
    lenA=strlen(setA)；
    lenB=strlen(setB)；
    char*setC=(char*)malloc(lenA+lenB+1);
if(!setC)
return NULL;
strncpy(setC,setA,lenA)；       //将setA的前lenA个字符复制后存入setC
lenC = (3);
for(i=0;i＜lenB；i++)
  if((4))             //调用is_elem判断字符是否在setA中
        setC[lenC++]=setB[i];
     (5) =‘/0’;        //设置合并后字符集的结尾标识
return setC;
}

参考答案：

（1）set[0]==ch或*set==ch或其他等价形式

（2）ch,set+1或ch,++set或其他等价形式

（3）lenA或其他等价形式

（4）is_elem(setB[i],*setA)==0或!is_elem(setB[i],*setA)或其他等价形式

（5）setC[lenC]或其他等价形式

解析：

（1）对于第一个空缺，我们需要比较给定的字符ch和集合set的第一个字符是否相等。在C语言中，可以使用字符之间的直接比较来实现这一点。因此，正确的表达式应该是ch == set或set == ch。这里使用指针访问集合的第一个字符。

（2）对于第二个空缺，我们需要将给定的字符ch与集合set的下一个元素进行比较。在递归调用中，我们需要更新指针的位置以便检查下一个字符。因此，我们可以使用表达式(ch, set + 1)或(ch, ++set)。这里使用的是指针算术和前置递增操作来移动指针位置。

（3）第三个空缺表示合并后集合的长度，由于我们知道原始集合A的长度是lenA，因此可以直接使用lenA来表示合并后的集合长度。在C语言中，字符串长度通常是指字符串中字符的数量，不包括结尾的空字符’\0’。因此，lenA表示的是合并前集合A的字符数量。

（4）第四个空缺是判断字符是否在集合A中的条件表达式。我们可以使用is_elem函数来判断字符是否在集合A中。如果字符不在集合A中，那么它应该在合并后的集合中。因此，正确的表达式是(is_elem(setB[i], *setA) == 0)或(!is_elem(setB[i], *setA))。这里使用了逻辑非操作符来反转条件判断的结果。

（5）最后一个空缺是设置合并后字符串的结尾标识。在C语言中，字符串以空字符’\0’结尾。因此，我们应该在最后一个字符后面添加’\0’来表示字符串的结束。正确的表达式是(setC[lenC])，其中lenC表示合并后字符串的长度（不包括结尾的空字符）。通过这种方式，我们确保新字符串正确地以空字符结尾。

3、

阅读以下说明和C代码，填补代码中的空缺，将解答填入答题纸的对应栏内。

【说明】

某文本文件中保存了若干个日期数据，格式如下（年／月／日）：

2005/12/1

2013/2/29

1997/10/11

1980/5/15

....

但是其中有些日期是非法的，例如2013/2/29是非法日期，闰年（即能被400整除或者能被4整除而不能被100整除的年份）的2月份有29天，2013年不是闰年。现要求将其中自1985/1/1开始、至2010/12/31结束的合法日期挑选出来并输出。

下面的C代码用于完成上述要求。

【C代码】

#include <stdio.h>
typedef struct{
int year,  month, day；/* 年，月，日*/
}DATE；
 
int  isLeap  Year(int  y)  /*判断y表示的年份是否为闰年，是则返回1，否则返回0*/
{
return((y%4==0 && y%100!=0)Il(y%400==0))；
}
 
int  isLegal(DATE  date)  /*判断date表示的日期是否合法，是则返回1，否则返回0*/
{
int  y=date.year,m=date.month,d=date.day;
if(y<1985 II  y>2010  II   m<1  II  m>12  II  d<l  II  d>31)  return  0;
if((m==4  ll  m==6   ll  m==9  II  m==11)&&(1) )   return  0;
If(m==2){
if(isLeap   Year(y) &&  (2))   return  1；
else
if(d28)  return  0；
}
return   1;
}
 
Int  Lteq(DATE  d1，DATE  d2)
/*比较日期d1和d2，若d1在d2之前或相同则返回1，否则返回0*/
{
Long  t1,t2;
t1=d1.year*10000+d1.month*100+d1.day;
t2=d2.year*10000+d2.month*100+d2.day;
if((3))  return   1;
else   return  0;
}
 
int  main()
{
DATE  date,start={1985,1,1},end={2010,12,30};
FILE*fp;
 
fp=fopen(“d.txt”,”r”);
If((4))
return-1;
 
while(!feof(fp)){
if(fscanf(fp,”%d%d%d”,date.year,date.month,date.day)!=3)
break;
if((5)) /*判断是否为非法日期*/
continue；
if((6)) /*调用Lteq判断是否在起至日期之间*/
printf(“%d%d%d\n”,date.year,date.month,date.day);
}
fclose(fp);
Return 0;
}

参考答案：

（1）d>30 或d＞=31或其等价表示

（2）d<=29或d<30或其等价表示

（3）t1<=t2或t1-t2<=0或其等价表示

（4）fp==null或!fp或其等价表示

（5）!isLegal(date) 或其等价表示

（6）Lteq(start,date)==1&&Lteq(date,end)==1或其等价表示

解析：

（1）对于判断日期是否合法，需要考虑每个月的天数。对于月份为4、6、9、11的情况，它们的最大天数为30，所以如果日期大于30则为非法日期。因此，第一个空填写的条件是检查天数是否大于最大天数或者是否等于超过最大天数的那一天。例如，对于月份为4的情况，可以填写为“d > 30 且 m == 4”。其他月份同理。

（2）对于二月份的天数判断，需要考虑闰年和非闰年的情况。在闰年中，二月份有29天，而在非闰年中只有28天。因此，第二个空填写的条件是检查二月份的天数是否超过了这个月的最大天数或者是否等于这个月的最后一天。例如，“d <= 29 或 d < 30”。对于闰年的情况，可以使用条件“isLeapYear(y) && d <= 29”。对于非闰年的情况，可以使用条件“d <= 28”。两者结合即可得到正确答案。

（3）在比较两个日期时，如果第一个日期在第二个日期之前或相同，则返回真。因此第三个空填写的条件是检查第一个日期的数值是否小于或等于第二个日期的数值。例如，“t1 <= t2”或者“t1 - t2 <= 0”。这两种表示方式是等价的。

（4）在读取文件之前，需要判断文件是否存在。第四个空填写的条件是检查文件指针是否为空或者文件是否成功打开。例如，“fp == NULL”或“!fp”。这两种表示方式是等价的。如果文件指针为空或者文件打开失败，则返回-1并退出程序。

（5）在判断日期是否合法时，使用isLegal函数进行判断。如果日期不合法，则跳过该日期继续处理下一个日期。因此第五个空填写的条件是判断日期是否不合法。例如，“!isLegal(date)”。如果isLegal函数返回假（即日期不合法），则跳过该日期。

（6）在判断日期是否在起始日期和结束日期之间时，需要使用Lteq函数进行比较。如果日期在起始日期之前且在结束日期之后或在两者之间相同，则输出该日期。因此第六个空填写的条件是判断日期是否在起始日期和结束日期之间。例如，“(Lteq(start, date) == 1 && Lteq(date, end) == 1)”。如果起始日期小于或等于当前日期且当前日期小于或等于结束日期，则输出该日期。

4、阅读以下说明和C代码，填补代码中的空缺，将解答填入答题纸的对应栏内。

【说明】

二叉查找树又称为二叉排序树，它或者是一棵空树，或者是具有如下性质的二叉树。

（1）若它的左子树非空，则左子树上所有结点的值均小于根结点的值。

（2）若它的右子树非空，则右子树上所有结点的值均大于根结点的值。

（3）左、右子树本身就是两棵二叉查找树。

二叉查找树是通过依次输入数据元素并把它们插入到二叉树的适当位置上构造起来的，具体的过程是：每读入一个元素，建立一个新结点，若二叉查找树非空，则将新结点的值与根结点的值相比较，如果小于根结点的值，则插入到左子树中，否则插入到右子树中；若二叉查找树为空，则新结点作为二叉查找树的根结点。

根据关键码序列{46，25，54，13，29，91}构造一个二叉查找树的过程如图4-1所示。

设二叉查找树采用二叉链表存储，结点类型定义如下：

typedef  int   KeyType；
typedef  struct  BSTNode{
KeyType  key；
struct   BSTNode  *left,*right；
}BSTNode,*BSTree；

图4-1(g)所示二叉查找树的二叉链表表示如图4-2所示。

函数int InsertBST(BSTree *rootptr,KeyType kword)功能是将关键码kword插入到由rootptr指示出根结点的二叉查找树中，若插入成功，函数返回1，否则返回0。

【C代码】

int  lnsertBST(BSTree*rootptr，KeyType  kword)
/*在二叉查找树中插入一个键值为kword的结点，若插入成功返回1，否则返回0；
*rootptr为二叉查找树根结点的指针
*/
{
BSTree  p,father;
(1)  /*将father初始化为空指针*/
p=*rootptr;  /*p指示二叉查找树的根节点*/
while(p&&（2）){   /*在二叉查找树中查找键值kword的结点*/
father=p;
if(kword＜p-＞key)
p=p-＞left；
else
p=p-＞right；
}
if((3))return   0;  /*二叉查找树中已包含键值kword，插入失败*/
 
p=(BSTree)malloc((4));  /*创建新结点用来保存键值kword*/
If(!p)return  0;   /*创建新结点失败*/
p-＞key=kword；
p-＞left=NULL；
p-＞right=NULL；
 
If(!father)
(5) =p； /*二叉查找树为空树时新结点作为树根插入*/
else
if(kword＜father-＞key)
(6)；/*作为左孩子结点插入*/
else
(7)；/*作右孩子结点插入*/
return 1；
}/*InsertBST*/

参考答案：

father=(void*)0

keyword!=p-key

sizeof(BSTNode)

*rootptr

father-left=p

father-right=p

解析：

本题主要考察二叉查找树的插入操作。根据题目描述和C代码，我们需要填补代码中的空缺，以完成二叉查找树的插入功能。

首先，我们需要初始化father指针为空指针，表示从根节点开始搜索。因此，填写"(1)"处应填写father=(void*)0。
在while循环中，我们需要在二叉查找树中查找与关键字kword相同的节点。如果找到了相同的节点，则插入失败，因此填写"(2)"处应填写keyword != p->key。
如果在树中找到了与关键字kword相同的节点，插入操作失败，函数返回0。因此，填写"(3)"处应填写p。
创建新节点时，需要为新节点分配内存空间。因此，填写"(4)"处应填写sizeof(BSTNode)，表示分配一个BSTNode结构体的大小。
当二叉查找树为空树时，新节点作为树根插入。因此，填写"(5)"处应填写*rootptr = p。
当新节点的值小于father节点的值时，将其作为左孩子节点插入。因此，填写"(6)"处应填写father->left=p。
当新节点的值大于father节点的值时，将其作为右孩子节点插入。因此，填写"(7)"处应填写father->right=p。

综上，完整的InsertBST函数应如下：

int InsertBST(BSTree* rootptr, KeyType kword) {
    BSTree p, father;
    father = (void*)0;  // 将father初始化为空指针
    p = *rootptr;  // p指示二叉查找树的根节点
    while (p && keyword != p->key) {  // 在二叉查找树中查找键值kword的结点
        father = p;
        if (kword < p->key) {
            p = p->left;
        } else {
            p = p->right;
        }
    }
    if (p) return 0;  // 二叉查找树中已包含键值kword，插入失败
    
    p = (BSTree)malloc(sizeof(BSTNode));  // 创建新结点用来保存键值kword
    if (!p) return 0;  // 创建新结点失败
    p->key = kword;
    p->left = NULL;
    p->right = NULL;
    
    if (!father) {
        *rootptr = p;  // 二叉查找树为空树时新结点作为树根插入
    } else if (kword < father->key) {
        father->left = p;  // 作为左孩子结点插入
    } else {
        father->right = p;  // 作为右孩子结点插入
    }
    return 1;  // 插入成功，返回1
}  // InsertBST

5、阅读以下说明和Java代码，填补代码中的空缺，将解答填入答题纸的对应栏内。

【说明】

以下Java代码实现两类交通工具（Flight和Train）的简单订票处理，

类Vehicle、Flight、Train之间的关系如图5-1所示。

【Java代码】

import  java.util.ArrayList;
import java.util.List;
 
abstract class   Vehicle {
void  book(int n) {  //订 n张票
if (getTicket0() >=n ) {
decrease  Ticket(n);
}  else  {
System.out.println(“余票不足！！“)；
}
}
 
abstract int getTicket();
abstract void decreaseTicket(int n);
};
 
class   Flight（1）{
Private（2）tickets=216； //Flight的票数
Int  getTicket(){
Return tickets；
}
 
void decreaseTicket(int n){
tickets=tickets - n；
}
}
 
class  Train（3）{
Private（4）tickets=2016; //Train的票数
int getTicket() {
return  tickets;
}
 
void decreaseticket(int  n) {
tickets  =  tickets  -  n; 
}
}
 
public  class  Test {
public  static  void main(String[] args) {
System.out.println（“欢迎订票!")；
ArrayListVehicle  v  =  new  ArrayListVehicle();
v.add(new  Flight());
v.add(new  Train());
v.add(new  Flight());
v.add(new  Train());
v.add(new  Train());
for(int i=0;iv.size(); i++){
（5）（i+1）; //订i+1张票
System.out.println（“剩余票数：”+v.get(i).getTicket())；
}
}
}

运行该程序时输出如下：

欢迎订票！

剩余票数：215

剩余票数：2014

剩余票数：（6）

剩余票数：（7）

剩余票数：（8）

参考答案：

extendsVehicle

int

extendsVehicle

int

v.get(i).book

213

2012

2011

解析：

这是一道关于Java面向对象编程的题目，涉及到抽象类、继承和订票逻辑的编写。下面是详细解析：

对于类Flight和Train，它们都是Vehicle类的子类，因此应该使用extends Vehicle来继承Vehicle类的属性和方法。所以(1)、(3)的答案都是extends Vehicle。
在类Flight和Train中，定义票数的变量应该是整型，所以(2)、(4)的答案都是int。
在Test类的main方法中，创建一个ArrayList来存储Vehicle类型的对象，然后通过调用v.get(i).book(i+1)来预订票。所以(5)的答案是v.get(i).book(i+1)。
对于输出部分，(6)、(7)、(8)表示的是剩余票数，但由于之前已经预订了一些票，所以当再次尝试获取剩余票数时，如果票数不足，应该输出一个表示票数不足的值，如null或其他合理的值。因此，(6)、(7)、(8)的答案都是表示票数不足的值。

整体而言，这段代码实现了通过继承抽象类Vehicle来创建不同的交通工具（Flight和Train），然后对这些交通工具进行订票操作的功能。

6、阅读下列说明和C++代码，填补代码中的空缺，将解答填入答题纸的对应栏内。

【说明】

以下C++代码实现两类交通工具（Flight和Train）的简单订票处理，类Vehicle、Flight、Train之间的关系如图6-1所示。

【C++代码】

#include <iostream>
#include <vector>
using  namespace  std;
 
class  Vehicle{
public:
virtual ~Vehicle(){}
void  book(int  n){  //订n张票
if(getTicket() >= n){
decreaseTicket(n);
} else{
coutn“余票不足！！”；
}
}
 
virtual int  getTicket()=0;
virtual void   decreaseTicket(int)=0；
}；
 
Class Flight: （1）{
private:
（2）tickets;//Flight的票数
public:
int getTicket();
void  decreaseTicket(int);
};
 
class   Train: （3）{
private:
（4）tickets; //Train的票数
public:
int getTicket();
void   decreaseTicket(int);
};
 
int Train::tickets =  2016; //初始化Train的票数为2016
int Flight::tickets =  216; //初始化Flight的票数为216
 
int Train：：getTicket() { return tickets；}
void  Train：：decreaseTicket(int  n){ tickets=tickets  -  n;}
 
int Flight::getTicket(){return  tickets; }
void  Flight::decreaseTicket(int  n) { tickets= tickets  -  n;}
 
int main() {
vector<Vehicle*> v;
 
v.push_back(new Flight());
v.push_back(new Train());
v;push_back(new Flight());
v.push_back(new Tram());
v.push_back(new Train());
 
cout《"欢迎订票！”《endl：
for (int i= 0;i<v.size(); i++) {
（5）(i+1)； //订i+l张票
cout《“剩余票数：”<<（*V[i]）.getTicket()<<endl;
}
 
for(vector<Vehicle*>：：iterator it  =  v.begin();  it  !=  v.end(); it ++) {
if (NULL !=*it) {
delete*it;
*it =  NULL;
}
}
v.clear();
Return0;
}

运行该程序时输出如下：

欢迎订票！

剩余票数：215

剩余票数：2014

剩余票数：（6）

剩余票数：（7）

剩余票数：（8）

参考答案：

public Vehicle

int

public Vehicle

int

(*v[i]).book();

213

2012

2011

解析：

本题主要考察的是面向对象编程中的类与继承、多态以及动态内存管理。下面是详细的解析：

题目中提到了Vehicle类、Flight类和Train类之间的关系，说明Flight和Train是Vehicle类的派生类。因此，在定义Flight和Train类时，需要继承Vehicle类。故第一处填空应为public Vehicle。

对于第二和第四处填空，由于票数是一个整数值，因此应该是int类型。所以第二和第四处应填写int。

在main函数中，调用订票功能时，需要通过对象指针调用book函数，所以第五处应填写(*v[i]).book()，即调用第i+1个对象的book函数预订一张票。

接下来的三个空（剩余票数：）对应的是程序运行过程中输出的剩余票数，由于题目没有给出具体的数值，所以这三个空需要根据程序的实际运行情况来填写。假设程序运行后，Flight剩余票数为213，Train剩余票数为2012和2011（由于第一次订票后数量减少），所以这三处应填写剩余票数：剩余票数：剩余票数：剩余票数：剩余票数：剩余票数：剩余票数：剩余票数：剩余票数：剩余票数：剩余票数：剩余票数：剩余票数：剩余票数：剩余票数：剩余票数等实际运行后的结果。

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

2016年上半年程序员下午题答案及解析

最热门资讯

JAVA工程师面试指导--猎头内部资料

常见面试问题100问！