自考02142数据结构导论密训高频考点重点汇总.doc

《自考02142数据结构导论密训高频考点重点汇总.doc》由会员分享，可在线阅读，更多相关《自考02142数据结构导论密训高频考点重点汇总.doc（15页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第一章 概论知识点名称内容引言2 算法+数据结构=程序 自考押题 vx 344647 公众号/小程序 顺通考试资料1.数据结构指一组相互之间存在一种或多种特定关系的数据的组织方式和它们在计算机内的存储方 式， 以及定义在该组数据上的一组操作。数据 、数据元素和数据项1.数据： 所有被计算机存储 、处理的对象。2.数据元素： 数据的基本单位， 是运算的基本单位 。常常又简称为元素。3.数据项是数据的不可分割的最小标识单位。在数据库中数据项又称为字段或域。4.从宏观上看， 数据 、数据元素和数据项实际上反映了数据组织的三个层次， 数据可由若干个数据元 素组成， 而数据元素又可由若干个数据项组成。5

2、.数据结构是相互之间存在一种或多种特定关系的数据元素的集合 。它包括数据的逻辑结构 、数据的 存储结构和数据的基本运算。数据的逻辑 结构1.数据的逻辑结构： 与数据元素本身的形式 、 内容 、相对位置 、个数无关 。2.集合： 任意两个结点之间都没有邻接关系， 组织形式松散。3.线性结构： 结点按逻辑关系依次排列形成一条 “链”， 结点之间一个一个依次相邻接。4.树形结构： 具有分支、层次特性， 其形态像自然界中的树， 上层的结点可以和下层多个结点相邻接， 但下层结点只能和上层的一个结点相邻接。5 图结构： 最复杂， 其中任何两个结点都可以相邻接。数据的存储 结构1.数据的逻辑结构在计算机中的

3、实现称为数据的存储结构。2.顺序存储方式： 指所有存储结点存放在一个连续的存储区里。利用结点在存储器中的相对位置来表 示数据元素之间的逻辑关系。3.链式存储方式： 指每个存储结点除了含有一个数据元素外， 还包含指针， 每个指针指向一个与本结 点有逻辑关系的结点， 用指针表示数据元素之间的逻辑关系。4.除了上述两种存储方式之外， 还有索引存储方式和散列存储方式。但主要的存储方式是： 顺序存储 方式和链式存储方式。运算1.运算是指在某种逻辑结构上施加的操作， 即对逻辑结构的加工。2.运算包括： 建立 、查找 、读取 、插入和删除等 。 3.线性表 、栈和队列中的元素具有相同的逻辑结构（即线性结构）

4、， 但有不同的运算集， 它们是不同 的数据结构。算法分析1.正确性： 能正确地实现预定的功能， 满足具体问题的需要。2.易读性： 易于阅读 、理解和交流， 便于调试 、修改和扩充。3.健壮性： 即使输入非法数据， 算法也能适当地做出反应或进行处理， 不会产生预料不到的运行结果。4.时空性： 指该算法的时间性能（或时间效率） 和空间性能（或空间效率） ， 前者是算法包含的计算 量， 后者是算法需要的存储量。时间复杂度1.常见的时间复杂度的比较：O（1）O（log2n）O（n）O（n2）O（n3）O（n4）next 。某带有头结点的单链表的头指针为 head， 判断该单链表为非空的条件是 head

5、-next!=NULL 。线性表的基本运算在单链表上的实现1.初始化（1）假设单链表的类型定义如下： typedef struct node DataType data;2/15struct node *next;node ， *LinkList;算法 InitiateLinkList（）实现单链表的初始化：LinkList InitiateLinkList（ ） /建立一个空的单链表 LinkList head; /头指针head=malloc（sizeof（node）; /动态构建一个结点， 并定义为头结点head-next=NULL;return head;/空表由一个头指针 head

6、和一个头结点组成。head 指向新创建的结点， 即头结点。一个空单链表仅有一个头结点， 它的指针域为 NULL。（2）在带头结点的单链表 L 中， 第一个数据元素结点的指针为 L-next。（ 3）设有一个单链表， 若结点的指针域为 next， 则指针 p所指的结点为最后一个结点的条件是 p-next=NULL 。工作指针 p-next 为 NULL 时， 说明已经走到了表的尾部， 这时已完成对所有 结点的访问。2.插入 p 指向的新结点的操作（1）设 r 指向单链表的最后一个结点， 要在最一个结点之后插入 s 所指的结点， 需执行的语句序列是 r-next=s;r=s;r-next=NULL

