温故而知新，下笔如有神。近三上半年程序员考试专题考练2及答案-下午卷试题一（共15分）阅读以下说明和流程图， 填补流程图中的空缺（1）-（5），将解答填入答题纸的对应栏内。 指定网页中， 某个关键词出现的次数除以该网页长度称为该关键词在此网页中的词频。 对新闻类网页， 存在一组公共的关键词。因此， 每个新闻网页都存在一组词频， 称为该新闻网页的特征向量。 设两个新闻网页的特征向量分别为： 甲（a1,a2,ak）、乙(b1,b2,. ,bk)，则计算这两个网页的相似度时需要先计算它们的内积S=a1b1+a2b2+akbk。一般情况下，新同网页特征向量的维数是巨大的， 但每个特征向量中非零元素却并不多。 为了节省存储空间和计算时间，我们依次用特征向量中非零元素的序号及相应的词频值来简化特征向量。为此，我们用（NA(i),A(i)|i=1,2,.,m）和（NB(j),B(j)|j=1,2,.,n）来简化两个网页的特征向量。 其中：NA(i)从前到后描述了特征向量甲中非零元素A(i)的序号（NA(1)NA(2) .）, NB(j)从前到后描述了特征向量乙中非零元素B(j)的序号（NB(1) NB(2) m 或 i=m+1 或 等价表示(4) jn 或 j=n+1 或 等价表示(5) im or jn 或 i=m+1 or j=n+1 或 等价表示【试题解析】 本题是简化了的个大数据算法应用之例。世界上每天都有大量的新闻网页，门户网站需要将其自动进行分类，并传送给搜索的用户。为了分类，需要建立网页相似度的衡量方法。流行的算法是，先按统一的关键词组计算各个关键词的词频，形成网页的特征向量，这样，两个网页特征向量的夹角余弦（内积两个向量模的乘积），就可以衡量两个网页的相似度。因此，计算两个网页特征向量的内积就是分类计算中的关键。 对于存在大量零元素的稀疏向量来说，用题中所说的简化表示方法是很有效的。这样，求两个向量的内积只需要在分别从左到右扫描两个简化向量时，计算对应序号相同（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+1)m 或 i=m+1（如果成立，则扫描结束）。因此（3） 处应填im 或 i=m1。 流程图中，NA(i)NB(j)时，下一步应再比较NA(i)n 或 j=n+1（如果成立，则扫描结束）。因此（4）处应填jn 或 j=n+1。 （5）处应填扫描结束的条件，im or jn 或 i=m+1 or j=n+1，即两个简化向量之一扫描结束时，整个扫描就结束了。试题二（共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函数】 【参考答案】（1） n%2=0， 或！(n%2)， 或其等价形式（2） n%k=0， 或！(n%k)， 或其等价形式（3） arr0， 或*arr， 或其等价形式（4） k-1，或其等价形式（5） t【试题解析】本题考查C程序的基本语法和运算逻辑。首先应认真分析题目中的说明，然后确定代码结构和各变量的作用。函数isPrime(int n)的功能是判断n是否为素数。根据素数的定义，小于2的数和大于2的偶数都不是素数，n是偶数可表示为“n%2等于0”，因此空（1）处应填入“n% 2=0”，或者“！(n%2)”。在n是大于2的奇数的情况下，下面的代码从3开始查找n的因子，直到n的平方根为止。若k的值是n的因子，则说明n不是素数。因此，空（2）处应填入“n%k=0”，或者“!(n%k)”。函数int minOne（int tarr, int k）的功能是用递归方法求指定数组中前k个元素中的最小者，显然，k为1时，这一个元素就是最小者。因此，空（3）处应填入“arr0”或其等价形式。空（4）所在的语句是通过递归方式找出arr1arrk-1中的最小者，第一个实参指出从arr1开始， 第二个参数为元素个数， 为k-1个， 因此空（4）应填入“k-1”。接下来的处理就很明确了， 当t表示arr1arrk-1中的最小者， 其与arr0比较后就可以得到arr0arrk-1中的最小者， 因此空（5）处应填入“ t”。 试题三（共15分）阅读以下说明和C程序， 填补代码中的空缺（1）（5）， 将解答填入答题纸的对应栏内。【说明】 函数areAnagrams（char*fstword，char*sndword ）的功能是判断fstword和sndword中的单词（不区分大小写）是否互为变位词，若是则返回1，否则返回0。所谓变位词是指两个单词是由相同字母的不同排列得到的。例如，”triangle“与“ integral” 互为变位词，而“dumbest”与“stumble”不是。 函数areAnagrarns的处理思路是检测两个单词是否包含相同的字母且每个字母出现的次数也相同。 过程是先计算第一个单词（即fstword中的单词）中各字母的出现次数并记录在数组counter中，然后扫描第二个单词（即sndword中的单词）的各字母，若在第二个单词中遇到与第一个单词相同的字母， 就将相应的计数变量值减1， 若在第二个单词中发现第一个单词中不存在的字母， 则可断定这两个单词不构成变位词。最后扫描用于计数的数组counter各元素，若两个单词互为变位词， 则counter的所有元素值都为0。 函数areAnagrams中用到的部分标准库函数如下表所述。【C函数】 【参考答案】（1）strcmp( fstword, sndword)=0 ，或其等价形式（2）fstword+， 或其等价形式（3） return 0（4） sndword+，或其等价形式（5） counterindex，或 counter index!=0，或其等价形式【试题解析】本题考查C程序的基本语法和运算逻辑。首先应认真分析题目中的说明， 然后确定代码结构和各变量的作用。空（1）所在语句是比较两个字符串，若它们完全相同，则可断定不是变位词。显然，根据说明中的描述，可以用标准库函数 strcmp 来完成该处理，当两个字符串相同时， strcmp 的返回值为 0 。 因此， 空（1）处应填入 “ strcmp(fstword, sndword)=0 ” 或 “ !strcmp（fstword, sndword）” 或其等价方式。上面代码中的第一个 while 语句用于扫描第一个单词中各字母出现的次数，并直接存入对应的数组元素 counter中，显然，空（2）处应填入 “ fstword” 或其等价方式，从而可以遍历单词中的每个字母。在接下来的 while 语旬中，通过 sndword 逐个扫描第二个单词中的字母，当*sndword 表示的字母在第一个单词中没有出现时（与该字母对应的数组元素 counter 的值为0），这两个单词显然不互为变位词，在这种情况下函数可返回，因此空（3）处应填入 “return 0”。空（4）处的处理与空（2）类似，应填入 “ sndword+”或其等价形式。根据题目中的说明，若两个词互为变位词，则它们包含的字母及每个字母出现的次数相同，这样数组 counter的每个元素都应为 0，如若不然，则可断定不是变位词。因此， 空（5 ）处应填入 “ counterindex ” 或 “ counterindex！=0” 或其等价形式。试题四（共15分）阅读以下说明和C函数， 填补代码中的空缺（1）（5），将解答填入答题纸的对应栏内。【说明】 函数 ReverseList（LinkList headptr）的功能是将含有头结点的单链表就地逆置。处理思路是将链表中的指针逆转，即将原链表看成由两部分组成：已经完成逆置的部分和未完成逆置的部分，令s指向未逆置部分的第一个结点，并将该结点插入已完成部分的表头（头结点之后），直到全部结点的指针域都修改完成为止。 例如，某单链表如图4-1所示，逆置过程中指针s的变化情况如图4-2所示。链表结点类型定义如下：【C函数】 【参考答案】（1） !headptr-next， 或！headptr|!headptr-next， 或其等价形式（2） headptr-next（3） headptr-next -next， 或 p-next， 或其等价形式（4） s-next, 或p-next, 或其等价形式（5） p【试题解析】 本题考查C语言的指针应用和运算逻辑。 本问题的图和代码中的注释可提供完成操作的主要信息， 在充分理解链表概念的基础上填充空缺的代码。 对于含有头结点的单链表， 链表为空时，头结点的指针域为空， 表示之后没有其他结点了。 因此， 空（1） 处应填入“！headptr-next”。 根据注释， 空（2）处所在语句令p指向链表的第一个元素结点， 因此空（2）填入 “ headptr-next”。 空（3）处的语句执行后， 可由图4-1所示的链表得到图4-2（a）的链表， 空（3）处应填入 “p-next” 或者 “headptr-next-next”。 代码中的while循环完成链表中除第一个元素结点之外的其他结点的指针域的修改。根据题目中的说明，s指向未逆置部分的第一个结点。在while循环中，变量p的作用是辅助完成将s所指结点插入头结点之后的处理， 处理步骤为： 因此， 空（4）处应填入 “ s-next” 或 “p-next”，从而避免链表断链。空（5）处应填入 “p”。 试题五（共15分）阅读下列说明、C代码和运行结果， 填补代码中的空缺（1）（5）， 将解答填入答题纸的对应栏内。【说明】 对部分乐器进行建模，其类图如图5-1所示，包括：乐器（Instrument）、管乐器（Wind）、打击乐器（Percussion）、弦乐器（Stringed）、木管乐器（Woodwind）、铜管乐器（Brass)。下面是实现上述设计的C+代码，其中音乐类（Music）使用各类乐器（Instrument）进行演奏和调音等操作。【C+代码】本程序运行后的输出结果为：Wind. play() 0 Wind. adjust () Woodwind. play()