201705程序员下午真题

第 1 题

阅读下列说明和流程图，填补流程图中的空缺，将解答填入答题纸的对应栏内。 
【说明】 
设有二维整数数组（矩阵）A[1:m,1:n],其每行元素从左到右是递增的，每列元素从上到下是递增的。以下流程图旨在该矩阵中需找与给定整数X相等的数。如果找不到则输出“false”;只要找到一个（可能有多个）就输出“True”以及该元素的下标i和j（注意数组元素的下标从1开始）。
例如，在如下矩阵中查找整数8，则输出为：True,4,1
      2    4    6     9
      4    5    9    10
      6    7   10   12
      8    9   11   13
流程图中采用的算法如下：从矩阵的右上角元素开始，按照一定的路线逐个取元素与给定整数X进行比较（必要时向左走一步或向下走一步取下一个元素），直到找到相等的数或超出矩阵范围（找不到）。

【流程图】

答案与解析

• 试题难度：较难
• 知识点：C程序设计>C程序设计
• 试题答案：
  （1）ipaddr
  （2）curval*10
  （3）p++
  （4）decNum++
  （5）decNum==4 && dotNum==3
• 试题解析：此题判断IPV4地址是否合法，主要是判断其每个十进制数的大小和总个数以及“.”个数来进行判别。
  首先用isdigital函数判断是否为十进制数，是则保留值。指针移到地址的下一个字符。
  每找到一个十进制数都需要和前一次找到的值进行组合，即前一次的结果要乘以10。
  每找完一个完整数字和“.”都需要记录，所以要有decNum++和dotNum++。
  最后，如果IP地址正确，则返回1。即：decNum=4和dotNum=3时成立。
  

第 3 题

阅读下列说明和C函数，填补C函数中的空缺，将解答填入答案纸的对应栏目内。
【说明】
字符串是程序中常见的一种处理对象，在字符串中进行子串的定位、插入和删除是常见的运算。
设存储字符串时不设置结束标志，而是另行说明串的长度，因此串类型定义如下：
typedef struct ﹛
     Char *str;      //字符串存储空间的起始地址
     int length;     //字符串长
     int capacity;    //存储空间的容量
﹜SString;

【函数1说明】
     函数indexStr（S,T,pos）的功能是：在S 所表示的字符串中，从下标pos开始查找T所表示字符串首次出现的位置。方法是：第一趟从S中下标为pos、T中下标为0的字符开始，从左往右逐个对于来比较S和T的字符，直到遇到不同的字符或者到达T的末尾。若到达T的末尾，则本趟匹配的起始下标pos为T出现的位置，结束查找；若遇到了不同的字符，则本趟匹配失效。下一趟从S中下标pos+1处的字符开始，重复以上过程。若在S中找到T，则返回其首次出现的位置，否则返回-1。
   例如，若S中的字符串为”students ents”,T中的字符串为”ent"，pos=0，则T在S中首次出现的位置为4。
【C函数1】
   int index Str（SString S ,SString T,int pos）
  {
     int i,j;
     if（S.length<1||T.length<1||S.length<pos+T.length-1）
         return-1;
     for（i=pos,j=0;i<S.length &&j<T.length;）{
          if （S.str[i]==T.str[j]）{
             i++;j++;
          }
          else{
               i=（  1   ）;j=0
          }
      }
     if （   2   ）return i -T.length;
         return -1;
}
【函数2说明】

函数 eraseStr（S，T}的功能是删除字符串S中所有与T相同的子串，其处理过程为：首先从字符串 S 的第一个字符（下标为0）开始查找子串T，若找到〈得到子串在S中的起始位置），则将串 S 中子串T之后的所有字符向前移动，将子串T覆盖，从而将其删除，然后重新开始查找下一个子串T，若找到就用后面的字符序列进行覆盖，重复上述过程，直到将S中所有的子串T删除。
例如，若字符串 S为 “12ab345abab678”、T为“ab”。第一次找到“ab”时（位置为2），将“345abab678”前移，S 中的串改为“12345abab678” ，第二次找到“ab”时（位置为 5）；将“ab678”前移，S中的串改为“12345ab678”，第三次找到“ab”时（位置为5）；将“678”前移 ，S中的串改为“12345678 ”。

答案与解析

• 试题难度：较难
• 知识点：C程序设计>C程序设计
• 试题答案：
  （1）i-j+1
  （2）j==T.length
  （3）*S,T,pos
  （4）i-T.length
  （5）S -＞length -T.length
