【试题三】阅读下列说明和 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=0for（;;）﹛／／调用 indexStr 在 S 所表示串的 pos 开始查找 T 的位置pos=indexStr（）;if（pos＝=-1） ／／S 所表示串中不存在子串 Treturn;for（i=pos+T.length;i＜S->length;i++） ／／通过覆盖来删除自串 TS->str[（）]=S->str[i];S->length=（）; ／／更新 S所表示串的长度﹜﹜

问答题

试题四（共 15 分）阅读以下说明和代码，填补代码中的空缺，将解答填入答题纸的对应栏内。【说明】 图是很多领域中的数据模型，遍历是图的一种基本运算。从图中某顶点 v出发进行广度优先遍历的过程是：①访问顶点 v；②访问 V 的所有未被访问的邻接顶点 W1 ,W2 ,..,Wk；③依次从这些邻接顶点 W1 ,W2 ,..,Wk 出发，访问其所有未被访问的邻接顶 点；依此类推，直到图中所有访问过的顶点的邻接顶点都得到访问。显然，上述过程可以访问到从顶点 V 出发且有路径可达的所有顶点。对于 从 v 出发不可达的顶点 u，可从顶点 u 出发再次重复以上过程,直到图中所有顶 点都被访问到。例如，对于图 4-1 所示的有向图 G，从 a 出发进行广度优先遍历，访问顶点 的一种顺序为 a、b、c、e、f、d。图 4-1设图 G 采用数组表示法（即用邻接矩阵 arcs 存储），元素 arcs[i][ j]定义如下： 图 4-1 的邻接矩阵如图 4-2 所示，顶点 a~f 对应的编号依次为 0~5.因此，访问顶点 a 的邻接顶点的顺序为 b，c，e。函数 BFSTraverse(Graph G)利用队

答案解析

问答题

【试题三】阅读下列说明和 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 中的字符串伟

答案解析

问答题

试题四（共 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

答案解析

问答题

阅读下列说明和 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′;（）f

答案解析