文档介绍：——数据结构与算法
第一节算法
? 算法:一组有穷的指令集,是解题方案的准确而完整的描述。或者说是计算机解题的过程。? 算法的特征:(确定性、有穷性、可行性、拥有足够的情报)或(有穷性、确定性、可行性、输入、输出) ? 算法的基本控制结构(顺序、选择、循环) 3种
第一节算法
? 算法的复杂度:算法效率的质量,评价算法优劣的重要依据。? 算法的复杂度包括:空间复杂度和时间复杂度? 算法的空间复杂度:执行过程中所占用的存储空间? 算法的时间复杂度:算法在执行时所需要的计算工作量。包括编译时间和运行时间。
第一节算法
? 空间复杂度和时间复杂度是从两个方面对算法的效率进行度量,两者之间没有必然的联系。 s=0; for(i=0;i<10;i++) s+=1;
第一节
练习
1、算法具有五个特性,以下选项中不属于算法特性的是(B ) (0504) 2、在下列选项中,哪个不是一个算法一般应该具有的基本特征(C ) 3、算法的时间复杂度是指(C )(1003)
第一节
练习
4、算法的空间复杂度是指( D )(0909) 5、算法一般都可以用哪几种控制结构组合而成( D ) 、分支、递归 、循环、嵌套 、递归、选择 、选择、循环 6、在计算机中,算法是指( C )
第一节
练习
7、算法分析的目的是( D ) 8、下列叙述中正确的是( D ) ,则其时间复杂度也必定大 ,则其时间复杂度也必定小 ,则其空间复杂度也必定小
第一节
练习
9、算法的复杂度主要包括( 时间)复杂度和空间复杂度。(0509) 10、实现算法所需的存储单元多少和算法的工作量大小分别称为算法( 空间复杂度和时间复杂度)。 11、算法的基本特征是可行性、确定性、( 有穷性)、和拥有足够的情报。 12、下面叙述正确的是______。 C (或语句)的条数
第一节练习
13、算法的有穷性是指(A )(0804) A)算法程序的运行时间是有限的 B)算法程序所处理的数据量是有限的 C)算法程序的长度是有限的 D)算法只能被有限的用户使用
第二节数据结构的基本概念
? 数据:能输入到计算机中,并能被计算程序识别和处理的符号的总称,如文档,声音,视频等。? 数据元素:数据的基本单位。一个数据元素由多个数据项组成。? 数据对象:性质相同的数据元素的集合,是数据和一个子集。? 数据元素不是孤立存在的,而存在着某种关系的, 这种元素之间的关系称为结构。? 数据结构:相互之间存在一种或多种特定关系的数据元素的集合。
数据的逻辑结构和存储结构
? 数据的逻辑结构:数据之间关系的一种结构。比如:族谱。? 数据的存储结构:也称数据的物理结构。是数据在计算机中存放的方式。? 常用的存储结构:顺序、链接、索引等。? 采用不同的存储结构,其数据处理的效率是不同的。
数据结构的分类
? 依据数据元素之间关系不同特性,数据结构可以分为四类基本结构:集合、线性结构、树形结构、图状结构或网状结构。或二类:线性结构和非线性结构。线性结构:栈、队列、双向链表非线性结构:树、二叉树、图和集合
第二节练习
C 1、以下数据结构中不属于线性数据结构的是______ A. 队列 B. 线性表 C. 二叉树 D. 栈(0909) A 2、下列叙述中正确的是______。 A. 线性表是线性结构 B. 栈与队列是非线性结构 C. 线性链表是非线性结构 D. 二叉树是线性结构 B 3、数据的存储结构是指______。(0504) A. 数据所占的存储空间量 B. 数据的逻辑结构在计算机中的表示 C. 数据在计算机中的顺序存储方式 D. 存储在外存中的数据 C 4、数据结构中,与所使用的计算机无关的是数据的( )。