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

第1页 / 共19页

第2页 / 共19页

第3页 / 共19页

第4页 / 共19页

第5页 / 共19页

第6页 / 共19页

第7页 / 共19页

第8页 / 共19页

2014 下半年程序员考试真题及答案-下午卷试题一（共 15 分）阅读以下说明和流程图，填补流程图中的空缺（1)〜（5)，将解答填入答题纸的对应栏内。【说明】本流程图旨在统计一本电子书中各个关键词出现的次数。假设已经对该书从头到尾依次分离出各个关键词{A(i)|i=1，…，n}(n>1) }，其中包含了很多重复项，经下面的流程处理后，从中挑选出所有不同的关键词共 m 个{K(j)lj=l，…，m}，而每个关键词 K(j)出现的次数为 K(j)，j=1,…，m。【流程图】【参考答案】

(1) 1 (2) K(j) (3)NK(j)+1->NK(j) 或 NK(j)++ 或等价表示 (4)m+1->m 或 m++ 或等价表示 (5)A(i) 【试题解析】流程图中的第 1 框显然是初始化。A (1) ->K(1)意味着将本书的第 1 个关键词作为选出的第 1 个关键词。1->NK (1)意味着此时该关键词的个数置为 1。m 是动态选出的关键词数目，此时应该为 1，因此（1)处应填 1。本题的算法是对每个关键词与已选出的关键词进行逐个比较。凡是遇到相同的，相应的计数就增加 1;如果始终没有遇到相同关键词的，则作为新选出的关键词。流程图第 2 框开始对 i=2，n 循环，就是对书中其他关键词逐个进行处理。流程图第 3 框开始 j=l，m 循环，就是按已选出的关键词依次进行处理。接着就是将关键词 A(I)与选出的关键词 K(j)进行比较。因此（2)处应填 K(j)。如果 A(i)=K(j)，则需要对计数器 NK(j)增 1，即执行 NK(j)+1->NK(j)。因此（3)处应填 NK(j)+1->NK(j)。执行后，需要跳出 j 循环，继续进行 i 循环，即根据书中的下一个关键词进行处理。如果 A(i)不等于 NK(j),则需要继续与下个 NK(j)进行比较，即继续执行 j 循环。如果直到 j 循环结束仍没有找到匹配的关键词，则要将该 A(i)作为新的已选出的关键词。因此，应执行 A(i)->K(m+1)以及 m+1->m。更优的做法是先将计数器 m 增 1，再执行 A(i) ->K(m)。因此（4)处应填 m+1->m，(5)处应填 A(i)。

试题二（共 15 分）阅读以下说明和 C 函数，填补代码中的空缺（1)〜（5)，将解答填入答题纸的对应栏内。【说明】函数 removeDuplicates(char *str)的功能是移除给定字符串中的重复字符，使每种字符仅保留一个，其方法是：对原字符串逐个字符进行扫描，遇到重复出现的字符时，设置标志，并将其后的非重复字符前移。例如，若 str 指向的字符串为"aaabbbbscbsss”，则函数运行后该字符串为"absc”。【C 代码】【参考答案】 (1)len<2 或 len<=l 或等价表示

(2)i+1 或等价表示 (3)flag =1 或给 flag 赋值为任何一个不是 0 的值 (4)idx++ 或 idx = idx+1 或等价表示 (5)idx 或等价表示【试题解析】本题考查 C 语言基本应用。题目要求在阅读理解代码说明的前提下完善代码。字符串的运算处理是 C 程序中常见的基本应用。根据注释，空（1)处应填入的内容很明确，为"len<=1"或其等价表示。要消除字符串中的重复字符，需要扫描字符串，这通过下面的代码来实现：上面代码中，循环变量 i 用于顺序地记下字符串中每个不同字符首次出现的位置，那么后面的处理就是从 i 的下一个位置开始，考查后面的字符中有没有与它相同的（str[i] =str[m]),因此空（2)应填入"i+1"或其等价表示。显然，当发现了重复宇符时，应设置标志，空（3)处应填入"flag=1"或者给 flag 赋值为任何一个不是 0 的值。根据说明，发现与 str[i]相同的第一个字符 str[m]后，需要将其后所有与 str[i]不同的字符前移，以覆盖重复字符 str[m]，对应的代码如下：

