数据结构全部（2013年5月）打印有答案版本 - 图文

数据结构

适用班级：软件设计师 主讲：张 红

网址：www.bitpx.com E-Mail:bitpx@163.com

分值说明：早上考8-12分, 下午考15-30分

比特培训中心 贵州·贵阳

课程：数据结构 主讲：张 红 版权所有：贵大比特培训中心(www.bitpx.com) 第一节．序论

1.1 什么是数据?

所有能输入到计算机中并能够被计算机程序处理的符号的总称.它是计算机程序加工的原料. 1.2 什么是数据元素?

数据的基本单位,在计算机程序中通常作为一个整体来进行考虑和处理.如数组中一个存储单元里面的数或者链表中一个结点. 1.3什么是数据结构?

是数据元素相互之间存在的一种或多种特定关系的集合.主要研究数据逻辑结构和存储结构及其运算的实现，数据结构的种类: ? 集合：结构中的数据元素之间除了“同属于一个集合”的

关系外，别无其它关系。

? 图：状结构或网状结构 结构中的数据元素之间存在多对

多的关系

? 线性结构：结构中的数据元素之间存在一个对一个的关系

? 树形结构：结构中的数据元素之间存在一个对多个的关系 1.4 数据的逻辑结构

结构定义中的“关系” 描述的是数据元素之间的逻辑关系,又称为逻辑结构.比如平常教学中所画的内存图,数组等为数据的逻辑结构.

1.5 数据的物理结构

数据结构在计算机中的实际表示形式称为数据的物理结构,又称为物理存储. 1.6 算法和算法分析 1.6.1 什么是算法？

对待定问题求解步骤的一定描述，它是指令的有限序列，其中每一条指令表示一个或多个步骤。为解决某问题的算法与为该问题编写的程序含义是相同的。 1.6.2算法的五个特性？

? 有穷性：算法必须在执行有穷步之后结束。

确定性：算法中每一条指令必须有确切的含义，读者在理解时不会产生二义性，并且在相同条件下，相同的输入只能得到相同的输出。 ? 可行性：算法能把问题真正的解决。 ? 输入：一个算法有零个或多个输入 ? 输出：一个算法有一个或多个输出

例（2002年）算法是对问题求解过程的一类精确描述，算法中描述的操作都是可以通过已经实现的基本操作在限定时间内执行有限次来实现的，这句话说明算法具有__(11)__特性。

(11) A. 正确性 B. 确定性 C. 能行性 D. 健壮性 1.6.3 算法设计的要求

? 正确性：算法应当满足具体问题的需求 ? 可读性：算法应该能让人读懂，能被计算机运行。 ? 健壮性：算法应该具有容错处理能力，不容易被击垮。 ? 高效率与低存储量要求：效率指程序的执行时间（越短越好），算法要占用计算机一定的存储量（越小越好）。 1.6.4算法效率的度量

? 时间复杂度

323

从运行时间上度量，使用大O记法假如一个程序的实际执行时间为T（n）= 2n+n+5，则T（n）=O（n）.常见的时间复杂度有： ? 空间复杂度

一个程序的空间复杂度是指程序运行从开始到结束所需的存储量。 1.固定空间 2.可变空间 第二节.线性表

线性表是由相同数据类型的结点组成的有限序列。如数组、链表（单链表、双链表、循环单链表，循环双链表）、栈、队列,双端队列等。 ? 数组：int a[5]={1,2,3,4,5};

a[0] a[1] a[2] a[3] a[4] 1 2 3 4 5 ? 单链表

1

课程：数据结构 主讲：张 红 版权所有：贵大比特培训中心(www.bitpx.com)

? 单循环链表

? 双向循环链表

使用头结点的好处:不管链表是否为空，头结点都不为空，这使得对链表的各种操作(查找和修改)得到统一. 2.1线性表的存储

(1)顺序存储 用地址连续的数据结构如数组来存储线性表。

? 优点：能随机存取线性表中的任何结点。 ? 缺点：数组的大小通常是固定的，不利于任意增加或减少线性表的个数；插入和删除线性表的结点时，要移动数组中的其他

元素，操作复杂。

(2)链接存储

用链表存储线性表(链表)，最简单的是单向链表。

? 优点：表的每个结点的实际存储位置是任意的，这给线性表的插入和删除带来方便，只要改变链表有关结点的后继指针就能

完成插入或删除的操作，不需移动任何表元。 ? 缺点：每个结点增加了一个后继指针成分，要化费更多的存储空间；不方便随机访问线性表的任一结点。 2.2 线性表的主要基本运算 2.2.1查找运算

在线性表查找具有给定键值的结点。算法有顺序查找、分块查找、二分查找、散列查找等，其中二分查找要求线性表是一个有 序序列。 注意：在链式存储的情况下，只能用顺序查找算法。

2.2.2 插入运算

在线性表的第i(0≤i≤n－I)个结点的前面或后面插入一个新结点。分顺序存储和链式存储两种情况： ? 顺序存储的情况下 ? 检查插入要求的有关参数的合理性 ? 把原来的第n-1个结点至第i个结点依次往后移动一个数组元素位置 ? 修改线性表的结点个数

在具有n个结点的线性表中插入新结点，其时间主要花费在移动结点的循环上，若插入任一位置的概率相等，则在顺序存储性表中插入一个新结点，平均移动次数为n／2。

? 链式存储的情况下 在链接存储线性表中插入一个键值为x的新结点，分以下4种情况： 1. 在某指针p所指结点之后插入；

2. 插在首结点之前，使待插入结点成为新的首结点； 3. 接在线性表的末尾；

4. 在有序链表中插入，使新的线性表仍然有序。 2.2.3删除运算

删除线性表的第i(O≤i≤n一1)个结点。也是分为顺序存储和链接储存两种情况。 （1）顺序存储

在有n个结点的线性表中，删除第i(O≤i≤n—1)个结点。删除时应将第i+1个表元至第n—1个结点依次向前移一个数组元素位置，共移动n-i-1个结点。完成删除主要有以下

几个步骤： ? 检查删除要求的有关参数的合理性； ? 把原来第i+1个表元至第n-1个结点依次向前移一个数组元素位置； ? 修改线性表元素的个数。

在具有n个结点的线性表中删除新结点，其时间主要花费在移动结点的循环上，若删除任一位置的概率相等，则在顺序存储性表中删除一个结点，平均移动次数为（n－1）／2。 （2）链接存储

在链表上删除指定值的结点，需考虑几种情况： ? 一是当链表为空链表，不执行删除操作；

2

课程：数据结构 主讲：张 红 版权所有：贵大比特培训中心(www.bitpx.com) ? 如果要删除的结点恰为链表的首结点，应将其他情况，先要在链表中查找要删除的结点，从链表首结点开始顺序查找。若找到，执行删除操作，结点个数减1，若直至链表末尾未找到指定值的结点，则不实行删除操作。 2.3 栈

