线性表

1. 线性表的逻辑结构定义、抽象数据类型定义。

2. 线性表的两种存储结构的不同特点及其适用场合。

顺序存储：借助元素在存储器中的相对位置来表示元素之间的逻辑关系。

链式存储：借助指示元素存储地址的指针来表示元素之间的逻辑关系。

顺序表和链表的优缺点比较（正好是相对的）。

3. 在线性表的两种存储结构上实现基本操作的算法。

查找、插入、删除、归并、分解、就地逆置等。

注意：单链表与双向链表、普通链表与循环链表的区别。

双向链表中结点的特征：p=p->next->prior=p->prior->next

因此，在插入和删除时，对单链表，必须要知道第i-1个结点

的地址，而对双向链表则不必如此。

例1.已知la是不带头结点的单链表的头指针，试编写逆序

输出表中各元素值的递归算法。

例2.按递增有序输出单链表中的元素值。

例3.实现集合的交、并、差等运算。

堆和队列

1. 栈的定义、特征以及抽象数据类型定义。

会灵活运用栈的特征（后进先出）。

例：设输入元素为1, 2, 3, P, A，输入次序为123PA，元素经过栈后到达输出序列，当所有元素均到达输出序列后，有哪些序列可以作为高级语言的变量名？

2.栈的存储结构顺序栈：栈满和栈空的条件

链栈

入栈、出栈、取栈顶元素等基本操作的实现算法。

3.栈的应用表达式计算：了解基本思想、栈在算法中的作用

实现递归算法

4. 队列的定义、特征以及抽象数据类型定义。

5.队列的存储结构（顺序）循环队列

链队列

入队、出队、取队头元素等基本操作的实现算法。

循环队列：入队：Q->queue[Q->rear]＝x；

Q->rear＝(Q->rear+1)%MaxQueueSize；

出队：*d=Q->queue[Q->front]；

Q->front＝(Q->front＋1) %MaxQueueSize；

判断队满和队空：（1）少用一个存储单元；

（2）设置一个标志位；

（3）设置一个计数器。

6. 队列的应用：结合后面二叉树和图的遍历算法。

数组

1. 数组采用行优先或列优先顺序存储时，数组元素的

存储地址的计算方法（重点掌握二维、三维数组）。

2. 特殊矩阵进行压缩存储时下标变换公式的推导方法。

要求掌握上三角矩阵、下三角矩阵、对称矩阵、三对角

矩阵分别按行优先或列优先压缩存储时的下标变换公式。

树

1. 树、二叉树的结构特性；二叉树的五种基本形态。

2. 满二叉树和完全二叉树的定义、特点；二叉树的性质

（五条，其中有两条只对完全二叉树满足）。

1、若深度从0开始计算则第i层有2^i个结点

2、共有2^(i+1) -1个结点

3、n0=n2+1

4、完全二叉树有n个结点，则他的深度为log2(n+1)-1

5、完全二叉树：第i个结点的左孩子在2i+1 右孩子是2i+2

3. 二叉树的遍历策略及算法（递归和非递归）。由前序

和中序遍历序列、中序和后序遍历序列能唯一构造出一棵二叉树。

会灵活运用遍历算法求解其他问题。

例1.输出某类结点的值或求某类结点的个数（如叶子结点）。

例2.判定一棵二叉树是否为二叉排序树（采用中序遍历策略，判断正在访问的结点与它的前驱结点之间是否递增有序）。

4. 树的三种存储结构及其特点（双亲表示法、孩子表示法和孩子兄弟表示法，重点掌握孩子兄弟表示法）；树、

森林与二叉树的转换方法。

5. 树的遍历方法：

先根（对应二叉树的前序遍历）

后根（对应二叉树的中序遍历）

森林的遍历方法：先序和中序。

6.

Huffman树的概念及构造方法，哈夫曼编码的设计。

注意：Huffman树是扩充二叉树（只含度为0和度为2的结点）。

补充作业：写出二叉树的中序和后序遍历的非递归算法。

voidNInOrder(BiTreeNode*bt)

/*中序遍历二叉树bt的非递归算法*/

