201311程序员下午真题

第 1 题

阅读以下说明和流程图，填补流程空中的空缺（1）～（5）将解答填入答题纸的对应栏内。
【说明】
两个包含有限个元素的非空集合 A、B  的相似度定义为 |A∩B|/|A∪B|，即它们的交集大小(元素个数）与并集大小之比。
以下的流程图计算两个非空整数集合(以数组表示）的交集和井集，并计算其相似度。己知整数组 A[1:m]和 B[1:n]分别存储了集合 A 和 B 的元素(每个集合中包含的元素各不相同)，其交集存放于数组C[1:s]，并集存放于数组D[1:t] ，集合A 和 B 的相似度存放于 SIM。
例如，假设 A={ 1， 2 ，3，4} ，B={ 1， 4 ，5，6}，则C={1， 4} ，D={1， 2 ，3 ，4 ，5， 6}，A 与 B 的相似度 SIM=1/3。

【流程图】

答案与解析

• 试题难度：较难
• 知识点：流程图>流程图
• 试题答案：（1）s             （2）t      （3）c[s]           （4）D[t] （5）s/t
  
• 试题解析：本题考查程序处理流程图的设计能力。
  首先我们来理解两个有限集合的相似度自含义。两个包含有限个元素的非空集合 A、B 的相似度定义为它们的交集大小(元素个数)与并集大小之比。如果两集合完全相等，则相似度必然为 1 (100%); 如果两集合完全X同(没有公共元素)，则相似度必然为0; 如果集合A 中有一半元素就是集合B 的全部元素，而另一半元素不属于集合 B，则这两 个集合的相似度为 0.5(50%)。因此，这个定义符合人们的常理性认识。
  在大数据应用中，经常要将很多有限集边行分类。例如，每天都有大量的新闻稿。
  为了方便用户检索，需要将新闻稿分类。用付么标准来分类呢?每一篇新闻稿可以用其 中所有的关键词来表征。这些关键词的集合勒为这篇新闻稿的特征向量。两篇新闻稿是 否属于同一类，依赖于它们的关键词集合是否具有较高的相似度(公共关键词个数除以 总关键词个数)。搜索引擎可以将相似度超过一定水平的新闻稿作为同一类。从而，可以 将每天的新闻稿进行分类，就可以按用户的需要将某些类的新闻稿推送给相关的用户。
  本题中的集合用整数组表示，因此，需要规定同一数组中的元素各不相同(集合中的元素是各不相同的)。题中，整数组 A[1:m] 阳 B[l:n]分别存储了集合 A 和 B 的元素。流程图的目标是将 A 、B 中相同的元素存放入数组C[ 1:s]  (共s 个元素)，并将 A 、B 中 的所有元素(相同元素只取一次)存放入数组  D[1:t]   (共t 个元素)，最后再计算集合 A 和 B 相似度的。
  流程图中的第一步显然是将数组 A 中的全部元素放入数组 D 中。随后，只需要对数 组 B 中的每个元素进行判断，凡与数组 A 中某个元素相同时，就将其存入数组 C;  否则就续存入数组 D (注意，数组 D 中已有 m 个元素)。这需要对 j (遍历数组 B) 与 i (遍历数组 A) 进行两重循环。判断框 B[j]=A[i]f lG立时， B[j]应存入数组 C; 否则应继续 i 循环，直到循环结束仍没有相等情况出现时， j 先应将 B[j]存入数组 D。存入数组 C 之前， 需要将其下标 s 增 1; 存入数组 D 之前，需要将其下标 t 增 1。因此，初始时，应当给j 赋 0，使数组C 的存数从C[1]开始。从而，（）处应填 s，(3)处应填c[s]。而数组D 是在已有 m 个元素后续存，所以，初始时，数 fi D 的下标 t 应当是 m ，续存是从D[m+1] 开始的。因此，   (2)   处应填 t ，(的处应填D[]。
  两重循环结束后，就要计算相似度的，将其赋予 SIM，因此(5) 处应填的。

第 2 题

【C 函数】
void sort(int n ,int a[ ])
{    int  b;
     int i ,k ,number;
     int minimum  = a[0] , maximum = a[0];
     / minimum 和 maximum 分别表示数组a的最小、最大元素值/

     for(i=1;i<n;i++){
         if(  （1） ) minimum=a[j];
         else
             if( （2） ) maximum=a[i];
     }

     number = maximum - minimum + 1;
     if  (number<=1)   return;
      b =  (int )calloc (number ，sizeof(int)) ;

答案与解析

• 试题难度：较难
• 知识点：C程序设计>C程序设计
• 试题答案：（1） a[i]<minimum ，或a[i]<= minimum ，或其等价形式
  （2） a[i]>maximum ，或a[i]>= maximum ，或其等价形式
  （3） 0
  （4）b[k] ，或b[k]>0 ，或b[k]!=0 ，或其等价形式
  （5）k
• 试题解析：本题考查 C 程序的基本语法和运算逻辑。 首先应认真分析题目中的说明，然后确定代码结构和各变量的作用。
  空（1）和 （2）所在 for 语句的功能是求出数组 a 中的最小元素 minimum 和最大元素 maxlmum 。在设置了minimum 和 maximum的初始值后，空（1）处的判断条件是只要目前的元素 a[i]小于 minimum ，就需要更新minimum ，反之，空（2）处的判断条件是只要目前的元素 a[i]大于 maximum ，就需    更新maximum ，因此空（1）处应填入 a[i]<minimum 或其等价方式，空 （2）处应填入 a[i] >maximum 或其等价方式。 minimum 和 maximum 的作用是要确定计数数组 b 的大小。
  根据题目中的描述，序列中的每个元素 a[i]都对应到计数数组 b[]的一个元素 b[k] 对应方式为: k = a[i] -minimum ，其中minimum 是数组 a 中的最小元素，显然在计数时， 一个数值出现一次，就在对应的 b[k] 中累加一次。
  空（3）～（5）所在的语句组是产生排序后的序列，重新写入数组 a。首先需明确
  变量 i和 k 的作用，根据它们在该语句组中的出现位置， i用于表示数组 a 的元素下标， k 用于表示数组 b 中元素的下标，因此，空（3）处应填入 0 ，使得从数组a 中下标为 0 的数组元素开始。通过循环控制 "for( k=0; k＜number; k++)"己经明确数组 b 的下标变化方式，而需要写入数组 a 的元素个数表示在 b[k] 中，所以 “ for(;（4）; --b[k])”中空（4）处应填入 "b[k]>0" 或其等价形式。 (由于 b[k] 中记录的是元素 k+ minimum 的出 现次数，所以空（5）处应填入 "k"，从而将元素值恢复后再写回去。

第 3 题

阅读以下说明和C程序，填充程序中的空缺，将解答填入答题纸的对应栏内。
【说明】
正整数n若是其平方数的尾部，则称n为同构数。例如，6是其平方数36的尾部，76是其平方数5776的尾部，6与76都是同构数。下面的程序求解不超过10000的所有同构数。
己知一位的同构数有三个: 1，5，6，到此二位同构数的个位数字只可能是1，5，6这三个数字。依此类推，更高位数同构数的个位数字也只可能是1，5，6 这三个数字。
下面程序的处理思路是:对不超过10000的每一个整数a，判断其个位数字，若为1、5或6，则将a 转换为字符串as，然后对a进行平方运算，并截取其尾部与as长度相等的若干字符形成字符串后与as比较，根据它们相等与否来断定a是否为同构数。

(1)a%10，或其等价形式

(2)right(rs，len)

(3)num%10 ，或其等价形式

(4)ch = s[i]，或ch = *(s+i)

【C++代码】

     #include <typeinfo>

     #include <iostream>

     using namespace std;

     class Vehicle  {  /*抽象基类，车辆*/
     public:
     virtual void run( )  = 0;
     }；
    class Emergency  { /*抽象基类，可在红灯时通行的接口，函数均为纯虚函数*/
    public:
          (1)    =  0;           // isEmergent ( )函数接口

阅读以下说明和Java代码，填充程序中的空缺，将解答填入答题纸的对应栏内。
【说明】
某应急交通控制系统(TraficControlSystem)在红灯时控制各类车辆 (Vehicle)的通行，其类图如图6-1所示，在紧急状态下应急车辆在红灯时可通行，其余车辆按正常规则通行。

下面的Java代码实现以上设计，请完善其中的空缺。

【Java 代码 】
abstract class Vehicle {
        public Vehicle( ) { }
        abstract  void  run( );
}；
interface  Emergency   {
             (1)     ;
             (2)     ;
}；
class  Car  extends  Vehicle   {
         public  Car( )   {        )
         void  run ( ) {   /代码略/    }
}；
class  Truck  extends  Vehicle  {
          public  Truck( )   { }
          void  run   ( ) {        /代码略/    }
}；
 
class PoliceCar     (3)     {
         boolean  isEmergency  =  false;
         public  PoliceCar()    {    }
         public   PoliceCar(boolean   b) {   this.isEmergency=b;   }
         public   boolean   isEmergent( ) { return     ( 4 )   ;    }
         public  void  runRedLight( )  {    /代码略/  }
};
/类Ambulance 、 FireEngine  实现代码略/
public    class   TraficControlSystem     { /交通控制类/
         private  Vehicle[ ]  v  =  new  Vehicle[24];
         int  numVehicles;
         public  void control( )  {
               for  (int  i = 0;  i <  numVehicles;  i++)  {
                        if  (v[i]  instanceof  EmErgency  &&   ((Emergency)v[i]).
                        isEmergent())  {
                           (     5   ) .runRedLigh   (   );
                         }    else
                           ( 6 )  .run ( ) ;
                }
         }    
                void  add(Vehicle  vehicle)   {  v[numVehicles++]  = vehiclei} /添加车辆/
                void   shutDown()    {   /代码略 /}
               
                public  static void  main (Str :.ng [ ]  args)   {
                         TraficControlSystem    tcs  =  new   TraficControlSystem();
                         tcs.add(new     Car()};
                         tcs.add(new  PoliceCar();
                         tcs.add(new  Ambulance();
                         tcs.add(new   Ambulance(t:ue));
                         tcs.add(new FireEngine( :rue));
                         tcs.add(new Truck());
                         tcs.add(new FireEngine( );
                         tcs.control();
                         tcs.shutDown();
         }
}

答案与解析

• 试题难度：较难
• 知识点：Java程序设计>Java程序设计案例
• 试题答案：(1) boolean isEmergent（）
  (2) void runRedLight（）
  (3)extends Car implements Emergency
  (4) this.isEmergency
  (5) (Emergency)v[i]
  (6) v[i]
• 试题解析：本题考查Java语言程序设计的能力，涉及类、对象、方法的定义和相关操作。要求考生根据给出的案例和执行过程说明，认真阅读理清程序思路，然后完成题目。
  根据题目说明，以交通控制系统 (Tn .ficControlSystem) 为背景，本题目中涉及的各类车辆和是否应急状态下在红灯时的通行情况。根据说明进行设计，题目给出了类图(图6-1 类图所示)。
  图中父类Vehicle ，代表交通工具，设计为抽象类。在Java用abstract 关键字表示， 表示行驶某一个具体的交通工具。 Vehiclt  包含一个抽象方法: run（），方法后没有实现， 直接用;来表示抽象方法，表示行驶的方法由具体子类型完成，所以Vehicle的 run（）为一 个抽象方法:
  abstract void run()；
  Car和Truck 都继承自 Vehicle 的两个子类型，所以他们都继承了Vehicle的 run（）方法，各自行驶方式有所不同，所以都覆盖了 Vehicle  的 run（）方法，并加以实现:
  void  run () U代码略/}
  Car的两个子类型 PoliceCar 和Ambuance 都继承自 Car ，从而PoliceCar 和Ambulance 也都继承了 Car 中的 run(  )方法。 Truck 的子类 FireEngine 也继承了 Truck 的 run（）方法。
  图 6-1 中 Emergency 在 Java 中采用技口实现，其中约定红灯时通行的相关接口为:
  isEmergent（）和runRedLight（）  。
  isEmergent（）接口约定应急车辆返回 11身紧急情况状态，用 bool 类型的 isEmergency
  表示:this.isEmergency  ，其值在紧急情况下为true ，非紧急情况下为fales。runRedLight（） 接口约定应急车辆在红灯时如何通行( isEmergency 为 true ，则通行，isEmergency  为 false ， 和普通车辆一样通行)。实现  Emergency   的类商 PoliceCar、Abmulance  和 FireEngine ，所以在这三个类中都要实现 Emergency 中定义的接口。在 Java 中，实现接口用 implements 关键字，后面加上所要实现的接口，即:
  . ClassName implements  InterfaceName
  交通控制类 TraficControlSystem   对运俨的交通工具进行控制，所有交通工具用 Vehicle 数组 v 表示; numVehicles 表示交通工具数量; control 函数进行控制在紧急情况 下应急车辆红灯通行，其他情况按常规通行; add（）表示有车辆加入系统， shutDown（）表 示系统关闭。 Vehicle 的子类具体类型有 Car、Tluck、PoliceCar、Abmulance 和 FireEngine ， 所以 v[ ]数组中对象有这些类型的对象，加入 v[]时会自动向上转型成为 Vehicle 类型， Emergency 接口的应急车辆有 runRedLight01.法，其他 Car 和 Truck 只有 run()方法。因 此，用 for  循环中对每个 v[i] ，判定是否是Emergency  类型的实例，即是否实现了 Emergency。Java 中判断一个对象是否是某个类型的实例用 instanceof 关键字。即: v[i] instanceof    Emergency ，如果是，说明是应急车辆，接着判定应急车辆的状态，在判定之 前先要将应急车辆进行向下转型， Java 中向下转型直接在对象前加上用括号括起来的转 换的目标类型即可，即:    ((Emergency)vl[i]).isEmergent(),  如果判定为真，执行 runRedLight() ，判定不成功，则调用run()  ，问用时动态绑定每个数组元素的实际类型， 需要通过动态类型转换并调用runR edLight():
  if   (v[i]  instanceof  Emergency  && ((Emergency)v[i)) .isEmergent())   { ((Emergency)v[i]) .runRedLight(  );
  )    else
  v [i]->run () ;
  主控逻辑代码在 mam 方法中实现。初始化 TraficControlSystem ，用tcs 表示，调用 tcs 的add()函数添加具体的交通工具，这里会自动向上转型成为Vehicle 类型，调用 control（）对各车辆进行控制，调用 shutDown（）系统关问。
  因此，空(1)和空（2）需要定义接口sEmergentO和runRedLight（） ，题目代码中 己经给出用分号结尾，所以空(1)和空(2)分别为   “bool    isEmergent（）”    和 “void runRedLight（）”;空(3)需要继承父类 Car 和实现接口 Emergency ，Java 中继承采用extends关键字，即应填入“extends Car implements Emergency ”：空（4）要返回应急车辆对象的状态，即填入“this.isEmergency”;空 (5) 处为动态类型转换后的对象 (Emergency)v[i]; 空 (6)处为普通车辆对象 v[i] 。