11级数据结构期末复习

算法、线性表

复习内容：

算法的概念、算法的评价标准、算法的时空效率（时间复杂度、空间复杂度、语句频度） 线性表：顺序存储、链式存储（单/双链表的插入、删除、合并算法）、循环链表、双链表 栈：顺序存储、链式存储（栈的基本运算：POP、PUSH、EMPTY、INITIAL；栈的应用：数制转换、括号匹配、表达式求值） 队列：顺序存储（循环队列）、链式存储（队列的基本运算） 串：子串、模式匹配，next函数

数组：特殊矩阵的压缩存储（对角矩阵、三对角矩阵、上三角矩阵、对称矩阵）及下标的计算

广义表：表头、表尾、长度、深度 要求掌握的课后习题

P91 1、5、6、7、11、17、23、27 P22 9

P50 2、3、18

树和二叉树

复习内容：

树：定义、节点的度、孩子、双亲、深度、有序树、无序树、 二叉树：定义、性质、二叉树的存储方式（顺序存储和链式存储） 遍历二叉树：4种遍历算法（递归和非递归），以及遍历算法的应用（求二叉树的深度、叶子数、交互左右子树、判断二叉树是否等价）、从遍历序列还原二叉树 树/深林与二叉树的转换、树和森林林的遍历

哈夫曼树：带权路径长度WPL、哈夫曼树的构造（算法）、哈夫曼编码

要求掌握的课后习题P129

第3、7、9、10、12、13、14、16、17、19、20题

图

复习内容：

图的基本概念：有向图、无向图、弧头、弧尾、有向完全图、入度、出度、连通分量、强连通图。

图的存储：邻接矩阵、邻接表

图的遍历：深度优先遍历、广度优先遍历（掌握在不同存储结构下的遍历算法及应用） 最小生成树：利用Prim算法和Kruskal算法构造最小生成树（最小生成树的构造过程） 拓扑排序：拓扑排序序列、关键路径的求解

最短路径：掌握Dijkstra算法求解最短路径的过程

要求掌握的课后习题P163

1.分别给出邻接矩阵、邻接表和逆邻接表，并计算每个顶点的度。 2.（2）给出深度优先搜索遍历序列和深度优先生成树。

（3）广度优先搜索遍历序列和广度优先生成树。

（4）、用prim算法求最小生成树的过程

（5）、用kruskal算法求最小生成树的过程。 1）将e条边按权值大小由小到大排序

2）从权值最小的边开始依权值递增顺序查看每一条边，如果该边所依附的两个顶点在不同的联通分量上，则选定此边，否则放弃。

3、对于图5-37，求： （1）、邻接矩阵

（2）、用Dijkstra算法求从V1出发到各顶点的最短路径。(按讲义PPT中的求解方法) 终点 V2 V3 V4 V5 Vj S i=1 10 (V1,V2) 18 (V1,V3) V2 V1,V2 i=2 18 (V1,V3) 15 (V1,V2,V4) 13 (V1,V2,V5) V5 V1,V2,V5 i=3 15 (V1,V2,V5,V3) 15 (V1,V2,V4) V3 V1,V2,V5,V3 i=4 15 (V1,V2,V4) V4 V1,V2,V5,V3,V4 P163

5、给出图5-35（a)所示有向无环图的所有拓扑有序序列，并指出按拓扑排序算法求得的序列是哪一个。

V1---V2---V3---V4---V6---V5 V1---V3---V2---V4---V6---V5 V1---V3---V4----V2---V6---V5 V1---V3---V4---V6---V2---V5

按拓扑算法；V1---V2---V3---V4---V6---V5

6、对于图5-39所示的AOE网，求出各个活动可能的最早开始时间和允许的最晚开始时间。并回答下列问题： （1） （2） （3） （1）25

最早发生时刻ve(j)：事件j可能发生的最早时刻。它是源点到j点的最长带权路径。 最迟发生时刻vl(i)：事件i允许的最迟开始时刻。

活动可能开始的最早时刻e(i,j)：对应的弧为vi-vj。e(i,j)=ve(i) 即为i可能开始的最早时刻。 活动允许的最迟开始时刻l(i,j):对应弧为vi-vj。l(i,j)=vl(j)-w(i,j)。

（2）

(3)存在，加快a2,a4,a9,a12,a8可适当缩小

10.设计算法，建立有向图的邻接表存储结构

第16、17、18、19题

算法题：1、判断一个图是否连通。

2、熟练掌握图的两张存储方式，并能进行转换。

检索（查找）

复习内容：

静态查找：顺序检索、二分检索、索引（分块）检索（算法、检索成功的ASL） 树表：二叉检索树的构造（插入、删除）、二叉检索树的检索算法、、平均检索长度 哈希检索：哈希函数、地址冲突的消解（开放定址法、拉链法）、平均检索长度。

P228

1、分别求出等概率情况下检索成功和不成功的平均检索长度。（答案参考P199） 检索成功的平均检索长度：ASL=(n+1)/2; 检索失败的平均检索长度：ASL=n+1;

5、画出判定树，并求出等概率情况下检索成功和不成功的平均检索长度。

判定树：

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库11级数据结构期末复习在线全文阅读。