二级公共基础 第1讲 _算法与数据结构(74+41)

计算机基础

●算法与数据结构基础 ●程序设计基础 ●软件工程基础 ●数据库设计基础

计算机基础

主要知识点算法:算法的基本概念、算法复杂度 数据结构的基本概念：什么是数据结构、 数据结构的图形表 示、 线性结构与非线性结构 线性表及其顺序存储结构：线性表的基本概念、 顺序存储结 构、插入运算、删除运算 栈和队列：栈及其基本运算、队列及其基本运算 线性链表：基本概念、基本运算、循环链表及其基本运算 树与二叉树：树的基本概念、二叉树及其基本性质、 二叉树 的存储结构、二叉树的遍历 查找技术： 顺序查找、二分法查找 排序技术：交换类排序法、 插入类排序法、选择类排序法

计算机基础

1.1 算法

计算机基础

1.1.1 算法的基本概念算法是解题方案的准确而完整的描述，它不等于程序，也不 等计算方法。 1.算法的基本特征 可行性(effectiveness) 确定性(definiteness) 有穷性(finiteness) 拥有足够的情报

2.算法的基本要素 算法中对数据的运算和操作

算术运算:包括加、减、乘、除等) 逻辑运算:包括“与”、“或”、“非”等运算) 关系运算:包括“大于”、“小于”、“等于”、“不等于”等) 数据传输:包括赋值、输入、输出等操作

算法的控制结构

计算机基础

1.1.1 算法的基本概念3.算法设计的基本方法 列举法 归纳法 递推 递归 减半递推技术 回溯法

计算机基础

1.1.2 算法的复杂度算法复杂度：时间复杂度、空间复杂度 1.算法的时间复杂度 执行算法所需要的计算工作量 与下列因素有关： 书写算法的程序设计语言 编译产生的机器语言，代码质量

机器执行指令的速度 问题的规模

计算机基础

1.1.2 算法的复杂度问题的规模函数算法的工作量=f(n)

算法中基本操作重复执行的频率T(n),是问题规模 n的某个函数f(n),记作：T(n)=O(f(n)) 记号“O”读作“大O”。表示随问题规模n的增加，算法 执行时间的增长率和f(n)相应增加。

常见算法复杂度： O(1):常数阶 O(n):作线性阶 O(n2):平方阶 O(n3):立方阶 O(logn):对数阶 O(2n):指数阶7

计算机基础

1.1.2 算法的复杂度n×n矩阵相乘算法：

时间复杂度为O(n3)。8

计算机基础

1.1.2 算法的复杂度分析算法的工作量两种方法： 平均性态 最坏情况复杂性

计算机基础

1.1.2 算法的复杂度2.算法的空间复杂度 算法执行过程中所需的最大存储空间 存储量包括以下三部分 算法程序所占的空间 输入的初始数据所占的存储空间 算法执行过程中所要的额外空间

算法空间复杂度可定义为： S(n)=O(f(n)) 原地工作(in place)的算法：记作O(1) 压缩存储技术10

计算机基础

1.2数据结构的基本概念

计算机基础

1.2.1 什么是数据结

构1.数据结构研究的主要内容 数据的逻辑结构 数据的存储结构 对各种数据结构进行的运算

2.研究数据结构目的 提高数据处理的速度 尽量节省在数据处理过程中所占用的计算机存 储空间

计算机基础

1.2.1 什么是数据结构1.数据结构研究的主要内容 数据的逻辑结构 数据的存储结构 对各种数据结构进行的运算

2.研究数据结构目的 提高数据处理的速度 尽量节省在数据处理过程中所占用的计算机存 储空间

计算机基础

1.2.1 什么是数据结构线性表 A.线性结构 1.数据的逻辑结构 数 据 结 构 的 三 个 方 面 B.非线性结构 栈 队 树形结构 图形结构 2、数据的存储结构 A 顺序存储 B 链式存储 3、数据的运算：检索、排序、插入、删除、修改等。

计算机基础

1.2.1 什么是数据结构3.数据结构的定义 相互有关联的数据元素的集合 数据元素之间的关系可以用前后件关系来描述 一个数据结构应包含以下两方面信息： 表示数据元素的信息 表示各数据元素之间的前后件关系

计算机基础

1.2.1 什么是数据结构4.数据的逻辑结构 对数据元素之间的逻辑关系的描述 只抽象地反映数据元素之间的逻辑关系，与计 算机中的存储无关 两个要素： 数据元素的集合，通常记为D; 前后件关系，通常记为R

一个数据结构B可以表示为：

B=(D,R)16