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

《数据结构考研课件-大连海事大学ky0-绪论.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

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

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

4、存在的关系。亦可表示为：S＝（D,R）或B=（K,R）元素有限集关系有限集Q2：学习数据结构有什么用？答：计算机内的数值运算依靠方程式，而非数值运算（如表、树、图等）则要依靠数据结构。这是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科。程序设计实质＝好算法＋好结构同样的数据对象，用不同的数据结构来表示，运算效率可能有明显的差异。Q3：数据结构涵盖的内容？一些你应该知道的定义数据类型：是一个值的集合和定义在该值上的一组操作的总称。抽象数据类型：由用户定义，用以

5、表示应用问题的数据模型。它由基本的数据类型构成，并包括一组相关的服务（或称操作）C语言中的数据类型charintfloatdoublevoid字符型整型浮点型双精度型无值抽象数据类型可以用以下的三元组来表示：ADT=（D，S，P）数据对象D上的关系集P上的操作集数据类型：Data_Structure=（D,S）算法效率的度量Q1.什么是算法？如何评判一个算法的好坏？Q2.时间复杂度和空间复杂度如何表示？Q3.计算举例讨论：程序设计实质＝好算法＋好结构答：算法是解决某一特定类型问题的有限运算序列。

6、是一系列输入转换为输出的计算步骤。常用时间复杂度来衡量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)/*3n+

7、24nforn2*/3n+3=O(n)/*3n+34nforn3*/100n+6=O(n)/*100n+6101nforn10*/10n2+4n+2=O(n2)/*10n2+4n+211n2forn5*/6*2n+n2=O(2n)/*6*2n+n27*2nforn4*/例：例：分析以下程序段的时间复杂度。i=1;①while(i<=n)i=i*2;②该算法的运行时间由程序中所有语句的频度（即该语句重复执行的次数）之和构成。解：分析：显然，语句①的频度是1。设语句2的频度是f(

8、n)，则有：即f(n)≤log2n，取最大值f(n)=log2n所以该程序段的时间复杂度T(n)=1+f(n)=1+log2n=O(log2n)算法的时间复杂度是由嵌套最深层语句的频度决定的。真题回顾：2013真题：第一部分判断时间和空间复杂度-间接考察小测试：递归运算longintfact(n)intn;{longf;if(n>1)f=n*fact(n-1);elsef=1;return(f);}main(){intn;longy;n=5;y=fact(n);printf(“%d,%ld”