201511程序员下午真题

第 1 题

阅读以下说明和流程图，填补流程图中的空缺，将解答填入答题纸的对应栏内。
【说明】
下面流程图的功能是：在给定的一个整数序列中查找最长的连续递增子序列。设序列存放在数组 A1:n中，要求寻找最长递增子序列 A[K: K+L-1] (即A[K]<A[K+1]<…<A[K+L-1])。流程图中，用 Kj 和Lj 分别表示动态子序列的起始下标和长度，最后输出最长递增子序列的起始下标 K 和长度 L。
例如，对于序列 A={1 ，2，4，4 ，5，6，8，9，4，5，8}，将输出K=4， L=5。

【流程图】

本题考查程序员在设计算法，理解并绘制程序流程图方面的能力。
本题的目标是：在给定的一个整数序列中查找最长的连续递增子序列。查找的方法是：对序列中的数，从头开始逐个与后面邻接的数进行比较。若发现后面的数大于前面的数，则就是连续递增的情况：若发现后面的数并不大，则以前查看的数中，要么没有连续递增的情况，要么连续递增的情况已经结束，需要再开始新的查找。
为了记录多次可能出现的连续递增情况，需要动态记录各次出现的递增子序列的起始位置（数组下标Kj）和长度 （Lj）。为了求出最大长度的递增子序列，就需要设置变量L和K。保存迄今为止最大的Lj及其相应的Kj。正如打擂台一样，初始时设置擂主 L=1，以后当 Lj>L 时，就将 Lj放到 L中，作为新的擂主。擂台上始终是迄今为止的连续递增序列的最大长度。而 Kj则随 Lj→L 而保存到 K 中。
由于流程图中最关键的步骤是比较 A[i]与 A[i+1].因此对i的循环应从1到n-1，而不是1到 n。最后一次比较应是“A[n-1]<A[n]？”。因此（1）处应填 n-1 。
当 A[i]<A[i+1]成立时，这是递增的情况。此时应将动态连续递增序列的长度增1，因此（2）处应填写 Lj+1→Lj。
当A[i]<A[i+1]不成立时，表示以前可能存在的连续递增已经结束。此时的动态长度Lj应与擂台上的长度 L 进行比较。即（3）处应填 Lj >L。
当 Lj>L 时，则 Lj将做新的擂主 （Lj→L）。同时执行Kj→K。所以（4）处应填Kj 。
当 Lj>L 不成立时，L 不变，接着要从新的下标 i+1 处开始再重新查找连续递增子序列。因此 （5）处应填 i+1。长度也要回到初始状态1。
循环结束时，可能还存在最后一个动态连续子序列（从下标码那里开始有长度的Lj子序列）没有得到处理。因此还需要再打一次擂台，看是否超过了以前的擂主长度。一旦超过，还应将其作为擂主，作为查找的结果。

（1） a[j]> pivot 或 a[j]>= pivot 或等价形式
（2） a[i] <= pivot 或 a[i] < pivot 或等价形式
（3） quicksort(a ,i) 或 quicksort(a,j) 或等价形式
（4） quicksort(a+i+1，n-i-1) 或 quicksort(a+j+1，n-j -1) 或等价形式
注： a+i+1可表示为 &a[i+1] ，a+j+1可表示为 &a[j+1]
（5） arr，sizeof(arr)/sizeof(int)
注： sizeof(arr)/sizeoftint) 可替换为 8

