[政史地]ds200911数据结构复习.ppt

● 数据的逻辑结构 ● 数据的操作 试题分析 (5’)参考答案如下： e j f g d b c i a k h 试题5.3——树 试题分析 例5.3 (10’)已知一组字符及其权值如下：a:35, b:9, c:19, d:27, e:81, f:14, g:21, h:12, i:25, j:5, k:11, l:8请构造相应的哈夫曼树，画出结果哈夫曼树即可。 ● 树 试题分析 (10’)参考答案如下： a:35, b:9, c:19, d:27, e:81, f:14, g:21, h:12, i:25, j:5, k:11, l:8 a/35 b/9 c/19 d/27 f/14 g/21 h/12 i/25 j/5 k/11 l/8 e/81 13 20 25 33 41 50 60 76 110 157 267 试题6.1——图 试题分析 例6.1 已知一个用邻接表存贮的有向图如下，请画出该图(2’)，并写出该图的深度优先遍历序列(5’)和广度优先遍历序列(5’)。 ● 图 0 ?2?7?9 1 ?3?9 2 ?0?5?8 3 ?6 4 ?1?6?9 5 ?0 6 ?5?9 7 ?0?2?5?8 8 ?6 9 ?8 a b c d e f g h i j 试题分析 参考答案如下： a b c d e f g h i j 深度遍历序为：acfigjhbde(5’) 广度遍历序为：achjfigbde(5’) 试题6.2——图 试题分析 例6.2 (2006) 请叙述最小生成树的MST性质（5‘）,并证明MST性质（5’）。 ● 图 参考答案如下： MST性质: 设无向图N=(V, E),U是顶点V的一个非空子集。若(u,v)是一条具有最小权值的边，其中u∈U, v∈V-U，则必存在一棵包含边(u,v)的最小生成树。 证明（反证法）： 设N的任何一棵最小生成树都不包含(u,v)，T是一棵最小生成树。 将边(u,v)加入到T中时，由生成树的定义，T必存在一条包含(u,v)的闭合回路。 T上必存在另一条边(u’,v’)，其中u’∈U, v’∈V-U，且u和u’之间，v和v’之间均有路径相通。 删去边(u’,v’)，可消去回路，同时得到另一棵生成树T’。 由于(u,v)的代价不高于(u’,v’)，则T’的代价不高于T，T’是包含(u,v)的一棵最小生成树，与假设矛盾。 试题分析 例6.3 (15’)已知连通网如下图所示，请用Prim或Kruskal算法计算出该连通网的最小生成树（写出计算过程）。 试题6.3——图 试题分析 ● 图 a 15 b e c g f h i d 20 31 3 17 4 23 9 21 9 34 15 23 61 2 试题分析 参考答案如下： 结论：ae, de, dg, gf, gh, ch, cb, hi ? K U a b c d e f g h i 0 - a - a 20 a ∞ a ∞ a 15 a ∞ a ∞ a ∞ a ∞ 1 e ae - a 20 a ∞ e 4 - e 31 e 17 a ∞ a ∞ 2 d ade - a 20 d 21 - - e 31 d 2 d 32 a ∞ 3 g adeg - a 20 d 21 - - g 3 - g 15 g 61 4 f adefg - a 20 d 21 - - - - g 15 g 61 5 h adefgh - a 20 h 9 - - - - - h 23 6 c acdefgh - c 9 - - - - - - h 23 7 b abcdefgh - - - - - - - - h 23 8 i abcdefghi - - - - - - - - - 试题6.4——图 试题分析 例6.4 已知某连通图如下，请计算图中的关节点。 。 ● 图 1 2 0 3 6 5 4 7 试题分析 参考答案如下： 深度优先遍历序如下所示： 对遍历起点v0，因从其第一个邻接点v1出发，未能遍历完全部结点，因此v0是关节点。 对v3，因其存在遍历子结点v2和v6的Low值为3，不小于v3的遍历序3，因此v3是关节点。 对v5，因其存在遍历子结点v5和v7的Low值为5，不小于v5的遍历序5，因此v5是关节点。 0 1 3 2 5 4 7 6 i 0 1 2 3 4 5 6 7 遍历序 1 2 4 3 6 5 8 7 完成序 8 1 2 7 3 5 6 4 Low - 1 3 1 5 1 3 5 试