1、计算机水平考试初级程序员 2014 年下半年下午真题及答案解析(总分：90.00，做题时间：150 分钟)1.试题一(共 15 分) 阅读以厂说明和流程图，填补流程图中的空缺(1)(5)将解答填入答题纸的对应栏内。 说明 本流程图旨在统计一本电子书中各个关键词出现的次数。假设已经对该书从头到尾依次分离出各个关键词(A(i)|i1，n)(n1)，其中包含了很多重复项，经下面的流程处理后，从中挑选出所有不同的关键词共 m 个K(j)|j=1，m，而每个关键词 K(j)出现的次数为 NK(j)，j1，m。 流程图 （分数：15.00）_2.试题二(共 15 分) 阅读以下说明和 C 函数，填补代码中
2、的空缺(1)(5)，将解答填入答题纸的对应栏内。说明 函数 removeDuplicates(char *str)的功能是移除给定字符串中的重复字符，使每种字符仅保留一个，其方法是：对原字符串逐个字符进行扫描，遇到重复出现的字符时，设置标志，并将其后的非重复字符前移。例如，若 str 指向的字符串为“aaabbbbscbsss”，则函数运行后该字符串为“absc”。 C代码 （分数：15.00）_3.试题三(共 15 分) 阅读以下说明和 C 函数，填补函数代码中的空缺(1)(5)，将解答填入答题纸的对应栏内。 说明 队列是一种常用的数据结构，其特点是先入先出，即元素的插入在表头、删除在表尾进
3、行。下面采用顺序存储方式实现队列，即利用一组地址连续的存储单元存放队列元素，同时通过模运算将存储空间看作一个环状结构(称为循环队列)。 设循环队列的存储空间容量为 MAXQSIZE，并在其类型定义中设置 base、rear 和 length 三个域变量，其中，base 为队列空间的首地址，rear 为队尾元素的指针，length 表示队列的长度。 例如，容量为 8 的循环队列如图 3-1 所示，初始时创建的空队列如图 3-1(a)所示经过一系列的入队、出队操作后，队列的状态如图 3-1(b)所示(队列长度为 3)。 下面的 C 函数 1、C 函数 2 和 C 函数 3 用于实现队列的创建、插入
4、和删除操作，请完善这些代码。 C 函数 1创建一个空的循环队列。 C 函数 2元素插入循环队列。 C 函数 3元素出循环队列。 （分数：15.00）_4.试题四(共 15 分) 阅读以下说明和 C 函数，填补代码中的空缺(1)(6)，将解答填入答题纸的对应栏内。说明 二叉树的宽度定义为含有结点数最多的那一层上的结点数。函数 GetWidth()用于求二叉树的宽度。其思路是根据树的高度设置一个数组 counter，counteri存放第 i 层上的结点数，并按照层次顺序来遍历二叉树中的结点，在此过程中可获得每个结点的层次值，最后从 counter中取出最大的元素就是树的宽度。 按照层次顺序遍历二
5、叉树的实现方法是借助一个队列，按访问结点的先后顺序来记录结点，离根结点越近的结点越先进入队列，具体处理过程为：先令根结点及其层次号(为 1)进入初始为空的队列，然后在队列非空的情况下，取出队头所指示的结点及其层次号，然后将该结点的左子树根结点及层次号入队列(若左子树存在)，其次将该结点的右子树根结点及层次号入队列(若右子树存在)，然后再取队头，重复该过程直至完成遍历。 设二叉树采用二叉链表存储，结点类型定义如下： GetWidth()函数中用到的函数原型如下所述，队列的类型名为 QUEUE： C 函数 （分数：15.00）_5.试题五(共 15 分) 阅读下列说明、C+代码和运行结果填补代码中
6、的空缺(1)(6)，将解答填入答题纸的对应栏内。 说明 很多依托扑克牌进行的游戏都要先洗牌。下面的 C+程序运行时先生成一副扑克牌，洗牌后再按顺序打印每张牌的点数和花色。 C+代码 （分数：15.00）_6.试题六(共 15 分) 阅读以下说明和 Java 程序，填补代码中的空缺(1)(6)，将解答填入答题纸的对应栏内。 说明 很多依托扑克牌进行的游戏都要先洗牌。下面的 Java 代码运行时先生成一副扑克牌，洗牌后再按顺序打印每张牌的点数和花色。 java 代码 （分数：15.00）_计算机水平考试初级程序员 2014 年下半年下午真题答案解析(总分：90.00，做题时间：150 分钟)1.试
7、题一(共 15 分) 阅读以厂说明和流程图，填补流程图中的空缺(1)(5)将解答填入答题纸的对应栏内。 说明 本流程图旨在统计一本电子书中各个关键词出现的次数。假设已经对该书从头到尾依次分离出各个关键词(A(i)|i1，n)(n1)，其中包含了很多重复项，经下面的流程处理后，从中挑选出所有不同的关键词共 m 个K(j)|j=1，m，而每个关键词 K(j)出现的次数为 NK(j)，j1，m。 流程图 （分数：15.00）_正确答案：( (1)1 (2)K(j) (3)NK(j)+1NK(j) 或 NK(j)+ 或等价表示 (4)m+1m 或 m+ 或等价表示 (5)A)解析： 流程图中的第 1
8、框显然是初始化。A(1)K(1)意味着将本书的第 1 个关键词作为选出的第 1 个关键词。1NK(1)意味着此时该关键词的个数置为 1。m 是动态选出的关键词数目，此时应该为 1，因此(1)处应填 1。 本题的算法是对每个关键词与己选出的关键词进行逐个比较。凡是遇到相同的，相应的计数就增加 1；如果始终没有遇到相同关键词的，则作为新选出的关键词。 流程图第 2 框开始对 i2，n 循环，就是对书中其他关键词逐个进行处理。流程图第 3 框开始 j1，m 循环，就是按已选出的关键词依次进行处理。 接着就是将关键词 A(i)与选出的关键词 K(j)进行比较。因此(2)处应填 K(i)。 如果 A(i
9、)K(j)，则需要对计数器 NK(j)增 1，即执行 NK(j)+1NK(j)。因此(3)处应填 NK(j)+1NK(j)。执行后，需要跳出 j 循环，继续进行 i 循环，即根据书中的下一个关键词进行处理。 如果 A(i)不等于 NK(j)，则需要继续与下个 NK(j)进行比较，即继续执行 j 循环。如果直到 j 循环结束仍没有找到匹配的关键词，则要将该 A(i)作为新的已选出的关键词。因此，应执行 A(i)K(m+1)以及 m+1m。更优的做法是先将计数器 m 增 1，再执行 A(i)K(m)。因此(4)处应填 m+1m，(5)处应填 A(1)。2.试题二(共 15 分) 阅读以下说明和 C
10、 函数，填补代码中的空缺(1)(5)，将解答填入答题纸的对应栏内。说明 函数 removeDuplicates(char *str)的功能是移除给定字符串中的重复字符，使每种字符仅保留一个，其方法是：对原字符串逐个字符进行扫描，遇到重复出现的字符时，设置标志，并将其后的非重复字符前移。例如，若 str 指向的字符串为“aaabbbbscbsss”，则函数运行后该字符串为“absc”。 C代码 （分数：15.00）_正确答案：( (1)len2 或 lenbase、Q-rear、Q-length”或“(*Q)base、(*Q)rear、(*Q)length”，由于队列元素类型为 QElemTyp
11、e、队列容量为 MAXQSIZE，因此空(1)处应填入“sizeof(QElemType)”。 入队列操作由 EnQueue(SqQueue*Q，QElemType e)实现。由于循环队列空间的容量为 MAXQSIZE(也就是队满条件为“Q-lengthMAXQSIZE”)，因此元素入队列时，需先判断是否队满，在队列中有空闲单元的情况下才能进行入队列操作。其次需确定新元素在队列空间中的位置，从图 3-1(b)中可以看出，Q-rear 指出了当前队尾元素，新元素应放入下一个位置，结合队列环形空间的要求，空(2)处应填入“(Q-rear+1)MAXQSIZE”或其等价形式。通过“Q-baseQ-r
12、eare”将元素加入队列后，队列长度增加了，因此空(3)处应填入“Q-length+”或其等价形式。 出队列操作由 DeQueue(SqQueue *Q，QElemType*e)实现。元素出队列时，需要判断队列是否为空，显然，队列长度为 0 就直接表示了队空，因此空(4)处应填入“Q-length=0”或其等价形式，空(5)处应填入“Q-length-”或其等价形式。4.试题四(共 15 分) 阅读以下说明和 C 函数，填补代码中的空缺(1)(6)，将解答填入答题纸的对应栏内。说明 二叉树的宽度定义为含有结点数最多的那一层上的结点数。函数 GetWidth()用于求二叉树的宽度。其思路是根据树
13、的高度设置一个数组 counter，counteri存放第 i 层上的结点数，并按照层次顺序来遍历二叉树中的结点，在此过程中可获得每个结点的层次值，最后从 counter中取出最大的元素就是树的宽度。 按照层次顺序遍历二叉树的实现方法是借助一个队列，按访问结点的先后顺序来记录结点，离根结点越近的结点越先进入队列，具体处理过程为：先令根结点及其层次号(为 1)进入初始为空的队列，然后在队列非空的情况下，取出队头所指示的结点及其层次号，然后将该结点的左子树根结点及层次号入队列(若左子树存在)，其次将该结点的右子树根结点及层次号入队列(若右子树存在)，然后再取队头，重复该过程直至完成遍历。 设二叉树
14、采用二叉链表存储，结点类型定义如下： GetWidth()函数中用到的函数原型如下所述，队列的类型名为 QUEUE： C 函数 （分数：15.00）_正确答案：( (1)!counter 或 0counter 或 NULLcounter 或等价表示 (2)!InitQueue(Q) 或0InitQueue(Q) 或等价表示 (3)!DeQueue(Q，b) 或 0DeQueue(Q，b) 或等价表示 (4)b.LevelNumber+1 或等价表示 (5)b.LevelNumber+1 或等价表示 (6)counteriwidth 或等价表示)解析： 本题考查数据结构实现和 C 语言基本应用。
15、 考生需要认真阅读题目中的说明，以确定代码部分的处理逻辑，从而完成代码。 根据注释，空(1)处应填入“!counter”或其等价形式。 由于初始化队列的函数原型为“InitQueue(QUEUE *Q)”且返回值为 0 表示操作失败，因此调用该函数时实参应取地址，即空(2)处应填入“!InitQueue(Q)”或其等价形式。 空(3)处需进行出队列操作，同时通过参数得到队头元素，根据说明，该空应填入“!DeQueue(Q，b)” 或其等价形式。 出队操作后，得到的队头元素用b 表示，根据队列元素的类型定义，其对应结点在二叉树中的层次号表示为 bLevelNumber，显然，其孩子结点的层次号应
16、加 1，因此空(4)和(5)处应填入“b.LevelNumber+1”。 从代码中可知变量 width 的作用是表示最大的层次编号，并通过顺序地扫描数组 counter 中的每一个元素来确定 width 的值，显然，空(6)处应填入“counteriwidth”或其等价形式。5.试题五(共 15 分) 阅读下列说明、C+代码和运行结果填补代码中的空缺(1)(6)，将解答填入答题纸的对应栏内。 说明 很多依托扑克牌进行的游戏都要先洗牌。下面的 C+程序运行时先生成一副扑克牌，洗牌后再按顺序打印每张牌的点数和花色。 C+代码 （分数：15.00）_正确答案：( (1)this- (2)this-
17、(3)decki 或*(deck+i) 或等价表示 (4)decki 或*(deck+i) 或等价表示 (5)new DeckOfCards() (6)d-printCards() 或等价表示)解析： 本题考查 C+语言程序设计能力，涉及类、对象、函数的定义和相关操作。要求考生根据给出的案例和代码说明，认真阅读，理清程序思路，然后完成题目。 本题目中涉及到扑克牌、牌桌等类以及洗牌和按点数排序等操作。根据说明进行设计。 定义了两个数组，Rank 表示扑克牌点数，Suits 表示扑克牌花色，定义时进行初始化，而且值不再变化，故用 const 修饰。 Card 类有两个属性，rank 和 suit，
18、在使用构造函数 Card(int rank，int suit)新建一个 Card 的对象时，所传入的参数指定 rank 和 suit 这两个属性值。因为参数名称和属性名称相同，所以用 this-前缀区分出当前对象。在类 Card 中包含方法 getRank()和 getSuit()，分别返回当前对象的 rank 和 suit 属性值。printCard()函数打印扑克牌点数和花色。 DeckOfCards 类包含 Card 类型元素的数组 deck52，表示牌桌上一副牌(52 张)。构造函数中对牌桌进行初始化并进行洗牌。先用 Card 对象填充牌桌，即创建 52 个 Card 对象并加入 de
19、ck 数组。然后洗牌，即将数组中的 Card 对象根据花色和点数随机排列。printCards()函数将所有 Card 对象打印出来。 主控逻辑代码在 main 函数中实现。在 main()函数中，先初始化 DeckOfCards 类的对象指针 d，即生成一个牌桌： DeckOfCards * d = new DeckOfCards()； 并发牌，即调用 d 的 printCards()函数，实现打印一副扑克牌中每张牌的点数和花色。 在 printCards()函数体内部，为每个数组元素调用当前对象的printCard()一张牌。 main()函数中使用完数组对象之后，需要用 delete 操
20、作进行释放对象，对 d 对象进行删除，即 deleted。 因此，空(1)和(2)需要表示当前对象的 this-；空(3)需要牌桌上纸牌对象，即数组元素 decki；空(4)也需要纸牌对象调用 printCard()，即数组元素 decki；空(5)处为创建DeckOfCards 类的对象指针 d 的 new DeckOfCards()；空(6)需要用对象指针 d 调用打印所有纸牌的printCards()函数，即 d-printCards()。6.试题六(共 15 分) 阅读以下说明和 Java 程序，填补代码中的空缺(1)(6)，将解答填入答题纸的对应栏内。 说明 很多依托扑克牌进行的游戏
21、都要先洗牌。下面的 Java 代码运行时先生成一副扑克牌，洗牌后再按顺序打印每张牌的点数和花色。 java 代码 （分数：15.00）_正确答案：( (1) this (2) this (3) deckcount+ 或等价表示 (4) get(i)getCard() (5) new DeckOfCards() (6) player)解析： 本题考查 Java 语言程序设计的能力，涉及类、对象、方法的定义和相关操作。要求考生根据给出的案例和代码说明，认真阅读，理清程序思路，然后完成题目。 先考查题目说明。本题目中涉及到扑克牌、牌桌、玩家等类以及洗牌和按点数排序等操作。根据说明进行设计。 Card
22、 类内定义了两个 static枚举类型，Face 枚举扑克牌点数，Suit 枚举扑克牌花色。Card 类有两个枚举类型的属性，face 和suit，而且值不再变化，故用 final 修饰。 在使用构造方法 public Card(Face face，Suit suit)新建一个 Card 的对象时，所传入的参数指定 face 和 suit 这两个属性值。因为参数名称和属性名称相同，所以用 this前缀区分出当前对象。在类 Card 中包含方法 getFace()和 getSuit()，分别返回当前对象的face 和 suit 属性值。getCard()方法返回 String 来表示一张牌，包括
23、扑克牌点数和花色。 牌桌类DeckOfCards 包含持有 Card 类型元素的 List 类型对象的声明 List，用以存储牌。List 是 Java 中的一种集合接口，是 Collection 的子接口。构造方法中用 CDd 对象填充牌桌并进行洗牌。先用 Card 对象填充牌桌，即创建 52 个 Card 对象加入 deck 数组，表示牌桌上一副牌(52 张)。然后洗牌，即将数组中的 Card对象根据花色和点数随机排列，使用集合工具类 Collections 中的 shuffle 方法，对以 List 类型表示的deck 数组进行随机排列。Collections 是 Java 集合框架中两
24、个主要工具类之一，用以进行集合有关的操作。 printCards()方法将所有 Card 对象打印出来，按 4 列显示 52 张牌。每张拍的打印用 list.get(i)获得 list 表示的 deck 中的第 i 个 Card 对象，然后进一步调用此对象的 getCard()方法，得到 String 表示的当前一张牌。 玩家类中包括启动发牌洗牌等操作，主入口方法 main 中实现创建牌桌对象，并调用按4 列显示 52 张牌。在 main()中，先初始化 DeckOfCards 类的对象 player，即生成一个牌桌： DeckOfCards player = new DeckOfCards(
25、)； 并发牌，即调用 player 的 printCards()方法，实现按 4列显示 52 张牌打印一副扑克牌中每张牌的点数和花色。在 printCards()方法体内部，用 list 调用每个数组元素，并为每个数组元素调用 getCard()返回当前对象所表示一张牌的花色和点数。用格式化方法进行打印，即： System.out.printf(“%-19s%s“,list.get(i).getCard(),(i+1)%4=0)?“n“:“); 因此，空(1)和(2)需要表示当前对象的 this；空(3)需要牌桌上纸牌对象，并将数组元素下标加 1，即数组元素 deckcount+；空(4)也需要用 list 对象获得纸牌对象的字符串表示，即 list后的 get(i)getCard()；空(5)处为创建 DeckOfCards 类的对象指针 player 的 new DeckOfCards()；空(6)需要用对象player 调用打印所有纸牌的 printCards()函数，即 player。
