数据结构与算法分析复习.doc

数据结构与算法分析期末复习大纲题型：一、判断题：（每题1分，共10分）重点第一、二、三、六、七章二、填空题（每题1分，共10分）重点第一、二、三、六、七章三、选择题（每题1分，共10分）重点第一、二、三、六、七章四、应用题（6道题，共60分）如：1. 栈、队列的特性。2. 已知二叉树的结点数，求叶子结点3. 树转换为二叉树，并求出先序、中序、后序4. 求哈夫曼树、哈夫曼编码5. 有向图、无向图的存储（邻接矩阵、邻接表）6. 求有向图、无向图的连通分题/强连通分量。7. 图的深度优先遍历、广度优先遍历序列。8. 图的深度优先遍历、广度优先遍历生成树。9. 按普里姆算法(加点法)、克鲁斯卡尔算法(加边法)求其最小生成树的步骤图。10. 求关键路径。11. 求拓扑排序五、算法设计题（共10分）重点第二章 复习方法：每章课件里的题必须要做会，每章习题要看。绪论一章的考点及对其掌握程度如下：1. 数据结构相关的基本概念，如数据结构、数据、数据元素（数据的基本单位，又称为元素、结点、顶点、记录）、数据项（数据不可分割的最小标识单位）。 2. 数据的逻辑结构和存储结构，数据的逻辑结构分类：线性结构（线性表、栈、队列 、串）、非线性结构（树 、图）。数据结构在计算机中的表示(或称映象）称为数据的存储结构，又称为物理结构，一般包括顺序存储结构、链式存储结构。3. 抽象数据类型的表示与实现4. 时间和空间复杂度的概念及度量方法。5. 算法的特性(要素)：有穷性、确定性、可行性、有0个或多个输入、一个或多个输出。6. 算法设计的要求：正确性、可读性、健壮性、高效率与低存储需求。线性表一章在线性结构的学习乃至整个数据结构学科的学习中其作用都是非常重要的。在这一章，第一次系统性地引入链式存储的概念，链式存储概念将是整个数据结构学科的重中之重，无论哪一章都涉及到了这个概念，所以一定搞透彻了。1. 线性表相关的基本概念，如：前驱、后继、表长、空表、首元结点，头结点，头指针等概念必须掌握。2. 线性表的结构特点，存在唯一一个被称做“第一个”的数据元素； 存在唯一一个被称做“最后一个”的数据元素；除第一个数据元素之外，每个元素都只有一个前驱；除最后一个数据元素之外，每个元素都只有一个后继。 。3. 线性表的顺序存储方式的实现。4. 线性表的链式存储方式的实现，几种常用链表的特点和运算：单链表、循环链表，双向链表，双向循环链表。5. 线性表的顺序存储及链式存储情况下，其优缺点比较，即其各自适用的场合，这点很重要，要掌握。6. 对于线性表的各种实现方式能够实现指定的操作，尤其是各种线性链表的插入，删除（删除自己，还是删除后继结点），判表空等。栈，队列和数组都属于线性结构的拓展，栈和队列是操作受限的线性表，数组是数据元素是非原子类型的线性表。大家在复习这一章的时候一定要注意对栈和队列的灵活运用。1. 栈、队列的定义及其相关数据结构的概念。2. 栈与队列插入删除操作的特点，栈和队列的特点，栈是后进先出，队列是先进先出。3. 栈的应用。4. 循环队列中判队空、队满条件，循环队列中入队与出队算法。5. 判循环队列是空还是满的两种处理方法。6. 数组的定义。7. 数组除了初始化和销毁之外只能进行存取和修改操作。8. 多维数组中某数组元素的position求解（不管是按行存储和按列存储）：一般是给出数组元素的首元素地址和每个元素占用的地址空间并组给出多维数组的维数，然后要求你求出该数组中的某个元素所在的位置。9. 特殊矩阵的压缩，包括对称矩阵，上（下）三角矩阵，对角矩阵，具有某种特点的稀疏矩阵等稀疏矩阵的三种不同实现方式：三元组，带辅助行向量的二元组，十字链表存储。例：5.有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？ A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 树和二叉树历来都是考试的重难点章节，从这章开始就从对线性结构的研究过渡到对树形结构的研究，这一章学习的好坏直接关系到在数据结构这门考试中能否能得高分。因此这一章大家对每个知识点都要吃透过关。二叉树：是有序的，即若将其左、右子树颠倒，就成为另一棵不同的二叉树。即使树中结点只有一棵子树，也要区分它是左子树还是右子树。满二叉树：在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样的一棵二叉树称作满二叉树。完全二叉树：一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1in）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。完全二叉树的特点是：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。1. 掌握本章的一些术语，如根、叶子、森林、有序树、无序树、双亲、孩子、兄弟、堂兄弟、祖先、子孙、结点、结点的度、结点的层次、终端结点、分支结点、树的度、树的深度(或高度)。2. 二叉树的概念：是n（n0）个结点的有限集合，由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成。3. 二叉树基本特征： 每个结点最多可有两棵子树（不存在度大于2的结点）； 左子树和右子树次序不能颠倒（有序树）。4. 二叉树的五种基本形态。5. 二叉树的五个性质，如已知结点总数或度为2的结点数，求叶子个数。性质1: 在二叉树的第i层上至多有2i-1个结点（i0）。性质2: 深度为k的二叉树至多有2k-1个结点（k0）。性质3: 对于任何一棵二叉树，若2度的结点数有n2个，则叶子数（n0）必定为n21 （即n0=n2+1）性质 4 ：具有 n 个结点的完全二叉树的深度为 log2n +1性质 5 ：若对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号，则对完全二叉树中任意一个编号为 i 的结点：(1) 若 i=1，则该结点是二叉树的根，无双亲；否则，编号为 i/2 的结点为其双亲结点;(2) 若 2in，则该结点无左孩子，否则，编号为 2i 的结点为其左孩子结点；(3) 若 2i+1n，则该结点无右孩子结点，否则，编号为2i+1 的结点为其右孩子结点。6. 二叉树的存储结构二叉链表、三叉链表、线索链表。7. 二叉树的三种遍历方法：先序，中序、后序。考法1：能够写出一棵二叉树的先序、中序、后序序列。考法2：已知一棵二叉树的先序、中序序列，画出二叉树，并求出后序序列。考法3：已知一棵二叉树的后序、中序序列，画出二叉树，并求出先序序列。8. 线索二叉树。9. 树的存储表示方法：双亲表示法、孩子表示法、孩子兄弟表示法。10. 树与森林转化为二叉树，树和森林的遍历问题。 11. 哈夫曼树，也叫最优二叉树，即带权路径长度最小的二叉树，要求能够构造哈夫曼树、哈夫曼编码，并求出最小带权路径长度。图这一章是每年考试必考的章节，这一张里面处处都是重点。无向完全图：在一个含有n个顶点的无向完全图中，有n(n-1)/2条边。有向完全图：在一个含有n个顶点的有向完全图中，有n(n-1)条边。顶点的度：是指依附于某顶点v的边数，通常记为TD (v)。对于具有n个顶点、e条边的图，顶点vi的度TD (vi)与顶点的个数以及边的数目满足关系： 边的权、网：与边有关的数据信息称为权。边上带权的图称为网图或网络。路径、路径长度：顶点vp到顶点vq之间的路径是指顶点序列vp,vi1,vi2, , vim,vq.。路径上边的数目称为路径长度。连通分量：无向图的极大连通子图。强连通分量：有向图的极大强连通子图。生成树：所谓连通图G的生成树，是G的包含其全部n 个顶点的一个极小连通子图。它必定包含且仅包含G的n-1条边。1. 图的基本概念：图的定义和特点，无向图，有向图，入度，出度，完全图，生成子图，路径长度，回路，（强）连通图，（强）连通分量等概念。2. 图的几种存储形式，尤其是邻接矩阵和邻接表。3. 图的两种遍历算法：深度遍历和广度遍历，这两个算法对图一章的重要性等同于“先序、中序、后序遍历”对于二叉树一章的重要性。 4. 生成树、最小生成树的概念以及最小生成树的构造：PRIM算法和KRUSKAL算法，要掌握这两个算法的基本思想。考查时，一般不要求写出算法源码，而是要求根据这两种最小生成树的算法思想写出其构造过程及最终生成的最小生成树 5. 拓扑排序问题。 6. 关键路径问题：这个问题是图一章的难点问题。理解关键路径的关键有三个方面：一是何谓关键路径，二是最早时间是什么意思、如何求，三是最晚时间是什么意思、如何求。简单地说，最早时间是通过“从前向后”的方法求的，而最晚时间是通过“从后向前”的方法求解的，并且，要想求最晚时间必须是在所有的最早时间都已经求出来之后才能进行。这个问题拿来直接考算法源码的不多，一般是要求按照书上的算法描述求解的过程和步骤 7. 最短路径问题：与关键路径问题并称为图一章的两只拦路虎。概念理解是比较容易的，关键是算法的理解。最短路径问题分为两种：一是求从某一点出发到其余各点的最短路径；二是求图中每一对顶点之间的最短路径。这个问题也具有非常实用的背景特色，一个典型的应该就是旅游景点及旅游路线的选择问题。解决第一个问题用DIJSKTRA算法，解决第二个问题用FLOYD算法。这个算法的要求就是要会用算法求解最短路径。第五大题算法设计是以下题目列表中之一。1. 已知L是无表头结点的单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。a.在P结点后插入S结点的语句序列是_。b.在P结点前插入S结点的语句序列是_。c.在表首插入S结点的语句序列是_。d.在表尾插入S结点的语句序列是_。(1)P-next=S;(2)P-next=P-next-next;(3)P-next=S-next;(4)S-next=P-next;(5)S-next=L;(6)S-next=NULL;(7)Q=P;(8)while(P-next!=Q)P=P-next;(9)while(P-next!=NULL)P=P-next;(10)P=Q;(11)P=L;(12)L=S;(13)L=P;/参考答案a.(4)(1) b.(7)(11)(8)(4)(1) c.(5)(12) d.(9)(1)(6) 2. 已知P结点是双向链表的中间结点，试从下列提供的答案中选择合适的语句序列。a在P结点后插入S结点的语句序列是_。b在P结点前插入S结点的语句序列是_。c删除P结点的直接后继结点的语句序列是_。d删除P结点的直接前驱结点的语句序列是_。e删除P结点的语句序列是_。(1)P-next=P-next-next; (10) P-prior-next=P;(2)P-prior=P-prior-prior;(11) P-next-prior =P;(3) P-next=S;(12)P-next-prior=S;(4) P-prior=S;(13) P-prior-next=S;(5)S-next=P; (14) P-next-prior=P-prior(6)S-prior=P; (15)Q=P-next;(7) S-next= P-next; (16)Q= P-prior; (8) S-prior= P-prior; (17)free(P);(9) P-prior-next=p-next; (18)free(Q);答案：a.(7)(6)(12)(3) 或 (7)(12)(3)(6)b.(8) (13) (5) (4) 或 (13) (8) (5) (4)c.(15)(1)(11)(18)d.(16)(2)(10)(18)e.(14)(9)(17) 或(9)(14)(17)3. 已知线性表LA和LB中的数据元素按值非递减有序排列，现要将LA和LB归并为一个新的链表LC，且LC中的数据元素仍按非值递减有序排序。/ 归并 La 和 Lb 得到新的单链表 Lc ，Lc 的元素也按非递减排列void MergeList_L ( LinkList La, LinkList Lb, LinkList *Lc, ) Node *pa,*pb;pa = La-next; pb = Lb-next;Lc = pc = La; / 用 La 的头结点作为 Lc 的头结点while ( pa & pb ) if ( pa-data data ) / 如果 pa-datapb-data pc-next = pa; pc = pa; pa = pa-next; else pc-next = pb; pc = pb; pb = pb-next; pc-next = pa ? pa : pb; / 插入剩余段free (Lb); / 释放 Lb 的头结点 4. 已知顺序表LA和LB中的数据元素按值非递减有序排列，现要将LA和LB归并为一个新表LC，且LC中的数据元素仍按非值递减有序排序。例如：LA（3,5,8,9） LB（2,6,8,9,11,15,20）则LC（2,3,5,6,8,8,9,11,11,15,20）参考程序：Void MergeList(SqList La, SqList Lb, SqList *Lc) Pa=La.elem;pb=La.elem;Lc-listsize=Lc.length=La.length+ Lb.length;Pc=Lc-elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemType);If(!Lc.elem) exit(overfiow);Pa_last=La.elem+La.length-1; pb_last=Lb.elem+Lb.length-1;While(pa=pa_last&pb=pb_last)if(*pa=*pb) *pc+=*pa+;else *pc+=*pb+;While(pa=pa_last) *pc+=*pa+;While(pb=pb