栈是一种特殊的线性表，栈只允许在同一端进行插入和删除运算。允许插入和删除的一端称为栈顶，另一端称为栈底。称栈的结点插入为进栈，结点删除为出栈。因为最后进栈的结点必定最先出栈，所以栈具有后进先出的特征。 两种形式存储栈： （1）顺序存储

用顺序存储线性表来表示栈（用数组实现），为了指明当前执行插入和删除运算的栈顶位置，需要一个地址变量top指出栈顶结点在数组中的下标。

（2）链接存储栈

栈也可以用链表来实现，用链表实现的栈称为链接栈，简称链栈。链表的第一个结点为顶结点，链表的首结点就是栈顶指针top,top为空的链表为空栈。

栈的应用: 数制转换、括号匹配的检验、行编辑程序、迷宫求解、表达式求值 2005年下半年：

? 若push、pop分别表示入栈、出栈操作，初始栈为空且元

素1、

2、3依次进栈，则经过操作序列push、push、pop、pop、push、pop之后，得到的出栈序列为__(29)__。 (29)A.321 B.213 C.231 D.123

? 可以用栈来检查算术表达式中的括号是否匹配。分析算术表达式时，初始栈为空，从左到右扫描字符，遇到字符“(”就将其入栈，遇到“)”就执行出栈操作。

对算术表达式“(a+b*(a+b))/c)+(a+b)”,检查时，__(33)__；对算术表达式“((a+b/(a+b)-c/a)/b”,检查时，__(34)__。这两种情况都表明所检查的算术表达式括号不匹配。

(33)A.栈为空却要进行出栈操作 B.栈已满却要进行入栈操作

C.表达式处理已结束，栈中仍留下有字符“(” D.表达式处理已结束，栈中仍留下有字符“)” (34) A.栈为空却要进行出栈操作 B.栈已满却要进行入栈操作

C.表达式处理已结束，栈中仍留下有字符“(” D.表达式处理已结束，栈中仍留下有字符“)”

逆波兰式：是一种算术表达式的另一种表示，也称为后缀表示，定义为把运算符放在两个运算对象的后面。 中缀算术表达式转换成对应的后缀算术表达式：把每个运算符都移到运算对象的后面，然后去掉括号即可。

例题：表达式采用逆波兰式表示时可以不用括号，而且可以用基于_1__的求值过程进行计算，与逆波兰式ab+cd+*对应的中缀表达式为：__2__

1．A.栈 B.队列 C.符号表 D.散列表 2．A．a+b+c*d B.(a+b)*c+d C.(a+b)*(c+d) D.a+b*c+d （2005年上半年）表达式a*(b+c)-d的后缀表达形式为____. (39) A.abcd*+- B.abc+*d- C.abc*+d- D.-+*abcd 2.3 队列

队列也是一种特殊的线性表，只允许在一端进行插入，另一端进行删除运算。允许删除运算的那一端称为队首，允许插入运算

3

课程：数据结构 主讲：张 红 版权所有：贵大比特培训中心(www.bitpx.com) 的一端称为队尾。称队列的结点插入为进队，结点删除为出队。因最先进入队列的结点将最先出队，所以队列具有先进先出的特征。 同栈一样，队列也有两种存储方式： （1）顺序存储

可以用顺序存储线性表来表示队列，为了指明当前执行出队运算的队首位置，需要一个指针变量head(称为队头指针)，为了指明当前执行进队运算的队尾位置，也需要一个指针变量tail(称为尾指针)。

若用有N个元素的数组表示队列，随着一系列进队和出队运算，队列的结点移向存放队列的数组的尾端，会出现数组的前端空着，而队列空间已用完的情况。一种可行的解决办法是当发生这样的情况时，把队列中的结点移到数组的前端，修改头指针和尾指针。另一种更好的解决办法是采用循环队列。

循环队列就是将实现队列的数组a的第一个元素a[0]与最后一个元素a[n-1]连接起来。队空的初态为head=tail=O。在循环队列中，当tail赶上head时，队列满。反之，当head赶上tail时，队列变为空。这样队空和队满的条件都同为head=tail，这会给程序判别队空或队满带来不便。因此，可采用当队列只剩下一个空闲结点的空间时，就认为队列已满，用这种简单办法来区别队空和队满。

即队空的判别条件是head=tail，队满的判别条件是head=(tail+1) mod n。 循环链表的操作算法如下： #define MAXSIZE 100 return (Q.rear-Q.front+ MAXSIZE)mod MAXSIZE; typedef struct } { int EnQueue(SqQueue &Q, int e) int *base; { int front; if((Q.rear+1)mod MAXSIZE= =Q.front)return 0; int rear; Q.base[Q.rear] = e; }SqQueue; Q.rear = (Q.rear+1)mod MAXSIZE; int InitQueue(SqQueue &Q) return 1; { } Q.base = (int *)malloc(MAXSIZE*sizeof(int)); int DeQueue(SqQueue &Q, QElemType &e)

if(!Q.base)exit(); //Q.base==null { Q.front = Q.rear = 0; if(Q.front == Q.rear)return 0; return 1; e = Q.base[Q.front];

} Q.front = (Q.front+1)mod MAXSIZE; int QueueLength(SqQueue &Q) return 1; { } （2）．链接存储

队列也可以用链接存储线性表实现，用链表实现的队列称为链接队列。链表的第一个结点是队列首结点，链表的末尾结点是队列的队尾结点，队尾结点的链接指针值为NULL。队列的头指针head指向链表的首结点，队列的尾指针tail指向链表的尾结点。当font==rear,队列为空。

4

课程：数据结构 主讲：张 红 版权所有：贵大比特培训中心(www.bitpx.com)

判断“链式队列为空”的条件是：____（front为头指针，rear为尾指针） A．front ＝ NULL B.rear==NULL C. front == rear D.front!=rear 2005年下半年：

● 若in、out分别表示入、出队操作，初始队列为空且元素a、b、c依次入队，则经过操作序列in、in、out、out、in、out之后，得到的出队序列为__(30)__。 (30)A.cba B.bac C.bca D.abc 2.4 双端队列

限定插入和删除操作在表的两端进行的线性表（注意其与队列的区别）。

2007年上半年试题 ? 输入受限的双端队列是指元素只能从队列的一端输入、但可以从队列的两端输出，如下图所示。若有8、1、4、2一次进入输入受限的双端队列，则得不到输出序列 (57)

(57) A.2、8、1、4 B.1、4、8、2 C、4、2、1、8 D、2、1、4、8 2.5 字符串

以下关于字符串的判定语句正确的是： 2005年下半年： A．字符串是一种特殊的线性表 B．串的长度必须大于零 ● 字符串“computer”中长度为3的子串有__(32)_个。 C．字符串不属于线性表的一种 D．空格字符组成的串就是空串 (32)A.4 B.5 C.6 D.7第三节 树和二叉树 3.1 树

3.1.1树的基本概念