• 试题解析：函数1为字符串匹配，算法为：先判断字符串S和T的长度，如果为空则不用循环，另外，如果字符串S的长度<字符串T的长度，那字符串S中也不能含有字符串T，也无需进行匹配。
  那当上述情况都不存在时，即需要进行循环。即从S的第一个字符开始，与T的第一个字符进行比较，如果相等，则S的第二个字符和T的第二字符进行比较，再相等就再往后移动一位进行比较，依次直到字符串T的结尾，也就是说j=T.length（数组的下标从0开始，最后一个是T.length-1，结束循环是j=T.length）。
  当某一个字符与T的字符不相等时，那么字符串S就应从下一个字符开始比较，此时i=i-j+1，（如果前面有匹配成功的话，i的值已经增加了j位，因此需要重新回到之前比较的位置的后一个字符进行比较，再次进行与T的第一个字符进行比较，此时j恢复初始值，j=0。
  函数2为字符串的删除运算。首先，要调用函数 indexStr，需要三个参数，字符串S、字符串T和pos。从函数2的调用Void eraseStr（SStringS,SStringT）可以看到，此处字符串S为指针变量，因此字符串前需使用。
  然后删除的字符串的位置为删除初始点的位置到其位置点+字符串T的长度，并将后面的字符串前移。而删除T字符串后，字符串S的总长度变化，需减去字符串T的长度。

第 4 题

阅读以下说明和C 函数，填补函数中的空缺，将解答填入答题纸的对应栏内。
【说明】
简单队列是符合先进先出规则的数据结构，下面用不含有头结点的单向循环链表表示简单队列。
函数EnQueue（Queue Q，KeyType new_elem） 的功能是将元素new_elem加入队尾。
函数DnQueue（Queue Q，KeyType *elem）的功能使将非空队列的队头元素出队（从队列中删除），并通过参数带回刚出队的元素。
用单向循环链表表示的队列如图 4-1 所示。

队列及链表结点等相关类型定义如下：
enum {ERROR, OK};
typedef int KeyType;
 
typedef struct    QNode{
      KeyType   data;
      Struct QNodenext;
}QNode,LinkQueue;
 
Typedef struct{
      int  size;
      Link:Queue rear;
}Queue;
 
【C函数】
 
int EnQueue(QueueQ,KeyType new_elem)
{   //元素new_elem 入队列
     QNodep;
     p=(QNode)malloc(sizeof(QNode));
     if（!p）
        return ERROR;
    p->data=new_elem;
    if（Q->rear）{
        p->next=Q->rear->next;
        （   1   ）;
     }
     else
         p->next=p;
     ﹙  2  ﹚;
     Q->size++;
    return OK;
}
 
int  DeQueue(QueueQ,KeyTypeelem)
{   //出队列
     QNodep;
     If(0＝＝Q->size)           //是空队列
         Return ERROR；
     p=（  3  ）;                    //令p指向队头元素结点
     *elem =p->data;
     Q->rear->next=（  4   ）;         //将队列元素结点从链表中去除
     if（（  5  ））                //被删除的队头结点是队列中唯一结点
        Q->rear=NULL;       //变成空队列
     free（p）;
     Q->size--;
     return OK;
}

答案与解析

• 试题难度：较难
• 知识点：C程序设计>C程序设计
• 试题答案：
  （1）Q→rear→next=p
  （2）Q→rear=p
  （3）Q→rear→next
  （4）p→next
  （5）Q→rear==p 或 Q→rear→next==p或p→next==p 或 Q→size==1 
• 试题解析：本题考查C语言指针与链表的知识，为入队列和删除队列问题。
  对于入队列，那么当队列Q不为空时，P的队尾t要指向原Q的队尾指向的元素，即：P->next=Q->rear->next，Q的队尾要指向p，即：Q→rear→next=p。当队列Q为空时，插入p元素，则p的队尾指向p自身，即：p→next=p，且整个队列Q的队尾也是p，即：Q→rear=p。
  对于队列删除元素p，先判断Q是否为空，为空队列则返回 ERROR;
   If(0＝＝q->size)           //是空队列
           Return ERROR；
  另p指向队头元素结点，队头元素结点可用Q→rear→next表示。此时，p转化为头结点，p出列，则需要Q的队尾指向p的下一个元素，因此第4空填：p→next。
  最后，判断被删除的队头结点是否是队列中的唯一结点，可采用：Q→rear==p 或 Q→rear→next==p或p→next==p或 Q→size==1等表示方法。

第 5 题

阅读以下说明和 Java程序，填补代码中的空缺，将解答填入答题纸的对应栏内。
【说明】
以下Java代码实现一个简单客户关系管理系统（CRM）中通过工厂（CustomerFactory ）对象来创建客户（Customer）对象的功能。客户分为创建成功的客户（RealCustomer）和空客户 （NullCustomer）。空客户对象是当不满足特定条件时创建或获取的对象。类间关系如图 5-1 所示。

abstract class Customer{
    protected String name;
    ( 1 ) boolean isNil();
    ( 2 ) String getName();
}
class RealCustomer ( 3 ) Customer{
    public RealCustomer(String name){ this.name=name; }
    public String getName(){ return name ; }
    public boolean isNil() { return false; }
}