7、。（ 2 ） 将 一 个 由 指 针 q 指 向 的 结 点 插 在 单 链 表 中由 指 针 p 所 指 向 的 结 点 之 后 的 操 作 是： q-next=p-next;p-next=q;。3.删除*p 结点的操作在一个单链表中， 已知指针 q 指向指针 p 所指结点的前驱结点， 则删除*p 结点的操作语句是 q-next=p-next。循环链表1.在单链表中， 如果让最后一个结点的指针域指向第一个结点可以构成循环链表。（1）只有头指针 head1）判断 P 所指结点为尾结点的条件： p-next=head2）判断指针 P 所指结点为首结点的条件： p=rear-next-next3）

8、判断链表是否为空的条件： head-next=head3/15（2）有头指针 head 和尾指针 rear说明： rear-next 指向头结点 head。在 带 有 头 结 点 的 循 环 链 表 中， 尾 指 针 为 rear， 判 断 指 针 P 所 指 结 点 为 首 结 点 的 条 件 是 p=rear-next-next。（3）只有尾指针 rear1）删除表首结点的操作可表示为：p=rear-next-next;rear-next-next=p-next;free（p）;2）已知尾指针的单向循环链表中，在第一个结点后面插入一个新结点，该算法的时间复杂度为 O（1）。双向循环链 表1

9、.每个结点有两个指针， next 指针指向直接后继结点； prior 指针指向直接前驱结点。2.带头结点的双向循环链表 L 为空的条件： （L-next=L）&（L-prior=L）。3.删除（1）设 p 指向待删结点， 删除*p 的操作：p-prior-next=p-next;/语句p-next-prior=p-prior;/语句free（p）;（2）这两个语句的执行顺序可以颠倒。4.插入在 p 所指结点的后面插入一个新结点*t 的操作:t-prior=p;t-next=p-next;4/15p-next-prior=t;p-next=t;顺序实现与链接实现的比较顺序表时间复杂度单链表时间复

10、杂度按位置查找运算O（1）O（n）定位运算O（n）O（n）插入 、删除运算O（n）O（n）第三章 栈 、队列和数组知识点名称内容栈 、队列和 数组1.栈和队列可看作是特殊的线性表 。它们是运算受限的线性表 。栈和队列也同样有两种存储结构（顺序存储结构和链式存储结构）。2.栈和队列可看作是特殊的线性表。（1）函数的嵌套调用和程序递归的处理都是用栈来实现的。（2）操作系统中进程调度 、网络管理中的打印服务等都是用队列来实现的。栈的基本概 念1.栈： 这种线性表上的插入和删除运算限定在表的某一端进行 。允许进行插入和删除的一端称为栈顶， 另一端称为栈底。不含任何数据元素的栈称为空栈 。2.栈的修改原

11、则： 后进先出， 栈又称为后进先出线性表， 简称后进先出表。3.栈的基本运算：（1）初始化 InitStack（S）： 构造一个空栈 S；（2）判栈空 EmptyStack（S）： 若栈 S 为空栈， 则结果为 1， 否则结果为 0；（3）进栈 Push（S， x）： 将元素 x 插入栈 S 中， 使 x 成为栈 S 的栈顶元素；（4）出栈 Pop（S）： 删除栈顶元素；（5）取栈顶 GetTop（S）： 返回栈顶元素。栈的顺序实 现1.当空栈， 栈顶下标值 top=0， 如果此时做出栈运算， 则产生 “下溢” 。当栈中的数据元素已经填满 了， 如果再进行进桟操作， 会发生 “上溢” 。2.初

12、始化Int InitStack（SeqStk *stk）stk-top=0;return 1;3.判栈空Int EmptyStack（SeqStk *stk）/若栈为空， 则返回值 1， 否则返回值 0if（stk-top=0）return 1;else return 0;5/154.进栈Int Push（SeqStk *stk， DataType x）/若栈未满， 元素 x 进栈 stk 中， 否则提示出错信息if（stk-top=maxsize-1）/判断找是否满 error（ “栈已满”）;return 0;else stk-top+; stk-datastk-top=x;/栈未满， t

