一数据结构的章节结构及重点构成
数据结构学科的章节划分基本上为概论线性表栈和队列串多维数组和广义表树和二叉树图查找内排外排文件动态存储分配
对于绝大多数的学校而言外排文件动态存储分配三章基本上是不考的在大多数高校的计算机本科教学过程中这三章也是基本上不作讲授的所以大家在这三章上可以不必花费过多的精力只要知道基本的概念即可但是对于报考名校特别是该校又有在试卷中对这三章进行过考核的历史那么这部分朋友就要留意这三章了
按照以上我们给出的章节以及对后三章的介绍数据结构的章节比重大致为
概论内容很少概念简单分数大多只有几分有的学校甚至不考
线性表基础章节必考内容之一考题多数为基本概念题名校考题中鲜有大型算法设计题如果有也是与其它章节内容相结合
栈和队列基础章节容易出基本概念题必考内容之一而栈常与其它章节配合考查也常与递归等概念相联系进行考查
串 基础章节概念较为简单专门针对于此章的大型算法设计题很少较常见的是根据KMP进行算法分析
多维数组及广义表 基础章节基于数组的算法题也是常见的分数比例波动较大是出题的可选单元或侯补单元一般如果要出题多数不会作为大题出数组常与查找排序等章节结合来作为大题考查
树和二叉树 重点难点章节各校必考章节各校在此章出题的不同之处在于是否在本章中出一到两道大的算法设计题通过对多所学校的试卷分析绝大多数学校在本章都曾有过出大型算法设计题的历史
图 重点难点章节名校尤爱考如果作为重点来考则多出现于分析与设计题型当中可与树一章共同构成算法设计大题的题型设计
查找 重点难点章节概念较多联系较为紧密容易混淆出题时可以作为分析型题目给出在基本概念型题目中也较为常见算法设计型题中可以数组结合来考查也可以与树一章结合来考查
排序 与查找一章类似本章同属于重点难点章节且概念更多联系更为紧密概念之间更容易混淆在基本概念的考查中尤爱考各种排序算法的优劣比较此类的题算法设计大题中如果作为出题那么常与数组结合来考查
二数据结构各章节重点勾划
第章概述
本章主要起到总领作用为读者进行数据结构的学习进行了一些先期铺垫大家主要注意以下几点数据结构的基本概念时间和空间复杂度的概念及度量方法算法设计时的注意事项本章考点不多只要稍加注意理解即可
第一章线性表
作为线性结构的开篇章节线性表一章在线性结构的学习乃至整个数据结构学科的学习中其作用都是不可低估的在这一章第一次系统性地引入链式存储的概念链式存储概念将是整个数据结构学科的重中之重无论哪一章都涉及到了这个概念
总体来说线性表一章可供考查的重要考点有以下几个方面
线性表的相关基本概念如前驱后继表长空表首元结点头结点头指针等概念
线性表的结构特点主要是指除第一及最后一个元素外每个结点都只有一个前趋和只有一个后继
线性表的顺序存储方式及其在具体语言环境下的两种不同实现表空间的静态分配和动态分配静态链表与顺序表的相似及不同之处
线性表的链式存储方式及以下几种常用链表的特点和运算单链表循环链表双向链表双向循环链表其中单链表的归并算法循环链表的归并算法双向链表及双向循环链表的插入和删除算法等都是较为常见的考查方式此外近年来在不少学校中还多次出现要求用递归算法实现单链表输出(可能是顺序也可能是倒序)的问题
在链表的小题型中经常考到一些诸如判表空的题在不同的链表中其判表空的方式是不一样的请大家注意
线性表的顺序存储及链式存储情况下其不同的优缺点比较即其各自适用的场合单链表中设置头指针循环链表中设置尾指针而不设置头指针以及索引存储结构的各自好处
第二章栈与队列
栈与队列是很多学习DS的同学遇到第一只拦路虎很多人从这一章开始坐晕车一直晕到现在所以理解栈与队列是走向DS高手的一条必由之路
学习此章前你可以问一下自己是不是已经知道了以下几点
栈队列的定义及其相关数据结构的概念包括顺序栈链栈共享栈循环队列链队等栈与队列存取数据(请注意包括存和取两部分)的特点
递归算法栈与递归的关系以及借助栈将递归转向于非递归的经典算法n!阶乘问题fib数列问题hanoi问题背包问题二叉树的递归和非递归遍历问题图的深度遍历与栈的关系等其中涉及到树与图的问题多半会在树与图的相关章节中进行考查
栈的应用数值表达式的求解括号的配对等的原理只作原理性了解具体要求考查此为题目的算法设计题不多
循环队列中判队空队满条件循环队列中入队与出队算法
如果你已经对上面的几点了如指掌栈与队列一章可以不看书了注意我说的是可以不看书并不是可以不作题哦
第三章串
经历了栈一章的痛苦煎熬后终于迎来了串一章的柳暗花明
串在概念上是比较少的一个章节也是最容易自学的章节之一但正如每个过来人所了解的KMP算法是这一章的重要关隘突破此关隘后走过去又是一马平川的大好DS山河了呵呵
串一章需要攻破的主要堡垒有
串的基本概念串与线性表的关系(串是其元素均为字符型数据的特殊线性表)空串与空格串的区别串相等的条件
串的基本操作以及这些基本函数的使用包括取子串串连接串替换求串长等等运用串的基本操作去完成特定的算法是很多学校在基本操作上的考查重点
顺序串与链串及块链串的区别和联系实现方式
KMP算法思想KMP中next数组以及nextval数组的求法明确传统模式匹配算法的不足明确next数组需要改进之外其中理解算法是核心会求数组是得分点不用我多说这一节内容是本章的重中之重可能进行的考查方式是求next和nextval数组值根据求得的next或nextval数组值给出运用KMP算法进行匹配的匹配过程
第四章数组与广义表
学过程序语言的朋友数组的概念我们已经不是第一次见到了应该已经一回生二回熟了所以在概念上不会存在太大障碍但作为考研课程来说本章的考查重点可能与大学里的程序语言所关注的不太一样下面会作介绍
广义表的概念是数据结构里第一次出现的它是线性表或表元素的有限序列构成该结构的每个子表或元素也是线性结构的所以这一章也归入线性结构中
本章的考查重点有
多维数组中某数组元素的position求解一般是给出数组元素的首元素地址和每个元素占用的地址空间并组给出多维数组的维数然后要求你求出该数组中的某个元素所在的位置
明确按行存储和按列存储的区别和联系并能够按照这两种不同的存储方式求解中类型的题
将特殊矩阵中的元素按相应的换算方式存入数组中这些矩阵包括对称矩阵三角矩阵具有某种特点的稀疏矩阵等熟悉稀疏矩阵的三种不同存储方式三元组带辅助行向量的二元组十字链表存储掌握将稀疏矩阵的三元组或二元组向十字链表进行转换的算法
广义表的概念特别应该明确表头与表尾的定义这一点是理解整个广义表一节算法的基础近来在一些学校中出现了这样一种题目类型给出对某个广义表L若干个求了若干次的取头和取尾操作后的串值要求求出原广义表L大家要留意
与广义表有关的递归算法由于广义表的定义就是递归的所以与广义表有关的算法也常是递归形式的比如求表深度复制广义表等这种题目可以根据不同角度广义表的表现形式运用两种不同的方式解答一是把一个广义表看作是表头和表尾两部分分别对表头和表尾进行操作;二是把一个广义表看作是若干个子表分别对每个子表进行操作
第五章树与二叉树
从对线性结构的研究过度到对树形结构的研究是数据结构课程学习的一次跃变此次跃变完成的好坏将直接关系到你到实际的考试中是否可以拿到高分而这所有的一切将最终影响你的专业课总分所以树这一章的重要性已经不说自明了
总体来说树一章的知识点包括
二叉树的概念性质和存储结构二叉树遍历的三种算法(递归与非递归)在三种基本遍历算法的基础上实现二叉树的其它算法线索二叉树的概念和线索化算法以及线索化后的查找算法最优二叉树的概念构成和应用树的概念和存储形式树与森林的遍历算法及其与二叉树遍历算法的联系树与森林和二叉树的转换
[] [] [] []
![数据结构复习重点归纳（适于清华严版教材)[1]](/UploadFiles/4.jpg)