1二级公共基础知识第一章 数据结构基础2内容提要 • 算法 : 算法的基本概念、算法复杂度• 数据结构的基本概念：什么是数据结构、 数据结构的图形表示、 线性结构与非线性结构• 线性表及其顺序存储结构：线性表的基本概念、 顺序存储结构、插入运算、删除运算• 栈和队列：栈及其基本运算、队列及其基本运算• 线性链表：基本概念、基本运算、循环链表及其基本运算• 树与二叉树：树的基本概念、二叉树及其基本性质、 二叉树的存储结构、二叉树的遍历• 查找技术： 顺序查找、二分法查找• 排序技术：交换类排序法、 插入类排序法、选择类排序法31.1 算法41.1.1 算法的基本概念•算法是解题方案的准确而完整的描述，它不等于程序，也不等计算方法。•1 ．算法的基本特征– 可行性 (effectiveness)– 确定性 (definiteness)– 有穷性 (finiteness)– 拥有足够的情报•2 ．算法的基本要素– 算法中对数据的运算和操作• 算术运算 : 包括加、减、乘、除等）• 逻辑运算 : 包括“与”、“或”、“非”等运算）• 关系运算 : 包括“大于”、“小于”、“等于”、“不等于”等）• 数据传输 : 包括赋值、输入、输出等操作– 算法的控制结构51.1.1 算法的基本概念• 3 ．算法设计的基本方法– 列举法– 归纳法– 递推– 递归– 减半递推技术– 回溯法61.1.2 算法复杂度• 算法复杂度：时间复杂度、空间复杂度• 1 ．算法的时间复杂度– 执行算法所需要的计算工作量– 与下列因素有关：• 书写算法的程序设计语言• 编译产生的机器语言，代码质量• 机器执行指令的速度• 问题的规模71.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) ：指数阶81.1.2 算法复杂度• n×n 矩阵相乘算法：• 时间复杂度为 O(n3) 。91.1.2 算法复杂度• 分析算法的工作量两种方法：– 平均性态– 最坏情况复杂性101.1.2 算法复杂度• 2 ．算法的空间复杂度– 算法执行过程中所需的最大存储空间– 存储量包括以下三部分• 算法程序所占的空间• 输...