本题考查 C 程序设计基本技能及快速排序算法的实现。
题目要求在阅读理解代码说明的前提下完善代码，该题目中的主要考查点为运算逻辑和函数调用的参数处理。
程序中实现快速排序的函数为 quicksort，根据该函数定义的首部，第一个参数为数组参数，其实质是指针，调用时应给出数组名或数组中某个元素的地址：第二个参数为整型参数，作用为说明数组中待排序列（或子序列）的长度。
快速排序主要通过划分来实现排序。根据说明，先设置待排序列（或子序列，存储在数组中）的第一个元素值为基准值。划分时首先从后往前扫描，即在序列后端找出比基准值小或相等的元素后将其移到前端，再从前往后扫描，即在序列前端找出比基准值大的元素后将其移动到后端，直到找出基准值在序列中的最终排序位置。再结合注释，空（1）处应填入" a[j]> pivot "，使得比基准值大者保持在序列后端。空 （2）处应填入"a[i]<= pivot"，使得不大于基准值者保持在前端。
在完成 1 次划分后，基准元素被放入a[i]，那么分出来的左子序列由a[0]-a[i-1]这 i 个元素构成，右子序列由 a[i+1] ～a[n-1]构成，接下来应递归地对左、右子序列进行快排。 因此，结合注释，空（3）应填入 "quicksort(a,i)" 或其等价形式，以对左子序列的 i 个元素进行快排，也可以用 &a[0]代替其中的a，它们是等价的，a 与&a[0]都表示数组的起始地址。
空 （4） 所在代码实现对右子序列进行快排。右子序列由 a[i+1] ～a[n-1]构成，其元素个数为 n-1-(i+1)+1，即 n-i-1 ，显然元素a[i+1]的地址为& a[i+1]或 a+i+1 ，所以空（4） 应 填入 "quicksort(a+i+1，n-i-1)" 或其等价形式。
在 main 函数中，空（5） 所在代码首次调用函数 quicksort 对 main 函数中的数组 arr进行快排，因此应填入 "arr，sizeof(arr)/sizeof(int) "或其等价形式。

阅读以下说明和 C 代码，填补代码中的空缺，将解答填入答题纸的对应栏内。
【说明】
函数 GetListElemPtr(LinkList L，int i)的功能是查找含头结点单链表的第i个元素。若找到，则返回指向该结点的指针，否则返回空指针。
函数DelListElem(LinkList L，int i，ElemType *e) 的功能是删除含头结点单链表的第 i个元素结点，若成功则返回 SUCCESS ，并由参数e 带回被删除元素的值，否则返回ERROR 。
例如，某含头结点单链表 L 如图 4-1 （a） 所示，删除第 3 个元素结点后的单链表如 图 4-1 （b）所示。 

图4-1

define  SUCCESS   0

define  ERROR    -1

 
typedef int Status;
typedef int ElemType;
 
链表的结点类型定义如下:
 
typedef struct Node{
                ElemType data;
                struct Node  next;
}Node ,LinkList;
【C 代码】
LinkList  GetListElemPtr(LinkList  L ，int  i)
{ / L是含头结点的单链表的头指针，在该单链表中查找第i个元素结点:
     若找到，则返回该元素结点的指针，否则返回NULL
/
          LinkList  p;
          int   k;      /用于元素结点计数/
 
          if  (i<1  ∣∣ !L  ∣∣  !L->next)  return NULL;
 
          k  =  1;   P  =  L->next;          / 令p指向第1个元素所在结点/
          while (p &&             （1）       ) {  /查找第i个元素所在结点/
                          （2）       ;  ++k;
          }
          return p;
}
 
Status  DelListElem(LinkList  L ，int i ，ElemType  e)
{   /在含头结点的单链表L中，删除第i个元素，并由e带回其值/
 
          LinkList  p，q;
 
          /令p指向第i个元素的前驱结点/
          if (i==1)
                     （3）      ；
          else
                p = GetListElemPtr(L ，i-1);
 
          if (!p ∣∣ !p->next)       return ERROR; /不存在第i个元素/
 
          q =      (4)     ；            /令q指向待删除的结点/
          p->next = q->next;     /从链表中删除结点/
                 (5)        ；              /通过参数e带回被删除结点的数据*/
          free(q);
          return  SUCCESS;
}

答案与解析

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

  （1） k<i
  （2）p = p->next
  （3）p=L
  （4）p->next
  （5）*e = q->data
  