13、op 值加 1/元素 x 进桟return 1;5.出栈Int PopSeqStk *stk） if（EmptyStack（stk） /判断是否下溢（栈空） error（ “下溢”）;return 0;else stk-top-;/未下溢， 栈顶元素出栈/top 值减 1return 1;也可以理解为： 原栈顶的下一个结点成为新的栈顶， 即 top=top-next;6.取栈顶元素DataType GetTop（SeqStk*stk）/取栈顶数据元素， 栈顶数据元素逋过参数返回if（EmptyStack（stk） ）return NULLData; /栈空， 返回 NULLDataelsere

14、turn stk-datastk-top; /返回栈顶数据元素栈的链接实 现1.栈的链接实现称为链栈，链栈可以用带头结点的单链表来实现 。LS 指向链表的头结点， 首结点是栈 顶结点， LS-next 指向栈顶结点， 尾结点为栈底结点。2.出栈操作始终是栈顶结点出栈， 即删除头结点之后的结点， 如下图：6/15原栈顶的下一个结点成为新的栈顶， 即top=top-next; 3.链栈由于采用了链表的方式作为存储方式， 各结点通过链域的连接组成栈， 由于每个结点空间都是 动态分配产生， 链栈不用预先考虑容量的大小。4.入栈时， 使用 malloc 申请空间后， 用指针相连接， 所以节点个数没有限制

15、； 但是出栈时， 如果栈中 的元素个数为 0， 则不能继续出栈， 所以需要判断当前栈是否为空 。综上， 链表不需要判满， 只需要 判定是否为空即可。5.链栈 LS 中， Ls 一next 指向栈顶结点， 则新结点 * P 入栈的操作为： P 一next=LS 一next； 和 LS-next=p； 。递归与栈1.将递归形式描述的算法改写为功能等价的非递归形式描述的算法， 通常应设置的输助结构是栈。队列的基本 概念1.队列是一种先进先出的线性表， 新加入的数据元素插在队列尾端， 出队列的数据元素在队列首部被 删除。队列的顺序 实现1.循环队列： 为了避免元素的移动， 将存储队列元素的一维数组首尾

16、相接， 形成一个环状 。2.入队列操作语句： SQ.rear=（SQ.rear+1）%maxsize;SQ.dataSQ.rear=x;3.出队列赋值语句： SQ.fronts（SQ.front+1）%maxsize;4.循环队列满： （ （CQ.rear+1）%maxsize=CQ.front）成立。5.队列空条件： （CQ.rear=CQ.front）成立。6.数组 Qn表示一个循环队列， 设 f 为队列中第一个元素的位置， r 为队列中实际队尾的位置加 1， 则 队列中元素个数的公式： （r-f+n）%n队列的链接 实现1. 由于链接实现需要动态申请空间， 故链队列在一定范围内不会出现队

17、列满的情况。2.当（LQ.front=LQ.rear）成立时， 队列中无数据元素， 此时队列为空 。带头结点的链队列中， 队 列头和队列尾指针分别为 front 和 rear， 则判断队列空的条件为front=rear 。 3.在实现队列的链表结构中， 仅设置尾指针的单循环链表的时间复杂度最优 。数组的存储 结构1.数组元素的存储位置是下标的线性函数： 对于二维数组 amn， 如果每个元素占 k 个存储单元， 以行为主序为例， 讨论数组元素 aij位置与下标的关系。2. 由于下标从 0 开始， 元素 aij之前已经有 i 行元素， 每行有 n 个元素， 在第 i 行， 有 j+1 个元素 ，

18、总共有 n*i+j+1 个元素，第一个元素与 aij相差 n*i+j+11 个位置，故 aij的位置为：loci，j=loc0， 0+（n*i+j）*k。矩阵的压缩 存储1.为了节省存储空间， 对这类矩阵采用多个值相同的元素只分配一个存储空间， 零元素不存储的策略， 这一方法称为矩阵的压缩存储。2.特殊矩阵7/15（1）对称矩阵 。一个 n 阶方阵 A 中的元素满足下述条件： aij=aji0i， jn-1 。假设以一维数组 Mn （n+1）/2作为 n 阶对称矩阵A 的存储结构。（2）三角矩阵 。以主对角线为界的上（下） 半部分是一个固定的值 c 或零。1）为存储 n 阶的三角矩阵， 采用数