树是由零个或多个结点组成的有限集合T。树的几个概念：树中各结点的层次的最大值称为树的层次。 树的结点、结点的度（又叫次数）、树的度（又叫次数）、叶子结点（终端结点）、非终端结点（分支结点）、孩子、双亲、兄弟、树的深度等。

如右图：根结点的度数为3，结点2的度数为4，结点4的度数为l，结点9的成数为2，其他结点的度数为0，该树的度数4，该树的深度为4。定义一棵树的根结点所在的层次为1（这里暂且定义1 ，也可以把它定义0层，考试时题目会有明确的规定），其他结点所在的层次等于它的父结点所在的层次加1。3.1.2 树的常用存储结构 (1)标准存储结构 在树的标准存储结构中，树中的结点内容可分成两部分，分

5

课程：数据结构 主讲：张 红 版权所有：贵大比特培训中心(www.bitpx.com) 别为结点的数据和指向孩子结点的指针数组。对于N度树，在 带逆存储结构在标准存储结构的基础上增加了一个指向其父其标准存储结构中指针数组有N个元素。 结点的指针，用c代码描述树结点的带逆存储结构的数据类型例如，设树的次数为5，树的结点数据仅限于字符，用c代如下： 码描述树结点的标准存储结的数据类型如下： #define N 5 #define N 5 typedef struct rtnode{ typedef struct tnode{ char data：//树的结点数据信息 char data；//树结点的数据信息 struc rtnode *child[N]；//树结点的子结点指针 struct tnode *child[N]；//树结点的子结点指 struct rtnode *parent； //p父结点指引 针 }RTNODE；//树结点的数据类型 }TNODE； //树结点的数据类型 (2)带逆存储结构 3.1.3树的遍历

(1)前序遍历：首先访问根结点，然后从左到右按前序遍历根结点的各棵子树。

(2)后序遍历：首先从左到右按后序遍历根结点的各棵子树，然后访问根结点。

(3)层次遍历：首先访问处于第1层上的根结点，然后从左到右依次访问处于第2层上的结点，然后在从左到右依次访问处于第3层上的结点等等，即自上而下从左到右逐层访问树各层上的结点。

上述各种遍历结果如下：

(1)前序：1，2，5，6，7，8，3，4，9，a，b。 (2)后序：5，6，7，8，2，3，a，b，9，4，1。 (3)层次：1，2，3，4，5，6，7，8，9，a，b。 注意：树没有中序遍历 3.2 二叉树

3.2.1二叉树的基本概念

二叉树是一个有限的结点集合，该集合或者为空，或者是由一个根结点及其两棵互不相交的左、右叉子树所组成的。二叉树的结点中有两棵子二叉树，分别称为左子树和右子树。因二叉树可以为空，所以二叉树中的结点可能没有孩子结点，也可能只有一个左子结点(或右子结点)，也可能同时有左右两个

二叉树的四种不同形态 了结点。下图所示的是二叉树的4种可能形态（如果把空树计

算在内，则共有5种状态）。 3.2.2二叉树与树的区别

? 二叉树中，结点的子树是有序的，分左右两棵子树。单就树来说，一个结点可能拥有更多的孩子，所以没有左右之分。 问题：二叉树是否为一种特殊的树？ 答案：不是 3.2.3树及森林转到二叉树

1.最左孩子结点变左孩子；2.兄弟结点变右孩子。 树转成二叉树：

森林转成二叉树：

给各棵树的根都定一个总双亲，让各棵树变成子树，然后按照树转二叉树的方法转，最后去掉总双亲。

6

课程：数据结构 主讲：张 红 版权所有：贵大比特培训中心(www.bitpx.com)

２001年：

●任一棵树均可唯一地转换成与它对应的二叉树。由树转换成的二叉树中,结点 N 的左子女是 N 在原树里对应结点的__(1)__,而 N 的右子女是原树里对应结点的__(2)__。 在下列二叉树中,图一为__(3)__树,图二为__(4)__树,图三为__(5)__树。

图一 图二 图三

(1): A.最左子结点 B.最右子结点 C.最邻近的右兄弟 D.最邻近的左兄弟 (2): A.最左的兄弟 B.最右的兄弟 C.最邻近的右兄弟 D.最邻近的左兄弟

+

(3): A.查找树 B.满二叉树 C.平衡树但不是满二叉树 D.B树

+

(4): A.查找树 B.满二叉树 C.平衡树但不是满二叉树 D.B树

+

(5): A.查找树 B.满二叉树 C.平衡树但不是满二叉树 D.B树 3.2.4 二叉树的性质

i-1

性质1：在二叉树的第i层上至多有2个结点(i≥1);

k

性质2：深度为k的二叉树最多有2-1个结点(k≥1);

性质3：对任何一棵二叉树，如果其叶子结点个数为n0,度为2的节点数为n2,则n0= n2+1。 补充:假设度为1的结点个数为n1,则二叉树的结点个数n= n0+ n1+ n2,且n0= n2+1. 2006年下半年：

? 结点数目为n的二叉查找树(二叉排序树)的最小高度为（52）、最大高度为(53). (52)A.n B.n C.[log2n] D.??log2(n+1)?? (53)A.n B.n C.[log2n] D.??log2(n+1)??

223.2.5 满二叉树

k

一棵深度为k且有2-1个结点的二叉树称为满二叉树。满二叉树中不存在度数为1的结点。

右图就是一棵满二叉树，对结点进行顺序编号。

3.2.6 完全二叉树

如果深度为k，有n个结点的二叉树中的结点能够与深度为K的顺序编号的满二叉树从1到n标号的结点相对应，则称这样的二叉树为完全二叉树。

右图中： a是，b、c不是，根据完全二叉树的定义，在一棵深度为K(k≥1)的完全二叉树中，所有的叶子结点都出现在第k层或第k-1层（最后两层）。

在完全二叉树中，若一个结点没有左子结点，则它必定没有右子结点，所以一定是叶子结点。 完全二叉树中度为1的结点数只能为0或1.

注意:满二叉树是完全二叉树,但完全二叉树不一定是满二叉树. 3.2.7 完全二叉树的性质

性质4：具有n个结点的完全二叉树的深度为?Log2n?+1(其中??为下取整);

例子:在一棵完全二叉树中，其根的序号为1，_(33)_可判定序号为p和q的两个结点是否在同一层。、 (33)A．Llog2P」=Llog2q」 B．log2P = log2q C．Llog2P」+1=Llog2q」 D．Llog2P」= Llog2q」+1 性质5：如果对一棵n个结点的完全二叉树的结点按层次编号（从第一层到第?Log2n?+1层，每层从左到右），则对任一结点i(1

7

课程：数据结构 主讲：张 红 版权所有：贵大比特培训中心(www.bitpx.com) ≤i≤n),有：

? 如果i=1,则结点i无双亲，是二叉树的根结点；如果i>1,则其双亲结点是?i/2?; ? 如果2i〉n,则结点i为叶子结点，无左孩子，否则，其左孩子是2i; ? 2i+1〉n,则结点i无右孩子；否则，其右孩子是结点2i+1.

