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

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

2、 1 二维数组 第七课时：广义表 1 第八课时：二叉树 4 平衡二叉树 B_树 完成二叉树 遍历 第九课时：图 1 堆 第十课时：查找 1 折半查找 第十一课时：内部排序 1 综合比较,第二部分：选择题10 X 2,第一课时：概论 第二课时：线性表 1 编程 第三课时：栈 2 进出栈、递归 第四课时：队列 第五课时：串 1 第六课时：数组 第七课时：广义表树 第八课时：二叉树 2 平衡二叉树 证明 第九课时：图 第十课时：查找 1 哈希表 第十一课时：内部排序 1 综合比较,第三部分：简答题,初试-数据结构：,（1）说是数据结构，实际考的是数据结构和算法，但算法比较少。 （2）只掌握卷子题目是

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

4、习数据结构有什么用？,答：计算机内的数值运算依靠方程式，而非数值运算（如表、树、图等）则要依靠数据结构。 这是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科。,程序设计实质好算法好结构,同样的数据对象，用不同的数据结构来表示，运算效率可能有明显的差异。,Q3：数据结构涵盖的内容？,一些你应该知道的定义,数据类型：是一个值的集合和定义在该值上 的一组操作的总称。,抽象数据类型：由用户定义，用以表示应用问题的数据模型。它由基本的数据类型构成，并包括一组相关的服务（或称操作）,C语言中的数据类型 char int float double void 字符型 整型

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

6、单性,常用空间复杂度来衡量,时间复杂度T(n)按数量级递增顺序为：,注1 O（）为渐近符号。 注2 空间复杂度S(n)按数量级递增顺序也与上表类同。,复杂度高,复杂度低,渐进符号（O）的定义：当且仅当存在一个正的常数 C，使得对所有的 n n0 ，有 f(n) Cg(n)，则f(n) = O(g(n),3n+2=O(n) /* 3n+24n for n2 */ 3n+3=O(n) /* 3n+34n for n3 */ 100n+6=O(n) /* 100n+6101n for n10 */ 10n2+4n+2=O(n2) /* 10n2+4n+211n2 for n5 */ 6*2n+n2=

7、O(2n) /* 6*2n+n2 7*2n for n4 */,例：,例：分析以下程序段的时间复杂度。,i=1; while(i=n) i=i*2; ,该算法的运行时间由程序中所有语句的频度（即该语句重复执行的次数）之和构成。,解：,分析：显然，语句的频度是1。设语句2的频度是f(n)，则有：,即f(n)log2n，取最大值f(n)=log2n,所以该程序段的时间复杂度T(n)=1+f(n)=1+ log2n= O( log2n),算法的时间复杂度是由嵌套最深层语句的频度决定的。,真题回顾：,2013真题：第一部分 判断,时间和空间复杂度-间接考察,小测试：递归运算,long int fact(n) int n; long f; if(n1)f=n*fact(n-1); else f=