初始时，idx 等于 m，使 str[n]覆盖 str[idx]后，需要将 idx 自增，以便将后面与 str[i] 不同的字符继续前移，因此空（4)处应填入"idx++"或等价表示。由于后面字符前移了，所以字符串结束标志也需重新设置，空（5)处应填入"idx"。

试题三（共 15 分）阅读以下说明和 C 凼数，填补函数代码中的空缺（1)〜（5)，将解答填入答题纸的对应栏内。【说明】队列是一种常用的数据结构，其特点是先入先出，即元素的插入在表头、删除在表尾进行。下面采用顺序存储方式实现队列，即利用一组地址连续的存储单元存放队列元素，同时通过模运算将存储空间看作一个环状结构（称为循环队列）。设循环队列的存储空间容量为 MAXQSIZE，并在其类型定义中设置 base、rear 和 length 三个域变量，其中，base 为队列空间的首地址，rear 为队尾元素的指针，length 表示队列的长度。例如，容量为 8 的循环队列如图 3-1 所示，初始时创建的空队列如图 3-1 (a)所示，经过一系列的入队、出队操作后，队列的状态如图 3-1 (b)所示（队列长度为 3)。

【参考答案】 (1) sizeof(QElemType) (2) (Q->rear + 1)% MAXQSIZE 或等价表示 (3) Q->length++ 或 Q->length = Q->length + 1 或等价表示 (4) Q->length<=0 或 Q->length=0 或等价表示 (5) Q->length- 或 Q->length = Q->length -1 或等价表示【试题解析】本题考査数据结构实现和 C 语言基本应用。

队列是一种基本的数据结构，其基本操作有初始化、判断是否为空、入队列和出队列等。循环队列是一种采用顺序存储结构实现的队列，其特点是将队列存储空间的首尾单元在逻辑上连接起来，从而得到一个环形结构的队列空间。在循环队列的类型定义 SqQueue 中，指针成员 base 存放队列空间的首地址，存储空间应在队列的初始化操作中实现，对应的语句如下：由于 InitQueue(SqQueue *Q)的形参为指向结构体的指针，因此队列的参数可表示为 “Q->base、Q->rear、Q->length” 或 “(*Q).base、（*Q).rear、(*Q).length”,由于队列元素类型为 QElemType、队列容量为 MAXQSIZE，因此空（1)处应填入“sizeof(QElemType)”。入队列操作由 EnQueue(SqQueue *Q, QElemType e)实现。由于循环队列空间的容量为 MAXQSIZE (也就是队满条件为“Q->length>=MAXQSIZE”)，因此元素入队列时，需先判断是否队满，在队列中有空闲单元的情况下才能进行入队列操作。其次需确定新元素在队列空间中的位置，从图 3-1 (b)中可以看出，Q->rear 指出了当前队尾元素，新元素应放入下一个位置，结合队列环形空间的要求，空（2)处应填入“(Q->rear+ 1)% MAXQSIZE”或其等价形式。通过“Q->base[Q->rear] = e”将元素加入队列后，队列长度增加了，因此空（3)处应填入“Q->length++”或其等价形式。出队列操作由 DeQueue(SqQueue*Q，QElemType *e)实现。元素出队列时，需要判断队列是否为空，显然，队列长度为 0 就直接表示了队空，因此空（4)处应填入 “Q->length=0” 或其等价形式，空（5)处应填入“Q->length--”或其等价形式。

资料库

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

相关推荐

程序员考试

热门标签

最新资料