注意:性质1、性质2、性质3适用于所有类型的二叉树，而性质4、性质5只适用于满二叉树和完全二叉树。 3.2.8二叉树的遍历 四种遍历：

? 前序遍历（先根遍历、先序遍历）：根-左-右 根一定是遍历序列的第一个元素； ? 中序遍历（中根遍历）：左- 根-右 ? 后序遍历（后根遍历）：左-右-根 根一定是遍历序列的最后一个； ? 层次遍历：根一定是遍历序列的第一个；

先序：12457836 中序：42785136 后序：48752631 层次：12345678

注意：前序遍历、中序遍历、后续遍历属于深度优先遍历，层次遍历属于广度优先遍历。都采用递归定义。 性质：一棵二叉树的前序序列与中序序列可以唯一地确定这棵树；

例：前序序列：ABHFDECKG 中序序列：HBDFAEKCG 则构造二叉树的过程为：

问题：

? 什么情况下，二叉树的前序遍历序列与中序遍历序列相同？

答：只有根结点的二叉树或只有右子树的二叉树。 ? 什么情况下，二叉树的前序遍历序列与后序遍历序列相同？

答：只有根结点的二叉树。

8

课程：数据结构 主讲：张 红 版权所有：贵大比特培训中心(www.bitpx.com) ●对矩阵压缩存储的主要目的是__(5)__。

(5) A．方便运算 B．节省存储空间 C．降低计算复杂度 D．提高运算速度 ●判断“链式队列为空”的条件是__(6)__（front为头指针，rear为尾指针）。 (6)A．front==NULL B．rear==NULL C．front==rear D．front!=rear ●以下关于字符串的判定语句中正确的是__(7)__。 (7)A．字符串是一种特殊的线性表 B．串的长度必须大于零 C．字符串不属于线性表的一种 D．空格字符组成的串就是空串

●在具有100个结点的树中，其边的数目为__(8)__。 (8)A．101 B．100 C．99 D．98

●若循环队列以数组 Q[O..m-1] 作为其存储结构，变量 rear 表示循环队列中队尾元素的实际位置，其移动按 rear=(rear+1) mod m 进行，变量 length 表示当前循环队列中的元素个数，则循环队列的队首元素的实际位置是__(5)__。 (5)A．rear-length B．(rear-length+m) mod m C．(1+rear+m-length) mod m D．m-length

队空的判别条件是front=tail，队满的判别条件是front=tail+1。 方法：1.代入具体数字排除法 2.硬算

●若一棵哈夫曼(Huffman)树共有9个顶点，则其叶子结点的个数为__(7)__。 (7)A.4 B.5 C.6 D.7

●在一棵度为3的树中，若有2个度为3的结点，有1个度为2的结点，则有__(9)__个度为0的结点。 (9)A．4 B．5 C．6 D．7

●设结点x和y是二叉树中任意的两个结点，在该二叉树的先根遍历序列中x在y之前，而在其后根遍历序列中x在y之后，则x和y的关系是__(10)__。

(10)A．x是y的左兄弟 B．x是y的右兄弟 C．x是y的祖先 D．x是y的后裔

