2017上半年程序员考试真题及答案-下午卷.doc-资料库

第1页 / 共17页

第2页 / 共17页

第3页 / 共17页

第4页 / 共17页

第5页 / 共17页

第6页 / 共17页

第7页 / 共17页

第8页 / 共17页

2017 上半年程序员考试真题及答案-下午卷试题一（共 20 分）阅读下列说明和图，回答问题 1 至问题 3，将解答填入答题纸的对应栏内。【说明】设有二维整数数组（矩阵）A[1:m,1:n],其每行元素从左至右是递增的，每列元素从上到下是递增的。以下流程图旨在该矩阵中需找与给定整数 X 相等的数。如果找不到则输出 “false”;只要找到一个（可能有多个）就输出“True”以及钙元素的下标 i 和 j（注意数组元素的下标从 1 开始）。例如，在如下矩阵中查找整数 8，则输出伟：True,4,1 2 4 6 8 4 5 7 9 6 9 10 11 9 10 12 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）B 读题，可以看出元素查找的过程为从右上角开始，往右或者往下进行查找。因此，初始值 i=1，j=n。如果查找值小于右上角值，则往右移动一位再进行比较。所以，第二空填 j-1→j 。接下来是判断什么时候跳出循环。此时，终止循环的条件是：j=0，也就是其从最右端移到了最左端。再看 X

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 地址是否合法，主要是判断其每个十进制数的大小和总个数以及“.”个数来进行判别。首先用 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

﹜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->length<||T.length<1||S->length

for（i=pos+T.length;ilength;i++）／／通过覆盖来删除自串 T S->str[（）]=S->str[i]; 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 qNode﹛ KeyType data; Struct qNode*next; ﹜qNode，*Linkqueue; Typedef struct﹛ int size; Link:queue rear; }queue;

资料库

2017上半年程序员考试真题及答案-下午卷.doc

相关推荐

程序员考试

热门标签

最新资料