搜索
2017年上半年程序员下午试卷第1页（共16页）全国计算机技术与软件专业技术资格（水平）考试2017年上半年程序员下午试卷（考试时间14:00～16:30共150分钟）请按下述要求正确填写答题纸1.在答题纸的指定位置填写你所在的省、自治区、直辖市、计划单列市的名称。2.在答题纸的指定位置填写准考证号、出生年月日和姓名。3.答题纸上除填写上述内容外只能写解答。4.本试卷共7道题，试题一至试题四是必答题，试题五至试题六选答1道。每题15分，满分75分。5.解答时字迹务必清楚，字迹不清时，将不评分。6.仿照下面例题，将解答写在答题纸的对应栏内。例题2017年上半年全国计算机技术与软件专业技术资格（水平）考试日期是（1）月（2）日。因为正确的解答是“5月20日”，故在答题纸的对应栏内写上“5”和“20”（参看下表）。例题解答栏（1）5（2）202017年上半年程序员下午试卷第2页（共16页）试题一（共20分）阅读下列说明和图，回答问题1至问题3，将解答填入答题纸的对应栏内。【说明】设有二维整数数组（矩阵）A[1:m,1:n],其每行元素从左至右是递增的，每列元素从上到下是递增的。以下流程图旨在该矩阵中需找与给定整数X相等的数。如果找不到则输出“false”;只要找到一个（可能有多个）就输出“True”以及钙元素的下标i和j（注意数组元素的下标从1开始）。例如，在如下矩阵中查找整数8，则输出伟：True,4,1246945910671012891113流程图中采用的算法如下：从矩阵的右上角元素开始，按照一定的路线逐个取元素与给定整数X进行比较（必要时向左走一步或向下走一步取下一个元素），直到找到相等的数或超出矩阵范围（找不到）。【流程图】【问题】该算法的时间复杂数是（）供选择答案：A.O（1）B.O（m+n）C.（m*n）D,O（m²+n²）2017年上半年程序员下午试卷第3页（共16页）试题二（共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是不合法的。【函数】intisLegal（char*ipaddr）﹛intflag;intcurVal;／／curVal表示分析出的一个十进制数intdecNum=0,dotNum=0;／／decNum用于记录十进制数的个数／／dotNum用户记录点的个数Char*p=（）for（;*p;p++）﹛curVal=0;flag=0While（isdigit（*p））﹛／／判断是否伟数字字符CurVal=（）+*p-′0′;（）flag=1;﹜if（curVal255）﹛return0;﹜if（flag）﹛（）﹜if（*p=′.′﹛dotNum++;2017年上半年程序员下午试卷第4页（共16页）﹜﹜if（）﹛return1；﹜return0;﹜2017年上半年程序员下午试卷第5页（共16页）【试题三】阅读下列说明和C函数，填补C函数中的空缺，将解答填入答案纸的对应栏目内。【说明】字符串是程序中常见的一种处理对象，在字符串中进行子串的定位、插入和删除是常见的运算。设存储字符串时不设置结束标志，而是另行说明串的长度，因此串类型定义如下：Typedefstruct﹛Char*str／／字符串存储空间的起始地址intlehgth／／字符串长intcapacity／／存储空间的容量﹜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中的字符串伟″studentsents″,T中的字符串伟″ent″，pos=0，则T在S中首次出现的位置为4。【C函数1】intindexStr（SStringS,SStringT,intpos）﹛inti,j:i（S.length1||S.lengthpos+T.length-1）return-1;for（i=pos,j=0;iS.length&&jT.length;）﹛if（S.str[i]==T.str[j]）﹛i++;j++;﹜else﹛2017年上半年程序员下午试卷第6页（共16页）i=（）;j=0﹜﹜if（）returni-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】VoideraseStr（SString*S,SStringT）﹛inti;intpos;if（S-length||T.length1||S-lengthT.length）return;Pos=0for（;;）﹛／／调用indexStr在S所表示串的pos开始查找T的位置Pos=indexStr（）;if（pos＝-1）／／S所表示串中不存在子串Treturn;for（i=pos+T.length;iS-length;i++）／／通过覆盖来删除自串T2017年上半年程序员下午试卷第7页（共16页）S-str[（）]=S-str[i];S-length=（）;／／更新S所表示串的长度﹜﹜2017年上半年程序员下午试卷第8页（共16页）试题四（共15分）阅读以下说明和C函数，填补函数中的空缺，将解答填入答题纸的对应栏内。【说明】简单队列是符合先进先出规则的数据结构，下面用不含有头结点的单向循环链表表示简单队列。函数enqueue（queue*q，KeyTypenew_elem）的功能是将元素new_elem加入队尾。函数Dnqueue（queue*q，KeyType*elem）的功能使将非空队列的队头元素出队（从队列中删除），并通过参数带回刚出队的元素。用单向循环链表表示的队列如图4-1所示。图4-1单向循环链表表示的队列示意图队列及链表结点等相关类型定义如下:enum{errOr，OK};typedefintKeyType;typedefstructqNode﹛KeyTypedata;StructqNode*next;﹜qNode，*Linkqueue;Typedefstruct﹛intsize;Link:queuerear;}queue;2017年上半年程序员下午试卷第9页（共16页）【C函数】intenqueue（queue*q,KeyTypenew_elem）﹛／／元素new_elem入队列qNode*p;P=（qNode*）malloc（sizeof（qNode））;if（!p）returnerrOr;P-data=new_elem;if（q-rear）﹛P-next=q-rear-next;（）;﹜elseP-next=p;﹙﹚;q-size++;returnOK;﹜intDequeue（queue*q,KeyType*elem）﹛／／出队列qNode*p;if（0＝＝q-size）／／是空队列returnerrOr；P=（）;／／令p指向队头元素结点*elem=p-data;q-rear-next=（）;／／将队列元素结点从链表中去除if（（））／／被删除的队头结点是队列中唯一结点q-rear=NULL／／变成空队列free（p）;2017年上半年程序员下午试卷第10页（共16页）q-size--;returnOK;﹜2017年上半年程序员下午试卷第11页（共16页）试题五（共15分）阅读以下说明和Java程序，填补代码中的空缺，将解答填入答题纸的对应栏内。【说明】以下Jave代码实现一个简单客户关系管理系统（CrM）中通过工厂（Customerrfactory）对象来创建客户（Customer）对象的功能。客户分为创建成功的客户（realCustomer）和空客户（NullCustomer）。空客户对象是当不满足特定条件时创建或获取的对象。类间关系如图5-1所示。【Java代码】AbstractclassCustomer﹛ProtectedStringname;（）booleanisNil（）（）StringgetName（）;﹜ClassrealCustomer（）Customer﹛PublicrealCustomer（Stringname）﹛returnfalse;﹜﹜ClassNullCustomer（）Customer﹛PublicStringgetName（）﹛return″NotAvailableinCustomerDatabase″;﹜PublicbooleanisNil（）﹛returntrue;﹜﹜classCustomerfactory{publicString[]names={rob，Joe，Julie};publicCustomergetCustomer（Stringname）{for（inti=0;inames.length;i++）{if（names[i].（））﹛returnnewrealCusωmer（name）;﹜2017年上半年程序员下午试卷第12页（共16页）﹜return（）﹜﹜PublicclassCrM﹛PublicviodgetCustomer（）﹛Customerfactory（）Customercustomer1-cf.getCustomer（″rob″）;Customercustomer2=cf.getCustomer（″rob″）;Customercustomer3=cf.getCustomer（″Julie″）;Customercustomer4=cf.getCustomer（″Laura″）;System.out.println（″customer1.getName（））;System.out.println（″customer2getName（））;System.out.println（″customer3.getName（））;System.out.println（″customer4.getName（））;﹜Publicstaticviodmain（String[]arge）﹛CrMcrm=newCrM（）;Crm,getCustomer（）;﹜﹜／*程序输出为：CustomerrobNotAvailableinCustomerDatabaseJulieNotAvailableinCustomerDatable*／2017年上半年程序员下午试卷第13页（共16页）intma