●已知有一维数组A[0..m*n-1]，若要对应为 m 行、n 列的矩阵，则下面的对应关系__(14)__可将元素A[k](0≤k

●已知有一维数组T[O...m*n-1]，其中m>n。从数组T的第一个元素(T[0])开始，每隔n个元素取出一个元素依次存入数组B[1...m]中，即B[1]=T[0]，B[2]=T[n]，依此类推，那么放入B[k](1≤k≤n)的元素是__(14)__。 (14) A．T[(K-1)*n] B．T[K*n] C．T[(K-1)*m] D．T[K*m] 方法：代入法，代入k＝1和k＝2只有A正确 ? 堆栈操作中_(10)_保持不变。

（10）A.堆栈的顶 B.堆栈中的数据 C.堆栈指针 D.堆栈的底 ● 判断一个表达式中左右括号是否匹配，采用_(36)_实现较为方便。

（36）A.线性表的顺序存储 B.队列 C.线性表的链式存储 D.栈 ● 字符串是一种线性表，其特殊性表现在_(37)_。

（37）A.它的数据元素是一个字符 B.它可以链式存储 C.它可以顺序存储 D.它的数据元素可以是多个字符 ● 在一颗非空二叉树中，叶子节点的总数比度为2的节点总数多_(38)_个。 （38）A.-1 B.0 C.1 D.2 方法：代入一个简单的二叉树即得解。

● 对于二维数组a[1..4，3..6]，设每个元素占两个存储单元，若分别以行和列为主序存储，则元素a[3，4]相对于数组空间起始地址的偏移量分别是_(44)_和_(45)_。

（44）A.12 B.14 C.16 D.18（45）A.12 B.14 C.16 D.18

●在一棵完全二叉树中，其根的序号为1，_(33)_可判定序号为p和q的两个结点是否在同一层。 (33)A．Llog2P」=Llog2q」 B．log2P = log2q C．Llog2P」+1=Llog2q」 D．Llog2P」= Llog2q」+1 2005年上半年：

●数据结构主要研究数据的（35） 。

（35）A.逻辑结构 B.存储结构 C.逻辑结构和存储结构 D.逻辑结构和存储结构及其运算的实现 ●PUSH和POP命令常用于（36）操作。 （36）A.队列 B.数组 C.栈 D.记录

●如果根的层次为１，具有６１个结点的完全二叉树的高度为 （38） ． （38）A.5 B.6 C.7 D.8

●数组是一种数据结构，对数组通常进行的两种基本操作是 （40）。

（40）A.插入和删除 B.插入和赋值 C.查找和修改 D.查找和删除 ● 循环链表的主要优点是_______。

(38) A.不再需要头指针了 B.已知某个结点的位置后，能很容易找到它的直接前驱结点

C.在进行删除操作后，能保证链表不断开 D.从表中任一结点出发都能遍历整个链表

●若二叉树的先序遍历序列为ABDECF，中序遍历序列DBEAFC，则其后序遍历序列为_____40________. (40) A.DEBAFC B.DEFBCA C.DEBCFA D.DEBFCA

● 在常用的描述二叉排序树的存储结构中，关键字值最大的结点_________.

(48)A.左指针一定为空 B.右指针一定为空 C.左右指针均为空 D.左右指针均不为空 ● 由权值为9，2，5，7的四个叶子构造一棵哈夫曼树，该树的带权路径长度为________. (50)A.23 B.37 C.44 D.46 2005年下半年：

●若push、pop分别表示入栈、出栈操作，初始栈为空且元素1、2、3依次进栈，则经过操作序列push、push、pop、pop、push、pop之后，得到的出栈序列为__(29)__。 (29)A.321 B.213 C.231 D.123

14

课程：数据结构 主讲：张 红 版权所有：贵大比特培训中心(www.bitpx.com) ● 若in、out分别表示入、出队操作，初始队列为空且元素a、b、c依次入队，则经过操作序列in、in、out、out、in、out之后，得到的出队序列为__(30)__。 (30)A.cba B.bac C.bca D.abc

●若线性表采用链式存储结构，则适用的查找方法为__(31)__。

(31) A.随机查找 B.散列查找 C.二分查找 D.顺序查找 ● 字符串“computer”中长度为3的子串有__(32)_个。 (32) A.4 B.5 C.6 D.7

● 可以用栈来检查算术表达式中的括号是否匹配。分析算术表达式时，初始栈为空，从左到右扫描字符，遇到字符“(”就将其入栈，遇到“)”就执行出栈操作。对算术表达式“(a+b*(a+b))/c)+(a+b)”,检查时，__(33)__；对算术表达式“((a+b/(a+b)-c/a)/b”,检查时，__(34)__。这两种情况都表明所检查的算术表达式括号不匹配。 (33)A.栈为空却要进行出栈操作 B.栈已满却要进行入栈操作

C.表达式处理已结束，栈中仍留下有字符“(” D.表达式处理已结束，栈中仍留下有字符“)” (34)A.栈为空却要进行出栈操作 B.栈已满却要进行入栈操作

C.表达式处理已结束，栈中仍留下有字符“(” D.表达式处理已结束，栈中仍留下有字符“)”

● 设数组a[1..3,1..4]中的元素以列为主序存放，每个元素占用1个存储单元，则数组元素a[2,3]相对于数组空间首地址的偏移量为__(42)__。

(42)A. 6 B. 7 C. 8 D. 9

●已知某二叉树的中序、层序序列分别为DBAFCE、FDEBCA，则该二叉树的后序序列为___(38)___。 供选择的答案：

（38）A.BCDEAF B.ABDCEF C.DBACEF D.DABECF

●在二叉树的顺序存储中，每个结点的存储位置与其父结点、左右子树结点的位置都存在一个简单的映射关系，因此可与三叉链表对应。若某二叉树共有n个结点，采用三叉链表存储时，每个结点的数据域需要d个字节，每个指针域占用4个字节，若采用顺序存储，则最后一个结点下标为k（起始下标为1）,那么___(39)___时采用顺序存储更节省空间。 供选择的答案：

(39)

? 由元素序列（27,16,75,38,51）构造平衡二叉树，则首次出现的最小不平衡子树的根（即离插入结点最近且平衡因子的绝对

值为2的结点）为____(46)____。 供选择的答案：

(46)A.27 B.38 C.51 D.75 2006年上半年：

? 为便于存储和处理一般树结构形式的信息，常采用孩子－

兄弟表示法将其转换成二叉树（左子关系表示父子，右子关系表示兄弟），与图所示的树对应的二叉树是：__(53)__.

?

给定一个有n个元素的有序线性表。若采用顺序存储结构，则在等概念前提下，删除其中一个元素平均需要移动（54）个元素。

（54）A.

nn?1n?1 B. C. D.1

22215

课程：数据结构 主讲：张 红 版权所有：贵大比特培训中心(www.bitpx.com) ●(2003年)给定一个有n个元素的线性表。若采用顺序存储结构，则在等概率前提下，向其插入一个元素需要移动的元素个数平均为__(5)__。 (5)A．n+l B．n/2 C.(n+l)/2 D.n ? 在平衡二叉树中, （55）

（55）A.任意结点的左、右子树结点数目相同 B.任意结点的左、右子树高度相同

C.任意结点的左、右子树高度之差的绝对值不大于1 D.不存在度为1的结点 2006年下半年：

? 结点数目为n的二叉查找树(二叉排序树)的最小高度为（52）、最大高度为(53). (52)A.n B.n C.[log2n] D.? C.[log2n] D.??log2(n+1)?? ?log2(n+1)?? (53)A.n B.n22? 某双向链表中的结点如下图所示，删除t所指结点的操作为(54).

(54)A.t->prior->next = t->next; t->next->prior = t->prior B.t->prior->prior = t->prior; t->next-> next = t-> next C.t->prior->next = t->prior; t->next->prior = t-> next D.t->prior->prior = t->next; t->next->prior = t->prior ? 对于二维数组a[0..4,1..5],设每个元素占1个存储单元，且以列为主序存储，则元素a[2,2]相对于数组空间起始地址的偏

移量是(55)。

（55）A.5 B.7 C.10 D.15 2007年上半年： ? 函数t()、f()的定义如下所示，若调用函数t时传递给x的值为3，并且调用函数f()时，第一个参数采用传值(call by value)

方式，第二个参数传引用(call by reference)方式，则函数t的返回值为 49 .

?

(49) A.35 B.24 C.22 D.11

输入受限的双端队列是指元素只能从队列的一端输入、但可以从队列的两端输出，如下图所示。若有8、1、4、2依次进入输入受限的双端队列，则得不到输出序列 （57） 。

? ?

（57）A.2、8、4、1 B.1、4、8、2 C.4、2、1、8 D.2、1、4、8

已知某二叉树的中序序列为CBDAEFI、先序序列为ABCDEFI,则该二叉树的高度为 58 。 （58）A.2 B.3 C.4 D.5

下图所示平衡二叉树(树中任一结点的左右子树高度之差不超过1)中，结点A的右子树AR高度为h，结点B的左子树BL高度为h，结点C的左子树CL、右子树CR高度都为h-1。若在CR中插入一个结点并使得CR的高度增加1，则该二叉树 (61).

(61)A.以B为根的子二叉树变为不平衡B.以 C为根的子二叉树变为不平衡 C.以A为根的子二叉树变为不平衡 D.仍然是平衡二叉树

? 由权值为29、12、15、6、23的五个叶子结点构造的哈夫曼树为 (64) ,其带权路径长度为 (65) .

16

课程：数据结构 主讲：张 红 版权所有：贵大比特培训中心(www.bitpx.com)

(64) A.B.

C.B. (65) A.85 B.188 C.192 D.222 2007年下半年

● 设栈S和队列Q的初始状态为空，元素按照a、b、c、d、e的次序进入栈S，当一个元素从栈中出来后立即进入队列Q。若队列的输出元素序列是c、d、b、a、e，则元素的出栈顺序是 （58） ，栈S的容量至少为 （59） 。 （58）A. a、b、c、d、e B. e、d、c、b、a C. c、d、b、a、e D. e、a、b、d、c （59）A. 2 B. 3 C. 4 D. 5

● 对于n（n≥0）个元素构成的线性序列L，在 （60） 时适合采用链式存储结构。 （60）A. 需要频繁修改Ｌ中元素的值 B. 需要频繁地对Ｌ进行随机查找

C. 需要频繁地对Ｌ进行删除和插入操作 D. 要求L存储密度高 ● 对于二叉查找树（Binary Search Tree），若其左子树非空，则左子树上所有结点的值均小于根结点的值；若其右子树非空，则右子树上所有结点的值均大于根结点的值；左、右子树本身就是两棵二叉查找树。因此，对任意一棵二叉查找树进行 （61） 遍历可以得到一个结点元素的递增序列。在具有n个结点的二叉查找树上进行查找运算，最坏情况下的算法复杂度为 （62） 。 （61） A. 先序 B. 中序 C. 后序 D. 层序

2

（62） A. O(n) B. O(nlog2n) C. O(log2n) D. O(n)

● 表达式“X = A + B ? (C ? D)/E”的后缀表示形式可以为 （22） （运算符优先级相同时，遵循左结合的原则）。 （22）A. XAB + CDE/??= B. XA+BC?DE/?= C. XABCD??E/+= D. XABCDE+??/= ● 关于算法与数据结构的关系， （64） 是正确的。

（64）A. 算法的实现依赖于数据结构的设计 B. 算法的效率与数据结构无关

C. 数据结构越复杂，算法的效率越高 D. 数据结构越简单，算法的效率越高 2008年上半年：

●若有数组声明a[0..3,0..2,1..4],设编译时为a分配的存储空间首地址为base_a,且每个数组元素占据一个存储单元。当元素以行为序存放（即按a[0,0,1],a[0,0,2], a[0,0,3], a[0,0,4], a[0,1,1], a[0,1,2],?, a[3,2,4]顺序存储），则数组元素a[2,2,2]在其存储空间中相对base_a的偏移量是 50 . (50)A.8 B.12 C.33 D.48

●若将某有序树T转换为二叉树T1，则T中结点的后(根)序序列就是T1中结点的 59 遍历序列。例如，下图(a)所示的有序树转化为二叉树后如图(b)所示。

(a) (b)

(59) A.先序 B.中序 C.后序 D.层序

●一个算法是对某类给定问题求解过程的精确描述，算法中描述的操作都可以通过将已经实现的基本操作执行有限次来实现，这句话说明算法具有 62 特性。

（62）A.有序性 B.可行性 C.确定性 D.健壮性 2008年下半年：

●表达式(a-b)*(c+5)的后缀式是 （22） 。

(22)A. a b c 5 + * - B. a b – c + 5 * C. a b c - * 5 + D. a b- c 5 + *

●一个具有m个结点的二叉树，其二叉链表结点（左、右孩子指针分别用left、right表示）中的空指针总数必定为 （57） 个。为形成中序（先序、后序）线索二叉树，现对该二叉链表所有结点进行如下操作：若结点p的左孩子指针为空，则将该左指针改为指向p在中序（先序、后序）遍历序列的前驱结点；若p的右孩子指针为空，则将该右指针改为指向p在中序（先序、后序）遍历序列的后继结点。假设指针s指向中序（先序、后序）线索二叉树中的某结点，则 (58） 。 （57） A. m+2 B. m+1 C. m D. m-1

（58） A. s－>right指向的结点一定是s所指结点的直接后继结点 B. s－>left指向的结点一定是s所指结点的直接前驱结

17

课程：数据结构 主讲：张 红 版权所有：贵大比特培训中心(www.bitpx.com) 点

C.从s所指结点出发的right链可能构成环 D.s所指结点的left和right指针一定指向不同的结点 ● 将一个无序列中的元素依次插入到一棵 （60） ，并进行中序遍历，可得到一个有序序列。 （60)A.完全二叉树 B.最小生成树 C.二叉排序树 D.最优二叉树

● 广义表中的元素可以是原子，也可以是表，因此广义表的适用存储结构是 （61） 。 （61）A.链表 B.静态数组 C.动态数组 D.散列表 2009年上半年：

●下面关于二叉排序树的叙述，错误的是 （59）。

（59）A.对二叉排序树进行中序遍历，必定得到结点关键字的有序列 B.依据关键字无序的序列建立二叉排序树，也可能构造出单支树

C.若构造二叉排序树时进行平衡化处理，则根结点的左子树高度与右子树高度的差值一定不超过1。 D.若构造二叉排序树时进行平衡化处理，则根节点的左子树高度与右子树高度的差值一定不超过1.

●下面关于栈和队列的叙述，错误的是 （60）。 （ 60）A.栈和队列都是操作受限的线性表

B.队列采用单循环链表存储时，只需设置队尾指针就可使入队和出队操作的时间复杂度都为O(1) C.若队列的数据规模n可以确定，则采用顺序存储结构比链式存储结构效率更高 D.利用两个栈可以模拟一个队列的操作，反之亦可

●下面关于二叉树的叙述，正确的是 （61）。

（ 61）A.完全二叉树的高度h与其结点数n之间存在确定的关系

B.在二叉树的顺序存储和链式存储结构中，完全二叉树更适合采用链式存储结构 C.完全二叉树中一定不存在度为1的结点 D.完全二叉树中必定有偶数个叶子结点

● 设L为广义表，将head(L)定义为取非空广义表的第一个元素，tail(L)定义为取非空广义表除第一个元素外剩余元素构成的广义表。若广义表定义为取L=((x,y,z),a,(u,t,w))，则从L中取出原子项y的运算是 （62）。

（ 62）A. head(tail(tail(L))) B. tail(head(head(L))) C. head(tail(head(L))) D. tail(tail(head(L))) 2009年下半年

●已知一个二叉树的先序遍历序列为①、②、③、④、⑤，中序遍历序列为②、①、④、③、⑤，则该二叉树的后序遍历序列为（57）。对于任意一棵二叉树，叙述错误的是（58）。

（57）A ②、③、①、⑤、④ B.①、②、③、④、⑤ C.②、④、⑤、③、① D. ④、⑤、③、②、① （58）A.由其后序遍历序列和中序遍历序列可以构造该二叉树的先序遍历序列

B.由其先序遍历序列和后序遍历序列可以构造该二叉树的中序遍历序列 C.由其层序遍历序列和中序遍历序列可以构造该二叉树的先序遍历序列 D.由其层序遍历序列和中序遍历序列不能构成该二叉树的先序遍历序列

●单向链表中往往含有一个头结点，该结点不存储数据元素，一般令链表的头指针指向该结点，而该结点指针域的值为第一个元素结点的指针。以下关于单链表头结点的叙述中，错误的是（60）。

（60）A.若在头结点中存入链表长度值，则求链表长度运算的时间复杂度为O(1)

B.在链表的任何一个元素前后进行插入和删除操作可用一致的方式进行处理 C.加入头结点后，代表链表的头指针不因为链表为空而改变 D.加入头结点后，在链表中进行查找运算的时间复杂度为O(1)

●对于长度为m（m>1）的指定序列， 通过初始为空的一个栈、一个队列后，错误的叙述是 （61 ）。 （61）A.若入栈和入队的序列相同，则出栈序列和出队序列可能相同

B.若入栈和入队的序列相同，则出栈序列和出队序列可以互为逆序

C.入队序列与出队序列关系为1:1，而入栈序列与出栈序列关系是1:n(n≥1)

D.入栈序列与出栈序列关系为1:1，而入队序列与出队序列关系是1:n(n≥1)

●字符串采用链表存储方式时，每个结点存储多个字符有助于提高存储密度。若采用结点大小相同的链表存储串，则串比较、求子串、串连接、串替换等串的基本运算中，（62）。

（62） A.进行串的比较运算最不方便 B.进行求子串运算最不方便 C. 进行串连接最不方便 D.进行串替换最不方便 2010年上半年：

●设有如下所示的下三角矩阵A[0..8,0..8]，将该三角矩阵的非零元素（即行下标不小于列下标的所有元素）按行优先压缩存储在数组M[1..m]中，则元素A[ij]（o≤i≤8，j≤i）存储在数组M的（58）中。

?i(i?1)?i(i?1)?M??M??j?1?2??（58）A. B.?2?i(i?1)??i(i?1)??M??j?1?M??j?j?? ? D.?2? C.?2●若用n个权值构造一棵最优二叉树（哈夫曼树），则该二叉树的结点总数为（59）。

（59）A.2n B.2n-1 C.2n+1 D.2n+2

●栈是一种按“后进先出”原则进行插入和删除操作的数据结构，因此，（60）必须用栈。 （60）A.实现函数或过程的递归调用及返回处理时 B.将一个元素序列进行逆置

18

课程：数据结构 主讲：张 红 版权所有：贵大比特培训中心(www.bitpx.com) C.链表结点的申请和释放 D.可执行程序的装入和卸载

●若对一个链表最常用的操作是在末尾插入结点和删除尾结点，则采用仅设尾指针的单向循环链表（不含头结点）时，（65）。 （65）A.插入删除操作的时间复杂度都为O(1)

B.插入和删除操作的时间复杂度都为O(n)

C.插入操作的时间复杂度为O(1),删除操作的时间复杂度为O(n) D.插入操作的时间复杂度为O（n）,删除操作的时间复杂度为O(1)

2011年上半年：

● 算术表达式采用逆波兰式表示时不用括号，可以利用 （20） 进行求值，与逆波兰式ab-cd+*对应的中缀表达式是 （21）。

（20）A. 数组 B. 栈 C. 队列 D. 散列表 （21）A. a-b+c*d B. (a-b)*c+d C. (a-b)*(c+d) D. a-b*c+d

● 设下三角矩阵（上三角部分的元素值都为0）A[0..n,0..n]如下所示，将该三角矩阵的所有非零元素（即行下标不小于列下标的元素）按行优先压缩存储在容量足够大的数组M[]中（下标从1开始），则元素A[I,j]（0≤i≤n,j≤i）存储在数组M的 （57） 中。

i(i?1)i(i?1)i(i?1)i(i?1)M[?j]M[?j]M[?j?1]M[?j?1]2222（57）A. B. C. D.

● 在 （59） 中，任意一个结点的左、右子树的高度之差的绝对值不超过1。 （59）A. 完全二叉树 B. 二叉排序树 C. 线索二叉树 D. 最优二叉树 2011年下半年：

● 若二维数组arr[1..M, 1..N]的首地址为base，数组元素按列存储且每个元素占用K个存储单元，则元素arr[I,j]在该数组空间的地址为 （21） 。

（21）A. base+((i-1)*M+j-1)*K B. base+((i-1)*N+j-1)*K C. base+((j-1)*M+i-1)*K C. base+((j-1)*N+i-1)*K ● 对于线性表（由n个同类元素构成的线性序列），采用单向循环链表存储的特点之一是 （58） 。

（58）A. 从表中任意结点出发都能遍历整个链表 B. 对表中的任意结点可以进行随机访问 C. 对于表中的任意一个结点，访问其直接前驱和直接后继结点所用时间相同 D. 第一个结点必须是头结点

● 一棵满二叉树，其每一层结点个数都达到最大值，对其中的结点从1开始顺序编号，即根结点编号为1，其左、右孩子结点编号分别为2和3，再下一层从左到右的编号为4、5、6、7，依此类推，每一层都从左到右依次编号，直到最后的叶子结点层为止，则用 （60） 可判定编号为m和n的两个结点是否在同一层。 （60）A. log2 m = log2 n

22 C. +1=

● （61） 是由权值集合{8，5，6，2}构造的哈夫曼树（最优二叉树）。 （61）A. B. C. D.

?logm??logn??log2m?=?log2n?

log2m?=?log2n?+1 D. ?B.

2012年上半年：

●对于二维数组a[l．．N，l．．N】中的一个元素a[i,j](1≤i,j≤N)，存储在a[i,j]之前的元素个数 (21) 。 (21)A．与按行存储或按列存储方式无关 B．在i-j时与按行存储或按列存储方式无关

C．在按行存储方式下比按列存储方式下要多 D．在按行存储方式下比按列存储方式下要少

●对于一个长度大于l且不存在重复元素的序列，令其所有元素依次通过一个初始为空的队列后，再通过一个初始为空的栈。设队列和栈的容量都足够大，一个序列通过队列（栈）的含义是序列的每个元素都入队列（栈）且出队列（栈）一次且仅一次。对于该序列在上述队列和栈上的操作，正确的叙述是 (57) 。

(57)A．出队序列和出栈序列一定相同 B．出队序列和出栈序列一定互为逆序

19

课程：数据结构 主讲：张 红 版权所有：贵大比特培训中心(www.bitpx.com) C．入队序列与出队序列一定相同，入栈序列与出栈序列不一定相同

D．入栈序列与出栈序列一定互为逆序，入队序列与出队序列不一定互为逆序

●若n2、n1、n0分别表示一个二叉树中度为2、度为1和叶子结点的数目（结点的度定义为结点的子树数目），则对于任何一个非空的二叉树， (59) 。

(59)A.n2一定大于n1 B.n1-定大于n0 C.n2-定大于n0 D. n0-定大于n2 2012年下半年：

● 若某二叉树的后序遍历序列为KBFDCAE，中序遍历序列为BKEFACD，则该二叉树为 (58) 。

(58) A.EBKFACDC.DFKBCAEBKEAD.FCDKBFAB.ECD

● 下图所示为一棵M阶B-树，M最有可能的值为 (61) 。

a1b118t35c24378d1F11Fe1F27Ff1F39Fg3F47F53F64Fh1F99F

(61) A．I B．2 C．3 D．4 ● 霍夫曼编码将频繁出现的字符采用短编码，出现频率较低的字符采用长编码。具体的操作过程为：i）以每个字符的出现频率作为关键字构建最小优先级队列；ii)取出关键字最小的两个结点生成子树，根节点的关键字为孩子节点关键字之和，并将根节点插入到最小优先级队列中，直至得到一颖最优编码树。

霍夫曼编码方案是基于 (64) 策略的。用该方案对包含a到f六个字符的文件进行编码，文件包含100,000个字符，每个字符的出现频率（用百分比表示）如下表所示，则与固定长度编码相比，该编码方案节省了 (65) 存储空间。

字 符 a b c d e f 出现频率 18 32 4 8 12 26 (64) A．分治 B．贪心 C．动态规划 D．回溯 (65) A．21% B．27% C．18% D．36%

第五节.图

在线性结构(例如队列和栈)中，除第一个结点没有前驱，最后一个结点没有后继之外，每一个结点都有唯一的前驱和后继。在树性结构(例如树和二叉树)中，除根结点没有前驱外，一个结点只有一个前驱结点，但可以有若干个后继。在图结构中，一个结点的前驱和后继的个数是任意的。 5.1图的基本概念

图分为有向图和无向图两种(见右图)：

（a是一个有向图，b是一个无向图）

? 图的表示方法

图G由两个集合V和E组成，记为G=(V，E)。通常，也将图G的顶点集和边集分别记为V(G)和 E(G)。E(G)可以是空集。若E(G)为空，则图G只有顶点而没有边。

20

课程：数据结构 主讲：张 红 版权所有：贵大比特培训中心(www.bitpx.com) ? 有向图边的表示方法

在有向图中，一条有向边是由两个项点组成的有序对，有序对通常用尖括号表示。表示一条有向边，Vi是边的始点(起点)，Vj是边的终点，和是两条不同的有向边。 有向边也称为弧，边的始点称为弧尾，终点称为弧头。

? 无向图边的表示方法

无向图中的边均是顶点的无序对，无序对通常用圆括号表示。在无向图G中，如果i≠j，i、j∈V，(i，j) ∈E，即i和j是G的两个不同的顶点，(i，j)是G中一条边，顶点i和顶点j相邻顶点，边(i，j)是与顶点i 和j相关联的边。

? 回路或环：第一个顶点和最后一个顶点相同的路径称为回路或环。 ? 无向完全图

如果限定任何一条边的两个顶点都不相同，则有n个顶点的无向图至多有n（n-1)／2条边，这样的无向图称为无向完全图(图中每两个顶点之间都有无向边)。