19、组 Mn（n+1）/2， 把矩阵中上（下） 三角部分的 n（n+1）/2 个 元素存储在数组 M0 Mn（n+1）/2-1的 n（n+1）/2 个单元中， 其中 c 若非 0， 则存放到数组的Mn（n+1）/2中。2）上三角矩阵中元素 aij在数组 M 中的位置对应关系：3.稀疏矩阵： 非零元素个数很少的矩阵 。矩阵压缩存储主要是为了节省存储空间 。三元组表示法： 用三个项来表示稀疏矩阵中的非零元素 aij， 即（i， j， aij）， 其中 i 表示行序号， j 表示 列序号， aij是非零元素的值， 通常称为三元组。第四章 树和二叉树知识点名称内容树的概念1.树是 n（n 多 0）个结点的

20、有限集合， 一棵树满足以下两个条件：（1）当 n=0 时， 称为空树；（2）当 n0 时， 有且仅有一个称为根的结点， 除根结点外， 真余结点分 m（m0）个互不相交的非 空集合 T1， T2， ， Tm， 这些集合中的每一个都是一棵树， 称为根的子树 。树的相关术 语1.结点的度： 树上任一结点所拥有的子树的数目称为该结点的度。2.叶子： 度为0 的结点称为叶子或终端结点。3.树的度： 一棵树中所有结点的度的最大值称为该树的度。一个结点的子树的根称为该结点的孩子（或称子结点）。相应地该结点称为孩子的双亲（也称父结点）。 父结点相同的结点互称为兄弟。4.结点的层次： 从根开始算起， 根的层次为

21、 1， 其余结点的层次为其双亲的层次加 1。 5.树的高度： 一棵树中所有结点层次数的最大值称为该树的高度或深度 。 6.对于任一个树都有： 结点数=分支数+1。二叉树的基 本概念1.二叉树是 n（n0）个元素的有限集合， 该集合或者为空， 或者由一个根及两棵互不相交的左子树 和右子树组成， 其中左子树和右子树也均为二叉树 。2.左右子树次序不可换， 都可为空。二叉树的性1.满二叉树： 深度为 k（k1）且有 2k-1 个结点的二叉树称为满二叉树 。由性质 2 知， 满二叉树上的8/15质（2）性质 2： 深度为 h（h1）的二叉树中至多含有 2 -1 个结点。i-1结点数已达到了二叉树可以容

22、纳的最大值 。2.完全二叉树： 如果对满二叉树按从上到下， 从左到右的顺序编号， 并在最下一层删去部分结点（删 后最后一层仍有结点） ， 如果删除的这些结点的编号是连续的且删除的结点中含有最大编号的结点， 那么这棵二叉树就是完全二叉树 。3.具体性质：（1）性质 1： 二叉树的第 i（i1）层上至多有 2 个结点。 h（3）性质 3： 若在任意一棵二叉树中， 若度数为 0 的结点（叶结点） 个数为 n0， 度数为 2 的结点个 数为 n0=n2+1。（4）性质 4： 具有 n 个结点的完全二叉树深为 log2n +1。（5）性质 5： 如果将一棵有 n 个结点的完全二叉树按层编号， 按层编号是

23、指： 将一棵二叉树中的所 有 n 个结点按从第一层到最大层， 每层从左到右的顺序依次标记为 1， 2， ， n 。则对任一编号为 i （1in）的结点 A 有：1）当 i=1 时， 该结点 A 为根， 它无双亲结点 。当 i1 时， 该结点 A 的双亲结点的编号为 i/2 。2）若 2in， 则结点 A 既无左孩子， 也无右孩子； 否则A 的左孩子的编号为 2i；3）若 2i+1n， 则结点 A 无右孩子； 否则， A 的右孩子的编号为 2i+1 。二叉树的顺 序存储结构1.二叉树的顺序存储结构可以用一维数组来实现。2.如果需要顺序存储的非完全二叉树， 首先必须用某种方法将其转化为完全二叉树，

