1、2014年下半年软件水平考试（初级）程序员下午（应用技术）真题试卷及答案与解析 1 阅读以下说明和流程图，填补流程图中的空缺 (1) (5)，将解答填入答题纸的对应栏内。【说明】 本流程图旨在统计一本电子书中各个关键词出现的次数。假设已经对该书从头到尾依次分离出各个关键词 A(i)|i=1， ， n)(n 1)，其中包含了很多重复项，经下面的流程处理后，从中挑选出所有不同的关键词共 m个K(=(i)|j=1， ， m)，而每个关键词 K(j)出现的次数为 NK(j)， j=1， ， m。【流程图】 2 阅读以 下说明和 C函数，填补代码中的空缺 (1) (5)，将解答填入答题纸的对应栏内。 【
2、说明】 函数 removeDuplicates(char*str)的功能是移除给定字符串中的重复字符，使每种字符仅保留一个，其方法是：对原字符串逐个字符进行扫描，遇到重复出现的字符时，设置标志，并将其后的非重复字符前移。例如，若 str指向的字符串为“aaabbbbscbsss”，则函数运行后该字符串为 “absc”。 【 C代码】 void remoVeDuplicates(char*str) int i， len=strlen(str)； *求字符串长度 * if( (1) )return； *空串或长度为 1的字符串无需处理 * for(i=0； i len； i+) int flag=
3、0； *字符是否重复标志 * int m； for(m= (2) ； m len； m+) if(stri=strm) (3) ； break； if(flag) int n， idx=m； *将字符串第 idx字符之后、与 stri不同的字符向前移 * for(n=idx+1； n len； n+) if(strn!=stri) stridx=strn； (4) ； str (5) = 0； *设置字符串结束标志 * 3 阅读以下说明和 C函数，填补函数代码中的空缺 (1) (5)，将解答填入答题纸的对应栏内。【说明】 队列是一种常用的数据结 构，其特点是先入先出，即元素的插入在表头、删除在
4、表尾进行。下面采用顺序存储方式实现队列，即利用一组地址连续的存储单元存放队列元素，同时通过模运算将存储空间看作一个环状结构 (称为循环队列 )。 设循环队列的存储空间容量为 MAXQSIZE，并在其类型定义中设置base、 rear和 length三个域变量，其中， base为队列空间的首地址， rear为队尾元素的指针， length表示队列的长度。 #define MAXQSIZE 100 typedef struct QElemType*base； *循环队列的存 储空间首地址 * int rear； *队尾元素索引* int length； *队列的长度 * SqQueue； 例如，容
5、量为 8的循环队列如图 3-1所示，初始时创建的空队列如图 3-1(a)所示，经过一系列的入队、出队操作后，队列的状态如图 3-1(b)所示 (队列长度为 3)。下面的 C函数 1、 C函数2和 C函数 3用于实现队列的创建、插入和删除操作，请完善这些代码。 【 C函数1】创建一个空的循环队列。 int InitQueue(SqQueue*Q) *创建容量为 MAXQSIZE的空队列，若成功则返回 1；否则返回 0* Q一base=(QElemType*)malloc(MAXQSIZE* (1) )； if(!Q- base)return 0； Q一length=0； Q- rear=0； r
6、eturn 1； *InitQueue* 【 C函数 2】元素插入循环队列。 int EnQueue(SqQueue*Q， QElemType e) *元素 e入队，若成功则返回 1；否则返回 0* if(Q- length=MAXQSIZE)return 0； Q一 rear= (2) ； Q- baseQ一 rear=e； (3) ， return 1； ) *EnQueue* 【 C函数 3】元素出循环队列。 int DeQueue(SqQueue*Q， QElemType*e) *若队列不空，则删除队头元素，由参数 e带回其值并返回 1；否则返回 0* if( (4) )return
7、0； *e=Q一 base(Q- rearQ- length+1+MAXQSIZE) MAXQSIZE； (5); return 1； *DeQueue* 4 阅读以下说明和 C函数，填补代码中的空缺 (1) (6)，将解答填入答题纸的对应栏内。【说明】 二叉树的宽度定义为含有结点数最多的那一层上的结点数。函数GetWidth()用于求二叉树的宽度。其思路是根据树的高度设置一个数组 counter，counteri存放第 i层上的结点数，并按照层次顺序来遍历二叉树中的结点，在此过程中可获得每个结点的层次值，最后从 counter中取出最大的元素就是树的宽度。 按照层次顺序遍历二叉树的实现方法是
8、借助一个队列，按访问结点的先后顺序来记录结点，离根结点越近的结点越先进入队列，具体处理过程为：先令根结点及其层次号 (为 1)进入初始为空的队列，然后在队列非空的情况下，取出队头所指示的结点及其层次号，然后将该结点的左子树根结点及层次号入队列 (若左子树存在 )，其次将该结点的右子树根结点及层次号入队列 (若右子树存在 )，然后再取队头，重复该过程直至完成遍历。 设二叉树采用二叉链表存储，结点类型定义如下： typedef struct BTNode TElemType data； struct BTNode *left， *right； )BTNode，*BiTree； 队列元素的类型定义如
9、下： typedef struct BTNode*ptr； int LevelNumbe r； )QElemType； GetWidth()函数中用到的函数原型如下所述，队列的类型名为 QUEUE：【 C函数】 int GetWidth(BiTree root) QUEUE Q； QElemType a， b； int width，height=GetHeight(root)； int i， *counter=(int*)calloc(height+l， sizeof(int); if( (1) ) return一 1； *申请空间失败 * if(!root) return 0； *空树的宽度
10、为 0* if( (2) ) return一 1； *初始化队列失败时返回 * a ptr=root； a LeveiNumber=1； if(!EnQueue( Q， a)return一 1 ; *元素入队列操作失败时返回 * while(!isEmpty(Q) if( (3) )return一 1； *出队列操作失败时返回 * counterb LevelNumber+; *对层号为 b LevelNumber的结点计数 * if(b ptr- left) *若左子树存在，则左子树根结点及其层次号入队 * a ptr=b ptr一 left； a LevelNumber= (4) ； if
11、(!EnQueue( Q， a)return一 1； i f(b ptr一right) *若右子树存在，则右子树根结点及其层次号入队 * a ptr=b ptr一right ； a LevelNumber= (5) ； if(!EnQueue( int main () DeckofCards*d= (5) ； 生成一个牌桌 (6) ; 打印一副扑克牌中每张牌的点数和花色 delete d； return 0； 6 阅读以下说明和 Java程序，填补代码中的空缺 (1) (6)，将解答填入答题纸的对应栏内。 【说明】 很多依托扑克牌进行的游戏都要先洗牌。下面的 Java代码运行时先生成一副扑克牌
12、，洗牌后再按顺序打印每张牌的点数 和花色。 Java代码 import java uti1 List； import java uti1 Arrays； import java uti1 Collections； clasS Card扑克牌类 publiC StatiC enum FaceAce t Deuce , Three , Four , Five , Six, Seven， Eight， Nine， Ten， Jack， Queen， King)； 枚举牌点 public static enum Suit(Clubs， Diamonds， Hearts， Spades；枚举花色 pri
13、vate final Face face ; private final Suit suit； public Card(Face face， Suit suit) (1) face=face； (2) suit=suit； public Face getFace() return face； public suit qetSLlit() return suit; public String getCard()( 返回 String来表示一张牌 return String format(“ S， S”， face， suit)； 牌桌类 clas S DeckOfCards private Li
14、stlist； 声明 List以存储牌 public DeckOfCards() 初始 化牌桌并进行洗牌 Carddeck=new Card52； int count=0； 牌数 用 Card对象填充牌桌 for(Card Suit suit： Card Suit values() for(Card Face face： Card Face values() (3) =new Card(face， suit); list=Arrays asList(deck)； Collections shuffle(list)； 洗牌 public void printCards() 按 4列显示 52张牌
15、 for(int i=0； i list Size()； i+) System.out.printf(”一 19s s”， list (4) ， (i+1) 4=0)?“ n”： “)； public class Dealer public static void main(Stringargs) DeckOfCards player= (5) ； (6) printCards()； 2014年下半年软件水平考试（初级）程序员下午（应用技术）真题试卷答案与解析 1 【正确答案】 (1)1 (2)K(j) (3)NK(j)+1NK(j) 或 NK(j)+ 或等价表示 (4)m+1m 或 m+ 或
16、等价表示 (5)A(i) 【试题解析】 流程图中的第 1框显然是初始化。 A(1)一 K(1)意味着将本书的第 1个关键词作为选出的第 1个关键词。 1一 NK(1)意味着此时该关键词的个数置为1。 m是动态选出的关键词数目，此时应该为 1，因此 (1)处应填 l。 本题的算法是对每个关键词与已选出的关键词进行逐个比较。凡是遇到相同的，相应的计数就增加 1；如果始终没有遇到相同关键词的，则作为新选出的关键词。 流程图第 2框开始对 i=2,n循环，就是对书中其他关键词逐个进行处理。流程图第 3框开始 j=1， m循环，就是按已选出的关键词依次进 行处理。 接着就是将关键词 A(i)与选出的关键
17、词 K(j)进行比较。因此 (2)处应填 K(j)。 如果 A(i)=K(j)，则需要对计数器： NK(j)增 1，即执行 NK(j)+1NK(j) 。因此 (3)处应填 NK(j)+1NK(j) 。执行后，需要跳出 j循环，继续进行 i循环，即根据书中的下一个关键词进行处理。 如果 A(i)不等于 NKj)，则需要继续与下个 NK(j)进行比较，即继续执行 j循环。如果直到 j循环结束仍没有找到匹配的关键词，则要将该 A(i)作为新的已选出的关键词。因此，应执行 A(i)K(m+1) 以及 m+1m 。更优的做法是先将计数器m增 1，再执行 A(i)K(m) 。因此 (4)处应填 m+1m
18、， (5)处应填 A(i)。 2 【正确答案】 (1)len 2 或 len =1 或等价表示 (2)i+1 或等价表示 (3)flag=1 或给 flag赋值为任何一个不是 0的值 (4)idx+ 或 idx=idx+1 或等价表示 (5)idx 或等价表示 【试题解析】 本题考查 C语言基本应用。 题目要求在阅读理解代码说明的前 提下完善代码。字符串的运算处理是 C程序中常见的基本应用。 根据注释，空 (1)处应填入的内容很明确，为 “fenI” 或其等价表示。 要消除字符串中的重复字符，需要扫描字符串，这通过下面的代码来实现： for(i=0； i len； i+) int flag=0
19、； *字符是否重复标志 * int m； for(m= (2) ； m len； m+) if(stri=strm) (3) ； break； 上面代码中，循环变量 i用于顺序地记下字符串中每个不同字符首次出现的位置，那么后面的处理就是从 i的下一个位置开始，考查后面的字符中有没有与它相同的 (stri=strm)，因此空 (2)应填入 “i+1”或其等价表示。显然，当发现了重复字符时，应设置标志，空 (3)处应填入 “flag=1”或者给 flag赋值为任何一个不是 O的值。 根据说明，发现与 s仃 i相同的第一个字符 strm后，需要将其后所有与 stri不同的字符前移，以覆盖重复字符 s
20、trm，对应的代码如下： if (flag ) int n， idx=m； *将字符串第 idx字符之后、与 stri不同的字符向前移 * for( n=idx+l； n len； n+ ) if( strn!=stri ) stridx =strn； (4) ； str (5) = 0； *设置字符串结束标志 * 初始时， idx等于 m，使 strn覆盖 stridx后，需要将 idx自增，以便将后面与stri不同的字符继续前移，因此空 (4)处应填入 “idx+”或等价表示。由于后面字符前移了，所以字符串结束标志也需重新设置，空 (5)处应填入 “idx”。 3 【正确答案】 (1)si
21、zeofi(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语言基本应用。 队列是一种基本的数据结构，其基本操作有初始化、判断是否为空、入队列和出队列等。 循环队列是一种采用顺序存储结构实现的队列，其特点是将队列存储空间的首尾单元在逻辑上连接起来，从而得到一个环形结构的队列空间。 在
22、循环队列的类型定义 SqQueue中，指针成员 base存放队列空间的首地址，存储空间应在队列的初始化操作中实 现，对应的语句如下： Q一 base= (QElemType*)malloc(MAXQSIZE* (1) )； 由于 InitQueue(SqQueue*Q)的形参为指向结构体的指针，因此队列的参数可表示为 “Q- base、 Q- rear、 Q- length”或 “(*Q) base、 (*Q) rear、(*Q) length”，由于队列元素类型为 QElemType、队列容量为 MAXQSIZE，因此空 (1)处应填入 “sizeof(QElemType)”。 入队列操作由
23、 EnQueue(SqQueue*Q， QElemType e)实现。由于循环队列空间的容量为 MAXQSIZE(也就是队满条件为 “Q- length =MAXQSIZE”)，因此元素入队列时，需先判断是否队满，在队列中有空闲单元的情况下才能进行入队列操作。其次需确定新元素在队列空间中的位置，从图 31(b)中可以看出， Q-rear指出了当前队尾元素，新元素应放入下一个位置，结合队列环形空间的要求，空 (2)处应填入 “(Q- rear+1) MAXQSIZE”或其等价形式。通过 “Q-baseQ- rear=e”将元素 加入队列后，队列长度增加了，因此空 (3)处应填入 “Q-lengt
24、h+”或其等价形式。 出队列操作由 DeQueue(SqQueue*Q， QElemType*e)实现。元素出队列时，需要判断队列是否为空，显然，队列长度为 0就直接表示了队空，因此空 (4)处应填入 “Q- length=0”或其等价形式，空 (5)处应填入 “Q- length-”或其等价形式。 4 【正确答案】 (1)!counter或 0=counter或 NULL=counter或等价表示 (2)!InitQueue(&Q) 或 0=InitQueue(&Q) 或等价表示 (3)!DeQueue(&Q， &b)或 0=DeQueue(&Q， b) 或等价表示 (4)b LevelNu
25、mber+1 或等价表示 (5)b LevelNumber+1 或等价表示 (6)counteri width 或等价表示 【试题解析】 本题考查数据结构实现和 C语言基本应用。 考生需要认真阅读题目中的说明，以确定代码部分的处理逻辑，从而完成代码。 根据注释，空 (1)处应填入 “!counter”或其等价形式。 由于初始化队列的函数原型为 “InitQueue(QUEUE*Q)”且返回值为 0表示操作失败，因此调用该函数时实参应取地址，即空 (2)处应填入 “!InitQueue(&Q)”或其等价形式。 空 (3)处需进行出队列操作，同时通过参数得到队头元素，根据说明，该空应填入 “!De
26、Queue(&Q， &b)”或其等价形式。 出队操作后，得到的队头元素用 b表示，根据队列元素的类型定义，其对应结点在二叉树中的层次号表示为 b LevelNumber，显然，其孩子结点的 层次号应加1，因此空 (4)和 (5)处应填入 “b LevelNumber+1”。 从代码中可知变量 width的作用是表示最大的层次编号，并通过顺序地扫描数组 counter中的每一个元素来确定 width的值，显然，空 (6)处应填入 “counteriwidth”或其等价形式。 5 【正确答案】 (1)this- (2)this- (3)decki 或 *(deck+i) 或等价表示 (4)deck
27、i 或 *(deck+i)或等价表示 (5)new DeckOfCards() (6)d- printCards() 或等价表示 【试题解析】 本题考查 C+语言程序设计能力，涉及类、对象、函数的定义和相关操作。要求考生根据给出的案例和代码说明，认真阅读，理清程序思路，然后完成题目。 本题目中涉及到扑克牌、牌桌等类以及洗牌和按点数排序等操作。根据说明进行设计。 定义了两个数组， Rank表示扑克牌点数， Suits表示扑克牌花色，定义时进行初始化，而且值不再变化，故用 const修饰。 Card类有两个属性， rank和 suit，在使用构造函数 Card(int rank， int suit
28、)新建一个 Card的对象时，所传入的参数指定 rank和 suit这两个属性值。因为参数名称和属性名称相同，所以用 this-前缀区分出当前对象。在类 Card中包含方法getRank()和 getSuit()，分别返回当前对象的 rank和 suit属性值。 printCard()函数打印扑克牌点数和花色。 DeckOfCards类包含 Card类型元素的数组 deck52，表示牌桌上一副牌 (52张 )。构造函数中对牌桌进行初始化并进行洗牌。 先用 Card对象填充牌桌，即创建 52个 Card对象并加入 deck数组。然后洗牌，即将数组中的 Card对象根据花色和点数随机排列。 pri
29、ntCards()函数将所有 Card对象打印出来。 主控逻辑代码在 main函数中实现。在 main(、 )函数中，先初始化 DeckOfCards类的对象指针 d，即生成一个牌桌： DeckOfCards *d=new DeckOfCards()； 并发牌，即调用 d的 printCards()函数，实现打印一副扑克牌中每张牌的点数和花色。 在 printCardsO函数体内部，为每个数组元素调用当前对象的 printCard()一张牌。 mainO函数中使用完数组对象之后，需要用 delete操作进行释放对象，对 d对象进行删除，即 delete d。 因此，空 (1)和 (2)需要表示
30、当前对象的 this-；空 (3)需要牌桌上纸牌对象，即数组元素 decki；空 (4)也需要纸牌对象调用 printCard()，即数组元素 decki；空 (5)处为创建 DeckOfCards类的对象指针 d的 new DeckOfCards()；空 (6)需要用对象指针 d调用打印所 有纸牌的 printCards()函数，即 d- printCards()。 6 【正确答案】 (1)this (2)this (3)deckcount+ 或等价表示 (4)get(i) getCard() (5)new DeckOfCards() (6)player 【试题解析】 本题考查 Java语言
31、程序设计的能力，涉及类、对象、方法的定义和相关操作。要求考生根据给出的案例和代码说明，认真阅读，理清程序思路，然后完成题目。 先考查题目 说明。本题目中涉及到扑克牌、牌桌、玩家等类以及洗牌和按点数排序等操作。根据说明进行设计。 Card类内定义了两个 static枚举类型， Face枚举扑克牌点数， Suit枚举扑克牌花色。 Card类有两个枚举类型的属性， face和 suit，而且值不再变化，故用 fina1修饰。 在使用构造方法 public Card(Face face， Suit suit)新建一个 Card的对象时，所传入的参数指定 face和 suit这两个属性值。因为参数名称和
32、属性名称相同，所以用 this前缀区分出当前对象。在类 Card中包含方法 getFace()和 getSuit()，分别返回当前对象的 face和 suit属性值。 getCard()方法返回 String来表示一张牌，包括扑克牌点数和花色。 牌桌类 DeckOfCards包含持有 Card类型元素的 List类型对象的声明 List，用以存储牌。 List是 JaVa中的一种集合接口，是 Collection的子接口。构造方法中用 Card对象填充牌桌并进行洗牌。先用 Card对象填充牌桌，即创建 52个 Card对象加入 deck数组，表示牌桌上一副牌 (52张 )。然后洗牌，即将数组中
33、的 Card对象根据花色和点数随机排列，使用集合工具类 Collections中的 shuffie方法，对以 Ifist类型表示的 deck数组进行随机排列。 Collections是 Java，集合框架中两个主要工具类之一，用以进行集合有关的操作。 printCards()方法将所有 Card对象打印出来，按 4列显示 52张牌。每张拍的打印用 list get(i)获得 list表示的 deck中的第 i个 Card对象，然后进一步调用此对象的 getCard()方法，得到 String表示的当前一张牌。 玩家类中包括启动发 牌洗牌等操作，主入口方法 main中实现创建牌桌对象，并调用按
34、4列显示 52张牌。在 main()中，先初始化 DeckOfCards类的对象 player，即生成一个牌桌： DeckOfCards player = new DeckOfCards()； 并发牌，即调用 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。