? 有向完全图

一个有向图至多有n（n-1)条弧，这样的有向图称为有向完全图(图中每两个顶点之间都有有向边)。 ? 顶点的度

在无向图中，一个顶点的度等于与其相邻接的顶点个数。在有向图中，一个顶点的入度等于邻接到该顶点的顶点个数，其出度等于邻接于该顶点的个数。

? 路径

在图G=(V，E)中，如果存在顶点序列(V0，V1 ??Vk－1Vk)其中V0=P，V k =Q，且(V0，V1)， (V1，V2)，?，(Vk－1，Vk)都在E中，则称顶点P到顶点Q有－条路径，并用(V0，V1，?????，Vk)表示这条路径，路径的长度是路径的边数，这条路径的长度为k。若G是有向图，则路径也是有向的。

? 连通图

在无向图中，如果从顶点v1到顶点v2有路径，称v1和v2是连通的。如果对于图中任意两个顶点Vi、Vj?V, Vi和Vj都是连通的，则称G是连通图。

? 连通分量

无向图中的极大连通子图。例子：

? 强连通图： 有向图G中，若对于V(G)中任意两个不同的顶点Vi和Vj，都存在从Vi到Vj及从Vj到Vi的路径，则称G是强连通图。 ? 强连通分量：有向图中的极大强连通子图称为有向图的强连通分量。

