文档介绍：全国计算机等级考试 二级公共基础知识
编辑课件
基本要求
1. 掌握算法的基本概念。
2. 掌握基本数据结构及其操作。
3. 掌握基本排序和查找算法。
4. 掌握逐步求精的结构化程序设计方法。
5. 掌握软件工程的基本方法结构
编辑课件
算法设计基本方法
列举法
归纳法
递推
递归（以简洁的形式设计和描述算法）
减半递推技术
回溯法
编辑课件
算法复杂度
时间复杂度
是指执行算法所需要的计算工作量。
通常有事后统计法和事前分析估算法。
★算法在执行过程中所需基本运算的执行次数来度量算法的工作量.
★算法所执行的基本运算次数与问题的规模n有关.
执行算法所需要的计算工作量和f(n)同步增长，记为:
算法的工作量=f(n)
时间复杂度=O(f(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
1+2+3+…+(n-2)
= (n-1)(n-2)/2
O（ ）
例子2：++x;
O（ 1 ）
例子3： for (i=1 ;i<=n;++i) ++x;
O（ n ）
时间复杂度：
O((n*n-3n+2)/2)
基本运算：
基本运算的执行次数：
时间复杂度：
1
X增1
基本运算：
基本运算的执行次数：
时间复杂度：
X增1
n
编辑课件
算法的空间复杂度
一般是指执行这个算法所需要的内存空间
一个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及某种数据结构所需要的附加存储空间
一个上机执行的程序除了需要存储空间来寄存本身所用指令、常数、变量和输入数据外，也需要一些对数据进行操作的工作单元和存储一些为实现计算所需信息的辅助空间。
编辑课件
算法的时间复杂度是指
A) 执行算法程序所需要的时间 B) 算法程序的长度
C) 算法执行过程中所需要的基本运算次数
D) 算法程序中的指令条数
算法的基本特征是可行性、确定性、 【1】 和拥有足够的情报。
算法的空间复杂度是指
A) 算法程序的长度 B) 算法程序中的指令条数
C) 算法程序所占的存储空间 D) 执行过程中所需要的存储空间
在计算机中，算法是指
A) 加工方法 B) 解题方案的准确而完整的描述
C) 排序方法 D) 查询方法
例题讲解
有穷性
编辑课件
算法分析的目的是
A) 找出数据结构的合理性 B) 找出算法中输入和输出之间的关系
C) 分析算法的易懂性和可靠性 D) 分析算法的效率以求改进
算法的工作量大小和实现算法所需的存储单元多少分别称为算法的 【1】 。
时间复杂度和空间复杂度
编辑课件
数据结构
数据结构的定义
数据的逻辑结构和存储结构
数据结构的图形表示
线性结构与非线性结构
编辑课件
数据结构研究的主要内容
(1)数据集中数据之间的逻辑关系
线性
树
图
(2)数据的存储结构
(3)各种数据结构的运算
编辑课件
能输入到计算机中
并能被计算机程序处理的
符号的集合。
整数(1,2)、实数(,)
字符串(Beijing)、
图形、声音。
基本概念和术语
数据结构是一门研究数据组织、存储和运算的一般方法的学科。
编辑课件
计算机管理图书问题
在图书馆里有各种卡片：有按书名编排的、
有按作者编排的、有按分类编排
如何将查询图书的这些信息存入计算机中
既要考虑查询时间短，又要考虑节省空间
数据结构是一门研究数据组织、存储和运算的一般方法的学科。
最简单的办法之一是建立一张表，
每一本书的信息在表中占一行，如
编辑课件
如何将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
数据元素在
计算机中的表示
数据结构是一门研究数据组织、存储和运算的一般方法的学科。
对数据结构中的节点进行
操作处理
(插入、删除、修改、查找、排序)
编辑课件