2014年5月 程序员 下午题答案及解析.pdfVIP

一、问答题

1、阅读以下说明和流程图，填补流程图中的空缺，将解答填入答题纸的对应栏

。

[说明]

指定网页中，某个关键词出现的次数除以该网页长度称为该关键词在此网页中的词

频。对新闻类网页，存在一组公共的关键词。因此，每个新闻网页都存在一组词频

，称为该新闻网页的特征向量。

设两个新闻网页的特征向量分别为：甲(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)的序号(N

B(1)＜NB(2)＜...)。

下面的流程图描述了计算这两个特征向量内积S的过程。

参考答案：

0

S+A(i)B(j)或等价表示

i＞m或i=m+1或等价表示

j＞n或i=n+1或等价表示

i＞morj＞n或i=m+1ori=n+1或等价表示

解析：

本题描述了如何计算两个新闻网页特征向量的内积。特征向量中的元素是关键词的

词频，而向量是非零元素的序号及相应的词频值组成的简化形式。计算内积的过程

需要遍历这两个简化特征向量，并计算对应序号相同时的元素乘积之和。

流程解析如下：

1.初始化S为0，作为内积的累计值。

2.对于每一个A(i)，需要与B(j)对应元素相乘并加到S上，直到NA(i)＜NB(j)，

此时需要比较下一个A(i+1)与NB(j)，或者比较NA(i)与下一个B(j+1)。

3.如果在比较A(i+1)与NB(j)后，发现i+1已经越界（即i＞m或i=m+1），则扫

描结束。

4.如果在比较NA(i)与B(j+1)后，发现j+1已经越界（即j＞n或j=n+1），则扫描

结束。

5.当两个简化向量之一扫描结束时，整个扫描结束，即满足条件i＞morj＞n

或i=m+1ori=n+1。

因此，答案中的填空部分应如上所述。

2、阅读以下说明和C函数，填补代码中的空缺，将解答填入答题纸的对应栏内。

[说明1]

函数isPrime(int

n)的功能是判断n是否为素数。若是，则返回1，否则返回0。素数是只能被1和自己

整除的正整数。例如，最小的5个素数是2，3，5，7，11。

[C函数]

intisPrime(intn)

{

intk,t;

if(n==2)

return1;

if(n＜2||______)return0;/*小于2的数或大于2的偶数不是素数//

t=(int)Sqrt(n)+1;

for(k=3;k＜t;k+=2)

if(______)

return0;

return1;

}

[说明2]

函数intminOne(intart[],int

k)的功能是用递归方法求指定数组中前k个元素中的最小者，并作为函数值返回。

[C函数]

intminOne(intarr[],intk)

{

intt;

assert(k＞0);

if(k==1)

return______;

t=minOne(arr+1,______);

if(arr[0]＜t)

returnamr[0];

return______;

}

参考答案：

n%2==0，或!(n%2)，或其等价形式

n%k==0，或!(n%k)，或其等价形式

arr[0]，或*arr，或其等价形式

k-1，或其等价形式

t

解析：

对于isPrime函数：

判断一个数是否为素数，首先需要排除小于2的数以及大于2的偶数，因为偶

数除了2以外都不是素数。因此，第一个空缺处是为了排除大于2的偶数，可

以使用n%2==0或!(n%2)来判断n是否为偶