[树结构在程序设计中的运用.pptVIP

树结构在程序设计中的运用 上海市控江中学　王建德 目录 引言 树结构在程序设计中的运用 2003年竞赛的知识结构分布 2003年竞赛的知识结构分布 2003年竞赛的知识结构分布 试题特点 1、强调基础知识的灵活应用。每一轮竞赛都有基础知识题，但对灵活应用基础知识的要求愈来愈高。例如IOI的《路径维护》在逐边添入无向图的过程中计算最小生成树；《文本编辑器》要求设计多样的数据结构。例如线性表、非线性的树和图；NOIP的《加分二叉树》采用的动态程序设计是递归形式的；NOI的《数据生成器》必须综合使用前序遍历和后序遍历 2、首次出现了线段树和可以选择类博弈树算法的试题 3、近似算法类的试题增加。例如IOI的《猜牛游戏》、《逆向输出》、《机器人》、NOI的《卫星探测》、《草莓》、《智破连环阵》等。由于这些例题视程序逼近最优解和最优效率的程度给分，因此拓展了选手思维的空间，易启发选手的创造性。但反过来说，由于近似算法类的选题空间比较大，因此有可能使得题目的难度加大。 试题特点 4、树形结构类的问题增多。例如NOI的《卫星探测》通过二分查找构造一棵隐形的二叉树；《草莓》和《数据生成器》使用了人们容易被忽视的后序遍历；IOI的《路径维护》要求计算最小生成树； 5、可“一题多解”和开放性的试题增多。例如，IOI的《逆向输出》就是一道没有固定模式和经典算法可套用、需要量身定制合适算法的试题；《猜牛游戏》既可以采用贪心法，亦可以采用类博弈树的算法；NOIP的《栈》既可以通过回溯法计算，亦可以通过组合数学的Catalan数计算； 6、出现一些“陷阱题”。例如NOIP的《传染病扩展》极易诱导选手错误地使用贪心法或动态程序设计，实际上该问题不具备最优子结构的特征，正确的算法是回溯有哪些信誉好的足球投注网站。 启示 培养内省智力 充分利用网络资源 以问题为出发点、以自主探究为途径、以构造网络式思维模式为基础、以创新为目的组织集训 充分利用网络上与信息学活动相关的信息资源 1、由于网络上大量的算法知识和试题的出现，使得学生学习的大部分时间和空间由课堂转移到网上学习，自主性显著提高，学习方式发生了根本性的变化 2、学习的效率取决于如何在浩如烟海的网上信息中选择适应于竞赛需要和个性发展的东西 3、千万不要有“太易了不屑做、太难了不愿做”的主观随意性 充分利用网络上与信息学活动相关的信息资源 编程解题能力是在长期的上机实践中积累起来的。如果长期的无所事事、无所作为，迟早会落得了“小题做不对、大题难题不会做”的可悲结局 应该对试题本身有一个科学的价值判断：“这道题是不是有利于夯实基础，或者这道题是不是引出带规律性的东西，能不能派生出更多类似的问题”，真正从提高自身的算法认知水平和编程能力的高度，来决定练习题的取舍。 以问题为出发点、以自主探究为途径、以构造网络式思维模式为基础、以创新为目的组织集训 第一步：界定问题。即明确试题要求我们做什么,解决什么问题，输出怎样的结果 第二步：明确出发点，即明确试题的初始状态是什么，给出了哪些求解条件，其中哪些是显性的，哪些是隐性的，必须无一漏失。 第三步：寻找怎样做的创意。即要求学生独立思考，尽可能多地收集相关资料，尝试各种组合，调动所有的灵感和思考方式。 第四步：集中测试。每人设计三组测试数据,分别从一般情况、边界情况、扩大问题规模三个角度测试程序的正确性、时间效率和空间效率。然后交流测试数据，学生间进行互测。这样做既能测出自己程序的正确程度，又能在改善程序的时空效率上取长补短。 建立知识信息网络 归纳概括 通过对相关问题（即形式不同、本质类似的一类问题）的归纳，揭示内在的联系，概括出解决类似问题的一般规律，并得到高度抽象、概括的模型，为以后分析问题、设计算法进行指导。 触类旁通、联想外推 通过举一反三、由此及彼、触类旁通，从一个问题拓广出许多新问题。在解决这些新问题的过程中，进一步锻炼思维，并通过联想的线索将新问题、新模型、新算法并入知识网 近年来，由于各种竞赛纷纷采用free-pascal，因此对于算法来说，空间效率上的要求降低了，而对时间效率却提出了更高的要求。这使得选手不仅要娴熟地掌握常规算法，而且要大胆创新，构造更高效的算法来解决问题。 在以往的程序设计中，链式结构采用得较多。的确链式结构有编程复杂度低、简单易懂等优点，但有一个致命的弱点：相邻的两个元素间的联系并不明显。而树结构却能很好的做到这一点。 选手对树的先根遍历十分娴熟，但对后根遍历却不能像先根遍历那样应用自如。 树结构在程序设计中的运用 一．并查集 二．线段树 三．解决动态统计的静态方法 四、二叉树应用的拓广 五、先根遍历与后根遍历的应用 小结 并查集 竞赛中会经常遇到这样的题目：给出各个元素之