• 试题解析：
        本题考查 C 语言的指针应用和运算逻辑。
        本问题的图和代码中的注释可提供完成操作的主要信息，在充分理解链表概念的基
  础上填充空缺的代码。
        函数GetListElemPtr(LinkList  L，int  i)的功能是在L为头指针的链表中查找第 i 个元素，若找到，则返回指向该结点的指针，否则返回空指针。描述查找过程的代码如下，其中k 用于对元素结点进行计数。
  
        上述代码执行时，k 的初始值为1，同时 p 指向第一个元素结点。当找到第 i个元素结点时，k 应等于 i ，尚未到达第i个结点时，k小于i。因此，空（1）处应填入"k<i" 或其等价形式，使得没有达到第i个结点时继续查找。空 （2）处应填入 "p=p->next"，从而使得指针 p 沿着链表中的结点向第i个结点移动。

  函数DelListElem(LinkList L，int i，ElemType*e) 的功能是删除含头结点单链表的第i个元素结点，若成功则返回SUCCESS，并由参数e 带回被删除元素的值，否则返回ERROR。
  根据注释，空（3）所在语句需要指向第一个结点之前的结点（即头结点），显然此处应填入"p=L"。
  空 （4）所在语句令 q 指向待删除的结点，由于之前已经令 p 指向待删除结点的前驱结点，显然，此空应填入" p->next"。
  空 （5）所在语句通过参数 e 带回被删除结点的数据，由于此时只能通过指针 q 找到被删除的结点，所以应填入"*e= q->data"。
  

第 5 题

阅读以下说明和 C++代码，填补代码中的空缺，将解答填入答题纸的对应栏内。
【说明】
在股票交易中，股票代理根据客户发出的股票操作指示进行股票的买卖操作。其类图如图5-1所示，相应的c++代码附后。

图5-1  类图

【C++代码】

include  <iostream>

include  <string>

include  <vector>

using namespace std;
class Stock  {
private:
     string name;   int quantity;
public:
     Stock(string  name ，int  quantity)    {    this->name= name;this->quantity
     =  quantity;   }
     void buy()  { cout<<" [买进]股票名称: "<< name <<  "，数量: "<< quantity <<
     endl;}
     void sell()  { cout<<" [卖出]股票名称: " << name  <<  "，数量:"<< quantity
     <<endl;  }
};
 
class Order  {
public:
     virtual  void execute()  =  0;
};
 
classBuyStock:         (1)  {
private:
     Stock stock;
public:
     BuyStock(Stock stock)   {      (2)   =    stock; }
     void  execute()   {    stock->buy () ;  }
};
//类SellStock的实现与BuyStock类似，此处略
 
class  Broker   {
private:
     vector < Order>   orderList;
public:
     void  takeOrder(    (3)      order)   {  orderList.push_back(order);}   
 
     void  placeOrders()    {
         for (int i=0; i<orderList.size(); i++)  {      (4) -> execute () ; }
         orderList.clear();
     }
}；
class  StockCommand  {
public:
     void main ()    {
         Stock aStock  =  new  Stock("股票 A" ，10);
         Stock bStock  =  new  Stock("股票 B" ，20);
         Order buyStockOrder   =  new  BuyStock(aStock);
         Order sellStockOrder  =  new  SellStock(bStock);
         Broker broker   =  new  Broker();
         broker->takeOrder(buyStockOrder);
         broker->takeOrder(sellStockOrder);
         broker->    (5)     () ;
     }
};
int main()   {
     StockCommand* stockCommand  =  new  StockCommand();
     stockCommand->main();
     delete stockCommand;
}

答案与解析

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

  （1）public Order
  （2）this->stock或(*this)stock
  （3）Order*
  （4）orderList[i]或*(orderList+i)
  （5）placeOrders
  

