信息科学与技术学院算法与数据结构专业技能大赛试题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；其表示形式为一对称矩阵：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与dj的相似度可定义为： 由Wij=sim（di，dj），建立模糊相似矩阵WRn

3、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，其中i1，c*。计算出ki的和即为总的聚类数K。输入一个数据集X=x1，x2，xk，输出由以上的数据集分割出来的k个

4、子集。计算每个子图的亲密矩阵S，当ij时，Sij=exp（-d（xi-x）j/22），Sii=0。构造Laplacian矩阵L，L=D-1/2SD-1/2，其中D为对角阵。计算L的前k个特征值特征向量1，2，k（重复特征值取其互相正交的特征向量），按照大小顺序将相应的特征向量排列构成矩阵U=1，2，kRnk，初始化聚类数m=2。令ki=m。取U的前ki个列向量构成矩阵Y，即Y=U（：，1：k），归一化Y为矩阵V，其中在ki维空间里，每个坐标轴的正负方向分别标记一个聚类。把V的行向量看作是ki维空间的点，将其标记为距离最近的坐标轴所标记的聚类。这样最多可以产生2ki个聚类。除去空聚类和只有少数点

5、的聚类，可以得到此时的聚类数m2k。比较m和ki，如果两者不等，重复上面过程。如果m=ki，则所得到的m就是确定的聚类数，同时得到相应聚类数下V的行向量聚类。当且仅当V的第i行为聚类j时，则原始数据点xi为第j类。计算ki的和得到总的聚类数k，和聚类结果。【试题二】假定每一段都有段落中心，段落中心句是与本段中所有其它语句相关度最高的语句，找段落的中心句。每个句子看成为一个文档，其相关度的计算思想如下：设 为第i个文档， 为第i个文档对应的第m个短语，为第i个文档中第m个短语的特征，则文档与的相关度为：其中： i= 1， 2 ，3 ，4包含关系计算： L为包含关系存在的层次。概念主类计算：=1为

6、两个概念主类。义原在Taxonomy树上的距离节点相似计算如下：同层相同节点的计算 ： 为同层相同节点数为同层最大节点数是层次数动态角色domain处理（两个det中都存在domain）：=a为相同domain节点个数为两个det的最深层两个det相同节点数与总节点数的计算：=a:相同节点个数:第1个det的节点数:第2个det的节点数主类义原相的计算，计算方法同。惩罚因子： 1；否定关系 0.3；其它指定关系 0.35短语特征值（tim） 短语的平均权重标题短语权重最高， 次标题短语权重次之，内容短语权重最低，专业短语权重比普通短语高。t:不重复短语数为短语平均频率 文档中短语出现的次数文档

7、中短语总数短语平均深度短语第一次出现原短语数文档中短语总数文档（包含短语）的文档频率 包含短语的文档数所有文档总数【试题三】找qq群的贴主、群主和专家。对一段时期的群聊天记录进行分析，将每一个ID对应的聊天记录看成是一个文本，对所有的文本进行分词；将分词后的文本依据单词的相似性进行聚类，得到若干主题类；对每个主题进行分析，发贴量最大的ID称为该主题的贴主，其余的贴称为贴主的跟随贴，跟随贴数称贴主的影响因子；占有主题最多的贴主称为该群这一时期的群主。设计合适的数据结构与算法，找出贴主与群主，并给出其影响因子。对不同时期的同一群的聊天记录进行分析，对不同时期的主题进行比较，不同时期内相同的主题数，

8、称为该群的专业绝对系数，专业绝对系数除以总主题数(不相同)，称为该群的专业相对系数，专业相对系数越大，则该群越专业；在不同时期内相同主题的具有最多的相同贴主数，则该贴主称为该主题的专家，设计合适的数据结构与算法，找出该群的若干时期内的所有专家，并给出该群的相对专业系数。【试题四】协同开发项目工作组影响力的测定团队成员i在团队网络中的影响力用网络交往约束Ni来刻画，网络交往约束Ni越低，则团队成员i社会影响力越大。网络交往约束Ni由成员交往的概率来决定，一个成员的社会影响力越大，其在相同时间内与其它成员交往的人数越多，其对应的网络交往约束Ni越低，团队成员i的网络交往约束Ni由他与其他成员交往的

9、概率决定：团队成员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.5 pBA=1/1=1 pBC=0 pCB=0 pCA=1/1=1 pCB=0 pBC=0 NA=( pAB+ PAC* pCB)2+ (pAC+ PAB* pBC)2=(0.5+0)2+ (0.5+0) 2=0.5 NB=( pBA+ PBC* pCA)

