1.数据结构的概念，逻辑结构、物理结构的概念及各自包含的内容

2.算法的特性、设计要求，如何度量算法的时间效率。

3.线性表的顺序/链式存储结构的特点，插入、删除算法。

4.栈和队列的逻辑特性，顺序栈的入栈/出栈、循环队列的入队/出队算法。

5.以三元组顺序表存放的稀疏矩阵的转置算法。

6.二叉树的性质及其四种遍历算法。

7.森林与二叉树的相互转换。

8.WPL、前缀编码的概念，哈夫曼树的构造算法。

9.图的相关概念，邻接矩阵及邻接表的存储结构。

10.图的深度优先/广度优先遍历算法。

11.最小生成树的两种算法。

12.拓扑排序的意义和算法。

14.顺序表、有序表的查找算法。

15.二叉排序树的性质、插入/删除算法、平衡二叉树的性质、插入算法。

16.哈希表的相关概念，常用的冲突处理方法。

17.直接插入排序、希尔排序、快速排序、堆排序、归并排序的算法。

1.上述每个知识点可能会以任何题型出现，复习的时候别把它们当做“简答题”

2.红色（下划线）标识的知识点或算法，只要求对给出的初始数据，能画出结

果则可。其他的算法则可能会出现在“算法题”中。

1.顺序存储方式只能用于存储线性结构。（错）

2.顺序查找法适用于存储结构为顺序或链式存储的线性表。（对）

1.计算机算法必须具备输入、输出、（ B ）等5个特性。

PAGE 13 . 范文. 《数据结构与算法》实验报告三 ——二叉树的操作与应用 实验目的 熟悉二叉链表存储结构的特征，掌握二叉树遍历操作及其应用 实验要求（题目） 说明：以下题目中（一）为全体必做，（二）（三）任选其一完成 从键盘输入二叉树的扩展先序遍历序列，建立二叉树的二叉链表存储结构； 分别用递归和非递归算法实现二叉树的三种遍历； 模拟WindowsXP资源管理器中的目录管理方式,模拟实际创建目录结构,并以二叉链表形式存储,按照凹入表形式打印目录结构（以扩展先序遍历序列输入建立二叉链表结构），如下图所示: (基本要求:限定目录名为单字符;扩展:允许目录名是多字符组合) eq \o\ac( eq \o\ac(○,A) eq \o\ac(○,C) eq \o\ac(○,D) eq \o\ac(○,B) eq \o\ac(○,E) eq \o\ac(○,F) eq \o\ac(○,G) A B E F C G D 分工说明 一起编写、探讨流程图，根据流程图分工编写算法，共同讨论修改，最后上机调试修改。 概要设计 实现算法，需要链表的抽象数据类型： ADT Binarytree { 数据对象：D是具有相同特性的数据元素的集合 数据关系R： 若D为空集，则R为空集，称binarytree为空二叉树； 若D不为空集，则R为{H}，H是如下二元关系； 在D中存在唯一的称为根的数据元素root，它在关系H下无前驱； 若D－{root}不为空，则存在D－{root}＝{D1，Dr}，且D1∩Dr为空集； (D1,{H1})是一颗符合本定义的二叉树，称为根的左子树，(Dr,{Hr})是一颗符合本定义的二叉树，称为根的右子树。 初始条件：二叉树S已经存在 操作结果：将二叉树S清为空树 Bitreeempty(S) 初始条件：二叉树S已经存在 操作结果：若S为空二叉树，则返回TRUE，否则返回FALSE Bitreedepth(S,&e) 初始条件：二叉树S已经存在 操作结果：返回S的深度 Parent(S) 初始条件：二叉树S已经存在，e是S中的某个结点 操作结果：若e是T的非根结点，则返回它的双亲，否则返回空 Preordertraverse(S) 初始条件：二叉树S已经存在，Visit是对结点操作的应用函数。 操作结果：先序遍历S，对每个结点调用函数visit一次且仅一次。一旦visit失败，则操作失败。 Inordertraverse (S,&e) 初始条件：二叉树S已经存在，Visit是对结点操作的应用函数。 操作结果：中序遍历S，对每个结点调用函数visit一次且仅一次。一旦visit失败，则操作失败。 Postordertraverse (&S,e) 初始条件：二叉树S已经存在，Visit是对结点操作的应用函数。