• 试题解析：本题考查C++语言程序设计能力，涉及类、对象、函数的定义和相关操作。要求考生根据给出的案例和代码说明，认真阅读理清程序思路，然后完成题目。
  先考查题目说明，在股票交易中，股票代理根据客户发出的股票操作指示进行股票的买卖操作。根据说明进行设计，题目说明中给出了类图。涉及到股票(Stock)、股票代理（Broker) 、股票操作指示(StockCommand)、买卖股票(Odrer接口、BuyStock与SellStock类)等类以及相关操作 。
  Stock类定义了两个函数buy()和sell()，分别实现买和卖的操作。在构造函数中接收参数name 和quantity，分别表示买卖股票的名称和数量，对当前所创建对象中的name和quantity赋值，用this表示区别当前对象，所以构造函数为:
  Stock(string  name ，int  quantity)    { this->name  =  name;
  this->quantity = quantity;
  }
  Order虚类声明纯虚函数 execute(): virtual void execute()= 0;表示执行股票交易(即买和卖)的函数原型。
  BuyStock继承Order，构造函数接收参数stock，实现函数execute()，进行股票买入，stock->buy()。ellStock和BuyStock类似，继承Order，构造函数接收参数stock，实现函数execute()，进行股票卖出，stock->sell()。
  Broker类实现接受客户的买卖指示tackOrder()，接收BuyStock或者SellStock的实例，BuyStock和SellStock均是Order的子类，所以BuyStock和SellStock的实例也是Order ，因此tackOrder()所接收的参数用Order类型。接收到买卖指示之后，存入
  vector<Order>类型的orderList中，即orderList.push_back(order)。placeOrders()函数是实现将所有买卖股票的指示进行实际买入和卖出操作，即采用for循环，对每个orderList中的Stock实例，调用在BuyStock和SellStock中实现的execute()加以执行。
  for  (int i = 0; i < orderList.size();  i++)  {    orderList[i]  -> execute();}
  StockCommand主要是根据操作指示进行股票交易，实现为一个函数main()，其中创建欲进行交易的股票对象aStock和bStock，创建买aStock卖bStock股票的对象buyStockOrder和sellStockOrder对象:
  Order buyStockOrder =new BuyStock(aStock);
  Order sellStockOrder =new SellStock(bStock);
  再创建股票代理Broker类的对象broker，并接收买卖股票的指示:
  broker->takeOrder(buyStockOrder);
  broker->takeOrder(sellStockOrder);
  最后将所有买卖指示用placeOrders()下执行命令:
  broker-> placeOrders  ();
  主控逻辑代码在main()函数中实现。在main()函数中，先初始化StockCommand类的对象指针 stockCommand，代码为:
  StockCommand stockCommand = new StockCommand();
  即生成一个股票指示，并调用其main()函数启动股票交易，即调用stockCommand的main()函数，实现股票的买卖指示的创建和执行。主控main()函数中，使用完数组对象之后，需要用delete操作释放对象，对stockCommand对象进行删除，即
  delete stockCommand;
  因此，空(1)需要表示继承Order类的"public Order”：空(2)需要表示当前对象的stock属性，填入" this->stock "或"(this).stock"; 空(3)需要填入BuyStock和SellStock均能表示的父类"Order”;空(4)需要orderList中每个对象指针调用execute()，即填入"orderList[i] "或."*(orderList+i)"; 空(5)处为调用"placeOrders()"来下达执行命令。

第 6 题

阅读以下说明和 Java 代码，填补代码中的空缺，将解答填入答题纸的对应栏内。
【说明】
在股票交易中，股票代理根据客户发出的股票操作指示进行股票的买卖操作。其类图如图 6-1 所示。相应的Java 代码附后。

图6-1  类图

【 Java 代码】
      import  java.util.ArrayList;
      import  java.util.List;
    
 class  Stock  {
          private String name;
          private  int  quantity;
          public   Stock(String  name ，int  quantity)    {
              this.name = name;    this.quantity    =   quantity;
          }
          public void  buy() {  System.out.println("[ 买进]: " + name   + "，数量:"
          + quantity);}
          public  void  sell() {  System.out.println("[ 卖出]: " + name  +  "，数量:"
          + quantity);}
      }
      interface Order  {
          void  execute();
      }
      class BuyStock      (1)  Order  {
          private   Stock   stock;
         
public  BuyStock(Stock   stock) {   (2)  = stock; }
          public  void  execute()   {  stock.buy();}
      }
 
