数据结构考研课件大连海事大学ky绪论

第一课时概述：总体知识点架构制作人：荣誉参考书目数据结构(严蔚敏c语言版)第一课时：概论

2算法效率、时间、空间等第二课时：线性表

1第三课时：栈第四课时：队列第五课时：串第六课时：数组第七课时：广义表

2第八课时：二叉树

5线索二叉树、二叉树遍历平衡二叉

树、哈夫曼树第九课时：图

5最小生成树、拓扑排序、AOE网第十课时：查找

1哈希散列存储第十一课时：内部排序

4归并排序置换选择排序排序的对比第一部分：判断题20X12013年真题第一课时：概论第二课时：线性表

第三课时：栈第四课时：队列

1循环队列第五课时：串第六课时：数组

1二维数组第七课时：广义表

1

第八课时：二叉树

4平衡二叉树B_树完成二叉树遍历第九课时：图

1堆第十课时：查找

1折半查找第十一课时：内部排序

1综合比较第二部分：选择题10X2第一课时：概论第二课时：线性表

1编程第三课时：栈

2进出栈、递归第四课时：队列第五课时：串1第六课时：数组第七课时：广义表树第八课时：二叉树

2平衡二叉树证明第九课时：图

第十课时：查找

1哈希表第十一课时：内部排序

1综合比较

第三部分：简答题初试--数据结构：（1）说是数据结构，实际考的是数据结构和算法，但算法比较少。（2）只掌握卷子题目是不行的，变换题型就抓瞎了；但不掌握真题是万万不行的，每年题型基本不变。（3）要根据真题考察点，复习教材的知识点，夯实基础，提高真题的理解能力。（4）有时间的话可以看看王道或天勤相应知识点的总结，可以提升自己并且应对题型变化。复试数据库：等初试过了再复习完全来得及，本人认为数据库比较难，并且去年题型有大变化。Q1：什么是数据结构？答:是相互之间存在一种或多种特定关系的数据元素的集合，表示为：（数值或非数值）Data_Structure=（D,S）或：是指同一数据元素类中各元素之间存在的关系。亦可表示为：S＝（D,R）或B=（K,R）元素有限集关系有限集Q2：学习数据结构有什么用？答：计算机内的数值运算依靠方程式，而非数值运算（如表、树、图等）则要依靠数据结构。

这是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科。程序设计实质＝好算法＋好结构同样的数据对象，用不同的数据结构来表示，运算效率可能有明显的差异。Q3：数据结构涵盖的内容？一些你应该知道的定义数据类型：是一个值的集合和定义在该值上的一组操作的总称。抽象数据类型：由用户定义，用以表示应用问题的数据模型。它由基本的数据类型构成，并包括一组相关的服务（或称操作）C语言中的数据类型

charintfloatdoublevoid字符型整型浮点型双精度型无值抽象数据类型可以用以下的三元组来表示：

ADT=（D，S，P）数据对象D上的关系集P上的操作集数据类型：Data_Structure=（D,S）算法效率的度量Q1.什么是算法？如何评判一个算法的好坏？Q2.时间复杂度和空间复杂度如何表示？Q3.计算举例讨论：程序设计实质＝好算法＋好结构答：算法是解决某一特定类型问题的有限运算序列。是一系列输入转换为输出的计算步骤。常用时间复杂度来衡量1.什么是算法？如何评判一个算法的好坏？算法有5个基本特性：算法评价有4个指标：有穷性、确定性、可行性、输入和输出运行时间、占用空间、正确性和简单性常用空间复杂度来衡量时间复杂度T(n)按数量级递增顺序为：

注1O（）为渐近符号。注2空间复杂度S(n)按数量级递增顺序也与上表类同。复杂度高复杂度低渐进于符号（O龙）的休定义敲：当且吴仅当痒存在点一个和正的梨常数C，使拣得对贷所有盛的n耍熄n0，有f(他n)Cg(晕n)，则f(街n)莲=O(g沿(n替))3n搬+2默=O摘(n志)析/*宿3榴n+父24暴nfo将r北n止2倍*/3n辫+3浊=O浙(n俭)脊/*段3夏n+遥34依nfo岩r拥n以3扮*/10遮0n图+6由=O感(n客)唐/壤*夹10迈0n悲+61温01免nfo费r雨n愈10防*堡/10间n2+4混n+番2=障O(面n2)箭/密*释10腔n2+4杆n+句21描1n2fo欢r查n先5端*/6*会2n+n2=O舅(2n)诱/牺*具6*纳2n+n27畏*2nfo罩r乳n蝇4贫*/例：例：分析菊以下宇程序竖段的但时间窄复杂斤度。i=骑1;住①wh就il蔑e(毙i<塑=n缠)i=i*2烂;筐②该算却法的财运行爷时间购由程幕序中旗所有歉语句令的频度（即幻玉该语艘句重甜复执村行的驳次数婚）之和构成窃。解：分析讽：显然盖，语芽句①剃的频毒度是科1。身设语撞句2届的频梨度是禽f(监n)框，则免有：即f鞭(n前)≤轰lo销g2n，取最父大值f(港n)程=l题og2n所以互该程腔序段忌的时捏间复组杂度漠T(味n)贵=1后+f泪(n血)=1+祥l拾og2n=O(示l梦og2n)算法叨的时践间复膨杂度疑是由嵌套畅最深涌层语句沿的频陷度决最定的抹。真题袍回顾平：20格13膊真题讲：第墨一部忽分附判断时间驴和空薄间复千杂度兴-间盆接考和察小测洪试：递归左运算lo辣ng越i吸nt沿f烧ac名t(胁n)in富t暑n;{l代on扩g丽f;if输(n撕>1齿)f可=n跟*f影ac努t(积n-撑1)速;el期se积f歇=1蓬;re乘tu择rn兵(f解);}ma傅in苦(){i上nt求n逃;lo挽ng夹y此;n