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

一、问答题

1、试题一（共 20 分）

阅读下列说明和图，回答问题 1 至问题 3，将解答填入答题纸的对应栏内。

【说明】

设有二维整数数组（矩阵）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 进行比较（必要时向左走一步或向下走一步取下一个元素），直到找到相等的数或超出矩阵范围（找不到）。

【流程图】

【问题】该算法的时间复杂数是（）

供选择答案：A.O（1） B.O（m+n） C.（m*n） D,O（m²+n²）

参考答案：

（1）n

（2）j-1→j

（3）i+1→I

（4）j

（5）C

解析：

该算法的时间复杂度取决于矩阵的大小（行数m和列数n）。在最坏情况下，可能需要遍历整个矩阵的每个元素，即需要进行mn次比较操作。因此，该算法的时间复杂度是O(mn)。

2、试题二（共 15 分）

阅读下列说明和 C 函数，填补函数中的空缺，将解答填入答案纸的对应栏目内。

【说明】

函数 isLegal（char*ipaddr）的功能是判断以点分十进制数表示的 iPV4 地址是否合法。参数 ipadddr 给出表示 iPV4 地址的字符串的首地址，串中仅含数字字符和“.”。若 iPV4 地址合法则返回1，否则反馈 0.判定伟合法的条件是：每个十进制数的值位于整数区间[0,25]，两个相邻的树之间用“.”分隔，共 4 个数、3 个“.”。；例如，192.168.0.15、1.0.0.1 是合法的，192.168.1.256、1.1..1是不合法的。

【函数】

int isLegal （char*ipaddr）

﹛

int flag;

int cur Val; ／／curVal 表示分析出的一个十进制数

int decNum=0,dotNum=0; ／／decNum 用于记录十进制数的个数

／／dotNum 用户记录点的个数

Char*p=（）

for（;*p;p++） ﹛

curVal=0;flag=0

While （isdigit（*p））﹛ ／／判断是否伟数字字符

CurVal=（）+*p-′0′;

（）

flag=1;

﹜

if（curVal>255）﹛

return 0;

﹜

if （flag）﹛

（）

﹜if（*p==′.′）

dotNum++;

﹜

﹜

if （）﹛

return 1；

﹜

return 0;

﹜

参考答案：

（1）ipaddr

（2）curval*10

（3）p++

（4）decNum++

（5）decNum==4 && dotNum==3

解析：

这是一个关于判断IPv4地址合法性的函数。根据题目描述和函数结构，我们可以逐步分析并填补空白。

1.（1）处需要填写的是函数参数ipaddr的地址，因为我们需要遍历这个地址指向的字符串。

2.（2）处表示在读取数字字符后，需要将当前值乘以10以便与前面的数字组合。例如，当读取到"19"时，第一次乘完后是19，第二次乘完后是190。所以填写curVal *= 10。

3.（3）处是为了移动到字符串的下一个字符，所以填写p++。

4.（4）处是为了记录十进制数的个数，每找到一个完整的十进制数就增加一次计数，所以填写decNum++。

5.（5）处是判断条件，IPv4地址由4个十进制数组成，并且由3个点分隔，所以填写decNum == 4 && dotNum == 3。

函数的流程大致是这样的：首先检查输入字符串的第一个字符是否为数字，如果是则继续读取并与之前的数字组合，同时增加十进制数的计数。如果遇到一个点"."，则增加点的计数。最后，如果找到了四个十进制数和三个点，并且所有的十进制数都在0到255之间，那么返回1表示IP地址合法，否则返回0表示不合法。

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 indexStr（SString S ,SString T,int pos）

﹛

int i,j:

if（S.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=（）;j=0

﹜

﹜

if （）return i -T.length;

return-1;

﹜

【函数 2 说明】

函数 eraseS 位（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 函数 2】

void eraseStr（SString*S,SStringT）

﹛

int i;

int pos;

if （S->leght<1||T.length<1||S->length<T.length）

return;

pos=0

for（;;）﹛

／／调用 indexStr 在 S 所表示串的 pos 开始查找 T 的位置

pos=indexStr（）;

if（pos＝=-1） ／／S 所表示串中不存在子串 T

return;

for（i=pos+T.length;i<S->length;i++） ／／通过覆盖来删除自串 T

S->str[（）]=S->str[i];

S->length=（）; ／／更新 S所表示串的长度

﹜

﹜

参考答案：

（1）i+1

（2）j==T.length

（3）S,T,pos

（4）i-T.length

（5）S -＞length -T.length

解析：

