考研数据结构

先序遍历(根左右)，u在w的前面后序遍历(左右根)，u在w的后面证明：u是w的祖先节点证明如下：反证法，假设u不是w的祖先节点，记二叉树为BT，二叉树的根节点为r，即u不在r到w的路径上。可分为以下两种情况：①u是w的字树上的节点记w的左子树wl（wleft），右子树wr（wright），u可能在wl上，或在wr上，先序遍历，w在wl之前，wl在wr之前，即w肯定在u之前，与题意不符。②u是w子树节点以外的其他节点记r到w的路径为r，r1，r2……rk，w.即u是r，r1，r2……rk 其中某个节点的子树节点。取r，r1，r2……rk其中某个节点rx，记rx的左子树rxl，右子树rxr，rxl=w，rxr=u，先序遍历，u在w后面，与题意矛盾rxl=u，rxr=w，后序遍历，u在w前面，与题意矛盾综上，u只能是r，r1，r2……rk其中的某一个节点，即u是w的祖先节点。问题得证。

基本术语：1. 数据：输入到电脑中的所有信息2. 数据元素，数据的基本单位3. 数据项：数据的最小单位4. 数据对象：是数据的一个子集本例中，每一行为数据元素每一列为数据项,每一列为数据项，行为元素（基本），列为项（最小）（2）数据结构定义：是相互之间存在一种或多种特定关系的数据元素的集合。逻辑结构+存储结构+操作=数据结构逻辑结构：数据元素的逻辑关系物理结构：印象（3）四种逻辑结构集合：集体线性：一对一关系树形：一对多图状结构：多对多（4）四种存储结构顺序存储：连续占用链接存储：不连续占用索引存储：类似于字典散列存储：（哈希算法）高效索引每一个问题都只有一个对应的逻辑结构，可以选择不同的存储结构->算法，可以提升效率。1.3 ADT-抽象数据类型ADT 抽象数据类型{数据对象：<数据对象的定义>数据关系: <数据关系的定义>基本操作：<基本操作的定义>}ADT 抽象数据类型名1.4算法定义：指一系列确定的而且是有限步骤内能完成的操作。（一系列有限步骤）特点：有穷性；确定性；有效性（可行性）；输入（0~多个）；输出（1~多个）；计算：复杂度（4）算法设计的要求：正确性；可读性；健壮性；效率与低存储量需求；算法优劣评价标准：时间；空间（5）时间复杂度定义：算法问题规模n的某个函数f(n)时间：O（logn）,O(n),O（nlogn）（7）空间复杂度定义：在内存中占空间的大小组成：本身的空间；输出、输入的空间；临时的辅助空间原地工作：辅助空间相对于输入数据量是常量。若依赖特定的输入，则按最坏的情况申请。小结：1. 在数据结构中，从逻辑上可以把数据结构分成：线性结构（集合，线性）和非线性（树、图）结构。算法的时间复杂度取决于什么：问题的规模和待处理数据的初态。