10、2+ (pBC+ PCA* pAC)2=(1+0)2+ (0+0) 2=1 NC=( pCB+ PCA* pAB)2+ (pCA+ PCB* pBA)2=(0+0)2+ (1+0) 2=1因此，A网络交往约束NA最低，因此A的社会影响力最大。团队社会网络交往分为种基本类型：一种是一个成员周围存在若干个成员在协同工作；一种是通过远程电话或视频交流；一种是通过短信或QQ等文本形式的交流。前一种我们认为是直接协同，其对应网络交往约束为NCi；后两种我们认为是远程交互, 其对应网络交往约束为NIi。在规定时间内，团队成员i与成员j协同的概率pij规定为：在规定时间段T内(假定为单位时间)i与j协同时间

11、tij所占的比例：协同时间由手机蓝牙技术测定。在规定时间内，团队成员i与成员j交互的概率pij规定为：在规定时间段T内(假定为单位时间)i与j交互时间tij所占的比例：交互时间由手机通话时间或短信总长度(字符数)测定。在团队项目组所有的成员中，i与NIi最小的成员，称为最佳协同员工和最有交流影响力的员工。我将其相关信息发送给团队项目组其他所有的成员，从而改进成员的协作与交流意识。所要处理的任务包括判断语音是否为合理的语音，如静音或忙音均为不合理语音，双方对话音一般为合理语音，对合理语音时长的统计，对短信字节数的统计，对蓝牙探测到对象时长的统计等。分布式计算计算量的分流主要考虑三个方面的要求：手

12、机的电池量及其它场所耗能、网络的延迟和需要向络传输的单位时间的数据量（数据拥塞），这三者都可以实时进行获取。将手机上要处理的任务T分成若干个子任务ti，并决定，哪些任务在手机本地执行，哪些任务远程执行，及在哪里执行。若共有n个子任务需要执行，则需n个可执行的场所，我们先选择耗能低、网络的延迟小、向络传输的数据量少的场所来完成任务。为统一计算场所的耗能、网络的延迟与向络传输的数据量，需要进行去量纲处理，设场所ck，每一个子任务都可能在场所ck进行处理(总共有2n个可能组合选择)，设子任务i在所有场所中进行处理对应最小的耗能、网络的延迟与向络传输的数据量分别为emin、lmin与dmin；子任务i

13、在场所ck处理所时对应的耗能、网络的延迟与向络传输的数据量分别为ei、li与di，则处理量纲后所对应的无量纲耗能、网络的延迟与向络传输的数据量分别为uei、uli与udi： 依据不同的需要，选择对应的耗能、网络的延迟与向络传输的数据量的不同权重（we+wl+wd=1），得到统一无量纲模型：由于uci为负值，因此选择uci值大的场所作为子任务i的处理器。手机上有三种类型的传感器si：加速器、蓝牙与话筒。对传递过来的每一次感知，对应一个应答ai，若传递过来的感器数据是有效的，则为正向应答，否则为负向应答。设传感器si的传递过来的数据正确的概率为pi，则其下一次传递过来的数据为正确的数据的概率为：（

14、正向应答） (负向应答 )其中为反馈因子，其值依据经验调整。取样时，依据pi来调整取样率，pi越大，信息越有效，取样间隔应当越小，反之，信息越无效，取样间隔应当越大。 可采用的系统架构为：【试题五】依据董振东的基于知网的义原语义计算原理，计算任意两网页之间的相似度。【基本要求】1.将网页进行预处理，得到处理好的文本；2.将处理好的文本进行分词，得到标注词；.3.由义原语义计算原理，计算任意两网页之间的相似度。【试题六】请自选一部电影，构造该电影中所有人物的自动机，反映人物命运状态的变迁，并用程序模拟。【试题七】实现SPSS中的二阶段聚类、K中心聚类、判别分析与决策树分析dll。【试题八】社会网

15、络动态结构测度定义1 社会网络是物联网的一种人类社会活动的抽象，不同的社会活动可以从同一物联网中抽象出不同的社会网络,时刻t物联网为NT(t)，对应社会活动角色Ri的社会网络为SN(t, Ri)。若有n类社会活动角色，则时刻t的社会网络为SN(t)= SN(t, R1), SN(t, R2), ，SN(t, Rn)。物联网NT时刻t所对应的社会网络为SN(t)可以看作为n个分层独立的社会网络的叠加。这种分层社会网络动态结构使得对社会网络的研究得到分解，而不是与以前的研究一样，不加区分地进行社会网络构建。我们把社会网络的分层架构称为社会网络结构的独立性。定义2 时刻t社会活动角色Ri的社会网络S

