问答题(2014年春程序员软考)

阅读以下说明和流程图,填补流程图中的空缺(1)~(5)。

【说明】

指定网页中,某个关键词出现的次数除以该网页长度称为该关键词在此网页中的词频。对新闻类网页,存在一组公共的关键词。因此,每个新闻网页都存在一组词频,称为该新闻网页的特征向量。

设两个新闻网页的特征向量分别为:甲(a1,a2,…,ak)、乙(b,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)<…)。

答案解析

(1)0(2)S+A(i)B(j) 或其等价形式(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(...

查看完整答案

讨论

有n个整数,使前面各数顺序后移m们位置,最后m个数变成最前面m个数。写一函数实现以上功能,在主函数中输入n个整数和输出调整后的n个整数。(要求使用指针方法处理)

写一程序实现:输入两个正整数m和n,求其最大公约数和最小公倍数。

输入N个学生某门课程的成绩,请按成绩从高到低的次序输出。

穷举算法是用下列哪种编程方法实现的【 】

阅读程序,选择一个最准确的答案。int MyFunc(int* a, int n, int x){ if(n<1)return FALSE; else if(n==1){ if(x==a[0])return n-1; else return FALSE; }else{ int m=n/2; if(x<a[m]return MyFunc(&a[0],m,x); else if(x==a[ m])return m; else return MyFunc(&a[m+1], n-m-1,x); }}以上程序采用的是【 】

栈和队的插入、删除操作服从哪组规律?【 】

打印魔方阵,所谓魔方阵是这样的方阵,它的每一列,每一行和对角线之和均相等。例如:三阶魔方阵为8 1 63 5 74 9 2写一程序能打印出由1到n2(n≤15)的自然数构成的魔方阵。

阅读以下说明和流程图,填补流程图中的空缺(1)~(5)。本流程图旨在统计一本电子书中各个关键词出现的次数。假设已经对该书从头到尾依次分离出各个关键词{A(i)|i=1,…,n}(n>1),其中包含了很多重复项,经下面的流程处理后,从中挑选出所有不同的关键词共m个{K(j)|j=1,…,m},而每个关键词K(出现的次数为NK(j)。

将源程序中多处使用的同一个常数定义为常量并命名,【 】。

在单入口单出口的do…while循环结构中,【 】。