数据结构考研真题

先序遍历(根左右)，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的祖先节点。问题得证。

第二章 线性表2.1 线性表的基本定义定义：相同数据类型数据元素的有序序列特点：唯一前驱（除头结点）、唯一后继（除尾结点）、唯一头/尾节点操作：增删改查、创建销毁、判空求长2.2 线性表的顺序存储结构（顺序表）2.2.1 线性表的基本描述静态描述：#define Maxsize 50; //链表允许的最大长度typedef struct{char data[Maxsize]; //存放链表元素的数组int length; //链表当前元素的长度}Sqlist;动态描述：#define InitSize 50; //链表初始化最大长度typedef struct{char * data; //指向链表的指针int MaxSize,length; //length链表当前元素的长度,MaxSize链表当前最大长度}Sqlist;2.2.2 基本操作这个太多了，直接拍照笔记吧，有不明白的在下方留言，我会解答的

基本术语：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. 在数据结构中，从逻辑上可以把数据结构分成：线性结构（集合，线性）和非线性（树、图）结构。算法的时间复杂度取决于什么：问题的规模和待处理数据的初态。

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

线性结构：最简单的线性结构就是线性表（1）特点a1 前驱 a2 后继 a31. a1只有后继2. a4只有前驱3. 其它元素一定是一个前驱 一个后继4. 逻辑上和物理上都相邻（2）类型：表、栈、队列（3）方法：逻辑结构、存储结构、操作（4）线性表：是一种线性结构，也是逻辑结构存储结构->顺序存储->操作 链式结构->单向、双向、循环->操作（5）不同操作：存储结构->顺序表（连续）1. 定义顺序表：数组2. 建表、查询、增加、删除、修改、输出（6）链式存储结构（链表）：不必连续有头、有尾、成链状，叫链表。定义存储结构、定义链表Struct node{Int data;// 数据域Struct node * next;//指针域 指针指向自身};（7）链表操作1.创建链表 前插：栈 后插：队2.链表查询 ：序号 数据链表查询必须顺next往下查询3. 链表插入：1 p指向a3前面的结点2先连s->next=p->next 后断p->next=s4. 链表的删除P->next=p->next->next或:q=p->next;p->next=q->next;free(q); 释放空间5. 链表逆序6. 链表合并多项式合并将次数低的插入次数高的，数据域进行相加。7. 链表输出引入一个指针p，while（p!=NULL）{Cout<<p->data;P=p->next;//往下移;}(8)循环链表每个结点都可以找到，最后一个结点next指针不为0，直接指向头指针。（9）双向链表每个结点中都有前驱和后继的指向，缺点：操作比较麻烦，空间浪费。双向链表插入方法：先连：p->prior=current;p->next=current->next;后断：current->next=p;p->next->prior=p;小结：1.带头结点链表，p的定义应该是头指针指向的后一个；不带头结点链表则p定义头指针。2.顺序表中第一个元素的存储地址是100，每个元素长度为2，则第5个元素地址是：108。100+（n-1）*2;编号从0开始。3.链接存储结构所占存储结构所占空间：分两部分，一部分存放结点值，另一部分存放结点间关系的指针。4.线性表L在什么情况下适用于链式结构实现：需不断对L进行删除插入。

数据结构真题回忆(初试)一、填空题：一个三维数组，要你求a[10][5][3]这种的存储地址。二、简答题：递归过程栈的变化比较各排序的优缺点、Dijkstra求最短路径过程三、大题1.用链表实现集合的交并补运算， 好像是求(AUB)-C。2.迷宫问题，四个方向可走，找出口。3.第二题由树的前序和中序序列来生成一颗树。4.村村通， 就是一个最小生成树的问题。复试：机试+笔试+面试笔试真题：一、计算机组成原理1.什么是控制器，控制器的输入信号(大概是)。2.存储器的位、字扩展。3.文件系统的文件逻辑结构和物理结构，管理大文件，200GB。4.解释指令的结构和组成。二、操作系统(操作系统出现填空题， 将之前的大题改成填空题，内容多分值小)1.磁盘调度，最短寻道时间优先2.页面调度，应该是 LRU3.进程的四个特性4.论述题， 操作系统如何提高CPU的利用率。5.进程的同步互斥， 一个读，一个移动，一个输出。三、离散数学 (离散今年也出现了填空题)1.集合的运算 {0，{0}} - 0 = ——2.平面图和边数的关系还是什么的。3.谓词逻辑病人喜欢医生，病人都不喜欢庸医结论是医生都不是庸医。(符号化，并推理)4.等价关系的证明iff我还以为是印刷错了... 没想到是当且仅当。4、5这两种关系的证明。5.偏序关系的证明6.有一个比赛四个人参加，三个人每人说了两句话，其中每人都只说对了一半，问最后真正的排名。免责声明：本站所提供的内容均来源于网友提供或网络搜集，由本站编辑整理，仅供个人研究、交流学习使用，不涉及商业盈利目的。如涉及版权问题，请联系本站管理员予以更改或删除。

文章转载自：大学考研帮手公众号因篇幅限制，仅保留没目录部分1、东北大学613法理学2003-2007考研真题汇编2、东北大学620分析化学2003-2004考研真题汇编3、东北大学622常微分方程1995-2003考研真题汇编4、东北大学626基础英语2002-2004考研真题汇编5、东北大学806政治学99-06、08-10；02-04、06、08-10有答案考研真题汇编6、东北大学811教育学2002-2004；其中2004有答案考研真题汇编7、东北大学816普通物理：普通物理（A）96-04；普通物理（B）97-01、04考研真题汇编8、东北大学817物理化学1995-2004、2006考研真题汇编9、东北大学821材料力学2002-2004、2007考研真题汇编10、东北大学823无机化学2002-2004、2006考研真题汇编11、东北大学828机械工程控制基础1999、2002-2004考研真题汇编12、东北大学829材料科学基础2001-2004、2006考研真题汇编13、东北大学830材料成形力学2003-2004考研真题汇编14、东北大学832冶金物理化学2002、2004考研真题汇编15、东北大学833化工原理2001-2008考研真题汇编16、东北大学834传热学2002-2004、2007、2009-2011考研真题汇编17、东北大学835金属学与热处理2001、2003-2004考研真题汇编18、东北大学839自动控制原理1999-2010；其中2000-2005有答案考研真题汇编19、东北大学841信号与系统2000-2002考研真题汇编20、东北大学843结构力学1997-2000、2002、2004考研真题汇编21、东北大学844测量学2001-2002考研真题汇编22、东北大学852运筹学1999-2004考研真题汇编23、东北大学856财务会计与财务管理2001-2004真题；其中2004有答案考研真题汇编24、东北大学857电子技术基础2000-2004考研真题汇编25、东北大学859综合英语2002-2004考研真题汇编26、东北大学传热学2001-2004考研真题汇编27、东北大学传热学2002-2004、2007、2009-2011考研真题汇编28、东北大学传热学历年真题2002-2004、2007考研真题汇编29、东北大学信号与系统2000-2002、回忆2010-2011考研真题汇编30、东北大学信号与系统历年真题2000-2002、回忆2010-2011考研真题汇编31、东北大学化工原理2001-2008考研真题汇编32、东北大学历年真题诉讼法2003-2007考研真题汇编33、东北大学数据结构00-04及答案，C语言程序设计00-04；00、02-04有答案考研真题汇编34、东北大学有机化学历年真题2004、2006考研真题汇编35、东北大学机械设计2000-2008；2002、2004、2006、2007有答案考研真题汇编36、东北大学机械设计基础2001-2004、2007考研真题汇编37、东北大学材料力学2002-2004、2007考研真题汇编38、东北大学测量学历年真题2001-2002考研真题汇编39、东北大学物理化学历年真题1995-2004、2006考研真题汇编40、东北大学管理学2000-2006、2008、2010、2013-2014考研真题汇编41、东北大学管理学基础2000-2007；2000、2004有答案考研真题汇编42、东北大学结构工程结构力学2000、2002、2004、2013考研真题汇编43、东北大学综合知识二通信原理2000-2002考研真题汇编44、东北大学运筹学1999-2004考研真题汇编45、东北大学金属学与热处理2001、2003-2004、回忆2014考研真题汇编

来源：大学考研帮手公众号1、湖南大学信息与通信工程828信号与系统2008真题2、湖南大学信息与通信工程828信号与系统2006真题3、湖南大学信息与通信工程(828)信号与系统2012年真题4、湖南大学信息与通信工程828信号与系统2007真题5、湖南大学801结构力学2019通关宝典6、湖南大学环境科学与工程811环境毒理学与环境工程微生物综合考试2016真题7、湖南大学控制科学与工程823自动控制原理一2013真题8、湖南大学化学工程与技术832物理化学(工一)2012真题9、湖南大学会计学836中级财务会计学2008真题10、湖南大学中国语言文学715文学理论和写作2016真题11、湖南大学力学(801)结构力学2012年真题12、湖南大学土木工程801结构力学2004真题13、湖南大学化学703有机化学(理)2011真题14、湖南大学化学703有机化学(理)2012真题15、湖南大学化学703有机化学(理)2013真题16、湖南大学化学703有机化学(理)2014真题17、湖南大学化学831物理化学(理)2011真题18、湖南大学化学831物理化学(理)2012真题19、湖南大学化学831物理化学(理)2013真题20、湖南大学化学831物理化学(理)2014真题21、湖南大学其它(836)日本语言文学专业基础2012年真题22、湖南大学文物与博物馆(348)文博综合2012年真题23、湖南大学工业设计工程(819)专业设计A2012年真题24、湖南大学交通运输工程(808)土力学2012年真题25、湖南大学计算机科学与技术866数据结构2011真题答案26、湖南大学计算机科学与技术866数据结构2014真题答案27、湖南大学应用经济学848经济学综合(含微观经济学、宏观经济学)2014真题答案28、湖南大学应用经济学848经济学综合(含微观经济学、宏观经济学)2013真题答案29、湖南大学应用经济学848经济学综合(含微观经济学、宏观经济学)2012真题答案30、湖南大学应用经济学848经济学综合(含微观经济学、宏观经济学)2009真题31、湖南大学应用经济学848经济学综合(含微观经济学、宏观经济学)2012真题32、湖南大学(440)新闻与传播专业基础初试笔记33、湖南大学哲学843中国哲学史2007真题34、湖南大学公共管理856公共行政学2007真题35、湖南大学新闻传播学714新闻传播史论2007真题36、湖南大学中国史722中国史2016真题37、湖南大学力学805机械原理2014真题38、湖南大学机械工程807机械设计基础2012真题39、湖南大学力学812材料力学2011真题40、湖南大学电子科学与技术822电子技术基础一2011真题41、湖南大学计算机技术829计算机程序设计2013真题42、湖南大学计算机技术829计算机程序设计2012真题43、湖南大学计算机技术829计算机程序设计2014真题44、湖南大学土木工程801结构力学2011真题45、湖南大学动力工程805机械原理2012真题46、湖南大学车辆工程805机械原理2012真题47、湖南大学材料科学与工程805机械原理2014真题48、湖南大学车辆工程805机械原理2014真题49、湖南大学动力工程807机械设计基础2011真题50、湖南大学动力工程807机械设计基础2012真题51、湖南大学车辆工程807机械设计基础2012真题52、湖南大学车辆工程807机械设计基础2011真题53、湖南大学日语语言文学707基础日语2006真题54、湖南大学日语语言文学707基础日语2007真题55、湖南大学外国语言文学609基础英语2005真题56、湖南大学外国语言文学214法语2008真题57、湖南大学外国语言文学(835)英语语言文学专业基础2012年真题58、湖南大学化学工程与技术832物理化学(工一)2011真题59、湖南大学统计学846经济学基础(含宏微观经济学、计量经济学)2013真题60、湖南大学统计学846经济学基础(含宏微观经济学、计量经济学)2016真题61、湖南大学数学610数学分析0真题62、湖南大学公共管理(844)教育学2012年真题63、湖南大学车辆工程812材料力学2014真题64、湖南大学机械工程812材料力学2015真题65、湖南大学材料科学与工程812材料力学2015真题66、湖南大学动力工程812材料力学2015真题67、湖南大学车辆工程812材料力学2015真题68、湖南大学机械工程812材料力学2016真题69、湖南大学车辆工程812材料力学2016真题70、湖南大学电气工程821电路一2014真题71、湖南大学软件工程829计算机程序设计2012真题72、湖南大学软件工程829计算机程序设计2014真题73、湖南大学应用经济学405经济学综合2007真题74、湖南大学其它850统计学2016真题75、湖南大学材料工程839材料科学基础二2015真题76、湖南大学翻译448汉语写作与百科知识2014真题77、湖南大学翻译448汉语写作与百科知识2016真题78、湖南大学工商管理840管理学原理2017真题79、湖南大学生物学712细胞生物学2014真题80、湖南大学公共管理710管理学原理2017真题81、湖南大学应用统计432统计学2013真题82、湖南大学应用统计432统计学2014真题83、湖南大学应用统计432统计学2015真题84、湖南大学应用统计432统计学2016真题85、湖南大学中国史722中国史2017真题86、湖南大学公共管理856公共行政学2016真题87、湖南大学工业设计工程337工业设计工程2015真题88、湖南大学数学610数学分析2011真题89、湖南大学中国语言文学715文学理论和写作2011真题90、湖南大学新闻与传播440新闻与传播专业基础2014真题91、湖南大学新闻传播学854新闻传播实务2013真题92、湖南大学材料科学与工程838材料科学基础2016真题93、湖南大学材料工程839材料科学基础二2011真题94、湖南大学材料科学与工程838材料科学基础2011真题95、湖南大学应用经济学846经济学基础(含宏微观经济学、计量经济学)2016真题96、湖南大学法学847专业综合二(含民法、刑法)2013真题97、湖南大学法学847专业综合二(含民法、刑法)2016真题98、湖南大学工商管理849财务会计学2011真题

【导语】全套资料已上线，现分享给大家。本内容全面丰富，共分为4部分内容，助力全面备考。首先通过历年考研试题进行汇编，并配有考研试题视频的讲解，能够更好地帮助广大考生朋友有针对性、有重点的掌握专业课考试的侧重考点、核心知识点，总结命题规律和特点，做到知己知彼、针对性备考；教材是学习的基础，因此结合指定的参考教材的重难点笔记、配套练习题、课后练习题答案等分析等来帮助全方位地吃透、理解透教材，并配置了名师高清视频讲解，帮助进一步记忆和理解掌握考点难点；最后通过出题规律总结汇编了考研题库，含有部分兄弟院校相近试题，帮助考生朋友检验学习效果，重点突破，查缺补漏。资料来源：学爽学习网（1）历年考研汇编南京航空航天大学计算机科学与技术学院829计算机专业基础历年考题汇编（2）指定教材笔记和课后习题详解严蔚敏《数据结构》（C语言版）笔记和习题含考研详解汤子瀛《计算机操作系统》（第3版）笔记和课后习题含考研详解说明：南京航空航天大学“829计算机专业基础”的指定教材为：①《计算机组成与系统结构》（第2版），（袁春风，清华大学出版社，2015年）；②《计算机组成与设计 硬件/软件接口》（第5版），（王党辉译，机械工业出版社，2015年）；③《计算机操作系统》（第3版），（汤子瀛，西安电子科技大学出版社，2007年）；④《数据结构》（C语言版），（严蔚敏编著，清华大学出版社，2007年）。（3）指定教材视频讲解【36小时高清视频】严蔚敏《数据结构》（C语言版）【教材精讲＋考研解析】讲义与视频课程【36小时高清视频】（4）指定教材配套题库严蔚敏《数据结构》（C语言版）配套题库【名校考研＋章节题库＋模拟试题】汤子瀛《计算机操作系统》（第3版）配套题库【名校考研＋课后习题＋章节题库＋模拟试题】（5）考研题库2021年数据结构考研题库【名校考研＋章节题库＋模拟试题】2021年操作系统考研题库【名校考研＋经典教材课后习题＋章节题库＋模拟试题】（6）全国名校考题全国名校数据结构考题汇编全国名校计算机操作系统考研汇编考研目录（第一部分）2014年南京航空航天大学829计算机专业基础考题2015年南京航空航天大学829计算机专业基础考题2016年南京航空航天大学829计算机专业基础考题2017年南京航空航天大学829计算机专业基础考题2018年南京航空航天大学829计算机专业基础考题试读（部分内容）更多考研全套、资格考试、大学课程等学习考试干货内容分享来源于学爽学习网，转载请注明~