数据结构与算法分析复习

《数据结构与算法分析复习》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《数据结构与算法分析》期末复习大纲题型：一、判断题：（每题1分，共10分）——重点第一、二、三、六、七章二、填空题（每题1分，共10分）——重点第一、二、三、六、七章三、选择题（每题1分，共10分）——重点第一、二、三、六、七章四、应用题（6道题，共60分）如：1.栈、队列的特性。2.已知二叉树的结点数，求叶子结点3.树转换为二叉树，并求出先序、中序、后序4.求哈夫曼树、哈夫曼编码5.有向图、无向图的存储（邻接矩阵、邻接表）6.求有向图、无向图的连通分题/强连通分量。7.图的深度优先遍历、广度优先遍历序列。8.图的深度优先遍历、广度优先遍历生成树。9.按普里姆算法(加点

2、法)、克鲁斯卡尔算法(加边法)求其最小生成树的步骤图。10.求关键路径。11.求拓扑排序五、算法设计题（共10分）——重点第二章复习方法：每章课件里的题必须要做会，每章习题要看。绪论一章的考点及对其掌握程度如下：1.数据结构相关的基本概念，如数据结构、数据、数据元素（数据的基本单位，又称为元素、结点、顶点、记录）、数据项（数据不可分割的最小标识单位）。2.数据的逻辑结构和存储结构，数据的逻辑结构分类：线性结构（线性表、栈、队列、串）、非线性结构（树、图）。数据结构在计算机中的表示(或称映象）称为数据的存储结构，又称为物理结构，一般包括顺序存储结构、链式存储结构。3.抽象

3、数据类型的表示与实现4.时间和空间复杂度的概念及度量方法。5.算法的特性(要素)：有穷性、确定性、可行性、有0个或多个输入、一个或多个输出。6.算法设计的要求：正确性、可读性、健壮性、高效率与低存储需求。线性表一章在线性结构的学习乃至整个数据结构学科的学习中其作用都是非常重要的。在这一章，第一次系统性地引入链式存储的概念，链式存储概念将是整个数据结构学科的重中之重，无论哪一章都涉及到了这个概念，所以一定搞透彻了。1.线性表相关的基本概念，如：前驱、后继、表长、空表、首元结点，头结点，头指针等概念必须掌握。2.线性表的结构特点，存在唯一一个被称做“第一个”的数据元素；存在

4、唯一一个被称做“最后一个”的数据元素；除第一个数据元素之外，每个元素都只有一个前驱；除最后一个数据元素之外，每个元素都只有一个后继。。3.线性表的顺序存储方式的实现。4.线性表的链式存储方式的实现，几种常用链表的特点和运算：单链表、循环链表，双向链表，双向循环链表。5.线性表的顺序存储及链式存储情况下，其优缺点比较，即其各自适用的场合，这点很重要，要掌握。6.对于线性表的各种实现方式能够实现指定的操作，尤其是各种线性链表的插入，删除（删除自己，还是删除后继结点），判表空等。栈，队列和数组都属于线性结构的拓展，栈和队列是操作受限的线性表，数组是数据元素是非原子类型的线性表

5、。大家在复习这一章的时候一定要注意对栈和队列的灵活运用。1.栈、队列的定义及其相关数据结构的概念。2.栈与队列插入删除操作的特点，栈和队列的特点，栈是后进先出，队列是先进先出。3.栈的应用。4.循环队列中判队空、队满条件，循环队列中入队与出队算法。5.判循环队列是空还是满的两种处理方法。6.数组的定义。7.数组除了初始化和销毁之外只能进行存取和修改操作。8.多维数组中某数组元素的position求解（不管是按行存储和按列存储）：一般是给出数组元素的首元素地址和每个元素占用的地址空间并组给出多维数组的维数，然后要求你求出该数组中的某个元素所在的位置。9.特殊矩阵的压缩，包

6、括对称矩阵，上（下）三角矩阵，对角矩阵，具有某种特点的稀疏矩阵等稀疏矩阵的三种不同实现方式：三元组，带辅助行向量的二元组，十字链表存储。例：5.有六个元素6，5，4，3，2，1的顺序进栈，问下列哪一个不是合法的出栈序列？A.543612B.453126C.346521D.234156树和二叉树历来都是考试的重难点章节，从这章开始就从对线性结构的研究过渡到对树形结构的研究，这一章学习的好坏直接关系到在数据结构这门考试中能否能得高分。因此这一章大家对每个知识点都要吃透过关。二叉树：是有序的，即若将其左、右子树颠倒，就成为另一棵不同的二叉树。即使树中结点只有一棵子树，也要区分

7、它是左子树还是右子树。满二叉树：在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样的一棵二叉树称作满二叉树。完全二叉树：一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。完全二叉树的特点是：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。1.掌握本章的一些术语，如根、叶子、森林、有序树、无序树、双亲、孩子、兄弟、堂兄弟、祖先、子孙、结点、结点的