第七届全国青少年信息学（计算机）奥林匹克分区联赛复赛解题报告

2001年12月8日,第七届全国青少年信息学(计算机)奥林匹克分区联赛复赛在全国29个分同时开赛。这是我国青少年信息学奥林匹克比赛中重要的一项比赛,全国近4万中学生参加了本次比赛。虽然这不是国际信息学奥赛的选拔赛,但是这次比赛的规模和影响都超过全国信息学奥赛(NOI),它的比赛水平基本反映了我国信息学奥赛的普及程度和信息技术教育的开展水平。 为了让更多的同学参与信息学奥赛,了解信息学奥赛,在信息学奥赛中取得更好的成绩,我们请了国家集训队选手俞伟、赵爽,复赛满分选手吴连龙写了复赛的解题报告,希望能给大家带来一些帮助(详细试题可以到本杂志网站www.nettime.net.cn下载)。     

基于特别兴趣组的P2P网络搜索算法

从实现搜索引擎的角度,分析了泛洪策略(flooding strategy), 扩展环策略(expending ring), 行走者(walker) 和多个行走者(k walker) 搜索策略。沿着这些策略的思路,引用“小世界”思想,进一步提出了基于特别兴趣组的P2P网路搜索查询算法。该算法的特点就是改变被动的提供信息网络节点为主动提供服务的网络节点,或者说把网络节点作用从信息提供者改变为查询向导。网络节点不但提供查询所求的内容,同时利用与它有相同兴趣的特别兴趣组通讯簿为所收到的查询提供指南。因此可以加快P2P网的查询速度,同时减轻网络负荷。