信息科学与技术学院算法与数据结构专业技能大赛试题new

《信息科学与技术学院算法与数据结构专业技能大赛试题new》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、2012年信息科学与技术学院算法与数据结构专业技能大赛试题说明：1、不限定开发语言2、最多不超过5人/题3、题目理解有问题找唐仕喜老师4、比赛时间为1个月，到2013年1月1日前截止提交5、10(2)(3)班所有学生都要参加比赛并提交作品，其它班级可参加6、学院通过答辩评选择出一、二、三等奖若干名，并发放证书和奖品【试题一】对给定文档，依据下面的思想设计聚类算法，并实现，输出聚类结果。无向加权图G=＜V，E，W＞，V={d1，d2，…，dn}；其表示形式为一对称矩阵：[wij]n×n，其中W={w1，w2，…，wm}是边权重代表两个文本间相似度。计算文档的词频以及文档间的相似度，

2、将文档粗化的聚成无关或是相关度极小的c个文档子类。首先除去在所有文档中出现的高频词；然后提取剩下词汇的短语存入词根表中。收集这些短语形成一个索引短语集T。短语t在文档di中权重为：tfij定义为短语t在文档中di出现的频率；dft定义为含有短语t的文档数量；L定义为文档di中包含的索引短语的数量；N定义为文档的数量。p_term_documen（tt，di）的值代表着短语t在文档di中的重要性，取值范围是[0，1]。计算出短语的权重，可以将短语表示成向量：di=（wi1，wi2，…，wis），其中0≤wij≤1，s代表索引短语表中词的数量。则两个文档di与dj的相似度可定义为：由

3、Wij=sim（di，dj），建立模糊相似矩阵W∈Rn×n，其中当i=j时，令Wii=0。由相似矩阵求得传递闭包t(W)，选取一个合适的λ值得到一个λ截集，得到的将是一个0，1矩阵，记为t(R)。由此矩阵可以分成c个文档类，即A={A1，A2，…，Ac}，满足了文档类间的相似性极小，将c个文本集看成c个子图。判断各个文档子类中如果存在只有一个文档的类，将其并入其他与其相似度最高的子类中，变成c*个子图。输入c*个子图，用基于谱图分割简单的谱聚类算法对每个子图G的顶点集Vk=（v1，v2，…，vn）进行聚类，得到每个子图的聚类结果及其对应的类别数ki，其中i∈[1，c*]。计算出k

4、i的和即为总的聚类数K。输入一个数据集X={x1，x2，…，xk}，输出由以上的数据集分割出来的k个子集。计算每个子图的亲密矩阵S，当i≠j时，Sij=exp（-d（xi-x）j/2σ2），Sii=0。构造Laplacian矩阵L，L=D-1/2SD-1/2，其中D为对角阵。计算L的前k个特征值特征向量ζ1，ζ2，…，ζk（重复特征值取其互相正交的特征向量），按照大小顺序将相应的特征向量排列构成矩阵U=[ζ1，ζ2，…，ζk]∈Rn×k，初始化聚类数m=2。令ki=m。取U的前ki个列向量构成矩阵Y，即Y=U（：，1：k），归一化Y为矩阵V，其中在ki维空间里，每个坐标轴的正负方

5、向分别标记一个聚类。把V的行向量看作是ki维空间的点，将其标记为距离最近的坐标轴所标记的聚类。这样最多可以产生2ki个聚类。除去空聚类和只有少数点的聚类，可以得到此时的聚类数m≤2k。比较m和ki，如果两者不等，重复上面过程。如果m=ki，则所得到的m就是确定的聚类数，同时得到相应聚类数下V的行向量聚类。当且仅当V的第i行为聚类j时，则原始数据点xi为第j类。计算ki的和得到总的聚类数k，和聚类结果。【试题二】假定每一段都有段落中心，段落中心句是与本段中所有其它语句相关度最高的语句，找段落的中心句。每个句子看成为一个文档，其相关度的计算思想如下：设为第i个文档，为第i个文档对应的

6、第m个短语，为第i个文档中第m个短语的特征，则文档与的相关度为：其中：i=1，2，3，4包含关系计算：L为包含关系存在的层次。概念主类计算：α=1为两个概念主类。义原在Taxonomy树上的距离节点相似计算如下：同层相同节点的计算：为同层相同节点数为同层最大节点数是层次数动态角色domain处理（两个det中都存在domain）：=a为相同domain节点个数为两个det的最深层两个det相同节点数与总节点数的计算：=a:相同节点个数:第1个det的节点数:第2个det的节点数主类义原相的计算，计算方法同。惩罚因子：1；否定关系0.3；其它指定关系0.35短语特征值（tim）短语

7、的平均权重标题短语权重最高，次标题短语权重次之，内容短语权重最低，专业短语权重比普通短语高。t:不重复短语数为短语平均频率文档中短语出现的次数文档中短语总数短语平均深度短语第一次出现原短语数文档中短语总数文档（包含短语）的文档频率包含短语的文档数所有文档总数【试题三】找qq群的贴主、群主和专家。对一段时期的群聊天记录进行分析，将每一个ID对应的聊天记录看成是一个文本，对所有的文本进行分词；将分词后的文本依据单词的相似性进行聚类，得到若干主题类；对每个主题进行分析，发贴量最大的ID