2014年下半年程序员下午试卷案例

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

问题：1.1 【流程图】

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

问题：2.1 【C代码】

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

例如，容量为8的循环队列如图3-1所示，初始时创建的空队列如图3-1 (a)所示，经过一系列的入队、出队操作后，队列的状态如图3-1 (b)所示（队列长度为3)。

问题：3.1

（共15分）
阅读以下说明和C函数，填补代码中的空缺（1)〜（6)，将解答填入答题纸的对应栏内。
【说明】
二叉树的宽度定义为含有结点数最多的那一层上的结点数。函数GetWidth()用于求二叉树的宽度。其思路是根据树的高度设置一个数组counter[]，counter[i]存放第i层上的结点数，并按照层次顺序来遍历二叉树中的结点，在此过程中可获得每个结点的层次值，最后从counter[]中取出最大的元素就是树的宽度。
按照层次顺序遍历二叉树的实现方法是借助一个队列，按访问结点的先后顺序来记录结点，离根结点越近的结点越先进入队列，具体处理过程为：先令根结点及其层次号 (为1)进入初始为空的队列，然后在队列非空的情况下，取出队头所指示的结点及其层次号，然后将该结点的左子树根结点及层次号入队列（若左子树存在)，其次将该结点的右子树根结点及层次号入队列（若右子树存在），然后再取队头，重复该过程直至完成遍历。

问题：4.1

（共15分）
阅读下列说明、C++代码和运行结果，填补代码中的空缺（1)〜（6)，将解答填入答题纸的对应栏内。
【说明】
很多依托扑克牌进行的游戏都要先洗牌。下面的C++程序运行时先生成一副扑克牌，洗牌后再按顺序打印每张牌的点数和花色。

问题：5.1

（共15分）
阅读以下说明和Java程序，填补代码中的空缺（1)〜（6)，将解答填入答题纸的对应栏内。
【说明】
很多依托扑克牌进行的游戏都要先洗牌。下面的Java代码运行时先生成一副扑克牌，洗牌后再按顺序打印每张牌的点数和花色。

问题：6.1