24、 为此可增设若干 个虚拟结点。会造成了空间的浪费 。二叉树的链 式存储结构1.二叉树有不同的链式存储结构， 其中最常用的是二叉链表与三叉链表。2.二叉链表： 具有 n 个结点的二叉树中， 共有 2n 个指针域， 其中只有 n-1 个用来指向结点的左 、右 孩子（因为没有指向根结点的指针域） ， 其余的 n+1 个指针域为 NULL。二叉树遍历 的递归实现1.先序遍历2.中序遍历3.后序遍历（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树 。（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树 。（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。应用举例1.由一个

25、二叉树的后序序列和中序序列， 可以唯一确定一棵二叉树 。2.由一个二叉树的先序序列和中序序列， 也可以唯一确定一棵二叉树。3.必须要有中序序列。树的存储结1.孩子链表表示法：9/15构 （1）树上的一个结点 X以及该结点的所有孩子结点组成一个带头结点的单链表。（2）头结点含有两个域： 数据域和指针域 。其中， 数据域用于存储结点 X 中的数据元素， 指针域用 于存储指向 X第一个孩子结点的指针 。（3）表结点也含两个域： 孩子域（child）和指针域（next）， 孩子域存储其中一个孩子的序号， 指 针域指向其下一个孩子的结点。2.孩子兄弟链表表示法（1）存储时每个结点除了数据域外， 还有指向

26、该结点的第一个孩子和下一个兄弟结点的指针。（2）孩子兄弟链表的结构形式与二叉链表完全相同，但结点中指针的含义不同。二叉链表中结点的左、 右指针分别指向左 、右孩子； 而孩子兄弟链表中结点的两个指针分别指向孩子和兄弟。3.双亲表示法由一个一维数组构成 。数组的每个分量包含两个域： 数据域和双亲域 。数据域用于存储树上一个结点 中数据元素， 双亲域用于存储本结点的双亲结点在数组中的序号（下标值）。树 、森林与二叉树的关系1.树转换成二叉树（1）将所有兄弟结点连接起来；（2）保留第一个兄弟结点与父结点的连接， 断开其他兄弟结点与父结点的连接， 然后以根结点为轴心 按顺时针的方向旋转 45角。2.森林

27、转换成二叉树（1）将每棵树转换成相应的二叉树；（2）将（1）中得到的各棵二叉树的根结点看作是兄弟连接起来.3.二叉树转换成森林在待转换的二叉树中， 断开根结点与右孩子的连线， 得到两棵二叉树， 其中一棵是以二叉树 B 的根结 点为根的二叉树， 另一棵是以根结点的右孩子 E为根结点的二叉树 。森林的遍历1.先序遍历森林2.中序遍历森林（1）访问森林中第棵树的根结点；（2）先序遍历森林第一棵树的根结点的子树组成 的森林；（3）先序遍历除去第一棵树之外其余的树组成的 森林。（1）中序遍历森林中第一棵树的根结点的子树组 成的森林；（2）访问第裸树的根结点；（3）中序遍历除去第一棵树之外其余的树组成的

28、森林。分类与判定 树1.分类： 一种常用运算， 其作用是将输入数据按预定的标准划分成不同的种类。2 判定树： 用于描述分类过程的二叉树 。哈夫曼（ Huffman）树与哈夫曼算法1.给定一组值 p1， pk， 如何构造一棵有 k 个叶子且分别以这些值为权的判定树， 使得其平均比较次数 WPL 最小。满足上述条件的判定树称为哈夫曼树 。2.平均比较次数：3.哈夫曼算法：（1） 由给定的值p1， ， pk构造森林 F=T1， ， Tk， 其中每个 Ti 为一棵只有根结点且其权为 pi 的二叉树 。10/15（2）从 F 中选取根结点的权最小的两棵二叉树 Ti 和 Tj， 构造一棵分别以 Ti 和