{BiTreeNode*stack [MaxNode], *p;

int top;

if (bt==NULL)

return;

top=0；p=bt；

while (! (p==NULL&&top==0))

{ while (p!=NULL)

{ if (top

{stack[top]=p;

top++;

}

else {printf(“\noverflow！”);

return;

}p=p->leftChild;/*访问左子树*/

}/*while (p!=NULL)*/

if (top==0) return;

else { top--;

p=stack[top];

visit (p);/*访问根结点*/

p=p->rightChild;/*访问右子树*/

}

}/*while*/

}

typedefstruct

{BiTreeNode*pt;

inttag;

} Node;

voidNPostOrder(BiTreeNode*bt)

/*后序遍历二叉树bt的非递归算法*/

{ Node stack [MaxNode],BiTreeNode*p;

inttop;

if (bt==NULL)

return;

top=0；p=bt；

while (! (p==NULL&&top==0))

{ while (p!=NULL)

{ if (top

{stack[top].pt=p;stack[top].tag=1;

top++;

}else {printf(“\noverflow！”);

return;

}

p=p->leftChild;/*访问左子树*/

}/*while (p!=NULL)*/

if (top==0) return;

else {if (stack[top-1].tag==1)

{ p=stack[top-1].pt;stack[top-1].tag=2;

p=p->rightChild;/*访问右子树*/

}

else { top--;

visit (stack[top].pt);/*访问根结点*/

}

}

}/*while*/

}

图

图的定义、基本术语。

（如：无向完全图、有向完全图、路径、回路、连通图和连通分量、强连通图和强连通分量、连通图的生成树）

无向完全图：弧数量为Cn2 的图，有向完全图的弧数量为An2

连通图 ：任意两个结点能连通

连通分量：在无向图中，极大的连通子图成为图的连通分量

连通图的生成树：一个连通图的生成树是一个极小连通子图，他含有途中全部定点n但只有足以构成一棵树的n-1条边。

注意：边数与顶点数、度之间的关系：

完全图、连通图以及生成树的特点。

判断图中是否存在回路的方法。?

无向图中结点的度均>=2 则改图一定存在回路

利用BFS，在遍历过程中，为每个节点标记一个深度deep，如果存在某个节点为v，除了其父节点u外，还存在与v相邻的节点w使得deep[v]<=deep[w]的，那么该图一定存在回路；

2.

图的各种存储结构（重点掌握邻接矩阵和邻接表）的

特点及构造方法。

注意：图和网的区别。

3. 图的两种遍历策略及遍历算法（深度优先和广度优先）。

会灵活运用遍历算法求解其他问题。

4. 图的应用

（1）生成树的定义、类型（深度优先和广度优先生成树）；

最小生成树的定义；

Kruskal算法和Prim算法(破圈法)求网的最小生成树的方法（注意：记住算法特点，不要混淆）。

（2）Dijkstra算法求单源最短路径的方法（有向网和无向网都适用）。

查找

1.静态查找表的顺序查找、折半查找方法的实现算法；

描述折半查找过程的二叉判定树的构造方法；三种方

法的比较。

2.

二叉排序树的定义、构造以及查找、插入的实现方法。

注意：二叉排序树按中序遍历是递增有序序列。

3.

哈希表的定义、构造及查找方法，重点掌握开放定址法和链地址法处理冲突时的构造方法。

开放地址法：线性探测、平方再散列法（-1^2,1^2,-2^2,2^2....）

链地址法：将冲突的结点连接在地址上，采用链式结构

4.

根据公式计算各种查找方法在等概率情况下的平均查找长度。

内部排序

1.

排序的定义，排序方法“稳定”或“不稳定”的含义。

注意：希尔排序、直接选择排序、堆排序、快速排序是不稳定的排序算法。

2.

各种排序方法的基本思想、算法特点、排序过程

以及它们的时间和空间复杂度分析。

（包括基本算法及它们的改进算法：直接插入排序、

折半插入排序、希尔排序、直接选择排序、堆排序、

冒泡排序、快速排序、归并排序及基数排序）

会根据实际应用情况选择合适的排序算法。

错误题目总结

1、数据的最小单位是数据项

2、时间复杂度不受初始状态影响而恒为 nlog2n 的是 堆排序。