关于这道题目给出的答案解析：
（一）关于函数indexStr的解析：
首先判断字符串S和T的长度是否合法以及起始位置是否合法，如果不合法则直接返回-1表示未找到子串。接着开始循环匹配字符串S和T中的字符，如果当前字符匹配成功则继续向后匹配下一个字符；如果当前字符匹配失败则重新开始匹配并将起始位置更新为下一个字符的位置。循环结束后判断是否已经成功匹配完T的所有字符并返回结果。
（二）关于函数eraseStr的解析：
函数eraseStr的功能是删除字符串S中所有与T相同的子串。处理过程为先调用indexStr函数找到子串T在S中的起始位置，然后通过覆盖操作删除子串T并更新字符串S的长度。需要注意的是在删除操作完成后需要再次调用indexStr函数查找下一个子串T的位置并进行删除操作，直到删除所有子串T为止。函数实现中还需要注意正确处理覆盖操作以及更新字符串S的长度。
由于题目没有给出具体的代码实现要求，因此无法给出具体的代码答案。需要根据题目要求和函数说明自行完成代码填写。

4、试题四（共 15 分）

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

【说明】

简单队列是符合先进先出规则的数据结构，下面用不含有头结点的单向循环链表表示简单队列。

函数 enqueue（queue *q，KeyType new_elem） 的功能是将元素new_elem 加入队尾。

函数 Dnqueue（queue *q，KeyType *elem）的功能使将非空队列的队头元素出队（从

队列中删除），并通过参数带回刚出队的元素。

用单向循环链表表示的队列如图 4-1 所示。

图 4-1 单向循环链表表示的队列示意图

队列及链表结点等相关类型定义如下:

enum {errOr， OK};

typedef int KeyType;

typedef struct qNode﹛

KeyType data;

Struct qNode*next;

﹜qNode，*Linkqueue;

Typedef struct﹛

int size;

Link:queue rear;

}queue;

【C 函数】

int enqueue（queue*q,KeyType new_elem）

﹛ ／／元素 new_elem 入队列

qNode*p;

P=（qNode*）malloc（sizeof（qNode））;

if（!p）

return errOr;

P->data=new_elem;

if（q->rear）﹛

P->next=q->rear->next;

（）;

﹜

else

P->next=p;

﹙﹚;

q->size++;

return OK;

﹜

int Dequeue（queue*q,KeyType*elem）

﹛ ／／出队列

qNode*p;

if（0＝＝q->size） ／／是空队列

return errOr；

P=（）; ／／令 p 指向队头元素结点

*elem =p->data;

q->rear->next=（）; ／／将队列元素结点从链表中去除

if（（）） ／／被删除的队头结点是队列中唯一结点

q->rear=NULL ／／变成空队列

free（p）;

q->size--;

return OK;

﹜

参考答案：

（1）Q→rear→next=p

（2）Q→rear=p

（3）Q→rear→next

（4）p→next

（5）Q→rear==p 或 Q→rear→next==p→next 或 Q→size==1 

解析：

对于enqueue函数，当队列不为空时，新元素p的next应该指向原队列的队尾元素的后继节点，即Q→rear→next。同时，为了保证队列的循环性，需要将Q的队尾rear指向新元素p，即Q→rear=p。这样新元素就被正确地插入到了队列的尾部。

对于Dequeue函数，首先判断队列是否为空，如果为空则直接返回错误。如果不为空，则通过Q→rear→next获取队头元素结点p。然后，通过q→rear→next=p→next将队尾的下一个元素指向原来队头元素的下一个节点，从而删除队头元素。最后，判断被删除的队头结点是否是队列中的唯一结点，如果是的话，将队列的队尾设置为空，并释放被删除节点的内存。这一过程可以通过多种方式判断，如Q→rear==p 或 Q→rear→next==p→next 或 Q→size==1等。

5、试题五（共 15 分）

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

【说明】

以下 Jave 代码实现一个简单客户关系管理系统（CrM） 中通过工厂 （Customerrfactory ）对象来创建客户（Customer） 对象的功能。客户分为创建成功的客户 （realCustomer） 和空客户（NullCustomer） 。空客户对象是当不满足特定条件时创建或获取的对象。类间关系如图 5-1 所示。

【Java 代码】

Abstract class Customer﹛

Protected String name;

（）boolean isNil（）

（）String getName（）;

﹜

Class realCustomer （）Customer﹛

Public realCustomer（String name ）﹛ return false; ﹜

﹜

Class NullCustomer（）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].（））﹛

return new realCusωmer（name）;

﹜

﹜

return （）

﹜

﹜

Public class CrM﹛

Public viod get Customer（）﹛

Customerfactory（）

Customer customer1-cf.getCustomer（″rob″）;