29、Tj 为左 、右子树的新 的二叉树 Th， 置 Th 根结点的权为 Ti 和 Tj 根结点的权值之和。（3）从 F 中删去 Ti 、Tj， 并将 Th 加入 F 。若 F 中仍多于一棵二叉树， 则返回， 直到 F 中只含一 棵二叉树为止， 这棵二叉树就是哈夫曼树 。4.结论：最终求得的哈夫曼树中共有结点总数：2n-1 个 。其中，n 个叶结点是初始森林中的 n 个结点，合并n-1 次共产生 n-1 个新结点， 且哈夫曼树中没有度数为 1 的分支结点。哈夫曼编码1.将哈夫曼树中每个结点的左分支标志 “0”， 每个结点的右分支标志为 “1”， 这样， 从根到每个叶 结点形成序列， 将该序列作为叶结

30、点对应字符的编码， 由此得到的二进制编码称为哈夫曼编码。第五章 图知识点名称内容图的定义和 术语1.在图结构中， 任意两个结点之间都可能相关， 即结点之间的邻接关系可以是任意的 。没有顶点的不 叫图， 故图最少有一个顶点。2.图的分类（1）无向完全图： 任何两点之间都有边的无向图称为无向完全图 。一个具有 n 个顶点的无向完全图的 边数为 n（n-1）/2。（2）有向完全图： 任何两点之间都有弧的有向图称为有向完全图 。一个具有 n 个顶点的有向完全图的 弧数为 n（n-1）。3.度无向图中顶点 v 的度是与该顶点相关联的边的数目， 记为 D（v） 。D（v）=ID（v）+OD（v） 。 （1

31、）入度： 如果 G 是一个有向图， 则把以顶点 v 为终点的弧的数目称为 v 的入度， 记为 ID（v）； （2） 出度： 把以顶点 v 为始点的弧的数目称为 v 的出度， 记为 OD（v）。4.连通在无向图中， 如果从顶点 v 到顶点 v有路径， 则称 v 和 v是连通的。5.连通图如果图中的任意两个顶点 vi 和 vj 都是连通的， 则称 G 为连通图 。6.连通分量是无向图中的极大连通子图。7.强连通图对于有向图来说， 如果图中任意一对顶点 vi 和 vj（其中 ij）都有顶点 vi 到顶点 vj 的路径， 也有从 vj 到vi 的路径， 即两个顶点间双向连通。8.强连通分量有向图的极大

32、强连通子图9.生成树一个连通图的生成树，是含有该连通图的全部顶点的一个极小连通子图 。若连通图 G 的顶点个数为 n， 则 G 的生成树的边数为 n-1 。如果边数大于 n-1， 则一定有环 。如果边数小于 n-1， 则不一定连通 。 10.树形结构中， 结点间有层次关系， 每一层结点只能和上一层中的至多一个结点相关， 但可能和下一 层的多个结点相关 。图结构中， 任意两个结点之间都可能相关， 即结点之间的邻接关系可以是任意的。邻接矩阵1.用矩阵来描述图中顶点之间的关联关系， 其中11/152.无向图的邻接矩阵是一个对称矩阵 。 3.有向图：（1）顶点 Vi 的出度 OD（vi）是邻接矩阵中第

33、 i 行元素之和。（2）顶点 Vi 的入度 ID（vi）是邻接矩阵中第 i 列元素之和。邻接表1.邻接表是顺序存储与链式存储相结合的存储方法。图的遍历1.深度优先搜索（1）类似于树的先序遍历 。（2）基本思想： 假定以图中某个顶点 vi为出发点， 首先访问出发点vi， 然后任选一个 vi 的未访问过 的邻接点 vj， 以 vj 为新的出发点继续进行深度优先搜索， 依此类推， 直至图中所有顶点都被访问过。 深度优先搜索遍历类似于树的先序遍历。（3）结论采用邻接矩阵作为存储结构的图的时间复杂度： O（n2）， n 为图的顶点数 。采用邻接表作为存储结构的图的时间复杂度： O（n+e）， n为图的顶

34、点数， e 为图的边数。2.广度优先搜索（1）类似于树的按层次遍历的过程。（2）基本思想： 从图中某个顶点 vi 出发， 在访问了 vi 之后依次访问vi的所有邻接点， 然后依次从这 些邻接点出发按广度优先搜索方法遍历图的其他顶点， 重复这一过程， 直至所有顶点都被访问到。最小生成树1.一个图的最小生成树是图所有生成树中权总和最小的生成树 。2.最小生成树算法分析：（1）Prim 算法1）初始化： U=u0 。其中 U 为一个新设置的顶点的集合， 初始 U 中只含有顶点 u0， 这里假设在构 造最小生成树时， 从顶点u0 出发；2）对所有 uU， vV-U（其中 u， v 表示顶点） 的边（u