－>

5.2图的存储结构

最常用的图的存储结构有邻接矩阵和邻接表 1.邻接矩阵

邻接矩阵反映顶点邻接关系．设G=(V,E)是具有n（n≥1)个顶点的图，G的邻接矩阵M是一个n行n列的矩阵，并有若(i，j)或∈E，则M[i][j]=l，否则，M[i][j]＝0。

例如:

?0 1 1 1??0 0 1 1?????1 0 1 01 0 1 0?Ma＝?? Mb＝??1 1 0 1??0 0 0 0?????1 0 1 01 0 1 0????由邻接矩阵的定义可知，无向图的邻接矩阵是对称的，有

向图的邻接矩阵不一定对称。对于无向图，其邻接矩阵第i行元素的之和即为顶点i的度。对于有向图，其邻接矩阵的第i行元素之和为顶点i的出度，而邻接矩阵的第j列元素之和为顶点j的入度。

若将图的每条边都赋上一个权，则称这种带权图为网(络)。如果图G＝(V，E)是一个网，若(i，j)或属于E，则邻接矩阵中的元素M[i][j]为(i,j)或上的权。若(i，j)或不属于E，则M[i][j]为无穷大或为大于图中任何权值的实数。

21

课程：数据结构 主讲：张 红 版权所有：贵大比特培训中心(www.bitpx.com)

