《数据结构》课程期末复习资料
第一章：绪论
一、基础知识
概念和术语(黑体字部分)。

另外，注意：
1、数据元素是数据的基本单位。

2、数据项是数据不可分割的最小单位。

3、数据结构及其形式定义。

四种基本结构：①集合②线性结构③树形结构④图（网）状结构
4、数据结构的
逻辑结构（抽象的，与实现无关）
物理结构（存储结构）顺序映像（顺序存储结构）位置“相邻”
非顺序映像（链式存储结构）指针表示关系
5、数据类型
抽象数据类型（ADT）
ADT=（数据对象，数据关系，基本操作）
ADT细分为原子类型，固定聚合，可变聚合类型。

6、算法的概念
7、算法的五个特征
①有穷性②确定性③可行性④输入（0个或多个）⑤输出（1个或多个）
8、算法设计的要求：①正确性②可读性③健壮性④效率与低存储量
其中正确性的四个层次（通常要求达到C层）。

9、算法的时间复杂度
常见有： O(1)，O(n)，O(n2)，O(log
2n)1，O(n log
2
n)，O(2n)
语句频度，用归纳法计算。

10、算法的空间复杂度
二、算法
起泡排序。

另一种形式
void BubbleSort ( DataType a[], int n )
{
for ( i=0; i<n-1; i++ )
for ( j=0; j<n-i-1; j++ )
if ( a[j]>a[j+1] )
a[j]<—>a[j+1];
}
或
void BubbleSort ( DataType a[], int n )
{
for ( i=1; i<n; i++ )
for ( j=0; j<n-i; j++ )
if( a[j]>a[j+1] )
a[j]<—>a[j+1];
}
或
void BubbleSort ( DataType a[], int n )
1分析算法的时间复杂度时，log2n常简单记作log n。