《2012年信息科学与技术学院算法与数据结构专业技能大赛试题new》由会员分享，可在线阅读，更多相关《2012年信息科学与技术学院算法与数据结构专业技能大赛试题new（15页珍藏版）》请在金锄头文库上搜索。
1、2012 年信息科学与技术学院算法与数据结构专业技能大赛试题说明：1、不限定开发语言 2、最多不超过 5 人/题 3、题目理解有问题找唐仕喜老师 4、比赛时间为 1 个月，到 2013 年 1 月 1 日前截止提交 5、10(2)(3)班所有学生都要参加比赛并提交作品，其它班级可参加 6、学院通过答辩评选择出一、二、三等奖若干名，并发放证书和奖品【试题一】对给定文档，依据下面的思想设计聚类算法，并实现，输出聚类结果。无向加权图 G=V，E，W，V=d1，d2，dn；其表示形式为一对称矩阵：wijnn，其中 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） ，其中 0wij1，s 代表索引短语表中词的数量。则两个文档 di
3、与 dj 的相似度可定义为：由 Wij=sim（di，dj） ，建立模糊相似矩阵 WRnn，其中当 i=j 时，令 Wii=0。由相似矩阵求得传递闭包 t(W)，选取一个合适的 值得到一个 截集，得到的将是一个0，1 矩阵，记为 t(R)。由此矩阵可以分成 c 个文档类，即 A=A1，A2，Ac，满足了文档类间的相似性极小，将 c 个文本集看成 c 个子图。判断各个文档子类中如果存在只有一个文档的类，将其并入其他与其相似度最高的子类中，变成 c*个子图。输入 c*个子图，用基于谱图分割简单的谱聚类算法对每个子图 G 的顶点集1,21,21,2(0.5*)log_(,).*lijkjkLijkL
4、kjktfNMaxdfptermdocuent tfaxf 1,2min(,)(,)ax0ikjkswsidjVk=（v1，v2，vn）进行聚类，得到每个子图的聚类结果及其对应的类别数 ki，其中i1，c*。计算出 ki 的和即为总的聚类数 K。输入一个数据集 X=x1，x2，xk，输出由以上的数据集分割出来的 k 个子集。计算每个子图的亲密矩阵 S，当 ij 时，Sij=exp（-d （xi-x）j/22），Sii=0。构造Laplacian 矩阵 L，L=D -1/2SD-1/2，其中 D 为对角阵 。计算 L 的前 k 个特征值特ijijS征向量 1，2，k（重复特征值取其互相正交的特征
5、向量），按照大小顺序将相应的特征向量排列构成矩阵 U=1，2，kR nk，初始化聚类数 m=2。令ki=m。取 U 的前 ki 个列向量构成矩阵 Y，即 Y=U（：，1：k），归一化 Y 为矩阵 V，其中在 ki 维空间里，每个坐标轴的正负方向分别标记一个聚类。把 V 的行向量看作是 ki维空间的点，将其标记为距离最近的坐标轴所标记的聚类。这样最多可以产生 2ki 个聚类。除去空聚类和只有少数点的聚类，可以得到此时的聚类数 m2k。比较 m 和 ki，如果两者不等，重复上面过程。如果 m=ki，则所得到的 m 就是确定的聚类数，同时得到相应聚类数下 V 的行向量聚类。当且仅当 V 的第 i 行
6、为聚类 j 时，则原始数据点 xi 为第 j 类。计算ki 的和得到总的聚类数 k，和聚类结果。【试题二】假定每一段都有段落中心，段落中心句是与本段中所有其它语句相关度最高的语句，找段落的中心句。每个句子看成为一个文档，其相关度的计算思想如下：设 为第 i 个文档， 为第 i 个文档对应的第 m 个短语，为第 i 个文档中第 m 个短语的特征，则文档 id与 j的相关度为：12()ijijijYVidimp imt(,)(,)Re(,)ij ijijijdlatij dd 其中： 41Re(,)Relat(,)kimjnkimjnklatppi= 1， 2 ，3 ，4包含关系计算： L 为包含
7、关系存在的层次。概念主类计算：=12(,)imjndp为两个概念主类。义原在 Taxonomy 树上的距离节点相似计算如下：同层相同节点的计算 ： simN为同层相同节点数ax为同层最大节点数2是层次数动态角色 domain 处理（两个 det 中都存在 domain）： 3d=a 为相同 domain 节点个数2x为两个 det 的最深层两个 det 相同节点数与总节点数的计算： 3d=a:相同节点个数1D:第 1 个 det 的节点数2:第 2 个 det 的节点数主类义原相的计算 4d，计算方法同 3d。11 1()(,)( , (,)vuimjnimjnnu vimiijnjjnimj
8、nn tptptp RelaelaRelat(,)imjnltL2Re2(,)(,)imjnimjnlatpdpmax32siNd2xa12aD惩罚因子： 1；否定关系 0.3；其它指定关系 0.35短语特征值（tim） imw短语 ip的平均权重标题短语权重最高， 次标题短语权重次之，内容短语权重最低，专业短语权重比普通短语高。t:不重复短语数 impf为短语平均频率np文档中短语 im出 现的次数i文档中短语总数imd短语平均深度impn短语 i第一次出现原短语数i文档中短语总数imdf文档 i（包含 imp短语）的文档频率impN包含 i短语的文档数所有文档 d总数221logimiim
9、i imitwpfdSfA1imimtpkkpntA221()imimimtpkpkpnStiinpfA1impindimpiNdf【试题三】找 qq 群的贴主、群主和专家。对一段时期的群聊天记录进行分析，将每一个 ID 对应的聊天记录看成是一个文本，对所有的文本进行分词；将分词后的文本依据单词的相似性进行聚类，得到若干主题类；对每个主题进行分析，发贴量最大的 ID 称为该主题的贴主，其余的贴称为贴主的跟随贴，跟随贴数称贴主的影响因子；占有主题最多的贴主称为该群这一时期的群主。设计合适的数据结构与算法，找出贴主与群主，并给出其影响因子。对不同时期的同一群的聊天记录进行分析，对不同时期的主题进行
10、比较，不同时期内相同的主题数，称为该群的专业绝对系数，专业绝对系数除以总主题数(不相同)，称为该群的专业相对系数，专业相对系数越大，则该群越专业；在不同时期内相同主题的具有最多的相同贴主数，则该贴主称为该主题的专家，设计合适的数据结构与算法，找出该群的若干时期内的所有专家，并给出该群的相对专业系数。【试题四】协同开发项目工作组影响力的测定团队成员 i 在团队网络中的影响力用网络交往约束 Ni 来刻画，网络交往约束 Ni 越低，则团队成员 i 社会影响力越大。网络交往约束 Ni 由成员交往的概率来决定，一个成员的社会影响力越大，其在相同时间内与其它成员交往的人数越多，其对应的网络交往约束 Ni
11、越低，团队成员 i 的网络交往约束 Ni 由他与其他成员交往的概率决定：团队成员 i 与成员 j 交往的概率 pij 规定为：在规定时间段 T 内(假定为单位时间)i 与 j交往时间 tij 所占的比例：pij=tij/T上图中：T=1 (成员 A、B、C 的规定时间段是同一时间段 )只与交往，所以认为把所有的时间都用来与交往了；同时与、交往，其的时间由、分配，这里假定为.5。pAB=0.5/1=0.5 pAC=0.5/1=0.5pBA=1/1=1 pBC=0 pCB=0 pCA=1/1=1 pCB=0 pBC=0NA=( pAB+ PAC* pCB)2+ (pAC+ PAB* pBC)2=(
12、0.5+0)2+ (0.5+0) 2=0.5NB=( pBA+ PBC* pCA)2+ (pBC+ PCA* pAC)2=(1+0)2+ (0+0) 2=1NC=( pCB+ PCA* pAB)2+ (pCA+ PCB* pBA)2=(0+0)2+ (1+0) 2=1因此，A 网络交往约束 NA 最低，因此 A 的社会影响力最大。团队社会网络交往分为种基本类型：一种是一个成员周围存在若干个成员在协同工作；一种是通过远程电话或视频交流；一种是通过短信或 QQ 等文本形式的交流。前一种我们认为是直接协同，其对应网络交往约束为 NCi；后两种我们认为是远程交互, 其对应网络交往约束为 NIi。在规定
13、时间内，团队成员 i 与成员 j 协同的概率 pij 规定为：在规定时间段 T 内(假定为单位时间)i 与 j 协同时间 tij 所占的比例：协同时间由手机蓝牙技术测定。在规定时间内，团队成员 i 与成员 j 交互的概率 pij 规定为：在规定时间段 T 内(假定为单位时间)i 与 j 交互时间 tij 所占的比例：交互时间由手机通话时间或短信总长度(字符数) 测定。在团队项目组所有的成员中，i 与 NIi 最小的成员，称为最佳协同员工和最有交流影响力的员工。我将其相关信息发送给团队项目组其他所有的成员，从而改进成员的协作与交流意识。所要处理的任务包括判断语音是否为合理的语音，如静音或忙音均为
14、不合理语音，双方对话音一般为合理语音，对合理语音时长的统计，对短信字节数的统计，对蓝牙探测到对象时长的统计等。分布式计算计算量的分流主要考虑三个方面的要求：手机的电池量及其它场所耗能、网络的延迟和需要向络传输的单位时间的数据量（数据拥塞） ，这三者都可以实时进行获取。将手机上要处理的任务 T 分成若干个子任务 ti，并决定，哪些任务在手机本地执行，哪些任务远程执行，及在哪里执行。若共有 n 个子任务需要执行，则需 n 个可执行的场所，我们先选择耗能低、网络的延迟小、向络传输的数据量少的场所来完成任务。为统一计算场所的耗能、网络的延迟与向络传输的数据量，需要进行去量纲处理，设场所 ck，每一个子
15、任务都可能在场所 ck 进行处理(总共有 2n 个可能组合选择)，设子任务 i在所有场所中进行处理对应最小的耗能、网络的延迟与向络传输的数据量分别为emin、lmin 与 dmin；子任务 i 在场所 ck 处理所时对应的耗能、网络的延迟与向络传输的数据量分别为 ei、li 与 di，则处理量纲后所对应的无量纲耗能、网络的延迟与向络传输的数据量分别为 uei、uli 与 udi： 依据不同的需要，选择对应的耗能、网络的延迟与向络传输的数据量的不同权重（we+wl+wd=1 ） ，得到统一无量纲模型：由于 uci 为负值，因此选择 uci 值大的场所作为子任务 i 的处理器。手机上有三种类型的传感器 si：加速器、蓝牙与话筒。对传递过来的每一次感知，对应一个应答 ai，若传递过来的感器数据是有效的，则为正向应答，否则为负向应答。设传感器 si 的传递过来的数据正确的概率为 pi，则其下一次传递过来的数据为正确的数据的概率为：（正向应答）(负向应答 )其中 为反馈因子，其值依据经验调整。取样时，依据 pi 来调整取样率， pi 越大，信息越有效，取样间隔应当越小，反之，信息越无效，取样间隔应当越大。可采用的系统架构为：【试题五】依据董振东的基于知网的义原语义计算原理，计算任意两网页之间的相似度。【基本要求】1.将网页进行预处理，得到处理好