//类SellStock实现和BuyStock 类似，略
   
  class  Broker  {
          private  List<Order>  orderList  =  new  ArrayList<Order>();
          public  void  takeOrder(   (3)    order) { orderList.add(order); }
          public void  placeOrders() {
               for  (         (4)   order  : orderList)   {      order.execute();   }
               orderList.clear();
          }
      }
     
public  class  StockCommand    {
          public   static  void  main(String[]   args)    {
               Stock aStock = new  Stock("股票 A" ，10);
               Stock bStock = new  Stock("股票 B" ，20);
              
               Order  buyStockOrder  = new  BuyStock(aStock);
               Order  sellStockOrder  =  new  SellStock(bStock );
              
               Broker  broker  =  new  Broker();
               broker.takeOrder(buyStockOrder);
               broker.takeOrder(sellStockOrder);
               broker.    (5) ;
          }
      }

答案与解析

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

  （1）implements
  （2）this.stock
  （3）Order
  （4）Order
  （5）placeOrders()
  

• 试题解析：

  本题考查 Java 语言程序设计的能力，涉及类、对象、方法的定义和相关操作。要求考生根据给出的案例和代码说明，认真阅读理清程序思路，然后完成题目。
  先考查题目说明，在股票交易中，股票代理根据客户发出的股票操作指示进行股票的买卖操作。根据说明进行设计，题目说明中给出了类图。涉及到股票（Stock） 、股票代理 （Broker） 、股票操作指示（StockCommand） 、买卖股票（Order接口、BuyStock与SellStock类）等类以及相关操作。
  Stock类定义了两个操作buy()和sell()，分别实现买和卖的操作。在构造函数中接收参数name和quantity，分别表示买卖股票的名称和数量，对当前所创建对象中的name和quantity赋值，用this表示区别当前对象，所以构造器为：
  

             public  Stock(String  name ，int  quantity)   {
                       this.name = name;
                       this.quantity = quantity;
             }
  Order接口声明接口execute()，表示执行股票交易（即买和卖）方法接口。
  BuyStock实现接口Order: class BuyStock implements Order ，构造器接收参数stock，实现方法execute()，进行股票买入，stock.buy()。SellStock和BuyStock类似，实现接口Order，构造器接收参数stock，实现函数execute()，进行股票卖出，stock.sell()。
  Broker 类实现接收客户的买卖指示tackOrder()，接收BuyStock或者SellStock的实例，BuyStock和SellStock均是 Order的实现类，所以BuyStock和SellStock的实例也是Order类型，因此tackOrder()所接收的参数用Order类型。接收到买卖指示之后，存入List<Order>类型(具体对象类型为Arr ayList<Order> )的orderList 中:
                   orderList.push_back(order);
  placeOrders()函数是实现将所有买卖股票的指示进行实际买入和卖出操作，即采用for循环，Java自1.5起支持岛reach循环，对每个orderList中的Stock实例，调用在BuyStock和SellStock中实现的execute()加以执行。
   
                  for   (Order  order  :  orderList)   {
                         order.execute()；
                  }
  StockCommand主要是根据操作指示进行股票交易，主控逻辑代码实现在main()方法中，其中创建欲进行交易的股票对象aStock和bStock，创建买aStock卖bStock股票的对象buyStockOrder和sellStockOrder对象:
             Order buyStockOrder = new BuyStock(aStock)；
             Order  sellStockOrder  =  new  SellStock(bStock)；
  再创建股票代理Broker类的对象broker，并接收买卖股票的指示:
          broker.takeOrder(buyStockOrder)；
          broker.takeOrder(sellStockOrder)；
  最后将所有买卖指示用 placeOrders()下执行命令:
         broker.placeOrders   ()；
  因此，空(1)需要表示实现Order接口的关键字implements; 空(2)需要表示当前对象的stock属性， this.stock;  空(3)需要BuyStock和SellStock均能表示的所实现的接口类型Order; 空(4)需要orderList中每个对象的类型Order 并能调用 execute();空(5)处为调用placeOrders()。