数据结构
数据结构是指数据对象及其相互关系和构造方法。在软件设计过程中，不同的数据结构的选用，对系统最终效果的影响极大。所以该知识点是软件设计师核心考点，无论是上午综合知识部分，还是下午的软件设计部分，考查分值都很高。
根据考试大纲，本章要求考生掌握数组、链表、队列和栈、树、图、杂凑相关知识，从历年的考试情况来看，本章主要考查常见数据结构的逻辑结构特性及存储的相关内容。
数组与线性表
按数据的逻辑结构来划分，常见的数据结构包括：数组（静态数组、动态数组）、线性表（顺序表、链表、队列、栈）、树（二叉树、查找树、平衡树、线索树、堆）、图。本节将介绍数组与线性表的相关内容。
1. 数组
数组是一种常见的数据结构，根据数组下标的个数，可以把数组分为一维、二维、…、多维数组，如表4-1所示。维度是指下标的个数。一维数组只有一个下标；二维数组则有两个下标，第一个称为行下标，第二个称为列下标。根据数组的定义，计算存储地址是一个经常考查的知识点。
注：表4-1计算公式中的a为数组首地址，len为每个数据对象的长度，i与j的下标默认从0开始。
2. 稀疏矩阵
在计算机中存储一个矩阵时，可使用二维数组。例如，M×N阶矩阵可用一个数组a[M][N]来存储（可按照行优先或列优先的顺序）。如果一个矩阵的元素绝大部分为零，则称为稀疏矩阵。若直接用一个二维数组表示稀疏矩阵，则会因存储太多的零元素而浪费大量的内存空间。
在稀疏矩阵中，有一种情况非常常见，即稀疏矩阵内部存在对称性。这样，我们可以采用一维数组来表示它们，这也常称为压缩存储，如表4-2所示。
注：图4-1到图4-2中，着色的点表示为非零值，虚线是对角线。
3. 线性表
线性表是用来表示数据对象之间的线性结构，通俗地说，线性结构就是指所有结点是按“一个接着一个排列”的方式相互关联而组成一个整体。
线性结构是n个结点的有穷序列。通常表示为（a1，a2，…，an），a1称为起始结点，an称为结束结点，i称为ai在线性表中的序号或位置，线性表所含结点的个数称为线性表的长度，长度为0的线性表称为空表。
线性表主要的存储结构有两种：顺序存储结构和链式存储结构。采用顺序存储结构，就称为顺序表（常用数组实现）；采用链式存储结构则称为线性链表（即链表）。
（1）顺序表
顺序存储是最简单的存储方式，通常用一个数组，从数组的第一个元素开始，将线性表的结点依次存储在数组中，即线性表的第i个结点存储在数组的第i（0≤i≤n–1）个元素中，用数组元素的顺序存储来体现线性表中结点的先后次序关系。
顺序存储线性表的最大优点就是能随机存取线性表中的任何一个结点，缺点主要有两个，一是数组的大小通常是固定的，不利于任意增加或减少线性表的结点个数；二是插入和删除线性表的结点时，要移动数组中的其他元素，操作复杂。
（2）链表
链表就是采用链式存储实现的线性表。它是动态分配链表结点，通过链接指针，将各个节点按逻辑顺序连接起来。根据其存储结构的不同，可以分为单链表、循环链表和双链表三种，软设目前主要考查前两种。
循环链表
循环链表与单链表的区别仅仅在于其尾结点的指针域值不是null，而是指向头结点的指针。这样做的好处是，从表中的任一结点出发都能够通过后移操作扫描整个循环链表。
循环链表
循环链表与单链表的区别仅仅在于其尾结点的指针域值不是null，而是指向头结点的指针。这样做的好处是，从表中的任一结点出发都能够通过后移操作扫描整个循环链表。
（4）队列
队列也是一种特殊的线性表，只允许在一端进行插入，另一端进行删除运算。允许删除运算的那一端称为队首，允许插入运算的一端称为队尾。称队列的结点插入为进队，结点删除为出队。因最先进入队列的结点将最先出队，所以队列具有先进先出的特征。
实现队列，可以使用顺序存储（如：数组方式）也可以用链表。
顺序存储
用顺序存储线性表来表示队列，为了指明当前执行出队运算的队首位置，需要一个指针变量head（称为头指针），为了指明当前执行进队运算的队尾位置，也需要一个指针变量tail（称为尾指针）。
若用有N个元素的数组表示队列，随着一系列进队和出队运算，队列的结点移向存放队列的数组的尾端，会出现数组的前端空着，而队列空间已用完的情况。一种可行的解决办法是当发生这样的情况时，把队列中的结点移到数组的前端，修改头指针和尾指针。另一种更好的解决办法是采用循环队列。
循环队列就是将实现队列的数组a[N]的第一个元素a[0]与最后一个元素a[N–1]连接起来。队空的初态为 head=tail=0。在循环队列中，当tail赶上head时，队列满。反之，当head赶上tail时，队列变为空。这样队空和队满的条件都同为head=tail，这会给程序判别队空或队满带来不便。因此，可采用当队列只剩下一个空闲结点的空间时，就认为队列已满的简单办法，以区别队空和队满。即队空的判别条件是head=tail，队满的判别条件是head=tail+1。
链式存储
队列也可以用链接存储线性表实现，用链表实现的队列称为链接队列。链表的第一个结点是队列首结点，链表的末尾结点是队列的队尾结点，队尾结点的链接指针值为NULL。队列的头指针head指向链表的首结点，队列的尾指针tail指向链表的尾结点。当队列的头指针head值为NULL时，队列为空。
（5）栈
栈是另一种特殊的线性表，栈只允许在同一端进行插入和删除运算。允许插入和删除的一端称为栈顶，另一端为栈底。称栈的结点插入为进栈，结点删除为出栈。因为最后进栈的结点必定最先出栈，所以栈具有后进先出的特征。
顺序存储
采用顺序实现的栈中，初始化运算负责将栈顶变量top初始化为“-1”，使栈为空；在进栈操作时，需要判断栈是否满（top=N-1说明栈满），如果未满，则将新元素入栈，并将top加1；在出栈操作时，需要判断栈是否为空（top=-1说明为空）,如果非空，则取出栈顶元素，将top减1。
顺序栈的缺点在于为了避免栈满时发生溢出，需预先为栈设立足够大的空间，但太大会造成空间浪费，太小又容易引发溢出。
链式存储
栈也可以用链表实现，用链表实现的栈称为链接栈。链表的第一个结点为顶结点，链表的首结点就是栈顶指针top，top为NULL的链表是空栈。
（6）字符串
字符串是由某字符集上的字符所组成的任何有限字符序列。当一个字符串不包含任何字符时，称它为空字符串。一个字符串所包含的有效字符个数称为这个字符串的长度。一个字符串中任一连续的子序列称为该字符串的子串。
字符串通常存于足够大的字符数组中，每个字符串的最后一个有效字符之后有一个字符串结束标志，记为“\0”。通常由系统提供的库函数形成的字符串的末尾会自动添加“\0”，但当由用户的应用程序来形成字符串时，必须由程序自行负责在最后一个有效字符之后添加“\0”，以形成字符串。
对字符串的操作通常有：
●统计字符串中有效字符的个数；
●把一个字符串的内容复制到另一个字符串中；
●把一个字符串的内容连接到另一个足够大的字符串的末尾；
●在一个字符串中查找另一个字符串或字符；
●按字典顺序比较两个字符串的大小。
练习
试题1
对于一个长度大于1且不存在重复元素的序列，令其所有元素依次通过一个初始为空的队列后，再通过一个初始为空的栈。设队列和栈的容量都足够大，一个序列通过队列（栈）的含义是序列的每个元素都入队列（栈）且出队列（栈）一次且仅一次。对于该序列在上述队列和栈上的操作，正确的叙述是__(1)__。
（1）A．出队序列和出栈序列一定相同
B．出队序列和出栈序列一定互为逆序
C．入队序列与出队序列一定相同，入栈序列与出栈序列不一定相同
D．入栈序列与出栈序列一定互为逆序，入队序列与出队序列不一定互为逆序
试题2
若二维数组arr[1．．M，1．．N]的首地址为base，数组元素按列存储且每个元素占用K个存储单元，则元素arr[i，j]在该数组空间的地址为__(2)__。
（2）A．base+（（i-1）*M+j-1）*K B．base+（（i-1）*N+j-1）*K
C．base+（（j-1）*M+i-1）*K D．base+（（j-1）*N+i-1）*K
试题3
对于线性表（由n个同类元素构成的线性序列），采用单向循环链表存储的特点之一是__(3)__。
（3）A．从表中任意结点出发都能遍历整个链表
B．对表中的任意结点可以进行随机访问
C．对于表中的任意一个结点，访问其直接前驱和直接后继结点所用时间相同
D．第一个结点必须是头结点
试题4
设下三角矩阵（上三角部分的元素值都为0）A[0．．n，0．．n]如图4-6所示，将该三角矩阵的所有非零元素（即行下标不小于列下标的元素）按行优先压缩存储在容量足够大的数组M[]中（下标从1开始），则元素A[i,j]（O≤i≤n，j≤i）存储在数组M的__(4)__中。
试题5
设循环队列Q的定义中有rear和len两个域变量，其中rear表示队尾元素的指针，len表示队列的长度，如图4-7所示（队列长度为3，队头元素为e）。设队列的存储空间容量为M，则队头元素的指针为__(5)__。
（5）A．(Q．rear+Q．len-1） B．(Q．rear+Q．len-1+M)%M
C．(Q．rear-Q．len+1） D．(Q．rear-Q．len+1+M)%M
试题6
对于二维数组a[1…N,1…N]中的一个元素a[i,j]（1≤i,j≤N），存储在a[i,j]之前的元素个数__(6)__。
（6）A．与按行存储或按列存储方式无关
B．在i=j时与按行存储或按列存储方式无关
C．在按行存储方式下比按列存储方式下要多
D．在按行存储方式下比按列存储方式下要少
答案
试题1分析
本题主要考查队列和栈的特性。队列具有先进先出的特点，而栈具有后进先出的特点。因此我们可以知道入队序列与出队序列一定相同，但入栈序列与出栈序列不一定相同。比如a，b，c这样一个序列，那么按照a，b，c的顺序入队列，那么其出队列的次序一定是a，b，c。而按照a，b，c的顺序入栈，那么可能是a入栈后就出栈，然后b入栈又出栈，然后C入栈出栈。也可能是等a，b，c都入栈后再出栈，那么出栈序列就是c，b，a。
试题1答案
（1）C
试题2分析
题目告诉我们是按列存储，那么在存储元素arr[i，j]以前，应该存放了j-1列，而每一列中有M个元素（即数组的行数），那么应该有（j-1）*M个元素，而在第j列中，存放元素arr[i，j]以前，应该有i-1个元素被存放，因此，在存放元素arr[i，j]以前总共有（j-1）*M+i-1个元素被存放，而每个元素占用K个存储单元，因此本题答案选C。
试题2答案
（2）C
试题3分析
采用单向循环链表存储的特点之一是从表中任意结点出发都能遍历整个链表，另外便于元素的元素节点的删除与插入。如需要对表中的任意节点进行随机访问需采用顺序存储结构。
试题3答案
（3）A
试题4分析
本题考查数据结构基础知识。
如图4-6所示，按行方式压缩存储时，A[i,j]之前的元素数目为（1+2+…+i+j）个，因为第i行前面的每行的元素个数分别为1,2,3,…,i。数组M的下标从1开始，因此A[i,j]的值存储在中。
试题4答案
（4）A
试题5分析
对于循环队列，求队头元素的指针的计算公式为：(rear-len+1+M)%M。
求队列中元素个数公式为：(rear-fear+M)%M。其中fear表示队列的对头指针。
试题5答案
（5）D
试题6分析
按行存储即先存储完第一行元素，再开始存储第二行元素，依次类推。按列存储即先存储完第一列元素，再开始存储第二列元素，依次类推。
因为按行存储和按列存储是两种不同的存储方式，因此在本题中，存储在a[i,j]之前的元素个数与存储方式的选择有关。另外，由于二维数组a的行和列都是n，是相等的，那么在i=j（即行等于列）的情况下，存储元素的个数也是与存储方式无关的。
试题6答案
（6）B
树
1. 树的概念
树是一种典型的非线性数据结构，它能够很好地应用于描述分支和层次特性的数据集合。树是由一个或多个结点组成的有限集合T，它满足以下两个条件：
（1）有一个特定的结点，称为根结点；
（2）其余的结点分成m（m≥0）个互不相交的有限集合。其中每个集合又都是一棵树，称T1,T2,…,Tm–1为根结点的子树。
显然，以上定义是递归的，即一棵树由子树构成，子树又由更小的子树构成。由条件（1）可知，一棵树至少有一个结点（根结点）。一个结点的子树数目称为该结点的度（次数），树中各结点的度的最大值称为树的度（树的次数）。度为0的结点称为叶子结点（树叶），除叶子结点外的所有结点称为分支结点，根以外的分支结点称为内部结点。例如，在图4-8所示的树中，根结点的度数为3，结点2的度数为4，结点4的度数为1，结点9的度数为2，其他结点的度数为0，该树的度数4。
在用图形表示的树中，对两个用线段连接的相关联的结点而言，称位于上端的结点是位于下端的结点的父结点或双亲结点，称位于下端的结点是位于上端的结点的（孩）子结点，称同一父结点的多个子结点为兄弟结点，称处于同一层次上、不同父结点的子结点为堂兄弟结点。例如在图4-8中，结点1是结点2,3,4的父结点。反之，结点2,3,4都是结点1的子结点。结点2,3,4是兄弟结点，而结点5,6,7,8,9是堂兄弟结点。
定义一棵树的根结点所在的层次为1，其他结点所在的层次等于它的父结点所在的层次加1。树中各结点的层次的最大值称为树的层次。
2. 树的遍历
另外一个重点则是树的遍历问题，也就是根据某种顺序逐个获得树中全部结点的信息，常见的遍历方法有三种：
前序遍历：“根左右”，即先访问根结点，然后再从左到右按前序遍历各棵子树。以图4-8为例，前序遍历结果为：1，2，5，6，7，8，3，4，9，a，b。
后序遍历：“左右根”，即从左到右遍历根结点的各棵子树，最后访问根结点。以图4-8为例，后序遍历结果为：5，6，7，8，2，3，a，b，9，4，1。
层次遍历：首先访问处于0层的根结点，然后从左到右访问1层上的结点，以此类推，层层向下访问。以图4-8为例，层次遍历结果为：1，2，3，4，5，6，7，8，9，a，b
3. 二叉树的概念
二叉树是一个有限的结点集合，该集合或者为空，或者由一个根结点及其两棵互不相交的左、右二叉子树所组成。
二叉树的结点中有两棵子二叉树，分别称为左子树和右子树。因为二叉树可以为空，所以二叉树中的结点可能没有子结点，也可能只有一个左子结点（右子结点），也可能同时有左右两个子结点。如图4-9所示是二叉树的4种可能形态（如果把空树计算在内，则共有5种形态）。
在二叉树中，有两种表现极为特殊，即满二叉树和完全二叉树，如图4-10所示。
满二叉树：一棵深度为k且有2k-1（k≥1）个结点的二叉树就称为满二叉树。
完全二叉树：如果深度为k、有n个结点的二叉树中各结点能够与深度k的顺序编号的满二叉树从1到n标号的结点相对应即为完全二叉树。
二叉树具有以下几个重要性质，经常成为出题的依据。
在二叉树的第i层上最多有2i-1个结点（i≥1）；
深度为k的二叉树最多有2k-1个结点（k≥1）；
对任何一棵二叉树，如果其叶子结点数为n0，度为2的结点数为n2，则n0=n2+1；
具有n个结点的完全二叉树的深度为? log2n ? ，（ ?m? 运算是表示大于等于m的整数）；
如果对一棵有n个结点的完全二叉树的结点按层序编号（从第1层到 ?log~2~n? +1层，每层从左到右），则对任一结点i（1≤i≤n），有：
如果i=1，则结点i无父结点，是二叉树的根；如果i>1，则父结点是 ?i/2? ；
如果2i>n，则结点i为叶子结点，无左子结点；否则，其左子结点是结点2i；
如果2i+1>n，则结点i无右子结点，否则，其右子结点是结点2i+1。
在考试时，对这几个特性的灵活应用是十分关键的，因此应熟练的掌握它们，其实这些性质都十分明显，只需绘制出二叉树，结合着体会将能更有效地记忆。
4. 二叉树的遍历
树的遍历方法也同样适用于二叉树（如右图4-11所示），不过由于二叉树的自身特点，还有一种中序遍历法。
前序遍历（根左右，先访问根结点，然后分别用前序分别遍历左、右子树，也称为前根遍历）。图4-11的前序遍历结果是：1，2，4，5，7，8，3，6。
中序遍历（左根右，先按中序遍历左子树，再访问根结点，然后再按中序遍历右子树，也称为中根遍历）。图4-11的中序遍历的结果是：4，2，7，8，5，1，3，6。
后序遍历（左右根，分别按后序遍历要左、右子树，然后再访问根结点，也称为后根遍历）。图4-11的后序遍历的结果是：4，8，7，5，2，6，3，1。
层次遍历（首先访问处于0层的根结点，然后从左到右访问1层上的结点，以此类推，层层向下访问）。图4-11的层次遍历的结果是：1，2，3，4，5，6，7，8。
根据上面的定义和描述，我们可以发现遍历是递归定义的，最适合使用递归函数来实现。在学习遍历时，最重要的是结合其概念来灵活应用。
5. 二叉查找树
二叉查找树，它或者是一棵空树；或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
（3）左、右子树也分别为二叉查找树；
当对这样的二叉树进行中序遍历，就可以得到一个排好序的结点序列，因此，二叉查找树也称为二叉排序树。二叉查找树主要考查其遍历。
7. 线索二叉树
二叉树在通常情况下是无法直接找到某结点在某种遍历序列中的前驱和后继结点的。而线索二叉树则通过利用二叉树上空的指针域来存放这些“线索”信息，通常其采用以下做法：
若前驱结点不为空，而且其右指针域为空，则将根结点的地址赋给前驱结点的右指针域，并将前驱结点的右线索标志置1；
若根结点的左指针域为空，则把前驱结点的地址赋给根结点的左指针域，同时将根结点的左线索标志置1；
将根结点地址赋给保存前驱结点指针的变量，以便当访问下一个结点时，此根结点成为前驱结点。
8. 哈夫曼树
在理解哈夫曼树之前，必须了解一些最基本的概念。
树的路径长度：是从树根到树中每一结点的路径长度之和，在结点数目相同的二叉树中，完全二叉树的路径长度最短；
权：在一些应用中会赋予树中结点一个有意义的实数，这个数字称为权；
带权路径长度：结点到树根之间的路径长度与该结点上权的乘积，称为结点的带权路径长度；
树的带树路径长度（树的代价）：所有叶结点的带树路径长度之和。
而在权值相同的n个叶子结点构成的所有二叉树中，带权路径长度最小的二叉树称为最优二叉树，也称为哈夫曼树。构造哈夫曼树的过程如图4-12所示。
从图4-12中，我们可以发现每次都是选取最小权值的二叉树进行合并，因此它使用的是贪婪法。而且，我们还可以发现，使用这种构造过程，哈夫曼树是不可能存在度为1的分支结点，而最初的n个节点将经过n-1次合并，生成n-1个新结点，因此哈夫曼树的总结点数是2n-1的结点，而叶子结点数正是n。
练习
试题1
若n2、n1、n0分别表示一个二叉树中度为2、度为1和叶子结点的数目（结点的度定义为结点的子树数目），则对于任何一个非空的二叉树，(1)。
（1）A．n2一定大于n1B．n1一定大于n0
C．n2一定大于n0D．n0一定大于n2
试题2
一棵满二叉树，其每一层结点个数都达到最大值，对其中的结点从l开始顺序编号，即根结点编号为1，其左、右孩子结点编号分别为2和3，再下一层从左到右的编号为4、5、6、7，依此类推，每一层都从左到右依次编号，直到最后的叶子结点层为止，则用__(2)__可判定编号为m和n的两个结点是否在同一层。
试题3
__(3)__一是由权值集合{8，5，6，2}构造的哈夫曼树（最优二叉树）。
试题4
在__(4)__中，任意一个结点的左、右子树的高度之差的绝对值不超过1。
（4）A．完全二叉树 B．二叉排序树
C．线索二叉树 D．最优二叉树
试题5
下面关于哈夫曼树的叙述中，正确的是__(5)__。
（5）A．哈夫曼树一定是完全二叉树
B．哈夫曼树一定是平衡二叉树
C．哈夫曼树中权值最小的两个结点互为兄弟结点
D．哈夫曼树中左孩子结点小于父结点、右孩子结点大于父结点
试题6
己知一棵度为3的树（一个结点的度是指其子树的数目，树的度是指该树中所有结点的度的最大值）中有5个度为1的结点,4个度为2的结点，2个度为3的结点，那么，该树中的叶子结点数目为__(6)__。
（6）A．10 B．9 C．8 D．7
答案
试题1分析
根据二叉树的性质，我们知道n0=n2+1，因此在一棵二叉树中，叶子结点的数目一定是大于度为2的结点的个数。
试题1答案
（1）D
试题2分析
如果是满二叉树，那么其第n层的结点数应该是第n-1层结点数的两倍，从根（第一层）开始，各层的结点数应分别是2n-1个，其中n为当前的层次，因此一颗m层的满二叉树，其总的结点数位2m-1个。而如果知道结点编号x，我们可以用log2x+1来求取该结点属于那一层。
试题2答案
（2）B
试题3分析
构造哈夫曼树的过程是首先从给出的权值集合中找出最小的两个权值，即2和5，用它们作为子结点构建一个父结点，其权值为7，然后将7放入权值集合中并将2和5去掉，再在集合中找出两个最小权值，即6和7，而7已经在我们构造的树种，然后用6和7作为子结点构建一个父结点，其权值为6+7=13，然后同样将13放入权值集合中并将6和7去掉，最好集合中只有8和13，将它们作为子结点构建一个父结点，就得到了这棵哈夫曼树。
试题3答案
（3）C
试题4分析
本题主要考查一些特殊二叉树的性质。
若二叉树中最多只有最下面两层的结点度数可以小于2，并且最下面一层的叶子结点都依次排列在该层最左边的位置上，则这样的二叉树称为完全二叉树，因此在完全二叉树中，任意一个结点的左、右子树的高度之差的绝对值不超过1。
二叉排序树的递归定义如下：二叉排序树或者是一棵空树；或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有结点的值均小于根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于根结点的值；
（3）左右子树也都是二叉排序树。
在n个结点的二叉树链式存储中存在n+1个空指针，造成了巨大的空间浪费，为了充分利用存储资源，可以将这些空链域存放指向结点在遍历过程中的直接前驱或直接后继的指针，这种空链域就称为线索，含有线索的二叉树就是线索二叉树。
最优二叉树即哈夫曼树。
试题4答案
（4）A
试题5分析
哈夫曼树是一种特殊的二叉树，但它不是完全二叉树，也不是平衡二叉树，给出n个权值{W1,W2,…Wn}s构造一棵具有n个叶子结点的哈夫曼树的方法如下：
第一步，构造n个只有根结点的二叉树集合F={T1 ，T2 ，…，Tn }，其中每棵二叉树 Ti 的根结点带权为 (1≤k≤n)；
第二步，在集合F中选取两棵根结点的权值最小的二叉树作为左右子树，构造一棵新的二叉树，
令新二叉树根结点的权值为其左、右子树上根结点的权值之和；
第三步，在F中删除这两棵二叉树，同时将新得到的二叉树加入到F中；
第四步，重复第二步和第三步，直到F只含有一棵二叉树为止，这棵二叉树便是哈夫曼树。
综上所述，我们可以知道哈夫曼树中权值最小的两个结点互为兄弟结点。
试题5答案
（5）C
试题6分析
由于叶子节点没有子树，因此它的度为0。而除根节点外，其它的节点都应该可以做为子节点，即可以用于计算度。
在本题中告我有5个度为1的结点,4个度为2的结点，2个度为3的结点，那么树中总的度数为5+8+6=19，因此树中除根节点外，就应该有19个节点，所以树中总的节点数应该为20，那么叶子节点数=20-5-4-2=9。
试题6答案
（6）B
图
图是一种比树更复杂的非线性结构，它是由顶点集合V和边集合E组成的，通常记做G(V，E)。它可以用来模拟现实世界中许多图状结构的事物与问题。
1. 图的相关概念
有向图：若一个图中的每条边都是有方向的，则称为有向图。在有向图中，<Vi，Vj>表示一条有向边，Vi是始点（起点），Vj是终点。<Vi，Vj>和<Vj，Vi>表示的是两条不同的边。有向边也称为弧，边的始点称为弧头，终点称为弧尾。
无向图：若一个图中的每条边都是无方向的，则称为无向图。无向图的边是顶点的无序对，通常使用（Vi，Vj）来表示一条边，无向图的边没有起点和终点，（Vi，Vj）和（Vj，Vi）表示的是同一条边。
无向完全图：如果限定任何一条边的两个顶点都不相同，则有n个顶点的无向图至多有n(n-1)/2条边，这样的无向图称为无向完全图。
有向完全图：恰好有n(n-1)条边的有向图称为有向完全图。
连通图：如果图中两个顶点间存在路径，则称它们是连通的；而如果图中任意两个顶点间都是连通的，则称该图为连通图。
2. 图的存储结构
图有两种主要的存储结构，它们是邻接矩阵表示法和邻接表表示法，如表4-5所示。
3. 图的遍历
图的遍历也是从某个顶点出发，沿着某条搜索路径对图中每个顶点各做一次且仅做一次访问，常用的遍历算法包括以下深度优先和广度优先两种，如表4-6所示。
4. 最小生成树
如果连通图G的一个子图是一棵包含G所有顶点的树，则该子图称为G的生成树。生成树是含有该连通图全部顶点的一个极小连通子图，它并不是唯一的，从不同的顶点出发可以得到不同的子树。含有n个顶点的连通图的生成树有n个顶点和n-1条边。
要求一个连通图的生成树很简单，只需从任何一个顶点出发，作一次深度优先或广度优先的搜索，将所经过的n个顶点和n-1条边连接起来，就形成了极小连通子图，也就是一棵生成树。
对一个带权的图，在一棵生成树中，各条边的权植之和为这棵生成树的代价，其中代价最小的生成树称为最小生成树。普里姆算法（Prim算法）和克鲁斯卡尔算法（Kruskal算法）是求连通的带权无向图的最小代价树的常用算法。
注：带权的图是指每条边带上权值的图，常用于表示通路的代价。
练习
试题1
从存储空间的利用率角度来看，以下关于数据结构中图的存储的叙述，正确的是__(1)__。
（1）A．有向图适合采用邻接矩阵存储，无向图适合采用邻接表存储
B．无向图适合采用邻接矩阵存储，有向图适合采用邻接表存储
C．完全图适合采用邻接矩阵存储
D．完全图适合采用邻接表存储
试题2
无向图中一个顶点的度是指图中与该顶点相邻接的顶点数。若无向图G中的顶点数为n，边数为e，则所有顶点的度数之和为__(2)__。
（2）A．n*e B．n+e C．2n D．2e
试题3
设一个包含N个顶点、E条边的简单无向图采用邻接矩阵存储结构（矩阵元素A[i][j]等于1/0分别表示顶点i与顶点j之间有/无边），则该矩阵中的非零元素数目为__(3)__。
（3）A．N B．E C．2E D．N+E
试题4
无向图中一个顶点的度是指图中__(4)__。
（4）A．通过该顶点的简单路径数 B．通过该顶点的回路数
C．与该顶点相邻的顶点数 D．与该顶点连通的顶点数
答案
试题1分析
本题主要考查图的存储结构，常见的图的存储结构有邻接矩阵存储和邻接表存储，其中在邻接矩阵存储方式中，矩阵中每个元素的值都表示两个点之间的边的信息，如果每两个点之间都有变的信息，那么矩阵中的所有元素都是有效元素，那么从存储空间的利用率角度来看，其利用率是100%，而采用邻接表存储其存储空间利用率肯定低于100%，因为采用邻接表存储，不仅要存储边的信息，还要存储节点信息，指针信息等。
这种情况下，这个图很显然是一个完全图，因此从存储空间的利用率角度来看，完全图适合采用邻接矩阵存储。
试题1答案
（1）C
试题2分析
在无向图中，一条边连接两个顶点，即如果存在一条边，那么与这条边相关的两个顶点的度都为加1，那么总的度就应该加2，因此，如果图中有n条边，那么所有顶点的度数之和就应该为2e。
试题2答案
（2）D
试题3分析
本题主要考查图的邻接矩阵存储结构。
设G=（V，E）是具有n个顶点的图，其中V是顶点的集合，E是边的集合，那么邻接矩阵中的每个元素的定义如下：
从这个定义我们可以知道，一条边在矩阵中有两个1表示，比如顶点1和顶点2之间有一条边，那么矩阵元素A[1,2]和A[2,1]的值都是1。
在本题中，题目告诉我们有E条边，那么其邻接矩阵中的非零元素数目应该为2E。
试题3答案
（3）C
试题4分析
此题是纯概念题。
（1）无向图中顶点V的度（Degree）。
无向图中顶点V的度是关联于该顶点的边的数目，也可以说是直接与该顶点相邻的顶点个数，记为D(V)。
例如，在图4-13中，V1的度为1，V2的度为2，V3的度为3，V4的度为2。
（2）有向图顶点V的入度（InDegree）。
有向图中，以顶点V为终点的边的数目称为V的入度，记为ID(V)。
例如，在图4-14中，V1的入度为1，V2的入度为2，V3的入度为1，V4的入度为0。
（3）有向图顶点V的出度（OutDegree）
有向图中，以顶点V为始点的边的数目，称为V的出度，记为OD(V)。
例如，在图4-15中，V1的出度为0，V2的出度为0，V3的出度为2，V4的出度也为2。
试题4答案
（4）C