35、， v）中， 找一条权最小的边（u， v）， 将这条边加入到集合 T 中， 将顶点 v加入到集合 U 中；3）如果 U=V， 则算法结束； 否则重复第 2）3）步。（2）克鲁斯卡尔（Kruskal）算法1）设 G=(V， E)， 令最小生成树初始状态为只有 n 个顶点而无边的非连通图 T= （V， ）， 每个顶 点自成一个连通分量；2）在 E 中选取代价最小的边，若该边依附的顶点落在 T 中不同的连通分量上，则将此边加入到 T 中， 否则， 舍去此边， 选取下条代价最小的边；3）依此类推， 重复 2）， 直至 T 中所有顶点都在同连通分量上为止。3.Dijkstm 算法求单源最短路径问题，即从

36、一个点到所有其他顶点的最短路径。Dijkstra 算法的思想是 按照最短路径长度递增的方法产生从一点到其他顶点的最短路径 。拓扑排序1.如果以图中的顶点来表示活动， 有向边表示活动之间的优先关系， 这种用顶点表示活动的有向图称 为 AOV 网。AOV 网中的弧表示了活动之间存在着的制约关系。12/152.拓扑排序算法的时间复杂度为 O（n+e）， n 是图的顶点个数， e 是图的弧的数目。 3.完成拓扑排序的前提条件是AOV 网中不允许出现回路。第六章 查找知识点名称内容基本概念1.查找表（SearchTable）是由同一类型的数据元素构成的集合， 它是一种以查找为 “核心”， 同时包括其他运

37、算的非常灵活的数据结构 。2.其分类有：（1）静态查找表： 建表 、查找 、读表中元素；（2）动态查找表： 初始化 、查找 、读表中元素 、插入 、删除。顺序表上的 查找1nii1.静态查找表最简单的实现方法是以顺序表作为存储结构， 即链式存储结构。2. “查找成功时的平均查找长度”（记为 ASL）：ASL PiCi， 其中， Pi 为查找第 i 个元素（即给定值 key 与顺序表中第 i 个元素的键值相等） 的概n率， 且Pi 1， Ci表示在找到第 i 个元素时， 与给定值已进行比较的键值个数。1有序表上的 查找n1.有序表： 如果顺序表中数据元素是按照键值大小的顺序排列的， 则称为有序表

38、 。适用于二分查找。2.二分查找： 用给定值 key 与处在中间位置的数据元素 T.elemmid的键值 T.elemmid.key 进行比 较， 可根据三种比较结果区分三种情况：（1）key=T.elemmid.key， 查找成功， T.elemEmid即为待查元素；（2）keyT.elemmid.key， 说明若待查元素若在表中， 则一定排在 T.elemmid之后。 3.平均查找长度二分查找的平均查找长度为ASLb n 1 log2 n 1 1故二分查找算法的平均时间复杂度为： O（log2n）。索引顺序表 上的查找1.索引顺序表由两部分组成： 一个是顺序表， 另一个是索引表。二叉排序树

39、1.定义： 一棵二叉排序树（又称二叉查找树）或者是一棵空二叉树， 或者是具有下列性质的二叉树：（1）若它的左子树不空， 则左子树上所有结点的键值均小于它的根结点键值；（2）若它的右子树不空， 则右子树上所有结点的键值均大于它的根结点键值；（3）根的左 、右子树也分别为二叉排序树。2.二叉排序树上的平均查找长度是介于 O（n）和 O（log2n）之间的。散列表1.数据元素的键值和存储位置之间建立的对应关系 H 称为散列函数， 用键值通过散列函数获取存储位 置的这种存储方式构造的存储结构称为散列表。2.设有散列函数 H 和键值 k1 、k2（k1k2）， 若 H（k1）=H（k2）， 则这种现象称为 “冲突”， 且 称键值 k1 和 k2 互为同义词 。常用散列法1.数字分析法又称数字选择法， 其方法是收集所有可能出现的键值， 排列在一起， 对键值的每一位进行分析， 选择13