Customer customer2=cf.getCustomer（″rob″）;

Customer customer3= cf.getCustomer（″Julie″）;

Customer customer4= cf.getCustomer（″Laura″）;

System.out.println（″customer1.getName（））;

System.out.println（″customer2getName（））;

System.out.println（″customer3.getName（））;

System.out.println（″customer4.getName（））;

﹜

Public static viod main （String[]arge）﹛

CrM crm =new CrM（）;

Crm,getCustomer（）;

﹜

﹜

／*程序输出为：

Customer

rob

Not Available in Customer Database

Julie

Not Available in Customer Datable

*／

int main（）﹛

CrM*crs=newCrM（）;

Crs->getCustomer（）;

Crs->getCustomer（）;

Delete crs;

return（）;

﹜

／*程序输出为：

Customer

rob

Not Available ini Customer Database

Julie

Not Available in Customer Database

参考答案：

1）public abstract

2) public abstract

3)extends

4)extends

5)equals(name)

6)new Null Customer()

7) cf=New CustomerFactory();

解析：

本题考察Java程序设计中客户关系管理系统的实现。根据题目描述和提供的代码片段，我们可以进行以下分析：

1. Customer 是一个抽象类，其中包含两个抽象方法 isNil() 和 getName()。因此，第一个和第二个空应该填写 “public abstract”，用于定义这两个抽象方法。
2. realCustomer 和 NullCustomer 是 Customer 的子类，分别表示创建成功的客户和空客户。它们应该使用 “extends” 关键字继承自 Customer 类。所以第三个和第四个空应该填写 “extends”。
3. 在 Customerfactory 类的 getCustomer 方法中，我们需要判断名字是否存在于 names 数组中。因此，第五个空应该填写 “equals(name)”，用于进行字符串比较。
4. 当不满足条件（即名字不在数组中）时，应该创建一个 NullCustomer 对象。因此，第六个空应该填写 “new NullCustomer()”。
5. 在 CrM 类的 getCustomer 方法中，需要实例化 Customerfactory 对象。因此，第七个空应该填写 “cf = new CustomerFactory()”。

根据以上分析，我们可以填补代码中的空缺，并得出最终的答案。

6、试题六（共 15 分）

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

【说明】

以下 C++代码实现一个简单客户关系管理系统（CrM）中通过工厂（Customerfactory）对象来创建客户（Customer）对象的功能。客户分为创建成功的客户（realCustomer）和空客户（NullCustomer）。空客户对象是当不满足特定条件时创建或获取的对象。类间关系如图6-1 所示。

【C++代码】

#include<iostream>

#include<string>

using namespace std；

class Customer｛

protected:

string name；

public:

（1） boll 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:

Customer*getCustomer（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）；

Customer*customer1=cf->getCustomer（〝rob〞）；

Customer*customer2=cf->getCustomer（〝Bob〞）；

Customer*customer3=cf->getCustomer（〝Julie〞）；

Customer*customer4=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（）｛

CrM*crs=new CrM（）；

crs->getCustomer（）；

delete crs；

return 0；

﹜

/*程序输出为：

Customers

rob

Not Available in Customer Database

Julie

Not Available in Customer Database

*/

参考答案：

1)virtual

2)virtual

3):public Customer

4):public Customer

5)compare(name)==0

6)new Null Customer()

7)cf=New CustomerFactory();

解析：

本题考察的是如何使用C++代码解决实际问题。针对题目中的客户关系管理系统（CrM）的实现，以下是详细的解析：

1. 在Customer类中，isNil()和getName()函数需要定义为虚函数（virtual），因为这两个函数将在派生类中被重写，并且需要根据对象的实际类型来调用相应的函数。所以，第一和第二个空都填virtual。
2. realCustomer和NullCustomer是Customer类的派生类，因此第三个和第四个空都填public Customer。这意味着它们继承自Customer类。
3. 在Customerfactory类中的getCustomer()函数中，需要对比数据库中的名字和传入的参数名字是否匹配。假设存在一个函数compare(name)用于比较名字是否相同，那么第五个空填compare(name)==0。当名字匹配时，返回一个新的realCustomer对象。
4. 当在getCustomer()函数中循环遍历名字数组后没有找到匹配的名字时，应该返回一个新的空客户对象。因此第六个空填new NullCustomer()。
5. 在CrM类中，创建了一个Customerfactory对象cf。因此第七个空填对象的创建语句，即cf = new CustomerFactory();。

最后的程序输出解释了为什么某些客户返回的是"Not Available in Customer Database"，因为当名字不匹配时，返回的是空客户对象，其getName()函数返回的是"Not Available in Customer Database"。

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