数据结构学位复习课-上海交通大学.pdf
需积分: 26 119 浏览量
2019-05-09
09:09:24
上传
评论
收藏 1.71MB PDF 举报
复习课(1)
主要内容：
1.第一部分 基本概念
2.第二部分 线性表、栈、队列
第一部分：数据结构与算法的基本概念
考核内容：
算法、算法正确性、复杂性；
算法的时间与空间复杂性级别；
数据类型、数据结构和表示、实现；
抽象数据类型的说明、高级语言对抽象数据类型的支持
考核要求：
理解算法、算法正确性、复杂性的概念；
了解算法的时间与空间复杂性级别；
重点掌握数据类型、数据结构和表示、实现的概念；
掌握抽象数据类型的说明、高级语言对抽象数据类型的支持。
算法：对特定问题求解步骤的一种描述，是指令的有序序列
算法的五个特性：有穷性、确定性、可行性、输入、输出
算法设计的要求：时间复杂度，空间复杂度
时间复杂度：算法执行时间随规模增长而增长的趋势
T(n)=O(f(n))
f(n)算法规模，T(n)称算法复杂度
估算办法：以算法中重复执行的次数作
为算法时间复杂度的依据。
三种最常见时间复杂度：
O(1) 常量级 O(n) 线性级
O(n2) 平方级
算法的空间复杂度
S(n)=O(f(n))
算法执行过程中所需的最大空间
估算方法：输入数据所占空间+
程序所占空间+
辅助变量所占空间
基本概念和术语
数据(Data)：
数据元素(Data Element)：
数据的基本单位，计算机中通常作为一个整体来考虑，如一棵树中的一个结点、一个图中的一个结点。
一个数据元素可以有若干个数据项(Data Item)组成。
数据对象(Data Object)：性质相同的数据元素的集合
数据结构：数据元素之间的关系——结构
四种基本结构
集合 线性结构 树形结构 图状结构/网状结构
剩余46页未读，继续阅读
资源评论
sjz1983
- 粉丝: 0
- 资源: 2
