Acknowledgement 被軒由05同冰计算机 MS XuWan危费提供现由 bbs. tongji.net宫方网站发布,鹿 费提供给大家使用,禁止任何单位和个人用作其它商业用途! -Andy Xia 同济计算机专业数据结构笔记总结 -是前人根据辅导班笔记做的浓缩,很 有用的,配着教材可拿它做大纲使用了:)有些是我补充的 第一章绪论 1)数据结构是解决非数值计算的问题的。 2)数据的基本单位是数据元素;最小单位是数据项。数据对象是性质相同的数据元素的集 合,是数据的一个子集 3)数据结构的划分通常有四种基本结构: 按性质分为(逻辑,物理结构);按存储方式分为(顺序存储,非顺序存储结构)。 4)顺序存储方式不只用于存储线性结构,比如也可以存储树型结构 5)算法:是对特定问题的求解步骤的一种描述。他的5个特性:有穷性,确定性,可行性 输入,输出。 6)算法和数据结构的关系:算法的设计依靠的是数据逻辑结构,而算法的实现依靠的是数 据物理结构。 ⑦)算法的要求:正确性,可读性,健壮性,效率与低存储量需求。 8)算法原地工作:额外空间相对于输入数据量来说是常数,既不依赖于问题的规模。 9)时间复杂度:最坏的情况下估算算法的一个上界。O(n)在时间上总优于O(n^2) 附:历年基本上没有出现过时间复杂度的计算题目,本章都是些概念题,出现在填空或选择中,在数据结 构填空,判断复习题中都有体现 第二章线性表 在本节中主要研究两种形式的线性表:顺序表和链表。 1)顺序表是随机存储结构的线性表,而单链表是顺序存储结构的线性表 2)顺序表的基本操作(査找,插入,删除)要求会熟练操作,这部分十分简单。 3)单链表分为带头节点的,和不带头节点的链表。这两种链表的基本操作(建立,输出 合并,拆分,插入,删除,逆置)要熟练掌握!尤其是插入和删除时的操作顺序。 4)链表的插入(表头插入法,表尾添加法)要熟练掌握。 5)用链表的插入进行排序 6)链表的逆置 7)循环链表和双向链表也要掌握操作! 8)一般在考试中有一道大题。 第三章栈和队列 在本节中主要研究链栈和顺序栈。 1)链栈是不带头节点的单链表,头指针指向栈顶元素,操作的时候在此添加元素。 2)顺序栈的建立 Typedef struct
Acknowledgement: 该资料由 同济计算机 05 MS XuWan 免费提供，现由 bbs.tongji.net 官方网站发布，免 费提供给大家使用，禁止任何单位和个人用作其它商业用途！―――Andy Xia 同济计算机专业数据结构笔记总结 -----是前人根据辅导班笔记做的浓缩，很 有用的，配着教材可拿它做大纲使用了：）有些是我补充的。 第一章 绪论 1） 数据结构是解决非数值计算的问题的。 2） 数据的基本单位是数据元素；最小单位是数据项。数据对象是性质相同的数据元素的集 合，是数据的一个子集。 3） 数据结构的划分通常有四种基本结构： 按性质分为（逻辑，物理结构）；按存储方式分为（顺序存储，非顺序存储结构）。 4） 顺序存储方式不只用于存储线性结构，比如也可以存储树型结构。 5） 算法：是对特定问题的求解步骤的一种描述。他的 5 个特性：有穷性，确定性，可行性， 输入，输出。 6） 算法和数据结构的关系：算法的设计依靠的是数据逻辑结构，而算法的实现依靠的是数 据物理结构。 7） 算法的要求：正确性，可读性，健壮性，效率与低存储量需求。 8） 算法原地工作：额外空间相对于输入数据量来说是常数，既不依赖于问题的规模。 9） 时间复杂度：最坏的情况下估算算法的一个上界。O（n）在时间上总优于 O（n^2）. 附：历年基本上没有出现过时间复杂度的计算题目，本章都是些概念题，出现在填空或选择中，在数据结 构填空，判断复习题中都有体现。 第二章 线性表 在本节中主要研究两种形式的线性表：顺序表和链表。 1）顺序表是随机存储结构的线性表，而单链表是顺序存储结构的线性表。 2）顺序表的基本操作（查找，插入，删除）要求会熟练操作，这部分十分简单。 3）单链表分为带头节点的，和不带头节点的链表。这两种链表的基本操作（建立，输出， 合并，拆分，插入，删除，逆置）要熟练掌握！尤其是插入和删除时的操作顺序。 4）链表的插入（表头插入法，表尾添加法）要熟练掌握。 5）用链表的插入进行排序。 6）链表的逆置。 7）循环链表和双向链表也要掌握操作！ 8）一般在考试中有一道大题。 第三章 栈和队列 在本节中主要研究链栈和顺序栈。 1） 链栈是不带头节点的单链表，头指针指向栈顶元素，操作的时候在此添加元素。 2） 顺序栈的建立： Typedef struct{
Acknowledgement 被軒由05同冰计算机 MS XuWan危费提供现由 bbs. tongji.net宫方网站发布,鹿 费提供给大家使用,禁止任何单位和个人用作其它商业用途! -Andy Xia Int stacksize 顺序栈是用数组描述栈的一种形式 3)要会判断两种栈的空满。 4)要熟练掌握两种栈的操作(插入,删除)。 5)栈的内容十分重点,应该有一道大体,和若干小题! 在本节中主要研究链队列和循环队列。 )链队列是带头节点的单链表,要熟练掌握链队列的插入和删除元素的操作。 2)循环队列的判断空满是一个考点:在循环队列中,浪费一个元素空间,以尾指针加1 于头指针作为队列满的标志。 队列空: front=rare 队列满:(rare+1)%max=font max是整个循环队列的元素空间个数,包 括浪费的那个元素空间 第四章串 初步了解串的三种结构:顺序存储结构(静态存储结构),链式存储结构(块状存储结 构),堆结构。这章不是特别重点。 1)串的堆结构中,串名的存储映像:串名←(位置,长度) 2)串值存储密度:串值所占的存储位/实际分配存储位。密度越小,操作越方便,但存储占 用的空间大。 第五章数组和广义表 1)数组 矩阵的压缩存储: 1.特殊矩阵。 ①对称阵:n*n对称阵要用n*(n+1)2个存储单元。 存储下三角对称阵。索引位置k=i*(-1)2+j-1 减1是考虑到c语言的数组下表从0开始。i,j是元素的坐标 ②三角阵: 下三角阵:k=i*(-)2+1 上三角阵:k=(2ni)*(i-1)2+-1 ③三对角阵(如下图形式)
Acknowledgement: 该资料由 同济计算机 05 MS XuWan 免费提供，现由 bbs.tongji.net 官方网站发布，免 费提供给大家使用，禁止任何单位和个人用作其它商业用途！―――Andy Xia Int top; Int stacksize; }sqStack; 顺序栈是用数组描述栈的一种形式。 3） 要会判断两种栈的空满。 4） 要熟练掌握两种栈的操作（插入，删除）。 5） 栈的内容十分重点，应该有一道大体，和若干小题！ 在本节中主要研究链队列和循环队列。 1） 链队列是带头节点的单链表，要熟练掌握链队列的插入和删除元素的操作。 2） 循环队列的判断空满是一个考点：在循环队列中，浪费一个元素空间，以尾指针加 1 等 于头指针作为队列满的标志。 队列空：front=rare 队列满：(rare+1)%max=front max 是整个循环队列的元素空间个数，包 括浪费的那个元素空间。 第四章 串 初步了解串的三种结构：顺序存储结构（静态存储结构），链式存储结构（块状存储结 构），堆结构。这章不是特别重点。 1） 串的堆结构中，串名的存储映像： 串名 ÍÎ(位置，长度)。 2） 串值存储密度：串值所占的存储位/实际分配存储位。密度越小，操作越方便，但存储占 用的空间大。 第五章 数组和广义表 1）数组 矩阵的压缩存储： 1． 特殊矩阵。 ○1 对称阵：n*n 对称阵要用 n*(n+1)/2 个存储单元。 存储下三角对称阵。索引位置 k= i*(i-1)/2+j-1 减 1 是考虑到 c 语言的数组下表从 0 开始。i，j 是元素的坐标。 ○2 三角阵： 下三角阵：k= i*(i-1)/2+j-1 上三角阵：k=(2n-i）*(i-1)/2+j-1 ○3 三对角阵 （如下图形式）
Acknowledgement 被軒由05同冰计算机 MS XuWan危费提供现由 bbs. tongji.net宫方网站发布,鹿 费提供给大家使用,禁止任何单位和个人用作其它商业用途! -Andy Xia 0 0081 0 存储三对角阵。索引位置k=2*+-3 2.稀疏矩阵的存储方式。 ①三元组法 ②十字链表法 要了解这两种方法,以及基本应用(矩阵转制,矩阵乘法)。了解即可。 2)重点:广义表:是递归结构,不能分配固定大小 长度:元素或子表的个数。 深度:括号重数。 表头为单元素或子表,表尾必为子表,不是单元素! 这些容易出试题。 附:05年考试中,第四五章均出现在填空判断中,将复习题中的同类题目会做就应该可以了 第六章树和二叉树 1)了解树以及二叉树的相关定义 结点拥有的子树数称为结点的度 树的度是树内各结点的度的最大值。 树中结点的最大层次称为树的深度 2)5个性质(必考内容,容易出现在小题中) 1.在二叉树的第i层上至多有2~(i-1)个结点(p>=1) 2.深度为k的二叉树至多有2^k-1个结点,(k>=1) 3.对任何一棵二叉树T如果其终端结点数为nO,度为2的结点数为n,则n0=n2+1。 4.具有n个结点的完全二又树的深度为[ogn+1。(向下取整) 5.双亲,孩子判断法。 3)满二叉树的定义,完全二叉树的定义
Acknowledgement: 该资料由 同济计算机 05 MS XuWan 免费提供，现由 bbs.tongji.net 官方网站发布，免 费提供给大家使用，禁止任何单位和个人用作其它商业用途！―――Andy Xia 1 2 0 0 0 3 4 5 0 0 0 6 7 8 0 0 0 9 1 2 0 0 0 3 4 存储三对角阵。索引位置 k= 2*i+j-3 2． 稀疏矩阵的存储方式。 ○1 三元组法 ○2 十字链表法 要了解这两种方法，以及基本应用（矩阵转制，矩阵乘法）。了解即可。 2) 重点：广义表: 是递归结构，不能分配固定大小。 长度：元素或子表的个数。 深度：括号重数。 表头为单元素或子表，表尾必为子表，不是单元素！ 这些容易出试题。 附：05 年考试中，第四五章均出现在填空判断中，将复习题中的同类题目会做就应该可以了 第六章 树和二叉树 1）了解树以及二叉树的相关定义： 结点拥有的子树数称为结点的度。 树的度是树内各结点的度的最大值。 树中结点的最大层次称为树的深度。 2）5 个性质（必考内容，容易出现在小题中） 1．在二叉树的第 i 层上至多有 2^(i-1)个结点（i> =1）. 2．深度为 k 的二叉树至多有 2^k-1 个结点，（k>=1）. 3．对任何一棵二叉树 T，如果其终端结点数为 n0,度为 2 的结点数为 n2，则 n0=n2+1。 4．具有 n 个结点的完全二叉树的深度为[logn]+1。（向下取整） 5．双亲，孩子判断法。 3） 满二叉树的定义，完全二叉树的定义
Acknowledgement 被軒由05同冰计算机 MS XuWan危费提供现由 bbs. tongji.net宫方网站发布,鹿 费提供给大求使用,禁止任何单位和个人用作其它离业用途!--- Andy xia 4)完全二叉树的特点 叶子结点只可能在层次最大的两层上出现 2.对任何一结点,若其右分支下的子孙的最大层次为1,则其左分支下的子孙的最 大层次必为l或H+1。 3.完全二叉树不一定是满二叉树 5)存储结构 1.顺序存储,适用于完全二叉树。 2.链式存储,怎么建立,基本操作,重点 3.静态二叉链表,三叉链表,大致了解。 6)遍历二叉树 递归遍历二叉树。如下是先序遍历 Void Order(BiTree T) f if(D)i Order(T->Lchild) Order(T->Rchild) 先序遍历1,2,3 中序遍历2,1,3 后序遍历2,3,1 逆先序遍历1,3,2 逆中序遍历3,1,2 逆后序遍历3,2,1 非递归遍历二叉树。掌握先序和中序。 先序 while(p) stop++, P=P->Chil p=p->Rchild; While(s. toplIP)
Acknowledgement: 该资料由 同济计算机 05 MS XuWan 免费提供，现由 bbs.tongji.net 官方网站发布，免 费提供给大家使用，禁止任何单位和个人用作其它商业用途！―――Andy Xia 4） 完全二叉树的特点： 1．叶子结点只可能在层次最大的两层上出现； 2．对任何一结点，若其右分支下的子孙的最大层次为 l，则其左分支下的子孙的最 大层次必为 l 或 l+1。 3．完全二叉树不一定是满二叉树。 5）存储结构 1．顺序存储，适用于完全二叉树。 2．链式存储，怎么建立，基本操作，重点。 3．静态二叉链表，三叉链表，大致了解。 6）遍历二叉树 1．递归遍历二叉树。如下是先序遍历。 Void Xorder (BiTree T) { if (T) { Visit (T->data); ……………………….○1 Xorder(T->Lchild); ……………………….○2 Xorder(T->Rchild); ……………………….○3 }} 先序遍历 1，2，3 中序遍历 2，1，3 后序遍历 2，3，1 逆先序遍历 1，3，2 逆中序遍历 3，1，2 逆后序遍历 3，2，1 1． 非递归遍历二叉树。掌握先序和中序。 先序： P=root; do{ while(P) { visit(P); s.top++; s.base[s.top]=p; P=P->Lchild; } If (s.top) { p=s.base[s.top]; s.top--; p=p->Rchild; } While (s.top||P)
Acknowledgement 被軒由05同冰计算机 MS XuWan危费提供现由 bbs. tongji.net宫方网站发布,鹿 费提供给大家使用,禁止任何单位和个人用作其它商业用途! -Andy Xia 中序 P=root while(p) s base[s. top]=p: P=P->Lchild p-s base(s top]: While(s top!IP) 7)找遍历的第一和最后一个结点 先序:第一个是根结点,最后一个要会编程寻找 If (P)i While(p->Lchild lp->Rchild) If(p->Rchild) p=p->Rchild Else p->Lchild 后序:第一个要会编程寻找,最后一个是根结点。 中序:第一个是最左边没有左子树的结点,最后一个是最右边无右子树的结点 8)线索二叉树(重点,必考) 要熟练掌握线索化的方法。 中序遍历线索二叉树寻找任一结点x的前驱和后继的方法。 寻找前驱 While(p->RTag==0) P=p->Rchild; Else p=x->Lchild
Acknowledgement: 该资料由 同济计算机 05 MS XuWan 免费提供，现由 bbs.tongji.net 官方网站发布，免 费提供给大家使用，禁止任何单位和个人用作其它商业用途！―――Andy Xia 中序： P=root; do{ while(P) { s.top++; s.base[s.top]=p; P=P->Lchild; } If (s.top) { p=s.base[s.top]; s.top--; visit(p); p=p->Rchild; } While (s.top||P) 7) 找遍历的第一和最后一个结点 先序：第一个是根结点，最后一个要会编程寻找。 P=root; If (P) { While (p->Lchild||p->Rchild) { If (p->Rchild) p= p->Rchild; Else p->Lchild; } } 后序：第一个要会编程寻找，最后一个是根结点。 中序：第一个是最左边没有左子树的结点，最后一个是最右边无右子树的结点。 8）线索二叉树（重点，必考） 要熟练掌握线索化的方法。 中序遍历线索二叉树寻找任一结点 x 的前驱和后继的方法。 寻找前驱： If (x->LTag==0) { p=x->Lchild; While (p->RTag==0) P=p->Rchild; } Else p=x->Lchild;
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）链地址法，了解就行。 排序：重点