2.邻接表

在图的邻接表表示中，为图的每个顶点建立一个链表，且第i个链表中的结点代表与顶点i相关联的一条边或由顶点i出发的一条弧。有n个顶点的图，需用n个链表表示，这n个链表的头指针通常由顺序线性表存储。

例如：

在无向图的邻接表中，对应某结点的链表的结点个数就是该顶点的度。在有向图的邻接表中，对应某结点的链表的结点个数就是该顶点的出度。 5.3图的遍历 1．深度优先遍历

图的深度优先遍历类似于树的前序遍历。对于无向图，如果图是连通的，那么按深度优先遍历时，可遍历全部顶点，得到全部顶点的一个遍历序列。如果遍历序列没有包含所有顶点，那么该图是是不连通的。 2.广度优先遍历

类似于树的层次优先遍历。广度优先的遍历过程是：首先访问出发顶点V，然后访问与顶点V邻接的全部未被访问过的顶点W0、W1、 Wk-1；接着再依次访问与顶点W。、W1、 Wk-1邻接的全部未被访问过的顶点。依此类推，直至图的所有顶点都被访问到，或出发顶点V所在的连通分量的全部顶点都被访问到为止。 5.4最小生成树

如果连通图G的一个子图是一棵包含G的所有顶点的树，则该子图称为G的生成树。生成树是连通图的包含图中的所有顶点的极小连通子图。值得注意的是，图的生成树并不唯一。从不同的顶点出发进行遍历，可以得到不同的生成树。

含有n个顶点的连通图的生成树有n个顶点和n-1条边。对一个带权的图（网），在一棵生成树中，各条边的权值之和称为这棵生成树的代价。其中代价最小的生成树称为最小代价生成树(简称最小生成树)。

MST性质：设G=(V，E)是一个连通网络，U是顶点集v的一个真子集。若(u，v)是G中所有的一个端点在U（u∈U）里，另一个端点不在U(即v∈v-U)里的边中，具有最小权值的一条边，则一定存在 G的一棵最小生成树包括此边（u，v）。 求连通的带权无向图的最小代价生成树的算法有普里姆(Prim)算法和克鲁斯卡尔（Kruskal）算法。 1．普里姆算法

算法从U＝{u0}( u0

本文来源：https://www.bwwdw.com/article/okt2.html