2014上半年程序员考试真题及答案-下午卷.doc-资料库

第1页 / 共19页

第2页 / 共19页

第3页 / 共19页

第4页 / 共19页

第5页 / 共19页

第6页 / 共19页

第7页 / 共19页

第8页 / 共19页

2014 上半年程序员考试真题及答案-下午卷试题一（共 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)

(3) i>m 或 i=m+1 或等价表示 (4) j>n 或 j=n+1 或等价表示 (5) i>m or j>n 或 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)m 或 i=m+1（如果成立，则扫描结束）。因此（3）处应填 i>m 或 i=m＋1。流程图中，NA(i)>NB(j)时，下一步应再比较 NA(i)n 或 j=n+1（如果成立，则扫描结束）。因此（4）处应填 j>n 或 j=n+1。（5）处应填扫描结束的条件，i>m or j>n 或 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） arr[0]，或*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）处应填入“arr[0]”或其等价形式。空（4）所在的语句是通过递归方式找出 arr[1]～arr[k-1]中的最小者，第一个实参指出从 arr[1]开始，第二个参数为元素个数，为 k-1 个，因此空（4）应填入“k-1”。接下来的处理就很明确了，当 t 表示 arr[1]～arr[k-1]中的最小者，其与 arr[0]比较后就可以得到 arr[0]～arr[k-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） counter[index]，或 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 ）处应填入 “ counter［index］ ” 或 “ counter［index］！=0” 或其等价形式。

试题四（共 15 分）阅读以下说明和 C 函数，填补代码中的空缺（1）～（5），将解答填入答题纸的对应栏内。【说明】函数 ReverseList（LinkList headptr）的功能是将含有头结点的单链表就地逆置。处理思路是将链表中的指针逆转，即将原链表看成由两部分组成：已经完成逆置的部分和未完成逆置的部分，令 s 指向未逆置部分的第一个结点，并将该结点插入已完成部分的表头（头结点之后），直到全部结点的指针域都修改完成为止。例如，某单链表如图 4-1 所示，逆置过程中指针 s 的变化情况如图 4-2 所示。链表结点类型定义如下：【C 函数】

资料库

2014上半年程序员考试真题及答案-下午卷.doc

相关推荐

程序员考试

热门标签

最新资料