1、计算机水平考试初级程序员 2014 年上半年下午真题及答案解析(总分：90.00，做题时间：150 分钟)试题一(共 15 分) 阅读以下说明和流程图，填补流程图中的空缺(1)(5)，将解答填入答题纸的对应栏内。说明 指定网页中，某个关键词出现的次数除以该网页长度称为该关键词在此网页中的词频。对新闻类网页，存在一组公共的关键词。因此，每个新闻网页都存在一组词频，称为该新闻网页的特征向量。 设两个新闻网页的特征向量分别为：甲(a1，a2，ak)、乙(b1，b2，bk)，则计算这两个网页的相似度时需要先计算它们的内积 Sa1b1+a2b2+akbk。一般情况下，新闻网页特征向量的维数是巨大的，但每
2、个特征向量中非零元素却并不多。为了节省存储空间和计算时间，我们依次用特征向量中非零元素的序号及相应的词频值来简化特征向量。为此，我们用(NA(i)，A(i)|i1，2，m)和(NB(j)，B(j)|j1，2，n)来简化两个网页的特征向量。其中：NA(i)从前到后描述了特征向量甲中非零元素 A(i)的序号(NA(1)NA(2)，NB(j)从前到后描述了特征向量乙中非零元素 B(j)的序号(NB(1)NB(2)。 下面的流程图描述了计算这两个特征向量内积 S 的过程。 （分数：15.00）(1).(1)（分数：3.00）_(2).(2)（分数：3.00）_(3).(3)（分数：3.00）_(4).
3、(4)（分数：3.00）_(5).(5)（分数：3.00）_试题二(共 15 分) 阅读以下说明和 C 函数，填补代码中的空缺(1)(5)，将解答填入答题纸的对应栏内。 说明 1 函数 isPrime(int n)的功能是判断 n 是否为素数。若是，则返回 1，否则返回 0。素数是只能被1 和自己整除的正整数。例如，最小的 5 个素数是 2，3，5，7，11。 C 函数 说明 2 函数 int minOne(int arr，int k)的功能是用递归方法求指定数组中前 k 个元素中的最小者，并作为函数值返回。 C 函数 （分数：15.00）(1).(1)（分数：3.00）_(2).(2)（分数
4、：3.00）_(3).(3)（分数：3.00）_(4).(4)（分数：3.00）_(5).(5)（分数：3.00）_试题三(共 15 分) 阅读以下说明和 C 程序，填补代码中的空缺(1)(5)，将解答填入答题纸的对应栏内。 说明 函数 areAnagrams(char*fstword，char *sndword)的功能是判断 fstword 和 sndword 中的单词(不区分大小写)是否互为变位词，若是则返回 1，否则返回 0。所谓变位词是指两个单词是由相同字母的不同排列得到的。例如，“triangle”与“integral”，互为变位词，而“dumbest”与“stumble”不是。函数
5、 areAnagrams 的处理思路是检测两个单词是否包含相同的字母且每个字母出现的次数也相同。过程是先计算第一个单词(即 fstword 中的单词)中各字母的出现次数并记录在数组 counter 中，然后扫描第二个单词(即 sndword 中的单词)的各字母，若在第二个单词中遇到与第一个单词相同的字母，就将相应的计数变量值减 1，若在第二个单词中发现第一个单词中不存在的字母，则可断定这两个单词不构成变位词。最后扫描用于计数的数组 counter 各元素，若两个单词互为变位词，则 counter 的所有元素值都为 0。 函数 areAnagrams 中用到的部分标准库函数如下表所述。 C 函数
6、 （分数：15.00）(1).(1)（分数：3.00）_(2).(2)（分数：3.00）_(3).(3)（分数：3.00）_(4).(4)（分数：3.00）_(5).(5)（分数：3.00）_试题四(共 15 分) 阅读以下说明和 C 函数，填补代码中的空缺(1)(5)，将解答填入答题纸的对应栏内。 说明 函数 ReverseList(LinkList headptr)的功能是将含有头结点的单链表就地逆置。处理思路是将链表中的指针逆转，即将原链表看成由两部分组成：已经完成逆置的部分和未完成逆置的部分，令 s 指向未逆置部分的第一个结点，并将该结点插入已完成部分的表头(头结点之后)，直到全部结点
7、的指针域都修改完成为止。 例如，某单链表如图 41 所示，逆置过程中指针 s 的变化情况如图 4-2 所示。 链表结点类型定义如下 C 函数 （分数：15.00）(1).(1)（分数：3.00）_(2).(2)（分数：3.00）_(3).(3)（分数：3.00）_(4).(4)（分数：3.00）_(5).(5)（分数：3.00）_试题五(共 15 分) 阅读下列说明、C+代码和运行结果，填补代码中的空缺(1)(5)，将解答填入答题纸的对应栏内。 说明 对部分乐器进行建模，其类图如图 51 所示，包括：乐器(Instrument)、管乐器(Wind)、打击乐器(Percussion)、弦乐器(S
8、tringed)、木管乐器(Woodwind)、铜管乐器(Brass)。 下面是实现上述设计的 C+代码，其中音乐类(Music)使用各类乐器(Instrument)进行演奏和调音等操作。 C+代码 本程序运行后的输出结果为： （分数：15.00）(1).(1)（分数：3.00）_(2).(2)（分数：3.00）_(3).(3)（分数：3.00）_(4).(4)（分数：3.00）_(5).(5)（分数：3.00）_试题六(共 15 分) 阅读以下说明和 Java 程序，填补代码中的空缺(1)(5)，将解答填入答题纸的对应栏内。 说明 对部分乐器进行建模，其类图如图 6-1 所示，包括：乐器(I
9、nstrument)、管乐器(Wind)、打击乐器(Percussion)、弦乐器(Stringed)、木管乐器(Woodwind)、铜管乐器(Brass)。 下面是实现上述设计的 Java 代码，其中音乐类(Music)使用各类乐器(Instrument)进行演奏和调音等操作。 java代码 本程序运行后的输出结果为： （分数：15.00）(1).(1)（分数：3.00）_(2).(2)（分数：3.00）_(3).(3)（分数：3.00）_(4).(4)（分数：3.00）_(5).(5)（分数：3.00）_计算机水平考试初级程序员 2014 年上半年下午真题答案解析(总分：90.00，做题时
10、间：150 分钟)试题一(共 15 分) 阅读以下说明和流程图，填补流程图中的空缺(1)(5)，将解答填入答题纸的对应栏内。说明 指定网页中，某个关键词出现的次数除以该网页长度称为该关键词在此网页中的词频。对新闻类网页，存在一组公共的关键词。因此，每个新闻网页都存在一组词频，称为该新闻网页的特征向量。 设两个新闻网页的特征向量分别为：甲(a1，a2，ak)、乙(b1，b2，bk)，则计算这两个网页的相似度时需要先计算它们的内积 Sa1b1+a2b2+akbk。一般情况下，新闻网页特征向量的维数是巨大的，但每个特征向量中非零元素却并不多。为了节省存储空间和计算时间，我们依次用特征向量中非零元素的
11、序号及相应的词频值来简化特征向量。为此，我们用(NA(i)，A(i)|i1，2，m)和(NB(j)，B(j)|j1，2，n)来简化两个网页的特征向量。其中：NA(i)从前到后描述了特征向量甲中非零元素 A(i)的序号(NA(1)NA(2)，NB(j)从前到后描述了特征向量乙中非零元素 B(j)的序号(NB(1)NB(2)。 下面的流程图描述了计算这两个特征向量内积 S 的过程。 （分数：15.00）(1).(1)（分数：3.00）_正确答案：(0)解析：(2).(2)（分数：3.00）_正确答案：(S+A(j)B(j) 或 等价表示)解析：(3).(3)（分数：3.00）_正确答案：(im 或
12、 im+1 或等价表示)解析：(4).(4)（分数：3.00）_正确答案：(jn 或 jn+1 或等价表示)解析：(5).(5)（分数：3.00）_正确答案：(im or jn 或 im+1 or j=n+1 或等价表示)解析：试题一分析 本题是简化了的一个大数据算法应用之例。世界上每天都有大量的新闻网页，门户网站需要将其自动进行分类，并传送给搜索的用户。为了分类，需要建立网页相似度的衡量方法。流行的算法是，先按统一的关键词组计算各个关键词的词频，形成闷页的特征向量，这样，两个网页特征向量的夹角余弦(内积两个向量模的乘积)，就可以衡量两个网页的相似度。因此，计算两个网页特征向量的内积就是分类计
13、算中的关键。 对于存在大量零元素的稀疏向量来说，用题中所说的简化表示方法是很有效的。这样，求两个向量的内积只需要在分别从左到右扫描两个简化向量时，计算对应序号相同(NA(i)=NB(j)时的 A(i)*B(j)之和(其他情况两个向量对应元素之乘积都是 0)。因此，流程图中(2)处应填 S+A(i)*B(j)，而累计的初始值 S 应该为 0，即(1)处应填 0。 流程图中，NA(i)NB(j)时，下一步应再比较 NA(i)n 或 jn+1(如果成立，则扫描结束)。因此(4)处应填 jn 或 j=n+1。 (5)处应填扫描结束的条件，im or jn 或 i=m+1 or jn+1，即两个简化向量
14、之一扫描结束时，整个扫描就结束了。试题二(共 15 分) 阅读以下说明和 C 函数，填补代码中的空缺(1)(5)，将解答填入答题纸的对应栏内。 说明 1 函数 isPrime(int n)的功能是判断 n 是否为素数。若是，则返回 1，否则返回 0。素数是只能被1 和自己整除的正整数。例如，最小的 5 个素数是 2，3，5，7，11。 C 函数 说明 2 函数 int minOne(int arr，int k)的功能是用递归方法求指定数组中前 k 个元素中的最小者，并作为函数值返回。 C 函数 （分数：15.00）(1).(1)（分数：3.00）_正确答案：(n2=0，或!(n2)，或其等价形
15、式)解析：(2).(2)（分数：3.00）_正确答案：(nk=0，或!(nk)，或其等价形式)解析：(3).(3)（分数：3.00）_正确答案：(arr0，或*arr，或其等价形式)解析：(4).(4)（分数：3.00）_正确答案：(k-1， 或其等价形式)解析：(5).(5)（分数：3.00）_正确答案：(t)解析：试题二分析 本题考查 C 程序的基本语法和运算逻辑。 首先应认真分析题目中的说明，然后确定代码结构和各变量的作用。 函数 isPrime(int n)的功能是判断 n 是否为素数。根据素数的定义，小于 2 的数和大于 2 的偶数都不是素数，n 是偶数可表示为“n2 等于 0”，因
16、此空(1)处应填入“n20”，或者“!(n2)”。 在 n 是大于 2 的奇数的情况下，下面的代码从 3 开始查找 n 的因子，直到 n 的平方根为止。 for(k=3;k试题三(共 15 分) 阅读以下说明和 C 程序，填补代码中的空缺(1)(5)，将解答填入答题纸的对应栏内。 说明 函数 areAnagrams(char*fstword，char *sndword)的功能是判断 fstword 和 sndword 中的单词(不区分大小写)是否互为变位词，若是则返回 1，否则返回 0。所谓变位词是指两个单词是由相同字母的不同排列得到的。例如，“triangle”与“integral”，互为变
17、位词，而“dumbest”与“stumble”不是。函数 areAnagrams 的处理思路是检测两个单词是否包含相同的字母且每个字母出现的次数也相同。过程是先计算第一个单词(即 fstword 中的单词)中各字母的出现次数并记录在数组 counter 中，然后扫描第二个单词(即 sndword 中的单词)的各字母，若在第二个单词中遇到与第一个单词相同的字母，就将相应的计数变量值减 1，若在第二个单词中发现第一个单词中不存在的字母，则可断定这两个单词不构成变位词。最后扫描用于计数的数组 counter 各元素，若两个单词互为变位词，则 counter 的所有元素值都为 0。 函数 areAna
18、grams 中用到的部分标准库函数如下表所述。 C 函数 （分数：15.00）(1).(1)（分数：3.00）_正确答案：(strcmp(fstword，sndword)0，或其等价形式)解析：(2).(2)（分数：3.00）_正确答案：(fstword+，或其等价形式)解析：(3).(3)（分数：3.00）_正确答案：(return 0)解析：(4).(4)（分数：3.00）_正确答案：(sndword+，或其等价形式)解析：(5).(5)（分数：3.00）_正确答案：(counterindex，或 counterindex!0，或其等价形式)解析：试题三分析 本题考查 C 程序的基本语法和
19、运算逻辑。 首先应认真分析题目中的说明，然后确定代码结构和各变量的作用。 空(1)所在语句是比较两个字符串，若它们完全相同，则可断定不是变位词。显然，根据说明中的描述，可以用标准库函数 strcmp 来完成该处理，当两个字符串相同时，strcmp 的返回值为 0。因此，空(1)处应填入“strcmp(fstword，sndword)0”或“!strcmp(fstword，sndword)”或其等价方式。 上面代码中的第一个 while 语句用于扫描第一个单词中各字母出现的次数，并直接存入对应的数组元素 counter中，显然，空(2)处应填入“fstword+”或其等价方式，从而可以遍历单词中
20、的每个字母。 在接下来的 while 语句中，通过 sndword 逐个扫描第二个单词中的字母，当*sndword 表示的字母在第一个单词中没有出现时(与该字母对应的数组元素 counter的值为 0)，这两个单词显然不互为变位词，在这种情况下函数可返回，因此空(3)处应填入“return 0”。空(4)处的处理与空(2)类似，应填入“sndword+”或其等价形式。 根据题目中的说明，若两个词互为变位词，则它们包含的字母及每个字母出现的次数相同，这样数组 counter 的每个元素都应为 0，如若不然，则可断定不是变位词。因此，空(5)处应填入“counterindex”或“counter
21、index!0” 或其等价形式。试题四(共 15 分) 阅读以下说明和 C 函数，填补代码中的空缺(1)(5)，将解答填入答题纸的对应栏内。 说明 函数 ReverseList(LinkList headptr)的功能是将含有头结点的单链表就地逆置。处理思路是将链表中的指针逆转，即将原链表看成由两部分组成：已经完成逆置的部分和未完成逆置的部分，令 s 指向未逆置部分的第一个结点，并将该结点插入已完成部分的表头(头结点之后)，直到全部结点的指针域都修改完成为止。 例如，某单链表如图 41 所示，逆置过程中指针 s 的变化情况如图 4-2 所示。 链表结点类型定义如下 C 函数 （分数：15.00
22、）(1).(1)（分数：3.00）_正确答案：(!headptr-next，或!headptr|!headptr-next，或其等价形式)解析：(2).(2)（分数：3.00）_正确答案：(headptr-next)解析：(3).(3)（分数：3.00）_正确答案：(headptr-next-next， 或 p-next， 或其等价形式)解析：(4).(4)（分数：3.00）_正确答案：(s-next， 或 p-next， 或其等价形式)解析：(5).(5)（分数：3.00）_正确答案：(p)解析：试题四分析 本题考查 C 语言的指针应用和运算逻辑。 本问题的图和代码中的注释可提供完成操作的主
23、要信息，在充分理解链表概念的基础上填充空缺的代码。 对于含有头结点的单链表，链表为空时，头结点的指针域为空，表示之后没有其他结点了。因此，空(1)处应填入“!headptrnext”。 根据注释，空(2)处所在语句令 p 指向链表的第一个元素结点，因此空(2)处应填入“headptr-next”。 空(3)处的语句执行后，可由图 41 所示的链表得到图 42(a)的链表，空(3)处应填入“p-next”或者“headptrnext-next”。 代码中的 while 循环完成链表中除第一个元素结点之外的其他结点的指针域的修改。根据题目中的说明，s 指向未逆置部分的第一个结点。在 while 循
24、环中，变量 p 的作用是辅助完成将 s 所指结点插入头结点之后的处理，处理步骤为： 试题五(共 15 分) 阅读下列说明、C+代码和运行结果，填补代码中的空缺(1)(5)，将解答填入答题纸的对应栏内。 说明 对部分乐器进行建模，其类图如图 51 所示，包括：乐器(Instrument)、管乐器(Wind)、打击乐器(Percussion)、弦乐器(Stringed)、木管乐器(Woodwind)、铜管乐器(Brass)。 下面是实现上述设计的 C+代码，其中音乐类(Music)使用各类乐器(Instrument)进行演奏和调音等操作。 C+代码 本程序运行后的输出结果为： （分数：15.00）
25、(1).(1)（分数：3.00）_正确答案：(virtual void play(Note n)=0)解析：(2).(2)（分数：3.00）_正确答案：(：public Instrument)解析：(3).(3)（分数：3.00）_正确答案：(：public Wind)解析：(4).(4)（分数：3.00）_正确答案：(Instrument*)解析：(5).(5)（分数：3.00）_正确答案：(new)解析：试题五分析 本题考查 C+程序设计的基本能力，涉及类、对象、函数的定义和相关操作。要求考生根据给出的案例和代码说明，认真阅读理清程序思路，然后完成题目。 先考察题目说明。本题目中涉及的部分
26、乐器，音乐类利用各类乐器进行演奏和调音等操作。根据说明进行设计，题目给出了类图(图 5-1 类图所示)。 图中父接口 Instrument，代表乐器，C+中设计为抽象基类，包含表示进行演奏的接口函数 play()和表示调音的接口函数 adjust()，其中函数 play()的参数 Note 实现为枚举类型(enum)，以枚举各种音调。这两个函数由具体子类型完成实现，所以 Instrument 的 play()和 adjust()为纯虚函数，原型中0 表示纯虚函数，实现由于类完成： virtual void play(Note n)O； virtual void run() 0； Wind、Pe
27、rcussion 和 Stringed 都是继承自 Instrument 的三个子类型，所以他们都继承了Instrument 的 play()和 adjust()函数，各自演奏和调音方式有所不同，所以都覆盖了 Instrument 的play()函数和 adjust()函数，并加以实现： void play(Note n) *代码略* void adjust() *代码略* Wind 的两个子类型 Woodwind 和 Brass 都继承自 Wind，继承用：Public 关键字，从而Woodwind 和 Brass 也都继承了 Instrument 的 play()函数和 adjust()函
28、数。图 51 中 Woodwind 类对应的 Woodwind 的实现中只有 play()，没有 adjust()，因此其父类 Wind 的 adjust()会自动被调用。 Music类对各类乐器进行演奏和调音操作。函数 tune()为一个乐器的定调，其参数为乐器对象指针Intrument*；函数 adjust()为一个乐器进行调音，其参数也为 Intrument*；函数 tuneAll()为每个乐器定调，其参数是所有乐器数组。Music 中的 tune()和 adjust()的参数均为 Insbument*类型的对象指针i，调用函数 play()和 adjust()，其真正执行的函数根据所传
29、实际对象指针所指对象而定，即动态绑定。 所有乐器用 Instument*对象指针数组 orchestra 表示；使用模板定义一个函数 size，该函数的参数为数组 array，函数返回数组 array 的元素个数，表示乐器的数量。 主控逻辑代码在 main 函数中实现。在main()函数中，先初始化 Music 类的对象指针 music，即： Music* music=new Music()； 并初始化各类乐器对象指针数组 orchestra，各类乐器用抽象父类 Instrument 类型，因为向上转型是安全的，可以自动向上转型成为 Instrument 类型，用父类表示其各个子类型，即： I
30、nstrument * orchestra = new wind(),new woodwind(); 然后调用 music 的 tuneAll()函数，实现为 orchestra 中的每个乐器定调。其参数为 orchestra 数组以及使用 size 计算的数组中的对象指针个数。0rchestra 指针数组的类型为Instrument*，所以 tuneAll 的第一个参数也应该为 Instrument*，而非其子类型。在 tuneAll()函数体内部，为每个数组元素调用当前对象的 tune()和 adjust()。 数组 orchestra 中第一个元素为 Wind 类对象，第二个元素为 Wo
31、odwind 类对象。tuneAll()中循环的第一次执行时 tune()函数中语句 i-p1ay(MIDDLE_C)；调用 wind 中的 play()函数，因此输出 Windplay()0；adjust()函数中语句 i-adjust()；为调用 Wind类的 adjust()函数，输出为 Windadjust()。tuneAll()中循环的第二次执行时 tune()函数中语句 i-play(MIDDLE_C)；调用 WoodWind 中的 play()函数，因此输出 Woodwindplay()0；adjust()函数中语句i-adjust()；为调用 Woodwind 类的 adjus
32、t()函数，输出为 Woodwindadjust()。 在 main()函数中使用完数组对象之后，需要用 delete 操作进行释放对象，对每个 orchestra 中的元素进行删除，即 delete orchestrai，对 Music 对象进行删除，即 delete music；。 因此，空(1)需要定义纯虚函数 play(Note n)，原型中0 表示纯虑函数，分号在题目代码中已经给出，所以空(1)为 virtual void play(Note n)0；空(2)需要继承 Instrument，即：public Instrument；空(3)需要继承 Wind，即：public Wind；空(4)需要定调的乐器指针，即 Instrument*；空(5)处为创建 Music 类的对象的关键字 new。试题六(共 15 分) 阅读以下说明和 Java 程序，填补代码中的空缺(1)(5)，将解答填入答题纸的对应栏内。 说明 对部分乐器进行建模，其类图如图 6-1 所示，包括：乐器(Instrument)、管乐器(Wind)、打击乐器(Percussion)、弦乐器(Stringed)、木管乐器(Woodwind)、铜管乐器(Brass)。 下面是实现上述设计的 Java 代码，其中音乐类(Music)使用各类乐器(Instrument)进行演奏和调音等操作。 jav