1. 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象 以及它们之间的 关系和运算等的学科。2. 数据结构被形式地定义为（D, R），其中D是数据元素 的有限集合，R是D上的 关系 有限集合。3. 数据结构包括数据的逻辑结构、数据的存储结构和数据的运算这三个方面的内容。4. 数据结构按逻辑结构可分为两大类，它们分别是线性结构 和非线性结构 。5. 线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。6． 在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有 1个前驱结点；最后一个结点没有后续结点，其余每个结点有且只有1个后续结点。7. 在树形结构中，树根结点没有前驱 结点，其余每个结点有且只有1个前驱结点；叶子结点没有后续 结点，其余每个结点的后续结点数可以任意多个 。8. 在图形结构中，每个结点的前驱结点数和后续结点数可以任意多个 。9．数据的存储结构可用四种基本的存储方法表示，它们分别是顺序 、 链式 、 索引 和 散列 。10. 数据的运算最常用的有5种，它们分别是插入 、 删除、修改、 查找 、排序。11. 一个算法的效率可分为时间效率和空间效率。12. 在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与表长和该元素在表中的位置有关。13. 线性表中结点的集合是有限的，结点间的关系是一对一的。14. 向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动n-i+1 个元素。15. 向一个长度为n的向量中删除第i个元素(1≤i≤n)时，需向前移动n-i 个元素。16. 在顺序表中访问任意一结点的时间复杂度均为O(1)，因此，顺序表也称为随机存取的数据结构。17. 顺序表中逻辑上相邻的元素的物理位置必定相邻。单链表中逻辑上相邻的元素的物理位置不一定 相邻。18．在单链表中，除了首元结点外，任一结点的存储位置由其直接前驱结点的链域的值指示。19． 在n个结点的单链表中要删除已知结点*p，需找到它的前驱结点的地址，其时间复杂度为O（n）。20.栈只能在栈顶插入和删除元素；对于队列只能在队尾插入和队首删除元素。21. 栈是一种特殊的线性表，允许插入和删除运算的一端称为栈顶。不允许插入和删除运算的一端称为栈底。22. 队列是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。23． 由３个结点所构成的二叉树有5种形态。24. 一棵深度为6的满二叉树有n1+n2=0+ n2= n0-1=31个分支结点和26-1=32个叶子。注：满二叉树没有度为1的结点，所以分支结点数就是二度结点数。25． 一棵具有２５７个结点的完全二叉树，它的深度为9。26．设一棵完全二叉树有700个结点，则共有350个叶子结点。答：最快方法：用叶子数＝[n/2]＝35027． 设一棵完全二叉树具有1000个结点，则此完全二叉树有500个叶子结点，有499个度为2的结点，有1个结点只有非空左子树，有0个结点只有非空右子树。答：最快方法：用叶子数＝[n/2]＝500，n2=n0-1=499。 另外，最后一结点为2i属于左叶子，右叶子是空的，所以有1个非空左子树。完全二叉树的特点决定不可能有左空右不空的情况，所以非空右子树数＝0.28．在数据的存放无规律而言的线性表中进行检索的最佳方法是顺序查找（线性查找）。29. 线性有序表（a1，a2，a3，…，a256)是从小到大排列的，对一个给定的值k，用二分法检索表中与k相等的元素，在查找不成功的情况下，最多需要检索8 次。设有100个结点，用二分法查找时，最大比较次数是7。30. 假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为2；比较四次查找成功的结点数为 8；平均查找长度为3.7。31．折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素28，6，12，20比较大小。32.在各种查找方法中，平均查找长度与结点个数n无关的查找方法是散列查找 。33. 散列法存储的基本思想是由关键字的值决定数据的存储地址。

