西安交通大学大数据结构复习资料
第一章绪论
1、数据结构的主要研究内容
①数据的逻辑结构--数据关系之间的逻辑关系
②数据的存储结构--数据的逻辑结构在计算机中的表示
2、数据逻辑结构的种类：集合、线性表、树和图的性质和特点。
?集合结构中的元素是各自独立的，元素之间没有联系
?线性结构中的元素是一个接一个串联起来的，它有一个头元素和一个尾元素，其余为中间元素；每个中间元素既有前驱元素，又有后继元素
?在树结构中，树根结点只有后继结点，而没有前驱结点；除树根结点外，每个结点都有唯一一个前驱结点，又称为是父结点或双亲结点
?在图结构中，每个结点或称顶点都可以有任意多个前驱结点和任意多个后继结点。
?树结构是图结构的特例，线性结构是树结构的特例。为了区别于线性结构，时常把树结构和图结构称为非线性结构。
3、数据结构的二元组定义，能根据给出的二元组来判断数据的逻辑结构类型。
?集合结构中的元素集合K和二元关系R分别为：
K={A，B，C，D，E，F，G}
R={ }
?线性结构中的元素集合K和二元关系R分别为：
K={A，B，C，D，E，F，G}
R={
?树结构中的元素集合K和二元关系R分别为：
K={A，B，C，D，E，F，G}
R={
?图结构中的元素集合K和二元关系R分别为：
K={A，B，C，D，E，F，G}
R={
4、了解数据的几种存储结构（物理结构）及它们各自的性质和特点。
（1）顺序的方法: 将逻辑上相邻的元素存储到物理上相邻的存储位置. 常用于线性的数据结构.
（2）链式结构：给结点附加一个指针字段, 指出其后继节点的位置, 即存放结点的存储单元分为两部分:
（3）散列（hashing) 结构：散列的方法是用结点的关键字值直接计算出结点的存储地址。这个取值函数也称为散列函数。
5、数据的逻辑结构、存储结构和总的数据结构之间的关系
?逻辑结构相同，但存储结构不同，则认为是不同的数据结构。如顺序表和链表具有相同的逻辑结构，但存储结构分别为顺序结构和链表结构
6、算法的设计要求有那些，会结合实际的语言设计来说明这些要求
1）正确性：对于合法的输入产生符合要求的输出；
2）可读性：算法应该易读、便于交流，这也是保证算法正确性的前提；添加注释也是一种增加可读性的办法；
3）健壮性：当输入非法时，算法还能做出适当的反应而不会崩溃，如输出错误信息；算法中应该考虑适当的错误处理；
4）效率高且内存消耗小：效率高指运行时间短。存储指算法执行过程中所需的最大存储空间。
7、了解时间复杂度的概念、时间复杂度的度量、时间复杂度的类型，能对实际的程序分析它的时间复杂度。
算法的时间复杂度是一个算法运行时间的相对量度。
把算法中包含简单操作次数的多少叫做该算法的时间复杂度，或者叫做时间复杂性，用它来衡量一个算法的运行时间性能或称计算性能
?平均复杂度(The Average Case)：所有可能输入.数据集的期望值．
?最坏情况复杂度 (The Worst Case)：估算最坏情况下时间复杂度的一个上界．这也是通常所指的复杂度．
?最好复杂度 (The Best Case):在最理想输入情况下的时间复杂度。
第二章线性表
1、了解并掌握线性表的定义及性质
线性表是线性结构的一种表现形式，即是具有相同属性数据元素的一个有限序列，序列中的元素是一个接一个在逻辑上是有序的，序列中元素的个数就是该线性表的长度.
?存在唯一的一个被称作“第一个”的数据元素
?存在唯一的一个被称作“最后一个”的数据元素
?除起点元素之外，集合中的每个数据元素均只有一个前驱
?除终点元素之外，集合中每个数据元素均只有一个后继
?起点元素只有后继没有前驱，终点元素只有前驱没有后继
?对于线性表中的数据元素a i-1和a i来说，a i-1是a i的直接前驱，a i是a i-1的直接后继。
?所有数据元素a i在同一个线性表中必须是相同的数据类型。
2、熟悉顺序线性表（顺序存储的线性表）的存储方式及其表单元（简单数据类型和记录数据类型）的定位和计算。
线性表的顺序存储指的是用一组地址连续的存储单元依次存储线性表的数据元素。线性表的顺序存储结构具有以下两个基本特点：
（1）线性表中所有元素所占的存储空间是连续的；
（2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的，即前驱元素一定存储在后继元素的前面。
3、熟悉顺序线性表的插入、删除和查找的算法思想和程序
4、了解线性表链接存储的结构和特点
?假设数据结构中的每一个数据结点对应于一个存储单元，这种存储单元称为存储结点，简称结点。
?在链式存储方式中，要求每个结点由两部分组成：一部分用于存放数据元素值，称为数据域（或称为信息域）；另一部分用于存放指针，称为指针域。其中指针用于指向该结点的前一个或后一个结点，从而可以表示数据元素之间的逻辑关系。
?长度可以任意扩充，存储效率较高；
?物理存储可以是不连续的；
?数据元素的逻辑次序可以与其存储的物理次序不一致。
?插入、删除运算灵活方便，不需移动结点，只要改变结点中指针域的值即可
5、了解单链表、双向链表和循环链表的结构和特点
通过每个结点的指针域将n个结点按其逻辑顺序链接在一起的结点序列我们就称为链表。如果这一链表中每个结点只有一个指针域，则称该链表为线性链表或单链表，否则则称为双向链表。
双向链表是指线性链表中的每个结点设置两个指针，一个称为左指针，用以指向其直接前驱；另一个称为右指针，用以指向其直接后继。
循环链表。循环链表和单链表的差别仅在于链表中最后一个结点的指针域不为“NULL”，而是指向头一个结点，成为一个由链指针链结的环。循环链表的特点：只要知道表中任何一个结点的地址，就能查询到表中的任何一个结点。
6、了解单链表的结点的类型定义
在程序中，L为单链表的头指针，它指向表中第一个结点。若 L 为“空”(L = NULL)，则所表示的线性表为“空”表，其长度为“零”。除了线性表第一个数据元素作为该链表的头结点外，在某些线性链表存储结构中，还可在单链表第一个结点之前附加一个同结构结点，称为附加头结点。头结点数据域可以不存储任何信息，也可以存储如线性表的长度等类的附加信息；头结点指针域存储指向第一个结点的指针(即第一个元素的存储位置)。那么，指向头结点的指针就是头指针。当头结点的指针域为“空”时，单链表为空链表
8、熟悉单链表中结点的定位、插入、删除、查询的算法思想和操作程序
9、了解线性表的顺序与链式存储各自的优点、不足与它们适用场合。
若线性表的操作主要是查找和读取时，采用顺序存储结构为宜；若线性表的操作主要是插入和删除时，采用链式存储结构为宜。
10、了解线性表的顺序与链式存储在不同操作场合下的时间复杂度指标
顺序表是随机存储结构，表中任一数据元素都可以通过计算直接得到地址进行存取，时间复杂度为O(1)。在顺序表中进行插入和删除数据元素时，平均要移动近一半的元素，尤其是当每个数据元素包含的信息量较大时，移动元素所花费的时间就相当可观。
动态链表是顺序存储结构，表中的任一结点都需要从头指针起顺链扫描才能取得，时间复杂度为O(n)(n为表长)。但在动态链表中进行插入和删除结点时，不需要移动结点，只需要修改指针。
第四章栈和队列
1、了解栈的定义及性质
栈（stack）又称堆栈，它是一种运算受限的线性表，其限制是仅允许在表的一端进行插入和删除运算。
2、能给出在特定要求下的进出栈序列以及判断某些出栈序列出现的可能性
3、了解栈的顺序存储结构实现，栈顶指针的设置
4、了解栈的链接存储结构的实现、栈顶指针的更改
5、熟悉栈在顺序和链接存储结构下的进栈、出栈和读取栈顶元素的操作程序
6、了解递归算法的特点及递归算法的中止条件，会结合具体程序来分析递归程序的合理性
7、了解队列的定义和它的顺序存储结构
?队列（queue）简称队，它也是一种运算受限的线性表，其限制是仅允许在表的一端进行插入，而在表的另一端进行删除。
?我们把进行插入的一端称作队尾(rear)，进行删除的一端称作队首(front)。向队列中插入新元素称为进队或入队，新元素进队后就成为新的队尾元素；从队列中删除元素称为离队或出队，元素离队后，其后继元素就成为队首元素。
?由于队列的插入和删除操作分别是在各自的一端进行的，每个元素必然按照进入的次序离队，所以又把队列称为先进先出表（first in first out, 简称FIFO）。
8、了解队列特别是循环队列情况下，队列头指针和尾指针的设置
9、了解队列出现“假溢出”现象的原因及解决办法：循环队列的实现（循环头指针和尾指针的计算、循环（和普通）队列长度的计算以及循环队列为空和满的判断方法）
第五章树和二叉树
1、了解树的定义和树的基本术语：树和结点的度、分支结点和叶子结点、父母结点和孩子结点、结点的层数和树的深度、有序树和无序树等
在树形表示法中，结点之间的关系是通过连线表示的，虽然每条连线上都不带有箭头(即方向)，但它并不是无向的，而是有向的，其方向隐含为从上向下或从左向右，即连线的上方或左边结点是下方或右边结点的前驱，下方或右边结点是上方或左边结点的后继。
?结点的度：树中每个结点具有的非空子树数或者说后继结点数被定义为该结点的度（degree）。
?树的度：一棵树上所有结点的度的最大值就是这棵树的度。
?叶子结点：度为零的结点称叶子结点或终端结点。
?分支结点：度非零的结点称为分支结点或称为非终端结点。
?孩子结点(child) ：某结点子树的根或者说某个结点的后继被称为该结点的孩子结点。
?双亲结点(parent)：一个结点是它的那些子树的根的双亲结点。
?兄弟结点(sibling)：同一个双亲的孩子之间互为兄弟。
?堂兄弟结点(cousins)：其双亲在同一层但不同的结点互为堂兄弟。
?子孙结点：每个结点的所有子树中的结点被称为该结点的子孙结点
?祖先结点：从整个（子）树的根结点到达该结点的路径上经过的所有分支结点?结点层次：从根结点开始，根结点为第1层，根结点的孩子为第2层，依此类推
1 A (1)
2 B 3 C 4 D (2)
5 E 6 F G 7 (3)
树的深度：树中结点的最大层次。
有序树：结点的子树从左到右有序安排。也即树T中各子树T1，T2，…，T n的相对次序是有意义的。在有序树中，改变了子树的相对次序就变成了另一棵树。
无序树：结点的子树顺序任意。
2、熟悉树的性质，并能根据这些性质进行相关推理和计算
?性质1:树中的结点数等于所有结点的度数加1。
证明：根据定义：除根结点外，每个结点有一个分支指向。树的总分支数为：?性质2：度为k的树中第i层上至多有k i-1个结点（i≥1）。∑=
n
i
i
t
1
用数学归纳法证明：
对于 i =1, k i-1 =k 0 =1 命题成立。
假设第i -1层(i >1)命题成立，该层上有k i-2 个结点。
对于第i 层，最多结点数为：k i-2.k = k i-1 命题得证。
? 性质3 深度为h 的k 叉树至多有 个结点。
证明：利用性质 2来证明，k 叉树的最大结点数为每一层最大结点数之和，则有：
当一棵k 叉树上的结点数等于 时，则称该树为满k 叉树。
? 性质4：具有n 个结点的k 叉树的最小深度为：
?log k (n (k -1)+1)?
分析：在结点数相同的 k 叉树中，每一层结点都满，或除最后一层外其余层都满的树，其
深度为最小。
证明：设k 叉树的最小深度为h ，则： 前h-1层满的 k 叉树结点数 上式可变换为： k h-1 < n (k-1)+1 ≤ k h 以k 为底取对数可得： h-1< log k ( n(k-1)+1) ≤h 即： log k ( n(k-1)+1) ≤h 因k 只能为整数，所以： h =?log k ( n(k-1)+1)? 因此得到具有n 个结点的一般k 叉树的最小深度为： ?log k ( n(k-1)+1)? 注： ?x ? 表示对x 进行向上取整 3、熟悉二叉树的定义及基本性质，并能根据这些性质进行相关推理和计算。 ? 二叉树(binary tree)是指树的度为2的有序树。它是一种树结构,在计算机领域有 着广泛地应用。 ? 二叉树的递归定义为：二叉树或者是一棵空树，或者是一棵由一个根结点和两棵互 不相交的分别称做根的左子树和右子树所组成的非空树，左子树和右子树又同样都 是一棵二叉树。 ? 性质1：在二叉树第i 层上最多有2i-1个结点( i≥1)。 性质2： 深度为k 的二叉树，最多有2k -1个结点 ( k ≥1)。 性质3：若二叉树的叶子结点数为n 0，度为2的结点有n 2个,则有：n 0=n 2+1 证明: (1) 由于在二叉树中，任一结点的度数小于或等于2，所以其结点总数n 为: n = n 0 + n 1 + n 2 (n 0 :终端结点; n 1 :单分支结点数, n 2 :双分支结点数) (2) 设B 为二叉树中总的分支数目，由于二叉树中除了根结点之外，其余结点都有一 个分支进入,而这些分支只能是由度数为1或2的结点所发出，所以： B = n 1 + 2n 2 于是得： n = n 1 + 2n 2 + 1 (3) 由(1)和(2)得： 1 1--k k h 11...11011--=+++=-=-∑ k k k k k k h h h i i 11--k k h 11111--≤<---k k n k k h h n0 + n1 + n2 = n1 + 2n2 + 1 所以 n0 = n2 + 1 #证毕性质4：对完全二叉树中编号为i的结点(1≤i≤n,n≥1，n为结点数)有： (1) 若i≤?n/2?，即2i≤n，则编号为i的结点为分支结点，否则为叶子结点。表达式?x?表示对x进行向下取整。 (2) 若n为奇数，则树中每个分支结点都既有左孩子，又有右孩子；若n为偶数，则编号最大的分支结点（编号为n/2）只有左孩子，没有右孩子，其余分支结点左、右孩子都有。 (3) 若编号为i的结点有左孩子，则左孩子结点的编号为2i；若编号为i的结点有右孩子，则右孩子结点的编号为2i+1，即遵循对一般二叉树的编号规则。 (4) 除树根结点外，若一个结点的编号为i，则它的双亲结点的编号为?n/2?,也就是说，当i为偶数时，其双亲结点的编号为i/2，它是双亲结点的左孩子，当i为奇数时，其双亲结点的编号为(i-1)/2，它是双亲结点的右孩子。此点也适合于一般二叉树。 性质5：具有n个(n>0)结点的完全二叉树的深度为?log2(n+1)?或?log2n?+1。 此性质可以从树的相应性质中直接导出，也可以进行如下证明。 证明：设所求完全二叉树的深度为h，由完全二叉树的定义可知，它的前h-1层都是满的，最后一层可以满，也可以不满，由此得到的如下不等式 2h-1-1 可变换为： 2h-1 取对数后得： h-1 即： log2(n+1)≤h 因h只能取整数，所以： h= ?log2(n+1)? 完全二叉树的深度h和结点数n的关系，还可表示为： 2h-1≤n<2h 取对数后得： h-1≤log2n 即： log2n 因h只能取整数，所以： h= ?log2n?+1 4、熟悉满二叉树、完全二叉树以及平衡二叉树等几种特殊的二叉树的性质、特点，并能根据这些性质进行相关的推理和计算 满二叉树:叉树每层的结点数达到最大值。 第i层有2i-1个结点；全部分支结点度为2。 完全二叉树：除最后一层外，其余层均满；最后层或为满，或缺少右边若干连续结点。 特点: ?除最后一层，第 i层有2i-1个结点； ?叶子只可能出现在最后两层； ?结点右子树深度为i时，左子树深度为i或i+1。 理想平衡二叉树：在一棵二叉树中，若除最后一层外，其余层都是满的，而最后一层上的结点可以任意分布，则称此树为理想平衡二叉树,简称理想平衡树或理想二叉树。 ?显然，理想平衡树包含满二叉树和完全二叉树。完全二叉树中深度h和结点数n之间的关系，在理想平衡树中同样成立， 5、了解二叉树的链接存储结构 根据二叉树的特性，任何一个结点最多有左、右两棵子树，所以每个结点至少设有三个域： 数据域和左、右指针域。其结点结构为： Left data right 其中data表示值域，用于存储对应的数据元素，left和right分别表示左指针域和右指针域，用以分别存储左孩子和右孩子结点的存贮位置（即指针） ?链接存储的另一种方法是：在上面的结点结构中再增加一个parent指针域，用来指向其双亲结点。这种存储结构既便于查找孩子结点，也便于查找双亲结点，当然也带来存储空间的相应增加。 lchild data parent rchild 6、熟悉二叉树的4种遍历方法，能按任何一种遍历方法来写出给定树的遍历序列 (1) 先序遍历： 若二叉树为空，则空操作；否则 ①访问根结点； ②先序遍历左子树； { 先访问左子树根节点；再遍历左子树根节点的左子树，再遍历左子树根节点的右子树；……直至遍历完所有左子树的节点} ③先序遍历右子树。 { 先访问右子树根节点；再遍历右子树根节点的左子树，再遍历右子树根节点的右子树；……直至遍历完所有右子树的节点} (2) 中序遍历： 若二叉树为空，则空操作；否则 ① 中序遍历左子树; （遍历的过程与先根级的递归遍历类似） ② 访问根结点； ③ 中序遍历右子树 （遍历过程与先根级的递归遍历相同） (3) 后序遍历： 若二叉树为空，则空操作；否则 ① 后序遍历左子树； ② 后序遍历右子树。 ③ 访问根结点； （4）按层遍历二叉树： ①访问根结点； ②遍历左子树根结点； ③遍历右子树根结点。 6、熟悉树的遍历序列与树结构之间的关系，并能由特定的遍历序列来恢复树结构和写出另外的遍历序列 7、熟悉树与二叉树的共性和差异之处 8、熟悉树的几种遍历算法 9、能根据树的定义（包括结点类型的定义）编程实现树的一些基本运算 第六章二叉树的应用 1、了解二叉搜索树的定义，性质并能根据定义由给定序列构造二叉搜索树 ?二叉搜索树(Binany Searching Tree)又称做二叉排序树(Binary Sorting Tree)， 它或者是一棵空树，或者是一棵具有如下特性的非空二叉树。 (1) 若它的左子树非空，则左子树上所有结点的关键字均小于树根结点的关键字； (2) 若它的右子树非空，则右子树上所有结点的关键字均大于树根结点的关键字； (3) 左、右子树本身又各是一棵二叉搜索树。 在一个二叉搜索树中，当每个结点的元素类型为简单类型时，则结点的关键字就为该结点的值；当结点的元素类型为记录类型时，则结点的关键字为该结点的某一个域的值。 ?由二叉搜索树的定义可知，在一棵非空的二叉搜索树中，其结点的关键字是按照左子树、根和右子树有序的，所以对它进行中序遍历得到的结点序列必然是一个有序序列。 2、了解二叉搜索树应用于查找时的特性及指标 ?在二叉搜索树上进行查找的过程中，给定值item同树中结点比较的次数最少为一次（即树根结点就是待查的结点)，最多为树的深度，所以平均查找次数要小于等于树的深度。 ?若二叉搜索树是一棵理想平衡树或接近理想平衡树，则进行查找的时间复杂度为O(log2n)， ?若为一棵单支树(这是最极端和最差的情况)，则其时间复杂度为O(n)， ?一般情况而言，其时间复杂度可大致可看做为O(log2n)。 由此可知，在二叉搜索树上查找比在集合或线性表上进行顺序查找的时间复杂度O(n)要小得多，这正是构造二叉搜索树的优势所在。二叉搜索树查找的递归算法的空间复杂度平均情况为O(log2n)，最差情况为O(n)，非递归算法的空间复杂度为O(1)。 3、了解堆的定义和性质 堆(Heap)分为小根堆和大根堆两种，对于一个小根堆，它是具有如下特性的一棵完全二叉树。 (1) 若树根结点存在左孩子，则树根结点的值小于等于左孩子结点的值； (2) 若树根结点存在右孩子，则树根结点的值小于等于右孩子结点的值； (3) 以左、右孩子为根的子树又同样各是一个堆。 大根堆的定义与上述类似，只要把小于等于改为大于等于就得到了。 ?若一棵完全二叉树是堆，则该树中以每个结点为根的子树也都是一个堆。 ?堆顶结点具有最小值(——对应于小根堆）或最大值（——对应于大根堆)。 4、能采用给定的数据序列来生成一个堆（大根堆或小根堆） 5、了解树的带权路径，以及哈夫曼树（最优二叉树）的概念和性质 (1) 路径和路径长度 若在一棵树中存在着一个结点序列k1,k2,…,k j，使得k i是k i+1的双亲(1≤i (2) 结点的权和带权路径长度 在许多应用中，常常将树中的结点赋予一个有着某种意义的实数，我们称此实数为该结点的权。结点的带权路径长度规定为从树根结点到该结点之间的路径长度与该结点上权的乘积。 (3) 树的带权路径长度 树的带权路径长度定义为树中所有叶子结点的带权路径长度之和，通常记为： WPL= 其中n 表示叶子结点的数目，w i 和l i 分别表示叶子结点k i 的权值和树根结点到k i 之间的路径长度。 ? 哈夫曼(Huffman)树又称作最优二叉树。它是n 个带权叶子结点构成的所有二叉树中， 带权路径长度WPL 最小的二叉树。 6、能根据给定的权值集合和结点集合构成具有n 个结点的哈夫曼树 (1) 根据与n 个权值{w 1,w 2,…,w n }对应的n 个结点构成具有n 棵二叉树的森林F ={T 1,T 2,…,T n }，其中每棵二叉树T i (1≤i ≤n)都只有一个权值为w i 的根结点，其左、右子树均为空； (2) 在森林F 中选出两棵根结点的权值最小的树作为一棵新树的左、右子树，且置新树的根结点的权值为其左、右子树上根结点的权值之和； (3) 从F 中删除构成新树的那两棵树，同时把新树加入F 中； (4) 重复(2)和(3)步，直到F 中只含有一棵树为止，此树便是哈夫曼树 第七章 图 1、了解图的定义以及基本性质 ? 图中的每个顶点，都允许有任意个前驱和后继，即对每个顶点的前驱和后继个数均 不加以限制 ? 对于一个图G ，若E 是有序对的集合，则每个有序对对应图形中的一条有向边，若E 是无序对的集合，则每个无序对对应图形中的一条无向边，所以可把E 看做为边的集合。这样图的二元组定义可叙述为： 图由顶点集(vertex set)和边集(edge set)所组成。 针对图G ，顶点集和边集可分别记为V(G)和E(G)。若顶点集为空，则边集必然为空，若顶点集非空，则边集可空可不空，当边集为空时，图G 中的顶点均为孤立顶点。 2、了解图的邻接矩阵、邻接表、逆邻接表和十字邻接表的定义及性质 邻接矩阵(adjacency matrix)是表示图形中顶点之间相邻关系的矩阵。设G=(V,E)是具有n 个顶点的图，顶点序号依次为0,1,2,…,n -1，则G 的邻接矩阵是具有如下定义的n 阶方阵。 ? 1, 对于无向图，(v i ,v j )或(v j , v i )∈E(G)； A [i ,j ]= ? 对于有向图， ? 0, 对应边不存在于E(G)中 ? 从邻接矩阵中可查两个结点的之间是否存在通路，若两个结点的坐标的交叉其值不 为零并不是一个很大的值的话，则有通路，否则没有通路。若其值大于1则为该通路的权值。 ? 无向图的邻接矩阵是对称的，有向图的邻接矩阵可能是不对称的。 ? 在有向图中, 统计第 i 行 中1的个数可得顶点 i 的出度，统计第 j 列中 1 的 个数可得顶点 j 的入度。 ? 在无向图中, 统计第 i 行 (列)中 1 的个数可得顶点i 的度。 ? 图的邻接矩阵的存储需要占用n × n 个整数存储位置，所以其空间复杂度为O(n 2)。 ? 图的邻接矩阵存储结构用于表示稠密图能够充分利用存储空间，但若用于表示稀疏 图，则将使邻接矩阵变为稀疏矩阵，从而造成存储空间的很大浪费。 ? 图的邻接矩阵表示，需要使用一个二维数组存储顶点之间相邻的关系，为了存储图 中n 个顶点元素的信息，通常还需要使用一个一维数组，用数组中下标为i 的元素存储顶点v i 的信息。 ∑=n i i i l w 1 邻接表(adjacency list)是对图中的每个顶点建立一个邻接关系的单链表，并把它们的表头指针用向量存储的一种图的表示方法。 ?为顶点v i建立的邻接关系的单链表称作v i邻接表。v i邻接表中的每个结点用来存储以该顶点为端点或起点的一条边的信息，因而被称为边结点。 ?v i邻接表中的结点数，对于无向图来说，等于v i的边数，或邻接点数或度数；对于有向图来说，等于v i的出边数、或出边邻接点数或出度数。 ?边结点通常包含三个域：一是邻接点域(adjvex)，用以存储顶点v i的一个邻接顶点v j的序号j；二是权域(weight)，用以存储边(v i, v j)或< v i, v j >上的权；三是链域(next)，用以链接v i邻接表中的下一个边结点。在这三个域中，邻接点域和链域是必不可少的，权域可根据情况取舍，若表示的是无权图，则可省去此域。 ?对于每个顶点v i的邻接表，需要设置一个表头指针，若图G中有n个顶点，则就有n个表头指针。为了便于随机访问任一顶点的邻接表，需要把这n个表头指针用一个向量(即一维数组)存储起来，其中第i个分量存储v i邻接表的表头指针。这样，图G就可以由这个表头向量来表示和存取。 3、图的边集数组的定义 ?能根据邻接矩阵或邻接表或边集数组来得到图的结构 ?熟悉图的深度和广度优先遍历的方法，并能根据相应遍历方法对给定的图写出其遍历序列 ?了解图的生成树和最小生成树的定义和性质 ?熟悉普里姆算法和克鲁斯卡尔算法，并能写出根据给定的图用这两种算法之一来构成最小生成树的过程。 第八章查找 ?了解顺序查找、二分查找以及索引查找等查找方法的原理，并熟悉应用各方法的先决条件，查找的结束条件，适宜的存储结构以及表示各种查找方法性能的时间复杂度指标 ?了解散列存储和散列函数的概念以及如何借助于散列存储结构来实现散列查找 ?熟悉常用的几种散列函数构成法 ?熟悉几种解决散列存储地址冲突的几种方法，以及各方法的优点与不足 ?熟悉散列存储的各项性能指标（时间复杂度和平均查找长度），并能结合具体的数据序列和冲突解决方法来计算相关性能指标。 第九章排序 ?熟悉直接插入排序的方法以及描述其排序性能的指标 ?熟悉直接选择排序、堆排序和交换排序的方法、性质以及描述排序性能的指标 ?熟悉快速排序和归并排序的方法、性质及指标 ?通过比较各排序方法性能（时间复杂度和空间复杂度等）熟悉如何选择合适的排序方法。