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

1、第一课时第一课时 概述：总体知识点架构概述：总体知识点架构制作人：荣誉参考书目参考书目数据结构数据结构( (严蔚敏严蔚敏 c c语言版语言版) )第一课时：概论 2 算法效率、时间、空间等第二课时：线性表 1第三课时：栈第四课时：队列第五课时：串第六课时：数组第七课时：广义表 2第八课时：二叉树 5 线索二叉树、二叉树遍历 平衡二叉树、哈夫曼树第九课时：图 5 最小生成树、拓扑排序、aoe网 第十课时：查找 1 哈希散列存储第十一课时：内部排序 4 归并排序 置换选择排序 排序的对比第一部分：判断题第一部分：判断题20 x 120 x 12013年真题第一课时：概论第二课时：线性表 第三课时：

2、栈第四课时：队列 第五课时：串第六课时：数组 1 二维数组第七课时：广义表 1 第八课时：二叉树 4 平衡二叉树 b_树 完成二叉树 遍历第九课时：图 1 堆第十课时：查找 1 折半查找第十一课时：内部排序 1 综合比较第二部分：选择题第二部分：选择题10 x 210 x 2第一课时：概论第二课时：线性表 1 编程第三课时：栈 2 进出栈、递归第四课时：队列第五课时：串 1第六课时：数组第七课时：广义表树第八课时：二叉树 2 平衡二叉树 证明第九课时：图 第十课时：查找 1 哈希表第十一课时：内部排序 1 综合比较 第三部分：简答题第三部分：简答题初试初试-数据结构：数据结构：（1）说是数据结

3、构，实际考的是数据结构和算法，但算法比较少。（2）只掌握卷子题目是不行的，变换题型就抓瞎了；但不掌握真题是万万不行的，每年题型基本不变。（3）要根据真题考察点，复习教材的知识点，夯实基础，提高真题的理解能力。（4）有时间的话可以看看王道或天勤相应知识点的总结，可以提升自己并且应对题型变化。复试数据库：等初试过了再复习完全来得及，本人认为数据库比较难，并且去年题型有大变化。q1q1：什么是数据结构？：什么是数据结构？答答: : 是相互之间存在一种或多种特定关系的数据元素的集合，相互之间存在一种或多种特定关系的数据元素的集合，表示为：表示为：（数值或非数值数值或非数值）data_structure

4、=（d, s）或：是指同一数据元素类中各元素之间存在的关系。或：是指同一数据元素类中各元素之间存在的关系。亦可表示为：亦可表示为：s（d, r） 或或 b=（k, r）元素有限集元素有限集关系有限集关系有限集q2q2：学习数据结构有什么用？：学习数据结构有什么用？答：答：计算机内的数值运算依靠方程式，而计算机内的数值运算依靠方程式，而非数值运非数值运算算（如表、树、图等）则要依靠数据结构。（如表、树、图等）则要依靠数据结构。 这是一门研究这是一门研究非数值计算非数值计算的程序设计问题中计算机的操的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科。作对象以及它们之间的关系和操作等

5、等的学科。程序设计实质好算法好结构程序设计实质好算法好结构同样的数据对象，用不同的数据结构来表示，同样的数据对象，用不同的数据结构来表示，运算效率可能有明显的差异。运算效率可能有明显的差异。q3q3：数据结构涵盖的内容？：数据结构涵盖的内容？一些你应该知道的定义一些你应该知道的定义数据类型：是一个值的集合和定义在该值上 的一组操作的总称。抽象数据类型：由用户定义，用以表示应用问题的数据模型。它由基本的数据类型构成，并包括一组相关的服务（或称操作）抽象数据类型抽象数据类型可以用以下的三元组来表示：可以用以下的三元组来表示： adt = （d，s，p） 数据对象数据对象 d上的关系集上的关系集 p

6、上的操作集上的操作集 数据类型：数据类型：data_structure=（d, s）算法效率的度量算法效率的度量q1. q1. 什么是算法？如何评判一个算法的好坏？什么是算法？如何评判一个算法的好坏？q2. q2. 时间复杂度和空间复杂度如何表示？时间复杂度和空间复杂度如何表示？q3. q3. 计算举例计算举例讨论：讨论：程序设计实质好算法好结构程序设计实质好算法好结构答：算法是解决某一特定类型问题的有限运算序答：算法是解决某一特定类型问题的有限运算序列。是一系列输入转换为输出的计算步骤。列。是一系列输入转换为输出的计算步骤。常用常用时间复杂度时间复杂度来衡量来衡量1. 什么是算法？如何评判一

7、个算法的好坏？什么是算法？如何评判一个算法的好坏？算法有算法有5个基本特性：个基本特性：算法评价有算法评价有4个指标：个指标：有穷性、确定性、可行性、输入和输出有穷性、确定性、可行性、输入和输出运行时间、占用空间、正确性和简单性运行时间、占用空间、正确性和简单性常用常用空间复杂度空间复杂度来衡量来衡量时间复杂度时间复杂度t(n)t(n)按数量级递增顺序为：按数量级递增顺序为： 注注1 o（）为渐近符号（）为渐近符号。注注2 空间复杂度空间复杂度s(n)按数量级递增顺序也与按数量级递增顺序也与上表类同。上表类同。复杂度高复杂度高复杂度低复杂度低渐进符号渐进符号（oo）的定义：）的定义：当且仅当存

8、在一个正的常当且仅当存在一个正的常数数 c c，使得对所有的，使得对所有的 n n n n0 0 ，有，有 f(n) f(n) c cg(n)g(n)，则则f(n) = f(n) = o o(g(n)(g(n) 3n+2=o(n) /3n+2=o(n) /* * 3n+2 3n+2 4n for n4n for n 2 2 * */ /3n+3=o(n) /3n+3=o(n) /* * 3n+3 3n+3 4n for n4n for n 3 3 * */ /100n+6=o(n)100n+6=o(n) / /* * 100n+6 100n+6 101n for n101n for n 10

9、10 * */ /10n10n2 2+4n+2=o(n+4n+2=o(n2 2) /) /* * 10n 10n2 2+4n+2+4n+2 11n11n2 2 for n for n 5 5 * */ /6 6* *2 2n n+n+n2 2=o(2=o(2n n) ) / /* * 6 6* *2 2n n+n+n2 2 7 7* *2 2n n for n for n 4 4 * */ /例：例：例：例：分析以下程序段的时间复杂度。分析以下程序段的时间复杂度。i=1; i=1; while(i=n)while(i1)f=nif(n1)f=n* *fact(n-1);fact(n-1); else f=1; else f=1;return(f);return(f); m