2017上半年程序员考试真题及答案-下午卷.doc
2017上半年程序员考试真题及答案-下午卷试题一（共 20 分）阅读下列说明和图，回答问题 1 至问题 3，将解答填入答题纸的对应栏内。【说明】设有二维整数数组（矩阵）A1:m,1:n,其每行元素从左至右是递增的，每列元素从上到下是递增的。以下流程图旨在该矩阵中需找与给定整数 X 相等的数。如果找不到则输出“false”;只要找到一个（可能有多个）就输出“True”以及钙元素的下标 i 和 j（注意数组元素的下标从 1 开始）。例如，在如下矩阵中查找整数 8，则输出伟：True,4,12 4 6 94 5 9 106 7 10 128 9 11 13流程图中采用的算法如下：从矩阵的右上角元素开始，按照一定的路线逐个取元素与给定整数 X 进行比较（必要时向左走一步或向下走一步取下一个元素），直到找到相等的数或超出矩阵范围（找不到）。【流程图】【问题】该算法的时间复杂数是（）供选择答案：A.O（1） B.O（m+n） C.（m*n） D,O（m²+n²）（1）n （2）j-1j （3）i+1I （4）j （5）B读题，可以看出元素查找的过程为从右上角开始，往右或者往下进行查找。因此，初始值i=1，j=n。如果查找值小于右上角值，则往右移动一位再进行比较。所以，第二空填j-1j 。接下来是判断什么时候跳出循环。此时，终止循环的条件是：j=0，也就是其从最右端移到了最左端。再看X<Ai,j不成立时，执行流程的右枝。此时，也就是说第一行的最大值都小于查找值，因此需往下移动一行。所以第三空填i+1I 。试题二（共 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=0While （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地址是否合法，主要是判断其每个十进制数的大小和总个数以及“.”个数来进行判别。首先用isdigital函数判断是否为十进制数，是则保留值。指针移到地址的下一个字符。每找到一个十进制数都需要和前一次找到的值进行组合，即前一次的结果要乘以10。每找完一个完整数字和“.”都需要记录，所以要有decNum+和dotNum+。最后，如果IP地址正确，则返回1。即：decNum=4和dotNum=3时成立。 【试题三】阅读下列说明和 C 函数，填补 C 函数中的空缺，将解答填入答案纸的对应栏目内。【说明】字符串是程序中常见的一种处理对象，在字符串中进行子串的定位、插入和删除是常见的运算。设存储字符串时不设置结束标志，而是另行说明串的长度，因此串类型定义如下：Typedef struct Char*str 字符串存储空间的起始地址int lehgth 字符串长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:i （S.length<1|S.length<pos+T.length-1）return-1;for（i=pos,j=0;i<S.length &&j<T.length;）if （S.stri=T.strj）i+;j+;elsei=（）;j=0if （）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->length<|T.length<1|S->length<T.length）return;Pos=0for（;）调用 indexStr 在 S 所表示串的 pos 开始查找 T 的位置Pos=indexStr（）;if（pos-1） S 所表示串中不存在子串 Treturn;for（i=pos+T.length;i<S->length;i+） 通过覆盖来删除自串 TS->str（）=S->stri;S->length=（）; 更新 S所表示串的长度（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。当某一个字符与T的字符不相等时，那么字符串S就应从下一个字符开始比较，此时i=i-j+1，（如果前面有匹配成功的话，i的值已经增加了j位，因此需要重新回到之前比较的位置的后一个字符进行比较）再次进行与T的第一个字符进行比较，此时j恢复初始值，j=0。函数2为字符串的删除运算。首先，要调用函数 indexStr，需要三个参数，字符串S、字符串T和pos。从函数2的调用Void eraseStr（SString*S,SStringT）可以看到，此处字符串S为指针变量，因此字符串前需使用*。然后删除的字符串的位置为删除初始点的位置到其位置点+字符串T的长度，并将后面的字符串前移。而删除T字符串后，字符串S的总长度变化，需减去字符串T的长度。试题四（共 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 qNodeKeyType data;Struct qNode*next;qNode，*Linkqueue;Typedef structint 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;（）;elseP->next=p;q->size+;return OK;int Dequeue（queue*q,KeyType*elem） 出队列qNode*p;if（0q->size） 是空队列return errOr；P=（）; 令 p 指向队头元素结点*elem =p->data;q->rear->next=（）; 将队列元素结点从链表中去除if（） 被删除的队头结点是队列中唯一结点q->rear=NULL 变成空队列free（p）;q->size-;return OK;（1）Qrearnext=p（2）Qrear=p（3）Qrearnext（4）pnext（5）Qrear=p 或 Qrearnext=p或pnext=p或 Qsize=1 本题考察C语言指针与链表的知识，为入队列和删除队列问题。对于入队列，那么当队列Q不为空时，P的队尾t要指向原Q的队尾指向的元素，即：P->next=Q->rear->next，Q的队尾要指向p，即：Qrearnext=p。当队列Q为空时，插入p元素，则p的队尾指向p自身，即：pnext=p，且整个队列Q的队尾也是p，即：Qrear=p。对于队列删除元素p，先判断Q是否为空，为空队列则返回 ERROR;If(0q->size) /是空队列Return ERROR；另p指向队头元素结点，队头元素结点可用Qrearnext表示。此时，p转化为头结点，p出列，则需要Q的队尾指向p的下一个元素，因此第4空填：pnext。最后，判断被删除的队头结点是否是队列中的唯一结点，可采用：Qrear=p 或 Qrearnext=pnext 或 Qsize=1 等表示方法。 试题五（共 15 分）阅读以下说明和 Java 程序，填补代码中的空缺，将解答填入答题纸的对应栏内。【说明】以下 Jave 代码实现一个简单客户关系管理系统（CrM） 中通过工厂 （Customerrfactory ）对象来创建客户（Customer） 对象的功能。客户分为创建成功的客户 （realCustomer） 和空客户（NullCustomer） 。空客户对象是当不满足特定条件时创建或获取的对象。类间关系如图 5-1 所示。【Java 代码】Abstract class CustomerProtected String name;（）boolean isNil（）（）String getName（）;Class realCustomer （）CustomerPublic realCustomer（String name ） return false; Class NullCustomer（）CustomerPublic 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 （namesi.（）return new realCusmer（name）;return （）Public class CrMPublic 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 （Stringarge）CrM crm =new CrM（）;Crm,getCustomer（）;*程序输出为：CustomerrobNot Available in Customer DatabaseJulieNot Available in Customer Datable*int main（）CrM*crs=newCrM（）;Crs->getCustomer（）;Crs->getCustomer（）;Delete crs;return（）;*程序输出为：CustomerrobNot Available ini Customer DatabaseJulieNot Available in Customer Database1）abstract2) abstract3)extends4)extends5)equals(name)6)new NullCustomer()7) cf=New CustomerFactory();本题考察Java程序设计客户关系管理系统。1) abstract 定义可访问方法2) abstract 3)extends 继承Customer类4)extends5)equals(name) 判断名字是否在数组集合内6)new NullCustomer() 当不满足条件时创建一个空对象7) cf=New CustomerFactory(); 实例化对象cf试题六（共 15 分）阅读下列说明和 C+代码，填补代码中的空缺，将解答填入答题纸的对应栏内。【说明】以下 C+代码实现一个简单客户关系管理系统（CrM）中通过工厂（Customerfactory）对象来创建客户（Customer）对象的功能。客户分为创建成功的客户（realCustomer）和空客户（NullCustomer）。空客户对象是当不满足特定条件时创建或获取的对象。类间关系如图6-1 所示。【C+代码】#include<iostream>#include<string>using namespace std；class Customerprotected: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 Customerfactorypublic:string names3=rob, Joe,Julie；public:Customer*getCustomer（string name）for （int i=0；i<3；i+）if （namesi.（5） ）return new realCustomer（name）；return （6）；class CrMpublic: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； deletecustomer2；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；/*程序输出为：CustomersrobNot Available in Customer DatabaseJulieNot Available in Customer Database*/1)virtual2)virtual3):public Customer4):public Customer5)compare(name)=06)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();