16、N(t, Ri)用状态图来测度。社会网络SN(t, Ri)对应着一个状态谱图： SN (t, Ri) = (t, Ri): G (V, E, ST)V为社会网络SN(t, Ri)所对应的角色结点的集合，这些角色结点的粒度依据研究的实际需要而定，可以是单个的个体，可以是一个团体，也可以是其不同粒度的组合，为简化，在本研究中只考虑同质角色的情况，要么是个体，要么是同一粒度的团体。E为社会网络SN(t, Ri)所对应的联系的集合。E测度了社会网络SN(t, Ri)的拓扑结构，一般情对应为有向图，反映了人与人之间的各种关系，或团队与团队之间的各种关系。设角色u,vV，则对eE有e u,v =，e v,

17、u =，分别为角色u与角色v的联系及角色v与角色u的联系。联系的性质由该社会网络的角色定位决定，一类角色可以对应一种或多种联系，比如工作社会网络角色之间的联系可以有经济联系、合作联系、竞争联系等，联系的粒度决定了研究的实际需要。ST为社会网络SN(t, Ri) 动态结构所对应的状态特征。ST测度了社会网络SN(t, Ri) 动态结构的相对于拓扑结构独立的无量纲特征，用来描述社会网络中的社会网络舆情突发性及其影响、社会网络复杂规模、社会网络小世界性、社会网络无标度性、社会网络成员间的相关程度、社会成员影响力的大小与真伪、社会网络团队的构成及其紧密程度等一般性问题。由状态谱图的测度可知，时刻t的社

18、会网络SN(t, Ri)对应社会网络流中的一个状态，随着时间的变化，社会网络SN(t, Ri)的结构及其特征值也对应着变化，这就是社会网络SN(Ri)的演化。社会网络SN(t, Ri) 状态简称t时刻社会网络，或t时刻状态。由于t时刻状中的状态特征是相对于拓扑结构独立的无量纲特征，这些t时刻不同社会活动角色对应的社会网络的状态特征可以进行叠加，得到t时刻总的社会网络SN(t)的状态特征值。如果不同社会活动角色数n趋于，则得到真实的人在t时刻的真实社会行为趋向，从这个意义上讲，我们的社会网络SN(t)只能近似地测度出人在t时刻的真实社会行为。从整个时间线来看，任一时刻，社会网络SN(t, Ri)

19、由若干状态SN(Ri)构成，其状态特征可以进行叠加；对同一社会活动角色Rit的社会网络SN(t)的演化过程，其状态特征不停地波动向前延伸，整个社会网络的演化过程就是粒子波的叠加过程，这个性质，我们称之为社会网络SN的波粒二象性。定义3 时刻t社会活动角色Ri的社会网络SN(t, Ri)的状态特征ST为一状态特征向量： ST=(, ，C, L/M, r, b, R, Q, k)社会网络密度反映社会网络的稀疏程度，代表社会网络成员的总体紧密程度。社会网络密度定义为网络边数M与总共可能边数N(N-1)/2的比值。无标度指数反映社会网络的无标度程度。顶点i连接其它顶点的边的数目称为该顶点i的度，顶点i

20、的度用k表示。一个随机选定的节点其度值恰好为k的概率称为度k的分布P(k)，对于一个具体的网络，P(k)表示度值为k的顶点数目占总顶点数目的比例。实际的社会网络的度分布服从幂律形式，即P(k)k-，值越大，则社会网络的无标度程度越大。聚类系数C反映社会网络集团化程度。网络中节点i，设与其直接相连的节点数为ki，这些节点间实际存在的边数为Mi，总共可能存在的边数为，节点i的聚类系数Ci定义为： Ci = Mi/。网络中所有节点聚类系数的平均值称为平均聚类系数或整个网络的聚类系数C。社会网络聚类系数C越大，则网络聚集性越强。平均路径长度与网络规模比L/M反映社会网络的小世界性。网络中节点i和节点j

21、之间最短路径上的边数定义为该节点对的最短距离Lij。平均路径长度l定义为任意两个节点之间的最短距离的平均值，网络规模用网络边数M表示，平均路径长度与网络规模比L/M随着社会网络规模的增大以对数尺度增长，即增长越来越小，呈现小世界特性。度同配系数r用于测度社会网络的同配性、异质性。如果网络中的节点趋于和它近似的节点相连，例如度大的节点趋于和度大的节点相连，则称该社会网络是同配网络；反之，称之为异配网络。社会网络的度同配系数定义为连在一起的节点对应的度值的Pearson相关系数，即：其中是第i条边所连接的两个节点的度值(i=1，M,M为总边数)。r0，整个社会网络呈同配结构；r0。网络平均介数B反

