计算机二级-数据结构与算法

D={ 1 , 2 , 3 } R={ (1,2) , (2,3) , (3,2) , (1,3) }
线性表
A．线性结构 栈
队 1．数据的逻辑结构
数 据
树形结构 B．非线性结构
结
构
图形结构
的
三 个
2、数据的存储结构 A 顺序存储
方 面
(亦称物理结构) B 链式存储
3、数据的运算：检索、排序、插入、删除、修改等。
线性结构
A , B , C , ·······，X ,Y , Z
线性表——结点间是以线性关系联结
学号
学生成绩表
姓名 张卓 刘忠赏 胡孝臣
成绩 100 95 86
数据结构可描述为 B=（D，R）
线性表
A．线性结构 栈
队 1．数据的逻辑结构
数 据
树形结构 B．非线性结构
结百度文库
构
图形结构
的
三 个
2、数据的存储结构 A 顺序存储
方 面
B 链式存储
3、数据的运算：检索、排序、插入、删除、修改等。
树形结构
全校学生档案管理的组织方式 计算机程序管理系统也是典型的树形结构
A
D
B
C
E
F
G
H
A
B
C
D
E
F
G
H
树形结构 —— 结点间具有分层次的连接关系
线性表
A．线性结构 栈
队 1．数据的逻辑结构
数 据
树形结构 B．非线性结构
结
构
图形结构
列举法 归纳法 递推 递归 减半递推技术 回溯法
1.2 算法复杂度
1.2.1 时间复杂度
所谓算法的时间复杂度，是指执行算法所需要的计 算工作量。
可以用算法在执行过程中所需要的基本运算的执行 次数来度量算法的工作量。
1.2.2 算法的空间复杂度
一般是指执行这个算法所需要的内存空间 一个算法所占用的存储空间包括算法程序所占的
1.1.2 算法的基本要素
1、对数据的运算和操作
算术运算 逻辑运算 关系运算 数据传输
2、算法的控制结构
算法中各操作之间的执行顺序 描述算法的工具通常有传统流程图、N-S结构化流程图、
算法描述语言等 一个算法一般可以用顺序、选择、循环三种基本机构组
合而成。
1.1.3 算法设计基本方法
存储地址 存储内容
元素1
Lo
顺
元素2
序
Lo+m
存
……..
储
元素i
Lo+(i-1)*m
……..
Lo+（n-1)*m 元素n
每个元素所占用 的存储单元个数
Loc(a)=Lo+（i-1)*m
存储内容
元素1
顺序存储结构常用于线性 数据结构，将逻辑上相邻 的数据元素存储在物理上 相邻的存储单元里。
元素2 …….. 元素i ……..
顺序存储结构的三个弱点：
元素n
1.作插入或删除操作时，需移动大量元数。
2.长度变化较大时，需按最大空间分配。
3.表的容量难以扩充。
线性表
A．线性结构 栈
队 1．数据的逻辑结构
数 据
树形结构 B．非线性结构
结
构
图形结构
的
三 个
2、数据的存储结构 A 顺序存储
方 面
(亦称物理结构) B 链式存储
3、数据的运算：检索、排序、插入、删除、修改等。
数据结构是一门研究数据组织、 存储和运算的一般方法的学科。
对数据结构中的节点进行 操作处理
(插入、删除、修改、查找、排序)
数据元素(Data Element)
数据元素是数据的基本单位，即数据 集合中的个体。
有时一个数据元素可由若干数据项 (Data Item)组成。数据项是数据的最小 单位。
数据元素亦称节点或记录。
h
链式存储
1345
元素1 1400 元素2 1536 元素3 1346 元素4 ∧
每个节点都由两部分组成：数据域和指针域。 数据域存放元素本身的数据， 指针域存放指针。
数据结构是一门研究数据组织、 存储和运算的一般方法的学科。
整数(能1,输2)入、到实计数算(1机.1中,1.2) 并能字被符计串算(B机ei程ji序ng处)、理的 符图形号、的声集音合。
1.2.2 基本概念和术语
数据结构是一门研究数据组织、 存储和运算的一般方法的学科。
计算机管理图书问题 在图书馆里有各种卡片：有按书名编排的、
的
三 个
2、数据的存储结构 A 顺序存储
方 面
(亦称物理结构) B 链式存储
3、数据的运算：检索、排序、插入、删除、修改等。
图形结构——节点间的连结是任意的
1
4
2
3
1
2
3
D={ 1 , 2 , 3 , 4} R={(1,2) , (1,3) , (1,4) , (2,3)
(3,4) , (2,4) }
数据结构是一门研究数据组织、 存储和运算的一般方法的学科。
如何将0,1,2,3,4,5,6,7,8,9这10个数存放在 计算机中能最快地达到你所需要的目的？ 目的不同，最佳的存储方方法就不同。
从大到小排列：9,8,7,6,5,4,3,2,1,0 输出偶数：0,2,4,6,8,1,3,5,7,9
1.2.2 基本概念和术语
空间、输入的初始数据所占的存储空间以及某种 数据结构所需要的附加存储空间
1.2 数据结构(0.96%)
数据结构的定义 数据的逻辑结构和存储结构 数据结构的图形表示 线性结构与非线性结构
1.2.2 基本概念和术语
数据结构是一门研究数据组织、 存储和运算的一般方法的学科。
1.2.2 基本概念和术语
有按作者编排的、有按分类编排 如何将查询图书的这些信息存入计算机中 既要考虑查询时间短，又要考虑节省空间
1.2.2 基本概念和术语
数据结构是一门研究数据组织、 存储和运算的一般方法的学科。
最简单的办法之一是建立一张表， 每一本书的信息在表中占一行，如
数1.2据.2元基素本在概念和术语 计算机中的表示
数据结构可描述为 B=（D，R） 有限个数据元素的集合
有限个节点间关系的集合
数据结构可描述为 B=（D，R）
线性表
A．线性结构 栈
队 1．数据的逻辑结构
数 据
树形结构 B．非线性结构
结
构
图形结构
的
三 个
2、数据的存储（物 A 顺序存储
方
理）结构
面
B 链式存储
3、数据的运算：检索、排序、插入、删除、修改等。
1. 基本数据结构与算法(10.22%)
1.1 算法(0.82%)
1.1.1 算法(algorithm)基本概念 定义：算法是指解题方案的准确而完整的描
述。算法不等于程序，不等于计算方法。只能说 程序是算法的一种描述，所以，程序不可能优于 算法的设计。算法是指一系列解决问题的清晰指 令。
特征：算法具有可行性、确定性、有穷性、 输入和输出（拥有足够的情报）等５个重要特 性。