Acknowledgement 被軒由05同冰计算机 MS XuWan危费提供现由 bbs. tongji.net宫方网站发布,鹿 费提供给大家使用,禁止任何单位和个人用作其它商业用途! -Andy Xia P为前驱结点。后继节点的方法与上面差不多。 掌握遍历线索二叉树的方法:例如中序线索二叉树,先找到第一个结点(最左边无左 孩子的结点),然后按照上述方法依次寻找后继结点 9)哈夫曼树 概念:没有度为1的结点的二叉树 掌握构造哈夫曼树的数学构造方法。 哈夫曼编码(左0右1) 练习题 1.确定一棵二叉树必须有中序遍历,再加上一种其他遍历。 2.先序 ABDECFGH中序 DEBAFCHG求叶子结点。EFH 3.二叉树链式结构的三种表示法:双亲,孩子,孩子兄弟表示法 4.先序 ABCDEFG中序 BDCAFGE,则先序 EACBDGF 5.若一个叶子是某中序遍历的最后一个,则它是该子树先序遍历的最后一个( right) 若一个结点是某中序遍历的最后一个,则它是该子树先序遍历的最后一个(wong) 哈夫曼树19个结点,则叶子结点10个。 7.N个节点用二叉链表存储,共有N+1个空链域。用了N-1个链域。 大题 1.求一棵二叉树的深度 2.求任意两个结点的最近共同祖先 3.层次遍历算法 4.先序 FAMBXCR中序 AFXBMCR,画出二叉树和后序线索二叉树。后序 ( AXBRCMF),再线索化 5.W={ ABCDEFG},权为{1l,14,8,6,13,22,18,26} 构造W的哈夫曼树,并求出WPL。(118) 写出字符哈夫曼编码。 A=010D=1011 G=111 B=100E=011 C=1010 F=110 第七章图 本章是考试的一个重点,很多应用内容都会涉及到! 图的基本概念 图的存储结构:1)数组表示法,邻接矩阵 2)邻接表及逆邻接表 图的遍历 1)深度优先,类似于二叉树的先序遍历 2)广度优先,类似于树的层次遍历 图的应用:1)最小生成树
Acknowledgement: 该资料由 同济计算机 05 MS XuWan 免费提供，现由 bbs.tongji.net 官方网站发布，免 费提供给大家使用，禁止任何单位和个人用作其它商业用途！―――Andy Xia P 为前驱结点。后继节点的方法与上面差不多。 掌握遍历线索二叉树的方法：例如中序线索二叉树，先找到第一个结点（最左边无左 孩子的结点），然后按照上述方法依次寻找后继结点。 9）哈夫曼树 概念：没有度为 1 的结点的二叉树 掌握构造哈夫曼树的数学构造方法。 哈夫曼编码（左 0 右 1） 练习题 1．确定一棵二叉树必须有中序遍历，再加上一种其他遍历。 2．先序 ABDECFGH,中序 DEBAFCHG, 求叶子结点。EFH 3．二叉树链式结构的三种表示法：双亲，孩子，孩子兄弟表示法。 4．先序 ABCDEFG,中序 BDCAFGE,则先序 EACBDGF。 5．若一个叶子是某中序遍历的最后一个，则它是该子树先序遍历的最后一个（right）。 若一个结点是某中序遍历的最后一个，则它是该子树先序遍历的最后一个（wrong）。 6．哈夫曼树 19 个结点，则叶子结点 10 个。 7．N 个节点用二叉链表存储，共有 N+1 个空链域。用了 N-1 个链域。 大题： 1．求一棵二叉树的深度。 2．求任意两个结点的最近共同祖先。 3．层次遍历算法。 4．先序 FAMBXCR,中序 AFXBMCR，画出二叉树和后序线索二叉树。后序 （AXBRCMF），再线索化。 5．W={ABCDEFG}，权为{11，14，8，6，13，22，18，26} 构造 W 的哈夫曼树，并求出 WPL。（118） 写出字符哈夫曼编码。 A=010 D=1011 G=111 B=100 E=011 C=1010 F=110 H=00 第七章 图 本章是考试的一个重点，很多应用内容都会涉及到！ 图的基本概念。 图的存储结构：1）数组表示法，邻接矩阵 2）邻接表及逆邻接表 图的遍历 ：1）深度优先，类似于二叉树的先序遍历 2）广度优先，类似于树的层次遍历 图的应用 ：1）最小生成树
Acknowledgement 被軒由05同冰计算机 MS XuWan危费提供现由 bbs. tongji.net宫方网站发布,鹿 费提供给大家使用,禁止任何单位和个人用作其它商业用途! -Andy Xia 2)拓扑排序 3)关键路径 4)最短路径 要掌握图的基本概念:顶点,弧,边,无向图,有向图,邻接点,度,出度,入度。 完全图:有n(n-1)2条边的无向图称为完全图 有向完全图:具有n(n-l)条弧的有向图称为有向完全图 连通图:如果对于图中任意两个顶点都是连通的,则称为连通图 连通分量:无向图中的极大连通子图 强连通图:在有向图G中,如果对于每一对ⅵi,yi,ⅵi∞vj。从ⅵ到v和从v到ⅵ 都存在路径,则称G为强连通图。 强连通分量:有向图中的极大强连通子图称为有向图的强连通分量 生成树:一个连通图的生成树是一个极小连通子图,它含有图中全部顶点,但只有足以 构成一棵树的n-1条边。一棵n个顶点的生成树有且仅有n-1条边 如果一个图有n个顶点和小于n-1条边,则是非连通图。如果它多于n-1 条边,则一定有环。但是,有n-1条边的图不一定是生成树 要掌握图的存储结构:1)数组表示法,邻接矩阵 2)邻接表及逆邻接表 尤其要会画邻接表,逆邻接表,会由邻接表读出某顶点的度,出度,入度。 无向图的邻接矩阵为对称矩阵,有向图的邻接矩阵则不一定对称 要掌握图的遍历的算法 1)深度优先,类似于二叉树的先序遍历 2)广度优先,类似于树的层次遍历 图的应用: 1)最小生成树(各边权值不同,则最小生成树唯一) 要掌握两种典型算法:普里姆算法,克鲁斯卡尔算法。会画出最小生成树。 2)拓扑排序 AOV网,活动优先关系网,其中不能有有向环 拓扑排序方法:在有向图中选一个没有前驱的顶点且输出之。从图中删除该顶 点和所有以它为尾的弧。重复上述两步,直至全部顶点均已输出,或者当前图中不存在无前 驱的顶点为止。后一种情况则说明有向图中存在环 3)关键路径 AOE网是一个带权的有向无环图,其中顶点表示事件,弧表示活动,权表示 活动持续的时间,AOE网可用来估算工程的完成时间。网中只有一个入度为零的点(称为 源点)和一个出度为零的点(叫做汇点)。 AOE网中路径长度最长的路径叫做关键路径 4)最短路径:掌握一道必会的习题 习题: )可判断一个网是否有环的方法:拓扑排序,深度优先搜索,求关键路径。但广度优先搜 索不可以
Acknowledgement: 该资料由 同济计算机 05 MS XuWan 免费提供，现由 bbs.tongji.net 官方网站发布，免 费提供给大家使用，禁止任何单位和个人用作其它商业用途！―――Andy Xia 2）拓扑排序 3）关键路径 4）最短路径 要掌握图的基本概念：顶点，弧，边，无向图，有向图，邻接点，度，出度，入度。 完全图：有 n (n-1)/2 条边的无向图称为完全图。 有向完全图：具有 n (n-1)条弧的有向图称为有向完全图。 连通图：如果对于图中任意两个顶点都是连通的，则称为连通图。 连通分量：无向图中的极大连通子图。 强连通图：在有向图 G 中，如果对于每一对 vi，vj，vi<>vj。从 vi 到 vj 和从 vj 到 vi 都存在路径，则称 G 为强连通图。 强连通分量：有向图中的极大强连通子图称为有向图的强连通分量。 生成树：一个连通图的生成树是一个极小连通子图，它含有图中全部顶点，但只有足以 构成一棵树的 n-1 条边。一棵 n 个顶点的生成树有且仅有 n-1 条边。 如果一个图有 n 个顶点和小于 n-1 条边，则是非连通图。如果它多于 n-1 条边，则一定有环。但是，有 n-1 条边的图不一定是生成树 要掌握图的存储结构：1）数组表示法，邻接矩阵 2）邻接表及逆邻接表 尤其要会画邻接表，逆邻接表，会由邻接表读出某顶点的度，出度，入度。 无向图的邻接矩阵为对称矩阵，有向图的邻接矩阵则不一定对称。 要掌握图的遍历的算法： 1）深度优先，类似于二叉树的先序遍历 2）广度优先，类似于树的层次遍历 图的应用 ： 1） 最小生成树（各边权值不同，则最小生成树唯一） 要掌握两种典型算法：普里姆算法，克鲁斯卡尔算法。会画出最小生成树。 2）拓扑排序 AOV 网，活动优先关系网，其中不能有有向环。 拓扑排序方法：在有向图中选一个没有前驱的顶点且输出之。从图中删除该顶 点和所有以它为尾的弧。重复上述两步，直至全部顶点均已输出，或者当前图中不存在无前 驱的顶点为止。后一种情况则说明有向图中存在环。 3）关键路径 AOE 网是一个带权的有向无环图，其中顶点表示事件，弧表示活动，权表示 活动持续的时间，AOE 网可用来估算工程的完成时间。网中只有一个入度为零的点（称为 源点）和一个出度为零的点（叫做汇点）。 AOE 网中路径长度最长的路径叫做关键路径。 4）最短路径：掌握一道必会的习题。 习题： 1）可判断一个网是否有环的方法：拓扑排序，深度优先搜索，求关键路径。但广度优先搜 索不可以
Acknowledgement 被軒由05同冰计算机 MS XuWan危费提供现由 bbs. tongji.net宫方网站发布,鹿 费提供给大家使用,禁止任何单位和个人用作其它商业用途! -Andy Xia 2)在非连通无向图,共28条边,则至少有几个顶点?(9) 3)所有顶点的入度之和等于所有顶点出度之和的几倍?(1) 4)n个顶点的连通图至少有n-1条边。 5)用邻接矩阵表示n个顶点的无向图,至少有2(n-1)个非零元素。 6)n个顶点的有向强连通图至少有n条边 7)n个有向强连通图,最多有n(n-1)条弧,至少有n条弧 8)有n个顶点的无向图中,边数等于邻接矩阵非零元素个数之和的一半。( right) 在一个无向图中,所有顶点的度之和等于边数的2倍( right) 具有n个顶点的无向图最多有n(n-1)n2度( right) n个顶点的无向图,有小于(n-1)条边,则是非连通图,多于(n-1)条边,则一定有 回路( right) 有(n-1)条边的图肯定都是生成树。( wrong 9)如图 的 画出强连通分量,邻接表,你邻接表。并指出每个顶点的出度,入度 10)如图对称邻接矩阵 画出最小生成树。 11)重点题:如图
Acknowledgement: 该资料由 同济计算机 05 MS XuWan 免费提供，现由 bbs.tongji.net 官方网站发布，免 费提供给大家使用，禁止任何单位和个人用作其它商业用途！―――Andy Xia 2）在非连通无向图，共 28 条边，则至少有几个顶点？（9） 3）所有顶点的入度之和等于所有顶点出度之和的几倍？（1） 4）n 个顶点的连通图至少有 n-1 条边。 5）用邻接矩阵表示 n 个顶点的无向图，至少有 2（n-1）个非零元素。 6）n 个顶点的有向强连通图至少有 n 条边。 7）n 个有向强连通图，最多有 n（n-1）条弧，至少有 n 条弧。 8）有 n 个顶点的无向图中，边数等于邻接矩阵非零元素个数之和的一半。（right） 在一个无向图中，所有顶点的度之和等于边数的 2 倍（right） 具有 n 个顶点的无向图最多有 n（n-1）/2 度（right） n 个顶点的无向图，有小于（n-1）条边，则是非连通图，多于（n-1）条边，则一定有 回路（right） 有（n-1）条边的图肯定都是生成树。（wrong） 9）如图： ○v1 ○v2 ○v5 ○v4 ○v3 画出强连通分量，邻接表，你邻接表。并指出每个顶点的出度，入度。 10）如图对称邻接矩阵： ∞ 17 ∞ ∞ 20 22 ∞ 6 7 ∞ 12 ∞ 11 ∞ ∞ ∞ 19 15 ∞ 34 ∞ 画出最小生成树。 11）重点题：如图
Acknowledgement 被軒由05同冰计算机 MS XuWan危费提供现由 bbs. tongji.net宫方网站发布,鹿 费提供给大家使用,禁止任何单位和个人用作其它商业用途! -Andy Xia 求各城之间到达的最短路径及公里数 若设一个中心,到各城的距离里的最大距离最短。应设在哪里? 若设一个中心,使各城到中心距离里的最大距离最短。应设在哪里? A(0)=010 A(1)=010 A(2)=01016
Acknowledgement: 该资料由 同济计算机 05 MS XuWan 免费提供，现由 bbs.tongji.net 官方网站发布，免 费提供给大家使用，禁止任何单位和个人用作其它商业用途！―――Andy Xia 15 ○1 10 ○2 3 6 8 ○3 2 ○4 4 求各城之间到达的最短路径及公里数。 若设一个中心，到各城的距离里的最大距离最短。应设在哪里？ 若设一个中心，使各城到中心距离里的最大距离最短。应设在哪里？ A（0）= 0 10 ∞ ∞ 15 0 6 ∞ 3 ∞ 0 4 ∞ 8 2 0 A（1）= 0 10 ∞ ∞ 15 0 6 ∞ 3 13 0 4 ∞ 8 2 0 A（2）= 0 10 16 ∞ 15 0 6 ∞ 3 13 0 4 23 8 2 0
Acknowledgement 被軒由05同冰计算机 MS XuWan危费提供现由 bbs. tongji.net宫方网站发布,鹿 费提供给大家使用,禁止任何单位和个人用作其它商业用途! -Andy Xia 0 A(4)=010162020 1010 120 12 0 8 121620 由上图可见,若设一个中心,到各城的距离里的最大距离最短。应设在④,最短为8。 若设一个中心,使各城到中心距离里的最大距离最短。应设在①,最短为9。 附:05年关键路径和最短路径都涉及到了 第八章查找与排序 静态查找:1顺序査找,这种查找的方法必须掌握,要会计算查找平均次数。 2折半(二分法)査找,这种查找的方法必须掌握,要会计算查找平均次数, 要会画出判定二叉树,通过判定二叉树求平均长度 3索引査找,要会计算查找平均长度〔索引长度+顺序查找长度〕。 动态查找 4树表的查找(二叉排序树),重点考点。 1)构造二叉排序树的方法 2)查找算法。 3)删除方法 4)二叉平衡树(AⅥL树),尤其是插入和删除节点的方法。 5)B树,尤其是插入和删除节点的方法 6)B+树的概念,尤其是和B树的区别。 5哈希表,掌握基本方法,重点是处理冲突 1)开放地址法(主要是线性探测) 2)链地址法,了解就行 排序:重点
Acknowledgement: 该资料由 同济计算机 05 MS XuWan 免费提供，现由 bbs.tongji.net 官方网站发布，免 费提供给大家使用，禁止任何单位和个人用作其它商业用途！―――Andy Xia A（3）= 0 10 16 20 9 0 6 10 3 13 0 4 5 8 2 0 A（4）= 0 10 16 20 20 9 0 6 10 10 3 12 0 4 12 5 8 2 0 8 9 12 16 20 由上图可见，若设一个中心，到各城的距离里的最大距离最短。应设在○4 ，最短为 8。 若设一个中心，使各城到中心距离里的最大距离最短。应设在○1 ，最短为 9。 附：05 年关键路径和最短路径都涉及到了 第八章 查找与排序 静态查找： 1 顺序查找，这种查找的方法必须掌握，要会计算查找平均次数。 2 折半（二分法）查找，这种查找的方法必须掌握，要会计算查找平均次数， 要会画出判定二叉树，通过判定二叉树求平均长度。 3 索引查找，要会计算查找平均长度〔索引长度+顺序查找长度〕。 动态查找： 4 树表的查找（二叉排序树），重点考点。 1）构造二叉排序树的方法。 2）查找算法。 3）删除方法。 4）二叉平衡树（AVL 树），尤其是插入和删除节点的方法。 5）B 树，尤其是插入和删除节点的方法。 6）B+树的概念，尤其是和 B 树的区别。 5 哈希表，掌握基本方法，重点是处理冲突。 1）开放地址法（主要是线性探测）。 2）链地址法，了解就行。 排序：重点