二级公共基础知识数据结构与算法文稿演示

二级公共基础知识数据结构与算法文稿演示
二级公共基础知识数据结构与 算法
注意事项
公共基础知识部份的内容是属于计算机专 业本科生的专业课，知识点特别散，而 且有一定的难度。所以考生在学习的过 程中，一定要克服畏难情绪，跟上老师 的节奏。老师让记的，要记住。没做要 求的，要学会放弃。
放弃该放弃的，选择轻装上阵
算法的工作量=f(n)
执行算法所需要的计算工作量和f(n)同步增长，记为: 时间复杂度=O(f(n))
而对于一个固定的规模，算法所执行的基本次数还与 特定的输入有关。
例子2：++x; 基本运算：X增1 基本运算的执行次数：1 时间复杂度：O（ 1 ）
例子3： for (i=1;i<=n;++i) ++x;
序、中序和后序遍历。 7. 顺序查找与二分法查找算法；基本排序算法（交换类排序，
插入类排序，选择类排序）。
1.1 算法
1.1.1 算法(algorithm)基本概念
算法 对解题方案准确而完整的描述称为算法。
它是指令的有限序列，其中每一条指令表示一个或多个操作。 计算机解题的过程实际上是在实施某种算法，这种算法称为计 算机算法。
一、 数据结构与算法
1. 算法的基本概念；算法复杂度的概念和意义（时间复杂度 与空间复杂度）。
2. 数据结构的定义；数据的逻辑结构与存储结构；数据结构 的图形表示；线性结构与非线性结构的概念。
3. 线性表的定义；线性表的顺序存储结构及其插入与删除运 算。
4. 栈和队列的定义；栈和队列的顺序存储结构及其基本运算。 5. 线性单链表、双向链表与循环链表的结构及其基本运算。 6. 树的基本概念；二叉树的定义及其存储结构；二叉树的前
算法的基本特征:
(1)有穷性 (2)确定性 (3)可行性 (4)拥有足够的情报
（有零个或多个输入，有一个或多个输出）
一个算法有零个或多个输入，以刻画运算对象的初始 情况，所谓零个输入是指算法本身定出了初始条件；
一个算法有一个或多个输出，以反映对输入数据加工 后的结果。没有输出的算法是毫无意义的；
描述算法的工具通常有传统流程图、N-S结构化流程 图、伪代码等。
在计算机中，算法是指
A) 加工方法
B) 解题方案的准确而完整的描述
C) 排序方法
D) 查询方法
算法分析的目的是 A) 找出数据结构的合理性 B) 找出算法中输入和输出之间的关系 C) 分析算法的易懂性和可靠性 D) 分析算法的效率以求改进
算法的工作量大小和实现算法所需的存储单元多少分别称为算法 的 【1】 。 时间复杂度和空间复杂度
算术运算 逻辑运算 关系运算 数据传输
顺序、选择、 循环3种基 本结构
1.1.3 算法设计基本方法
列举法 归纳法 递推 递归（以简洁的形式设计和描述算法） 减半递推技术 回溯法
1.2 算法复杂度
1.2.1 时间复杂度 是指执行算法所需要的计算工作量。 通常有事后统计法和事前分析估算法。 ★算法的工作量用算法所执行的基本运算次数来度量. ★算法所执行的基本运算次数与问题的规模n有关（即算 法所执行的基本次数是问题规模的函数）.
1+2+3+…+(n-2) = (n-1)(n-2)/2
O（ n 2 ）
1.2.2 算法的空间复杂度
一般是指执行这个算法所需要的内存空间
一个算法所占用的内存空间包括算法程序所占 的空间、输入的初始数据所占的存储空间以及 算法在执行过程中所需要的额外空间这3部分。
例题讲解
算法的时间复杂度是指
1.2 数据结构
数据结构的定义 数据的逻辑结构和存储结构 数据结构的图形表示 线性结构与非线性结构
1.2.2 基本概念和术语
}while(r<=0); s=PI*r*r; printf("Area=%f\n", s); return 0; }
1.1.2 算法的基本要素
1、对数据对象的运算和操作
算术运算 逻辑运算 关系运算 数据传输
2、算法的控制结构
算法中各操作之间的执行顺序 一个算法一般可以用顺序、选择、循环3种基本结
第9页
例题:已知圆的半径,求圆的面积.
算法:Байду номын сангаас
S1:输入圆的半径R;
S2:求面积∏R2;
程序
S3:输出面积;
#include <stdio.h> #define PI 3.14159 int main() { float r, s;
do{ printf("Please input r:"); scanf("%f", &r); if (r<0) printf("Error！\n");
例1:已知圆的半径,求圆的面积.
伪代码: S1:输入圆的半径R; S2:求面积 ∏R2; S3:输出面积;
开始 输入R S=3.14 * R*R
输出S
结束
传统流程图
算法与计算机程序 算法——是一组逻辑步骤 程序——用计算机语言描述的算法
算法是程序设计的核心
算法不等于程序，也不等于计算方法，程序的编制不可能优于算法的 设计。
A) 执行算法程序所需要的时间
B) 算法程序的长度
C) 算法执行过程中所需要的基本运算次数
D) 算法程序中的指令条数
算法的基本特征是可行性、确定性、 【1】 和拥有足够的情报。
有穷性
算法的空间复杂度是指
A) 算法程序的长度
B) 算法程序中的指令条数
C) 算法程序所占的存储空间 D) 执行过程中所需要的存储空间
基本运算：X增1 基本运算的执行次数：n 时间复杂度：O（ n ）
例子4：for ( i=2;i<=n;++i) for (j=2;j<=i-1;++j) ++x ;
基本运算：X增1 基本运算的执行次数：i=2 0
i=3 1 i=4 2 … i=n n-2 时间复杂度：O((n*n-3n+2)/2)
构组合而成。
#include <stdio.h> #define PI 3.14159 int main() { float R, S;
do{ printf("Please input R:"); scanf("%f", &R); if (R<0) printf("Error！\n");
}while(R<=0); s=PI*R*R; printf("Area=%f\n", S); return 0; }