文档介绍：《数据结构与算法分析》期末复习大纲
题型：
一、 判断题：（每题1分，共10分）——重点第一、二、三、六、七章
二、 填空题（每题I分，共10分）——重点第一、二、三、六、七章
三、 选择题（每题I分，共10分）一重点第一、二、三、六、七章
四、 应用题（6道题，共60分）
如：
1 •栈、队列的特性。
已知二叉树的结点数，求叶子结点
树转换为二叉树，并求出先序、中序、后序
求哈夫曼树、哈夫曼编码
有向图、无向图的存储（邻接矩阵、邻接表）
求有向图、无向图的连通分题/强连通分量。
图的深度优先遍历、广度优先遍历序列。
&图的深度优先遍历、广度优先遍历生成树。
按普里姆算法（加点法）、克鲁斯卡尔算法（加边法）求其最小生成树的步骤图。
求关键路径。
求拓扑排序
五、 算法设计题（共10分）——重点第二章
复习方法：每章课件里的题必须要做会，每章习题要看。
绪论一章的考点及对其掌握程度如下：
数据结构相关的基本概念，如、、为元素、结点、顶点、记录）、数据项（数 据不可分割的最小标识单位）。
数据的和，数据的逻辑结构分类：线性结构（线性表、栈、队列、串）、非 线性结构（树、图）。数据结构在计算机中的表示（或称映象）称为数据的存储 结构，又称为物理结构，一般包括顺序存储结构、链式存储结构。
的表示与实现
时间和空间的概念及度量方法。
算法的特性（要素）：有穷性、确定性、可行性、有0个或多个输入、一个或 多个输出o
:正确性、可读性、健壮性、高效率与低存储需求。
线性表一章在线性结构的学习乃至整个数据结构学科的学习中其作用都是非 常重要的。在这一章，第一次系统性地引入链式存储的概念，链式存储概念将是 整个数据结构学科的重中之重，无论哪一章都涉及到了这个概念，所以一定搞透 彻了。
线性表相关的基本概念，女口：前驱、后继、表长、空表、首兀结点，头结点, 头指针等概念必须掌握。
线性表的结构特点，存在唯一一个被称做“第一个”的数据元素；存在唯一 一个被称做“最后一个”的数据元素；除第一个数据元素之外，每个元素都只有一 个前驱；除最后一个数据元素之外，每个元素都只有一个后继。。
线性表的顺序存储方式的实现。
线性表的链式存储方式的实现，几种常用链表的特点和运算：单链表、循环 链表，双向链表，双向循环链表。
线性表的顺序存储及链式存储情况下,其优缺点比较，即其各自适用的场合, 这点很重要，要掌握。
对于线性表的各种实现方式能够实现指定的操作，尤其是各种线性链表的插 入，删除（删除自己，还是删除后继结点），判表空等。
栈，队列和数组都属于线性结构的拓展，栈和队列是操作受限的线性表，数组 是数据元素是非原子类型的线性表。大家在复习这一章的时候一定要注意对栈和 队列的灵活运用。
栈、队列的定义及其相关数据结构的概念。
栈与队列插入删除操作的特点，栈和队列的特点，栈是后进先出，队列是先 进先出。
栈的应用。
循环队列中判队空、队满条件，循环队列中入队与出队算法。
判循环队列是空还是满的两种处理方法。
数组的定义。
数组除了初始化和销毁之外只能进行存取和修改操作。
&多维数组中某数组元素的position求解（不管是按行存储和按列存储）：一 般是给出数组元素的首元素地址和每个元素占用的地址空间并