考研院校选择是一个决定考研成败的一步，也是人生中一次重大的选择！下面汇总了计算机考研计算机科学与技术学硕专业课只考一门数据结构的院校，一起来看看吧！专业课只考数据结构院校汇总北京12所北京交通大学、北方工业大学、北京化工大学、北京工商大学、中国农业大学（自划线院校）、首都师范大学、中国传媒大学、中央民族大学、中国矿业大学（北京）、中国地质大学（北京）、华北计算机系统工程研究所、军事科学院天津3所天津大学（自划线院校）、天津工业大学、天津城建大学河北3所河北地质大学、石家庄铁道大学、河北经贸大学山西4所山西大学、太原科技大学、中北大学、山西财经大学内蒙2所内蒙古科技大学、内蒙古工业大学辽宁8所大连理工大学（自划线院校）、沈阳工业大学、沈阳理工大学、辽宁工程技术大学、辽宁石油化工大学、沈阳化工大学、大连海事大学、辽宁工业大学吉林省3所长春理工大学、东北电力大学、长春工业大学黑龙江6所黑龙江大学、黑龙江科技大学、东北石油大学、东北农业大学、东北林业大学、哈尔滨商业大学上海2所上海海事大学、上海科技大学江苏7所常州大学、南京邮电大学、江苏大学、南京财经大学、扬州大学、南京审计大学、陆军工程大学浙江2所浙江师范大学、温州大学安徽2所安徽工业大学、安徽理工大学福建1所福建农林大学江西6所华东交通大学、东华理工大学、南昌航空大学、江西理工大学、江西农业大学、江西中医药大学山东12所中国石油大学（华东）、青岛科技大学、济南大学、青岛理工大学、齐鲁工业大学、山东理工大学、山东农业大学、山东师范大学、鲁东大学、青岛大学、烟台大学、山东工商学院河南3所河南理工大学、河南工业大学、河南财经政法大学湖北3所湖北工业大学、华中师范大学、三峡大学湖南5所湖南大学（自划线院校）、中南大学（自划线院校）、长沙理工大学、湖南农业大学、湖南师范大学广东3所广东海洋大学、华南师范大学、东莞理工学院广西3所广西大学、桂林电子科技大学、桂林理工大学重庆1所重庆邮电大学四川2所西南交通大学、西华大学贵州1所贵州财经大学云南1所昆明理工大学陕西7所西安理工大学、西安工业大学、西安科技大学、西安石油大学、陕西师范大学、西安邮电大学、火箭军工程大学甘肃2所兰州理工大学、兰州交通大学对于初试只考一门数据结构，复习内容量相比408来说不是很大，对于本科期间基础薄弱的同学来说，这些学校是个很好的选择！

