搜索
数据结构考研要点解析清华大学计算机系殷人昆数据结构辅导2数据结构考研要点解析概述第一章知识点第二章知识点第三章知识点第四章知识点第五章知识点第六章知识点3考试的要求研究生考试主要从两个方面进行考查：知识和技能。1.知识方面从数据结构的结构定义和使用，以及存储表示和操作的实现两个层次，系统地考查：1)掌握常用的基本数据结构（包括顺序表、链接表、栈与队列、数组、二叉树、堆、树与森林、图、查找结构、索引结构、散列结构）及其不同的实现。42)掌握分析、比较和选择不同数据结构、不同存储结构、不同算法的原则和方法。2.技能方面1)系统地掌握基本数据结构的设计方法;2)掌握选择结构的方法和算法设计的思考方式及技巧；3)提高分析问题和解决问题的能力。5复习的纲领数据结构课程是计算机专业的专业基础课程，为业界做系统开发提供了不可或缺的技术和知识，是计算机专业考研的重头科目。数据结构课程复习有几点重要的体会提供给大家参考。注重概念抓住特点学会算法拓展应用61.注重概念从考研情况分析，试题涉及的内容都很基本，没有很深很难的内容，所以要重视概念的复习：a)牢记定义。结构定义有规范写出的，有言外隐藏的和引伸的概念。b)注意传承。某些结构与其他结构间有传承关系，有变种关系。c)区分层次。分清逻辑的和物理的结构，以及它们之间的关系。d)挖掘细节。细节可提供更多解题的知识。72.抓住特点每种结构有它的特点和用途，这对于在解题中应使用哪种结构(who)，在何时(when)，何种场合(where)使用，以及如何(how)使用有重要作用。1)理解结构的行为特征。明确每种结构的行为特征，例如栈是先进后出，队列是先进先出的，可帮助在解题时作出选择。2)理解结构的应用背景。知道每种结构常在什么场合做什么用，可适时作出适当选择。3)理解结构的声明方式。在适当时机合理地定义它们，可减少算法逻辑的混乱。83.学会算法包括结构必要操作（初始化、建立、销毁、遍历、插入、删除）的实现和常用算法（查找、排序）、算法设计（迭代、递归、分治、回溯）的设计与分析。a)基本数据结构的实现方式。主要是数据结构的存储方式定义和相应操作的程序实现。b)常用算法的设计。包括设计的三阶段（基本思想、算法框架、程序实现）。c)算法的简单分析。掌握时间复杂性的分析技能和附加存储空间的计算。94.拓展应用每种结构都有许多应用场合，有不同应用目的和应用方式。每种算法也可变通以适用于不同的问题求解。a)明确问题求解的步骤。掌握问题求解的三阶段：分析(弄懂题意)、设计(考虑解决方案)、实现(算法设计与分析)。b)坚持算法设计与分析的步骤。算法设计三阶段（基本思想、算法框架、程序实现）。c)结构和算法的不同应用。这是最繁杂、范围最广的部分。通过多练习达到熟练应用。10复习的范围根据2009年考试分析和历年考试经验，可以对今后考试作一个简单评估：单项选择题覆盖了考试大纲涉及的所有各章，主要考查对各个数据结构的定义和特点的理解，以及相应延伸的概念。综合应用题分为两个部分：算法分析题和算法设计题（编程题），主要考查分析问题和解决问题的能力。算法分析题的重点在图、查找、排序部分，算法设计题的重点在线性表、树与二叉树、查找和排序部分。11为在有限的时间内复习好这门课程，应当注意以下几点:1.注意复习用C/C++/Java语言编写小程序时的语法规则和方法，为算法分析和算法设计题的求解打下基础。1)函数定义和参数使用。算法一般以函数形式给出，函数编写需要注意的问题包括函数类型，函数参数传递，函数返回值类型等，以及传值参数和引用参数在使用上的区别。2)函数中局部变量的作用域。特别注意在函数中对局部变量的任何改变，在函数外不能使用。123)算法设计所用数据结构的自定义。算法设计时不能忽视所用数据结构的声明。2009年考试42题有关链表的题，在答案中不写链表结点定义是扣了分的。4)C／C++中的动态存储分配和回收方式。涉及链表结构的地方都可能有动态存储分配和回收操作。要掌握正确使用相关语句的方法。5)在C／C++中输入／输出文件的定义和使用。特别注意正确使用文件的打开、关闭、读入、写出操作的使用。2.在复习数据结构时，要注意知识体系。13数据结构课程中的知识本身具有良好的结构性，有些结构面向应用，有些结构面向实现。在复习时要注意这两个层次以及它们之间的联系。1)注意循序渐进在复习数据结构时，首先需要复习数据结构的定义和特点，数据结构的使用范围，再复习各种操作的实现。在阅读算法之前，要先弄清其基本设计思想、基本步骤，并通过事例学习了解每个算法的处理流程以加深理解，最后再阅读程序代码。142)注意比较在复习中应当注意从“横向”和“纵向”进行对比以加深理解。纵向对比将一种结构与它的各种不同的实现加以比较，理解不同实现方式的优点和问题。如二叉树的顺序和链表实现。横向对比是对属于同一类逻辑结构的不同数据结构（如线性表、栈、队列）加以比较，对具有相同功能的不同算法进行比较等，了解数据结构与算法实现间的关系。153)注意练习只看书不做题，不能真正学会有关知识，不能达到技能培养的目的。做题是自我检查的重要手段。在做算法设计类型的习题时，应考虑数据结构的定义。3.提高算法设计的能力。编写算法的题可能是学生比较棘手的问题，特别是在考试这样一个氛围，时间又短促，想编出一个好算法不太容易。16一个建议是a)首先仔细阅读试题题目，了解它到底要你干什么。b)然后用一个简单的例子走一下，总结每一步向下走可用什么语句实现。c)再做归纳，整理出处理流程。d)按照结构化程序设计的方法，搭建框架，再根据例子填入细节。在设计一个算法时，要考虑问题解决方案的多样性、算法的适用性、问题对算法选择的限制。选择合适的数据结构，设计有效的算法。17本章“线性表”的知识点有5个：1)线性表的定义和特点：由数据元素组成，惟一直接前驱与后继。2)线性表的基本操作：查找、定位、遍历、插入、删除。3)线性表的存储表示：顺序存储、链表存储。4)循环链表和双向链表：定义和基本运算。5)线性表的应用：掌握使用线性表基本操作实现应用算法第一章知识点解析18线性表的定义和特点问题1.如果一个元素集合中每个元素都有1个且仅有1个直接前驱和1个直接后继，它是线性表吗？解析：答案“否”，该元素集合是一个回路（环）。引伸：循环链表是一个“环”，它符合线性表的定义吗？问题的关键是：线性表是逻辑结构，线性表和非线性表是从逻辑上划分的。而循环链表是存储结构，是线性表的一种特殊的表示，是线性链表的一种扩展。它在形态上有线性的特征，在行为上有线性表的循序访问的特点。19问题2.如果一个元素集合有一个元素仅有1个直接后继而没有直接前驱，另一个元素仅有1个直接前驱而没有直接后继，其他每个元素都仅有1个直接前驱和1个直接后继，但其中各个元素可能数据类型不同，该元素集合是线性表吗？解析：答案“是”，它符合线性表的定义和特性，只要把元素定义为Union类型即可。因为线性表的定义只规定了元素间的关系及每个表元素是原子类型，并未规定每个表元素的类型必须相同。Union是一种等价类型，它允许不同类型数据共享同一存储空间，可保证每个表元素所占空间相同。20线性表的基本操作问题3.我们可以为线性表定义查找、插入、删除等操作吗？它们如何实现？解析：可以为线性表定义这些操作，也可以在程序中直接使用这些操作。但它们的实现与线性表选用何种存储结构有关。在定义了线性表的存储表示之后，必须为相关操作定义它们的实现代码。具体的线性表实例一定与某一存储表示相联系，因此，要使用相应的基于该存储结构实现的操作。21线性表的存储表示问题4.线性表的顺序存储表示是一维数组吗？解析：答案“否”，应是顺序表，其区别在顺序表中元素是相继连续存放的。而一维数组只能有两个操作“按下标存”“按下标取”，它不一定是相继存放，不适宜存储顺序的、连续的序列元素。问题5.想要以O(1)的时间代价存取第i个表元素，线性表应采用顺序表还是单链表？解析：“顺序表”，因为单链表只能顺序地逐个访问，顺序表可以直接访问第i个元素。22问题6.为了统一空链表和非空链表的操作，简化链表的插入删除操作，需要给链表增加点什么？解析：“增加表头结点”。问题7.在何种场合选用顺序表？链表呢？解析：从时间角度来看，需要经常查看不需经常增删的场合使用顺序表，因它可直接存取，但增删要大量移动存储块；反之，选择链表，因它在增删元素时不需移动存储，修改指针即可，但只能顺序访问，存取速度慢。从空间角度来看，顺序表存储密度（有效存储/总存储）高，空间利用率好；链表存储密度较低，空间利用率差一些。23循环链表和双向链表问题8.想要以O(1)的时间代价把两个链表连接起来可采用何种链表结构？解析：“循环链表”，若设两个循环链表头指针为p和q，用r=p-link;p-link=q-link;q-link=r;即可把这两个连接起来。pqr24问题9.想要判断一个带表头结点的循环链表L是否为空，应采用何种语句？解析：“L-link==L”。空表还需保留一个表头结点，它的下一个结点还是它自己。问题10.想要以O(1)的时间代价访问第i个表元素的直接前驱和／或直接后继，应采用何种链表结构？解析：“双向链表”。只要事先定位于该表结点，通过该结点的前驱指针和后继指针，直接能够找到该元素的直接前驱或直接后继。25第二章知识点解析本章“栈、队列与数组”的知识点有8个：1)栈和队列的定义及其特点2)栈的存储表示及其基本运算的实现3)队列的存储表示及其基本运算的实现4)栈的应用5)队列的应用6)多维数组7)特殊矩阵8)稀疏矩阵26栈和队列的定义及其特点问题1.元素1,2,3,4依次进栈，可能的出栈序列有多少种？队列呢？解析：用catalan函数计算有8!/4!/4!/5=14种，用队列是1种。因栈有FILO，队列有FIFO特性。问题2.当元素以A,B,C,D,E顺序进栈，D,B,C,E,A是可能的出栈顺序吗？解析：“否”，因序列的进出栈顺序为IAIBICIDOD,当D出栈后，栈顶为C，不能让B先出来。所以D,B,C,E,A不是可能的出栈顺序。27问题3.可否用两个栈模拟一个队列？反过来呢？解析：“可以”，一个栈把全部数据反过来，另一个栈再把这些数据反过去即可。而队列不能。问题4.栈、队列对线性表加了什么限制？解析：“限制了存取位置”。栈要求只能在表的一端（栈顶）访问、插入和删除，队列要求只能在表的一端（队尾）插入，在另一端（队头）访问和删除，不能在表的中间做上述运算。这决定了在栈和队列上只能顺序访问，不能直接存取，无论采用何种存储表示。这表现了它们优秀的“结构化”特性。28栈的存储表示及其基本运算的实现问题5.当栈空时顺序栈的栈顶指针top=-1，当栈非空时top是否指示最后元素加入的位置？解析：“是”，每当新元素进栈时让栈顶指针top先加1，再按top指示位置把新元素加入，所以栈非空时栈顶指针总是指示最后加入元素的位置。问题6.顺序栈的进栈、出栈的先决条件是什么？解析：进栈的先决条件是栈未满，栈满再进栈就会产生溢出；出栈的先决条件是栈不空，栈空再退栈可报告操作失败。29问题7.当两个栈共享同一个存储空间V[m]时，可设栈顶指针数组t[2]和栈底指针数组b[2]。如果进栈采用两个栈相向前行的方式，则任一栈的栈满条件是什么？解析：“t[0]+1==t[1]”。设0号栈正向进栈，1号栈反向进栈，t[0]与t[1]碰头即栈满。问题8.链式栈的栈顶指针是指在链头还是链尾？解析：“链头”，链式栈一般采用单链表，栈顶指针即为链头指针。进栈出栈均在链头进行，每次都要修改栈顶指针。链空即栈空，top==NULL。30问题9.链式栈只能顺序存取，而顺序栈不但能顺序存取，还能直接存取，这话对吗？解析：“不对”，顺序栈不能直接存取。问题10.理论上链式栈没有栈满问题，但在进栈操作实现时，还要判断一个先决条件，是何条件？解析：每创建新的栈结点时还要判断是否动态分配成功。若不成功则进栈操作失败