温故而知新，下笔如有神。近三下半年程序员考试专题考练2及答案-下午卷试题一（共15分）阅读以下说明和流程图，填补流程图中的空缺（1)（5)，将解答填入答题纸的对应栏内。【说明】本流程图旨在统计一本电子书中各个关键词出现的次数。假设已经对该书从头到尾依次分离出各个关键词A(i)|i=1，n(n1) ，其中包含了很多重复项，经下面的流程处理后，从中挑选出所有不同的关键词共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)len2 或len=l 或等价表示(2)i+1 或等价表示(3)flag =1或给flag赋值为任何一个不是0的值(4)idx+ 或idx = idx+1 或等价表示(5)idx 或等价表示【试题解析】本题考查C语言基本应用。题目要求在阅读理解代码说明的前提下完善代码。字符串的运算处理是C程序中常见的基本应用。根据注释，空（1)处应填入的内容很明确，为lenrear + 1)% MAXQSIZE 或等价表示(3) Q-length+ 或 Q-length = Q-length + 1 或等价表示(4) Q-lengthlength=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-baseQ-rear = e”将元素加入队列后，队列长度增加了，因此空（3)处应填入“Q-length+”或其等价形式。出队列操作由DeQueue(SqQueue*Q，QElemType *e)实现。元素出队列时，需要判断队列是否为空，显然，队列长度为0就直接表示了队空，因此空（4)处应填入 “Q-length=0”或其等价形式，空（5)处应填入“Q-length-”或其等价形式。试题四（共15分）阅读以下说明和C函数，填补代码中的空缺（1)（6)，将解答填入答题纸的对应栏内。 【说明】二叉树的宽度定义为含有结点数最多的那一层上的结点数。函数GetWidth()用于求二叉树的宽度。其思路是根据树的高度设置一个数组counter，counteri存放第i层上的结点数，并按照层次顺序来遍历二叉树中的结点，在此过程中可获得每个结点的层次值，最后从counter中取出最大的元素就是树的宽度。按照层次顺序遍历二叉树的实现方法是借助一个队列，按访问结点的先后顺序来记录结点，离根结点越近的结点越先进入队列，具体处理过程为：先令根结点及其层次号 (为1)进入初始为空的队列，然后在队列非空的情况下，取出队头所指示的结点及其层次号，然后将该结点的左子树根结点及层次号入队列（若左子树存在)，其次将该结点的右子树根结点及层次号入队列（若右子树存在），然后再取队头，重复该过程直至完成遍历。 【参考答案】(1) !counter 或 0=counter 或 NULL=counter 或等价表示(2) !InitQueue(&Q)或 0 = InitQueue(&Q)或等价表示(3) !DeQueue(&Q,&b)或 0 = DeQueue(&Q,&b)或等价表示(4) b.LevelNumbert+1 或等价表示(5) b.LevelNumbert+1 或等价表示(6) counterfi width 或等价表示【试题解析】本题考查数据结构实现和C语言基本应用。考生需要认真阅读题目中的说明，以确定代码部分的处理逻辑，从而完成代码。根据注释，空（1)处应填入“!counter”或其等价形式。由于初始化队列的函数原型为“InitQueue(QUEUE *Q)”且返回值为0表示操作失败，因此调用该函数时实参应取地址，即空（2)处应填入“!InitQueue(&Q)”或其等价形式。空（3)处需进行出队列操作，同时通过参数得到队头元素，根据说明，该空应填入“! DeQueue(&Q,&b) ”或其等价形式。出队操作后，得到的队头元素用b表示，根据队列元素的类型定义，其对应结点在二叉树中的层次号表示为b.LevelNumber，显然，其孩子结点的层次号应加1，因此空（4) 和（5)处应填入 “b.levelNumber+1 ”。从代码中可知变最width的作用是表示最大的层次编号，并通过顺序地扫描数组counter中的每一个元素来确定width的值，显然，空（6)处应填入“counteri width” 或其等价形式。试题五（共15分）阅读下列说明、C+代码和运行结果，填补代码中的空缺（1)（6)，将解答填入答题纸的对应栏内。【说明】很多依托扑克牌进行的游戏都要先洗牌。下面的C+程序运行时先生成一副扑克牌，洗牌后再按顺序打印每张牌的点数和花色。【参考答案】(1) this-(2) this-(3) decki 或*(deck+i)或等价表示(4) decki. 或*(deck+i).或等价表示(5) new DeckOfCards()(6) d-printCards()或等价表示 【试题解析】本题考查C+语言程序设计能力，涉及类、对象、函数的定义和相关操作。要求考生根据给出的案例和代码说明，认真阅读，理清程序思路，然后完成题目。本题目中涉及到扑克牌、牌桌等类以及洗牌和按点数排序等操作。根据说明进行设计。定义了两个数组，Rank表示扑克牌点数，Suits表示扑克牌花色，定义时进行初始化，而且值不再变化，故用const修饰。Card类有两个属性，rank和suit,在使用构造函数Card(int rank, int suit)新建一个Card的对象时，所传入的参数指定rank和suit这两个属性值。因为参数名称和属性名称相同，所以用this-前缀区分出当前对象。在类Card中包含方法getRank()和getSuit(), 分别返回当前对象的rank和suit属性值