万学海文从往年计算机统考大纲数据结构部分及其相关知识点可以看出：数据结构占了45分，和计算机组成原理部分同一个比重，这足以体现计算机专业研究生选拔对数据结构课程的重视程度。针对这样的情况，为我们的考生们精心准备了一些数据结构重难点解析和复习建议。统考大纲对数据结构的考查目标定位为掌握数据结构的基本概念、基本原理和基本方法，掌握数据的逻辑结构、存储结构以及基本操作的实现；能够对算法进行基本的时间复杂度和空间复杂度的分析；能够运用数据结构的基本原理和方法进行问题的分析求解，具备采用C、C 或JAVA语言设计程序与实现算法的能力。当然，考生也不必因此而专门复习一遍C或C 程序设计，毕竟复习时间有限，而且数据结构要求的重点在于算法设计的能力，而不是编写代码的能力，因此，只要能用类似伪代码的形式把思路表达清楚就行，不用强求写出一个没有任何语法错误的程序。下面我们来解析一下知识点：线性表这一章里面的知识点不多，但要做到深刻理解，能够应用相关知识点解决实际问题。链表上插入、删除节点时的指针操作是选择题的一个常考点，诸如双向链表等一些相对复杂的链表上的操作也是可以出现在综合应用题当中的。栈、队列和数组可以考查的知识点相比链表来说要多一些。最基本的，是栈与队列FILO和FIFO的特点。比如针对栈FILO的特点，进栈出栈序列的问题常出现在选择题中。其次，是栈和队列的顺序和链式存储结构，这里一个常考点是不同存储结构下栈顶指针、队首指针以及队尾指针的操作，特别是循环队列判满和判空的2种判断方法。再次，是特殊矩阵的压缩存储，这个考点复习的重点可以放在二维矩阵与一维数组相互转换时，下标的计算方法，比如与对角线平行的若干行上数据非零的矩阵存放在一维数组后，各个数据点相应的下标的计算。这一章可能的大题点，在于利用堆栈或队列的特性，将它们作为基础的数据结构，支持实际问题求解算法的设计，例如用栈解决递归问题，用队列解决图的遍历问题等等。树和二叉树：这一章中我们从顺序式的数据结构，转向层次式的数据结构，要掌握树、二叉树的各种性质、树和二叉树的不同存储结构、森林、树和二叉树之间的转换、线索化二叉树、二叉树的应用(二叉排序树、平衡二叉树和Huffman树)，重点要熟练掌握的，是森林、树以及二叉树的前中后三种遍历方式，要能进行相应的算法设计。这一部分是数据结构考题历来的重点和难点，复习时要特别关注。一些常见的选择题考点包括：满二叉树、完全二叉树节点数的计算，由树、二叉树的示意图给出相应的遍历序列，依据二叉树的遍历序列还原二叉树，线索化的实质，计算采用不同的方法线索化后二叉树剩余空指针域的个数，平衡二叉树的定义、性质、建立和四种调整算法以及回溯法相关的问题。常见的综合应用题考点包括：二叉树的遍历算法，遍历基础上针对二叉树的一些统计和操作(比如结点数统计、左右子树对换等等)，判断某棵二叉树是否二叉排序树，以上这些都要求能用递归的和非递归的算法解决，特别要重视非递归的算法，线索化后二叉树的遍历算法，如查找某结点线索化后的前驱或后继结点的算法以及给出Huffman编码等等。图：在这一章中需要识记的是图以及基于图的各种定义，存储方式。要熟练掌握图的深度遍历和广度遍历算法，这是用图来解决应用问题时常用的算法基础。需要掌握基于图的多个算法，能够以手工计算的方式在一个给定的图上执行特定的算法求解问题。常见的应用问题直接给出或经过抽象，会成为下列问题：最小生成树求解(PRIM算法和KRUSKAL算法，两种方法思想都很简单，但要注意不要混淆这两种方法)，拓扑排序问题(这里会用到数组实现的链表，可以注意一下)，关键路径问题(数据结构的较大难点，要把概念理解透，能做出表格找出关键路径)，最短路径问题(有重要的应用背景，也是贪心法不多的能给出最优解的典型问题之一)。查找：这一章，需要识记关键字、主关键字、次关键字的含义;静态查找与动态查找的含义及区别;平均查找长度ASL的概念念及在各种查找算法中的计算方法和计算结果，特别是一些典型结构的ASL值，B-树的概念和基本操作冲突解决方法的选择和冲突处理过程的描述，B 树的概念(新增考点)，特别要注意B-树和B 树概念的对比，以及Hash表相关的概念。要熟练掌握顺序表、链表、二叉树上的查找方法，特别要注意顺序查找、二分查找的适用条件(比如链表上用二分查找就不合适)和算法复杂度。排序：最新的大纲将去年的内部排序范围扩展为排序，排序既是重点，又是难点。排序算法众多，今年大纲还加上了外部排序，总共10种，各种不同算法还有相应的一些概念定义需要记住。选择题常见的问题包括：给定数列要求给出某种特定排序方法运行一轮后的排序结果，或者给出初始数列和一轮排序结果要求选择采用的排序算法，给定时间、空间复杂度要求以及数列特征要求选择合适的排序算法等等。如果排序这一考点出现在综合应用题中则常与数组结合来考查。数据结构的复习要紧扣参考书，把书认真看几遍，深入理解大纲相关的知识点。

