计算机专业考研必备殷仁昆数据结构考研-要点解析(清华大学殷仁昆教授数据结构辅导班讲义).ppt

数据结构 考研要点解析 清华大学计算机系 殷人昆 数据结构考研要点解析 概述 第一章知识点 第二章知识点 第三章知识点 第四章知识点 第五章知识点 第六章知识点 考试的要求 研究生考试主要从两个方面进行考查：知识和技能。 知识方面 从数据结构的结构定义和使用，以及存储表示和操作的实现两个层次，系统地考查： 掌握常用的基本数据结构（包括顺序表、链接表、栈与队列、数组、二叉树、堆、树与森林、图、查找结构、索引结构、散列结构）及其不同的实现。 2) 掌握分析、比较和选择不同数据结构、不同存储结构、不同算法的原则和方法。 技能方面 系统地掌握基本数据结构的设计方法; 掌握选择结构的方法和算法设计的思考方式及技巧； 提高分析问题和解决问题的能力。 复习的纲领 数据结构课程是计算机专业的专业基础课程，为业界做系统开发提供了不可或缺的技术和知识，是计算机专业考研的重头科目。 数据结构课程复习有几点重要的体会提供给大家参考。 注重概念 抓住特点 学会算法 拓展应用 注重概念 从考研情况分析，试题涉及的内容都很基本，没有很深很难的内容，所以要重视概念的复习： 牢记定义。结构定义有规范写出的，有言外隐藏的和引伸的概念。 注意传承。某些结构与其他结构间有传承关系，有变种关系。 区分层次。分清逻辑的和物理的结构，以及它们之间的关系。 挖掘细节。细节可提供更多解题的知识。 抓住特点 每种结构有它的特点和用途，这对于在解题中应使用哪种结构 (who)，在何时 (when)，何种场合(where)使用，以及如何 (how) 使用有重要作用。 理解结构的行为特征。明确每种结构的行为特征，例如栈是先进后出，队列是先进先出的，可帮助在解题时作出选择。 理解结构的应用背景。知道每种结构常在什么场合做什么用，可适时作出适当选择。 理解结构的声明方式。在适当时机合理地定义它们，可减少算法逻辑的混乱。 学会算法 包括结构必要操作（初始化、建立、销毁、遍历、插入、删除）的实现和常用算法（查找、排序）、算法设计（迭代、递归、分治、回溯）的设计与分析。 基本数据结构的实现方式。主要是数据结构的存储方式定义和相应操作的程序实现。 常用算法的设计。包括设计的三阶段（基本思想、算法框架、程序实现）。 算法的简单分析。掌握时间复杂性的分析技能和附加存储空间的计算。 拓展应用 每种结构都有许多应用场合，有不同应用目的和应用方式。每种算法也可变通以适用于不同的问题求解。 明确问题求解的步骤。掌握问题求解的三阶段：分析(弄懂题意)、设计(考虑解决方案)、实现(算法设计与分析)。 坚持算法设计与分析的步骤。算法设计三阶段（基本思想、算法框架、程序实现）。 结构和算法的不同应用。这是最繁杂、范围最广的部分。通过多练习达到熟练应用。 复习的范围 根据2009年考试分析和历年考试经验，可以对今后考试作一个简单评估： 单项选择题覆盖了考试大纲涉及的所有各章，主要考查对各个数据结构的定义和特点的理解，以及相应延伸的概念。 综合应用题分为两个部分：算法分析题和算法设计题（编程题），主要考查分析问题和解决问题的能力。算法分析题的重点在图、查找、排序部分，算法设计题的重点在线性表、树与二叉树、查找和排序部分。 为在有限的时间内复习好这门课程，应当注意以下几点: 注意复习用 C / C++ / Java 语言编写小程序时的语法规则和方法，为算法分析和算法设计题的求解打下基础。 函数定义和参数使用。算法一般以函数形式给出，函数编写需要注意的问题包括函数类型，函数参数传递，函数返回值类型等，以及传值参数和引用参数在使用上的区别。 函数中局部变量的作用域。特别注意在函数中对局部变量的任何改变，在函数外不能使用。 算法设计所用数据结构的自定义。算法设计时不能忽视所用数据结构的声明。2009 年考试42 题有关链表的题，在答案中不写链表结点定义是扣了分的。 C／C++ 中的动态存储分配和回收方式。涉及链表结构的地方都可能有动态存储分配和回收操作。要掌握正确使用相关语句的方法。 在C／C++ 中输入／输出文件的定义和使用。特别注意正确使用文件的打开、关闭、读入、写出操作的使用。 在复习数据结构时，要注意知识体系。 数据结构课程中的知识本身具有良好的结构性，有些结构面向应用，有些结构面向实现。在复习时要注意这两个层次以及它们之间的联系。 注意循序渐进 在复习数据结构时，首先需要复习数据结构的定义和特点，数据结构的使用范围，再复习各种操作的实现。 在阅读算法之前，要先弄清其基本设计思想、基本步骤，并通过事例学习了解每个算法的处理流程以加深理解，最后再阅读程序代码。 注意比较 在复习中应当注意从“横向”和“纵向”进行对比以加深理解。 纵向对比将一种结构与它的各种不同的实现加以比较，理解不同