22、映社会网络节点的平均影向力。节点i的介数定义为：其中g(m,n)表示节点m和n之间的最短路径数，gi(m,n)表示节点m和n之间经过节点i的最短路径数。社会网络中某个节点的介数越大，其在信息传播过程中通过该节点的信息量越多，其影响力就越大，发生拥塞的可能性也越大。社会网络中的总节点数为N，网络平均介数，则网络中的各节点的平均影响力越大。互惠指数R反映有向社会网络无向程度，定义为有向网络中双向二元组的百分比，即双向节点对(v,w)且(w,v)的数量与至少具有一条有向边的节点对(v,w)或(w,v)的数量的比值。互惠指数R0,1。设(v,w)是一条有向边，若R=0，则(w,v)不存在；若R=1，则

23、(w,v)存在。模块度Q用来测度社会网络的社团性，社会网络由若干个较为明显的社团构成，社团内部节点间连接相对比较紧密，而社团之间连接比较稀疏，设社会网络划分为m个社团，eij为网络中连接两个不同社团i、j的节点的边在所有边中所占的比例，表示网络中边接所有社团内部各节点的边在所有边中所占的比例，表示与第i个社团中的节点相连的边在所有边中所占的比例，其模块度。一般以Q=0.3作为网络具有明显社团结构下界。互补累积分布斜率k用于测度社会网络活动性，即流行度、热度、吸引度，设用户u对应的节点的度为n(u)，简记为n，则其对应的广义极值分布SED为：其对应的互补累积分布CCDF为：两边取对数得： 以作为

24、y轴，以x轴，由最小二乘法进行线性拟合可求出n0和c的值，其对应的互补累积分布斜率,|k|越大，则社会网络的活动性越强，参与交互的节点越多。以上九个特征参数分别从社会网络紧密程度、无标度程度、集团化程度、小世界程度、同配程度、影向力、无向程度、社团形成度、吸引度等角度测度了社会网络的宏观特征结构，这些参数以无量纲特征的方式画表达，以保证各社会网络的宏观特征结构的独立可叠加性。本文侧重于社会网络宏观特征的动态演化研究，对社会网络内部各结点的具体状态变化，我们另作研究。定义4 社会网络SN(t, Ri)的社团依据对人们的主观作用分为两类，一类为积极社团，一类为消极社团，积极社团反映社会网络中人与人

25、的协作共进；消极社团反映社会网络中人与人的破坏与攻击，包括恶意诋毁，如垃圾邮件社团、网络炒作社团等。积极社团定义为一准完全子图，设S为一个完全子图，为节点u对节点v的依赖取值，节点u的k近邻集合kNN(u)是节点u在社会网络G中最近的k个节点：对节点集,若，则S为一个k近邻积极社团；若，|S|为社团S中节点的数量，为比例系数，则S为一个准积极社团。消极社团定义为一普通有向图S，为节点u对节点v的依赖取值，节点u的k近邻集合kNN(u)是节点u在社会网络G中最近的k个节点：对节点集,若，则S为一个以u为中心的k近邻消极社团。【试题九】基于灰色聚类模型的实验成绩评定实验采用灰色聚类模型对实验结果进

26、行评定。用预习实验报告、实验操作、安全操作、实验报告作为本模型的4个指标。灰类级别为：优、良、中、及格、不及格。算法中指定了各指标的相对重要性权重。1. 考查指标体系的确定本模型的4个指标为：预习实验报告、实验操作、安全操作、实验报告。灰类级别为：优、良、中、及格、不及格。确定各指标的相对重要性权重：2. 给出j指标k子类的白化权函数 fjk（x）灰类k= k1，k2,k3,k4,k5)=优，良，中，及格，不及格)优采用上限测度白化权函数表示(如图1所示)，良、中、及格采用适中测度白化权函数表示(如图2所示)，不及格采用下限测度白化权函数表示(如图3所示)根据要求，优不大于25 ，中和及格不小于25 ，并根据学生成绩总体分布情况确定各指标灰类划分标准，即确定灰色白化权函数的转折点优和不及格的白化权函数转折点记为x(1) x(2)，良、中和及格的白化权函数转折点则记为x (1) x(2) x(3)。各个白化权函数图如下：白化权函数表达式：对于图1所示白化权函数有各个聚类指标的灰类转折点如表2：程序中表示：程序中各个白化权函数表示如下：（详细计算步骤见程序