数据来源18年。包含数据结构单一门，或加一门C语言&C++。据统计，985学校中一共19所学校计算机相关专业只考数据结构1.华中科技大学软件学院软件专硕思想政治理论、 英语二、数学二、887数据结构与算法分析2.厦门大学信息科学与技术学院计算机专硕思想政治理论、 英语二、数学二、903数据结构B3.中南大学信息科学与工程学院（北校区）计算机学硕思想政治理论、 英语一、数学一、943数据结构计算机专硕思想政治理论、 英语二、数学二、943数据结构4.南开大学计算机学院计算机专硕思想政治理论、 英语二、数学二、814（数据结构75分、C++75分）软件学院软件工程学硕思想政治理论、 英语一、数学一、815（数据结构75分、C++75分）软件工程专硕思想政治理论、 英语二、数学二、816（数据结构75分、C75分）5.北京航空航天大学软件学院软件学硕政治、数一、英一、991数据结构与C语言程序设计软件专硕政治、数二、英二、991数据结构与C语言程序设计6.华东师范大学计算机科学技术系计算机专硕思想政治理论、 英语二、数学二、839数据结构(含C语言程序设计)软件科学与技术系软件专硕思想政治理论、 英语二、数学二、834程序设计综合(含数据结构与C语言)计算中心计算机专硕思想政治理论、 英语二、数学二、839数据结构(含C语言程序设计)数据科学与工程学院计算机专硕思想政治理论、 英语二、数学二、839数据结构(含C语言程序设计)7.北京理工大学计算机学院计算机专硕思想政治理论、 英语二、数学二、889数据结构软件学院计算机学硕思想政治理论、 英语一、数学一、885（数据结构75+程序设计75）数字表演学硕思想政治理论、 英语一、数学二、885（数据结构75+程序设计75）软件工程专硕思想政治理论、 英语一、数学二、885（数据结构75+程序设计75）8.吉林大学计算机科学与技术学院计算机专硕思想政治理论、英语一、数学二、966数据结构+程序设计（C/C++/JAVA任选）软件学院软件专硕思想政治理论、英语一、数学二、967高级语言程序设计+数据结构9.西安交通大学软件学院软件专硕思想政治理论、英语二、数学二、915 计算机软件基础（数据结构和程序设计）10.天津大学计算机科学与技术学院模式识别与智能系统、计算机科学与技术、软件学硕思想政治理论、 英语一、数学一、901数据结构与程序设计计算机专硕思想政治理论、 英语二、数学二、901数据结构与程序设计11.湖南大学信息科学与工程学院计算机学硕思想政治理论、 英语一、数学一、866数据结构OR867计算机系统计算机专硕思想政治理论、 英语二、数学二、829计算机程序设计OR830数字电路与逻辑设计软件专硕思想政治理论、 英语二、数学二、829计算机程序设计12.中国海洋大学信息科学与工程学院软件学硕思想政治理论、英语一、数学一、912数据结构和软件工程计算机专硕（技术方向）思想政治理论、英语二、数学二、910高级程序设计（C语言）13.大连理工大学软件学院软件学硕思想政治理论、英语一、数学一、887数据结构与软件工程软件专硕思想政治理论、英语二、数学二、887数据结构与软件工程14.山东大学计算机科学与技术学院计算机专硕思想政治理论、英语二、数学二、909数据结构软件学院软件专硕思想政治理论、英语二、数学二、858C语言程序设计与数据结构15.北京师范大学信息科学与技术学院计算机学硕思想政治理论、英语一、数学一、847数据结构与程序设计软件专硕思想政治理论、英语二、数学二、860教育与教学设计或867数据科学或879数据结构与程序设计16.东北大学计算机科学与工程学院计算机学硕思想政治理论、英语一、数学一、842计算机基础（数据结构与C语言）计算机专硕思想政治理论、英语二、数学二、842计算机基础（数据结构与C语言）软件学院软件学硕思想政治理论、英语一、数学二、858数据结构与C语言程序设计软件专硕思想政治理论、英语二、数学二、858数据结构与C语言程序设计17.中国农业大学计算机学硕思想政治理论、 英语一、数学一、809 地理信息系统（含遥感原理）或 816 数学分析或 820 电路原理或 821 数据结构或 833 电子技术计算机专硕思想政治理论、 英语二、数学二、809 地理信息系统（含遥感原理）或 816 数学分析或 820 电路原理或 821 数据结构或 833 电子技术18.西北农林科技大学计算机学硕思想政治理论、 英语一、数学一、846（计算机组成原理，C 语言，数据结构）（专业课 3 选 2）软件工程专硕思想政治理论、 俄语或日语或英语二、数学二、842 数据结构与 C语言农业工程与信息管理专硕思想政治理论、 俄语或日语或英语二、农业知识综合三、967 数据结构19.中央民族大学19年改考