class NullCustomer ( 4 ) Customer{
    public String getName(){ return "Not Available in Customer Database"; }
    public boolean isNil() { return true; }
}
class CustomerFactory {
    public String[] names = {"Rob","Joe","Julie"};
    public Customer getCustomer(String name) {
        for (int i = 0 ; i < names.length ; i++) {
            if (names[i].( 5 ) ){
                  return new RealCustomer(name);
            }
        }
     return ( 6 );
    }
}
public class CRM {
    public void getCustomer(){
         CustomerFactory ( 7 ) ;
         Customer customer1 = cf.getCustomer( "Rob" );
         Customer customer2 = cf.getCustomer( "Bob" );
         Customer customer3 = cf.getCustomer( "Julie" );
         Customer customer4 = cf.getCustomer( "Laura" );
         System.out.println( "Customers" );
         System.out.println( customer1.getName() );
         System.out.println( customer2.getName() );
         System.out.println( customer3.getName() );
         System.out.println( customer4.getName() );
   }
    public static void main (String[] args){
         CRM crm =new CRM();
         crm.getCustomer();
      }
}
/*程序输出为：
Customers
Rob
Not Available in Customer Database
Julie
Not Available in Customer Database
*/

答案与解析

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

  1）abstract
  2）abstract
  3）extends
  4）extends
  5）equals(name)
  6）new NullCustomer()
  7）cf=new CustomerFactory();
  

• 试题解析：

  本题考查Java程序设计客户关系管理系统。
  1）abstract 定义抽象方法
  2）abstract
  3）extends 继承Customer类
  4）extends
  5）equals(name) 判断名字是否在数组集合内
  6）new NullCustomer() 当不满足条件时创建一个空对象
  7）cf=new CustomerFactory(); 实例化对象cf
  

第 6 题

阅读下列说明和C++代码，填补代码中的空缺，将解答填入答题纸的对应栏内。
【说明】
     以下C++代码实现一个简单客户关系管理系统（CRM）中通过工厂（Customerfactory）对象来创建客户（Customer）对象的功能。客户分为创建成功的客户（realCustomer）和空客户（NullCustomer）。空客户对象是当不满足特定条件时创建或获取的对象。类间关系如图6-1所示。

图6-1

【C++代码】

include<iostream>

include<string>

using namespace std;
 
class Customer｛
protected:
     string name;
public:
   （   1   ） bool isNil()=0;
   （   2   ） string getName()=0;
};
 
class RealCustomer (   3   )｛
Public:
     realCustomer(string name)｛this->name=name;﹜
     bool isNil()｛ return false;  ﹜  
     string getName()｛ return name;  ﹜
};
class NullCustomer (    4   ) ｛
public:
     bool isNil()｛  return true; ﹜
     string getName()｛ return "Not Available in Customer Database"; ﹜
};
 
class Customerfactory｛
public:
    string names［3］=｛"rob", "Joe","Julie"};
public:
    CustomergetCustomer(string name)｛
       for (int i=0;i<3;i++)｛
           if （names[i].(   5   ) )｛
               return new realCustomer(name);
            }
        }
        return (   6   );
    }
};
 
class CRM｛
public:
    void getCustomer()｛
        Customerfactory(   7   );
        Customercustomer1=cf->getCustomer("Rob");
        Customercustomer2=cf->getCustomer("Bob");
        Customercustomer3=cf->getCustomer("Julie");
        Customercustomer4=cf->getCustomer("Laura");
 
        cout<<"Customers"<<endl;
        cout<<Customer1->getName()<<endl;  delete customer1;
        cout<<Customer2->getName()<<endl;  delete customer2;
        cout<<Customer3->getName()<<endl;  delete customer3;
        cout<<Customer4->getName()<<endl;  delete customer4;
        delete cf;
     }
};
 int main()｛
      CRMcrs=new CRM();
      crs->getCustomer();
      delete crs;
      return 0;
}
 
/程序输出为：
Customers
rob
Not Available in Customer Database
Julie
Not Available in Customer Database
*/

答案与解析

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

  1）virtual
  2）virtual
  3）:public Customer
  4）:public Customer
  5）compare(name)==0
  6）new Null Customer()
  7）cf=New CustomerFactory()
  

• 试题解析：

  本题考查使用C++代码实现实际问题。
  在C++中，动态绑定是通过虚函数来实现的。此题中用到了虚函数，所以要在成员函数原型前加一个关键字virtual。
  类RealCustomer和类NullCustomer是类Customer的派生类，因此3、4空都填public Customer。
  进行对比数据库中的人名compare(name)==0
  第6空与前面语句是相反的，一个是返回new RealCustomer(name)，那么此处应填：new Null Customer()
  第7空，用工厂创建对象，cf=New CustomerFactory();