数据结构是计算机学科考研中的一门必考课。例如计算机专业课全国统考408中有一门课就是数据结构，另外一些自主命题的高校专业课就考数据结构一门。不仅数据结构对于考研来说十分关键，而且学习它有助于提高编程水平。小编今年要参加今年的考研，考的正是计算机专业。大学学的是经贸专业，对数据结构这门课没有太好的基础，只是去年学过python数据分析和爬虫相关的一些语句。所以，我的学习经历对于小白还是有一定的参考意义的。入门推荐小甲鱼的数据结构和C语言视频。因为小白会弄不清楚数据结构中指针、结构体等概念，结合C语言视频，就会好很多。小甲鱼这个主讲老师的特点:给人信心、多次一节课的重复、准确、有趣。正式学习推荐清华大学严蔚敏老师的数据结构视频和相应书本，书本内容和视频完全是对应的。严蔚敏老师的课程也是全程没有一句无用的话，可以让脑子全程运转。而且老师讲的思路也很清晰，最棒的是通常老师会画图辅助教学，常常把每一步都讲得很清楚。

考研院校选择是一个决定考研成败的一步，也是人生中一次重大的选择！选择一个适合的院校也是十分重要的。下面汇总了一些初试专业课考两门数据结构和计算机网络的学校：北京1所中国石油大学（北京）内蒙古1所内蒙古工业大学浙江1所浙江工业大学河南2所郑州轻工业大学、河南农业大学武汉2所华中科技大学、武汉科技大学数据结构是计算机专业的基础课程，数据结构和计算机网络作为初试科目，复习内容量来说不是特别大，如果你对于这两门课掌握的较好，可以考虑一下些院校！了解更多请私信~

有些人考研只需要花三个月，有些人却要花上三年。考研难吗？尤其是计算机考研？今天小任老师就为大家分析一下真实的计算机考研群体面对的备考现状。首先需要评估一下院校难度，A区的985和211虽然很好，但是也很难，竞争压力太大；还有网上流传的B区某广西211不保护一志愿，只为接收985、211的优质调剂生源，素质之低，可见一斑。还需要注意到一个趋势，那就是更多学校的保研招生比例逐年增高，留给统考生名额逐渐减少；再加上全国报考人数每年几十万的增加，想想都觉得考个名校真是难到怀疑人生。对于计算机的408，初试想要高分，408也要120+，只要稍微努力一下，上120分还是可以的。然而关键是数学基础要好，所以在备考过程中，要多付出一些时间给数学。其次，要跟着教材进行复习，单科的基础知识点从头到尾，认认真真多刷几遍，把所有题同步认真学习。要想完成这个工作，最起码要用3个月以上的时间，这样才能把所有基础知识点、重点和难点全部熟练掌握。在小任老师身边，就有这么一位考计算机的同学：他非科班出身，9月份才决心要考研，跨计算机。了解自己实力不够，时间不够，就从考英二数二，专业课考两门以内的学校里找一个211。全程赶进度，10月过了一半才把数学过完一轮，同时看数据结构，用了天勤的书，把里面的题目刷的差不多。11月开始见缝插针看政治，睡前用小程序刷政治选择题。最后各个科目直接上真题。因为英语准备不足，考试发挥的很不好，但是还是把心态稳住完成了第二天的考试，最后擦边惊险上岸，所以无论怎么样都要坚持到最后。总而言之，计算机专业考研不仅初试难度较大，复试难度也比较高，一部分高校不仅会进行多个科目的笔试，同时还会安排上机考核，这对于考生的动手实践能力要求还是比较高的。另外，一部分重点高校在复试过程中，会随机考察一门专业课，这也在很大程度上增加了考生的复习难度。距2021考研初试只剩二十多天的时间了。这是一条孤独的路，也许会有一瞬，想过要放弃。但走过不平凡的2020，请给自己一个理由，继续咬牙坚持。奋斗到底的，一定是最接近梦想的人。