当前位置：文档之家 › 数据结构习题课-数据结构习题课5

数据结构习题课-数据结构习题课5

  • 格式：pptx
  • 大小：236.42 KB
  • 文档页数：32

下载文档原格式

  / 32

合集下载

严蔚敏版数据结构习题及参考答案

严蔚敏版数据结构习题及参考答案

习题1一、单项选择题A1.数据结构是指（）。

A.数据元素的组织形式B.数据类型C.数据存储结构D.数据定义C2.数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（）。

A.存储结构B.逻辑结构C.链式存储结构D.顺序存储结构D3.树形结构是数据元素之间存在一种（）。

A.一对一关系B.多对多关系C.多对一关系D.一对多关系B4.设语句x++的时间是单位时间，则以下语句的时间复杂度为（）。

for(i=1; i<=n; i++)for(j=i; j<=n; j++)x++;A.O(1)B.O(2n)C.O(n)D.O(3n)CA5.算法分析的目的是（1），算法分析的两个主要方面是（2）。

（1） A.找出数据结构的合理性 B.研究算法中的输入和输出关系C.分析算法的效率以求改进D.分析算法的易懂性和文档性（2） A.空间复杂度和时间复杂度 B.正确性和简明性C.可读性和文档性D.数据复杂性和程序复杂性6.计算机算法指的是（1），它具备输入，输出和（2）等五个特性。

（1） A.计算方法 B.排序方法C.解决问题的有限运算序列D.调度方法（2） A.可行性，可移植性和可扩充性 B.可行性，确定性和有穷性C.确定性，有穷性和稳定性D.易读性，稳定性和安全性7.数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（）。

A.低B.高C.相同D.不好说8.数据结构作为一门独立的课程出现是在（）年。

A.1946B.1953C.1964D.19689.数据结构只是研究数据的逻辑结构和物理结构，这种观点（）。

A.正确B.错误C.前半句对，后半句错D.前半句错，后半句对10.计算机内部数据处理的基本单位是（）。

A.数据B.数据元素C.数据项D.数据库二、填空题1.数据结构按逻辑结构可分为两大类，分别是______________和_________________。

南邮陈慧南版数据结构课后习题答案

南邮陈慧南版数据结构课后习题答案

template <class T> void LinkedStack<T>::SetNull() { Node<T> *q; while (top) { q=top->link; delete top; top=q; } }
i k(循环次数) 2*i 1 1 21<n 2 2 22<n 2k-1 n 2k<n 2k<n, k<log2n, k=log2n
划线语句的执行次数为 log2n。O(log2n) (3) for(int i=1;i<=n;i++) for(int j=1;j<=i;j++) for (int k=1;k<=j;k++) x++;
习题三（第50页）
3.1 设A、B、C、D、E五个元素依次进栈(进栈后可立即出栈)，问 能否得到下列序列。若能得到，则给出相应的push和pop序列；若不 能，则说明理由。 1) A,B,C,D,E 2) A,C,E,B,D 3) C,A,B,D,E 4) E,D,C,B,A 答：2）和3）不能。对2）中的E，B，D而言，E最先出栈则表明，此 时B和D均在栈中，由于，B先于D进栈，所以应有D先出栈。同理3） 也不能。 (1)能。 push,pop,push,pop,push,pop,push,pop,push,pop (4)能。 push,push,push,push,push,pop,pop,pop,pop,pop
template <class T> bool LinkedStack<T>::IsEmpty() const { return !top; }
template <class T> bool LinkedStack<T>::IsFull() const { return false; }

数据结构课后习题及答案

数据结构课后习题及答案

填空题（10 ＊1’ = 10' ）一、概念题2。

2.当对一个线性表经常进行的是插入和删除操作时，采用链式存储结构为宜。

2。

3。

当对一个线性表经常进行的是存取操作，而很少进行插入和删除操作时，最好采用顺序存储结构。

2。

6。

带头结点的单链表L中只有一个元素结点的条件是L—〉Next->Next==Null。

3。

6。

循环队列的引入,目的是为了克服假溢出.4。

2。

长度为0的字符串称为空串。

4。

5.组成串的数据元素只能是字符。

4。

8.设T和P是两个给定的串，在T中寻找等于P的子串的过程称为模式匹配，又称P为模式。

7.2。

为了实现图的广度优先搜索，除一个标志数组标志已访问的图的结点外，还需要队列存放被访问的结点实现遍历。

5.7。

广义表的深度是广义表中括号的重数7。

8.有向图G可拓扑排序的判别条件是有无回路。

7.9。

若要求一个稠密图的最小生成树，最好用Prim算法求解。

8。

8.直接定址法法构造的哈希函数肯定不会发生冲突。

9。

2。

排序算法所花费的时间，通常用在数据的比较和交换两大操作。

1。

1。

通常从正确性﹑可读性﹑健壮性﹑时空效率等几个方面评价算法的（包括程序）的质量。

1。

2.对于给定的n元素，可以构造出的逻辑结构有集合关系﹑线性关系树形关系﹑图状关系四种。

1。

3。

存储结构主要有顺序存储﹑链式存储﹑索引存储﹑散列存储四种。

1。

4。

抽象数据类型的定义仅取决于它的一组逻辑特性,而与存储结构无关，即不论其内部结构如何变化，只要它的数学特性不变,都不影响其外部使用。

1。

5.一个算法具有五大特性:有穷性﹑确定性﹑可行性，有零个或多个输入﹑有一个或多个输入。

2.8.在双向链表结构中，若要求在p指针所指的结点之前插入指针为s所指的结点,则需执行下列语句:s—〉prior= p—〉prior; s-〉next= p; p-〉prior- next= s；p-〉prior= s；。

2.9。

在单链表中设置头结点的作用是不管单链表是否为空表，头结点的指针均不空,并使得对单链表的操作（如插入和删除)在各种情况下统一。

数据结构 习题课

数据结构 习题课

算 法
练习5 若已知非空线性链表第一个结点的指针为list， 请 写一个算法， 将该链表中数据域值最小的那个 移到链表的最前端。
list
35 67 18
…
52
10
14
71
…
82
65
q
p
^
list=q;
list
35 67 18
s->link=q->link;
…
52 10 14 71
…
82
65
s
q
^
（删除表中第i元素）
寻找满足条件的元素，即从表中第一个 元素开始到最后那个元素，反复比较相邻的 两个元素是否相同,若相同，删除其中一个， 否则，比较下一对相邻元素。
for(j=i+1; j<n; j++) A[j−1]=A[j]; n--;
（删除表中第i元素）
void DEL( ElemType A[ ], int &n ) { int j, i=0; 比较相邻元素 while(i<n-1) if(A[i]!=A[i+1]) i++; else { for(j=i+1; j<n; j++) A[j−1]=A[j]; n– – ; } } 删除一个元素
list
35 68 59 28
q->link=list;
… q p r r sp qp
r=p; p=p->link;
void REMOVE(LinkList &list ) { 算法 LinkList q=list,s,r; p=list → link; r=list; while (p!=NULL) { if (p→data<q→data) then 寻找值最小结点 { s=r; q=p; } r=p; O (链表长度) p=p→link; // 找到值最小的那个结点 ，地址由q记录 // } if (q!=list) then // 若值最小的结点不是链表最前面那个结点 // { s→link=q→link; q→link=list; list=q ; list s q } } … … 28 39 35 82

数据结构课程课后习题集答案解析

数据结构课程课后习题集答案解析

《数据结构简明教程》练习题及参考答案练习题11. 单项选择题（1）线性结构中数据元素之间是（）关系。

A.一对多B.多对多C.多对一D.一对一答：D（2）数据结构中与所使用的计算机无关的是数据的（）结构。

A.存储B.物理C.逻辑D.物理和存储答：C（3）算法分析的目的是（）。

A.找出数据结构的合理性B.研究算法中的输入和输出的关系C.分析算法的效率以求改进D.分析算法的易懂性和文档性答：C（4）算法分析的两个主要方面是（）。

A.空间复杂性和时间复杂性B.正确性和简明性C.可读性和文档性D.数据复杂性和程序复杂性答：A（5）计算机算法指的是（）。

A.计算方法B. 排序方法C.求解问题的有限运算序列D.调度方法答：C（6）计算机算法必须具备输入、输出和（）等5个特性。

A.可行性、可移植性和可扩充性B.可行性、确定性和有穷性C.确定性、有穷性和稳定性D.易读性、稳定性和安全性答：B2. 填空题（1）数据结构包括数据的①、数据的②和数据的③这三个方面的内容。

答：①逻辑结构②存储结构③运算（2）数据结构按逻辑结构可分为两大类，它们分别是①和②。

答：①线性结构②非线性结构（3）数据结构被形式地定义为（D,R），其中D是①的有限集合，R是D上的②有限集合。

答：①数据元素②关系数据结构简明教程（4）在线性结构中，第一个结点 ① 前驱结点，其余每个结点有且只有1个前驱结点；最后一个结点 ② 后继结点，其余每个结点有且只有1个后继结点。

答：①没有 ②没有 （5）在树形结构中，树根结点没有 ① 结点，其余每个结点有且只有 ② 个前驱结点；叶子结点没有 ③ 结点，其余每个结点的后继结点数可以是 ④ 。

答：①前驱 ②1 ③后继 ④任意多个（6）在图形结构中，每个结点的前驱结点数和后继结点数可以是（ ）。

答：任意多个（7）数据的存储结构主要有四种，它们分别是 ① 、 ② 、 ③ 和 ④ 存储结构。

答：①顺序 ②链式 ③索引 ④哈希（8）一个算法的效率可分为 ① 效率和 ② 效率。

数据结构课后习题答案

数据结构课后习题答案

大学课程《数据结构》课后习题答案第 1 章绪论课后习题讲解1. 填空⑴（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

【解答】数据元素⑵（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。

【解答】数据项，数据元素【分析】数据结构指的是数据元素以及数据元素之间的关系。

⑶从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。

【解答】集合，线性结构，树结构，图结构⑷数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。

【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系⑸算法具有五个特性，分别是（）、（）、（）、（）、（）。

【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性⑹算法的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。

【解答】自然语言，程序设计语言，流程图，伪代码，伪代码⑺在一般情况下，一个算法的时间复杂度是（）的函数。

【解答】问题规模⑻设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n，则表示成数量级的形式为（）。

【解答】Ο(1)，Ο(nlog2n)【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。

2. 选择题⑴顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。

A 线性结构B 非线性结构C 存储位置D 指针【解答】C，D【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。

⑵假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。

则表示该遗产继承关系的最合适的数据结构应该是（）。

数据结构习题和答案

数据结构习题和答案习题课填空1、对于⼀棵⼆叉树，若⼀个结点的编号为i，则它的左孩⼦结点的编号为，双亲结点的编号为。

2、向⼀个长度为n的向量中删除第i个元素(1≤i≤n)时，需向前移动个元素。

3、在⼀棵⼆叉树中，若双分⽀结点数为5个，单分⽀结点数为6个，则叶⼦结点数为个。

4、为了实现折半查找，线性表必须采⽤⽅法存储。

顺序5、⼀种抽象数据类型包括数据对象和。

6、在以L为表头指针的带表头附加结点的单链表和循环单链表中，判断链表为空的条件分别为__________和_______。

7、数据结构被形式地定义为（D, R），其中D是的有限集合，R是D上的有限集合。

8、队列的插⼊操作在进⾏，删除操作在进⾏。

9、⼆叉搜索树的中序遍历得到的结点序列为____ ____。

10、在顺序表中插⼊或删除⼀个元素，需要平均移动元素，具体移动的元素个数与有关。

11、栈的特点是。

12、在单链表中，除了⾸元结点外，任⼀结点的存储位置由。

13、在⼀个具有n个顶点的⽆向图中，要连通所有顶点则⾄少需要条边。

14、深度为k（设根的层数为1）的完全⼆叉树⾄少有个结点，⾄多有个结点。

15、⼀棵深度为6的满⼆叉树有个分⽀结点和个叶⼦结点。

16、⼀个算法的效率可分为效率和效率。

17、队列的特点是。

18、⼀棵深度为5的满⼆叉树中的结点数为个。

19、在⼀个具有n个顶点的⽆向完全图中，包含有________条边，在⼀个具有n个顶点的有向完全图中，包含有________条边。

简答题1、已知⼀组元素为（38，26，62，94，35，50，28，55），画出按元素排列顺序输⼊⽣成的⼀棵⼆叉搜索树。

答:2、假设有⼆维数组A[0..5,0..7]，每个元素⽤相邻的6个字节存储，存储器按字节编址。

已知A的起始存储位置（基地址）为1000，计算：（1）末尾元素A57的第⼀个字节地址为；（2）若按列存储时，元素A47的第⼀个字节地址为。

(3) 数组A的体积（存储量）；(4) 若按⾏存储时，元素A14的第⼀个字节地址为。

《数据结构》第五章习题参考答案

《数据结构》第五章习题参考答案一、判断题（在正确说法的题后括号中打“√”，错误说法的题后括号中打“×”）1、知道一颗树的先序序列和后序序列可唯一确定这颗树。

( ×)2、二叉树的左右子树可任意交换。

（×）3、任何一颗二叉树的叶子节点在先序、中序和后序遍历序列中的相对次序不发生改变。

（√）4、哈夫曼树是带权路径最短的树，路径上权值较大的结点离根较近。

（√）5、用一维数组存储二叉树时，总是以前序遍历顺序存储结点。

( ×)6、完全二叉树中，若一个结点没有左孩子，则它必是叶子结点。

( √)7、一棵树中的叶子数一定等于与其对应的二叉树的叶子数。

（×）8、度为2的树就是二叉树。

（×）二、单项选择题1．具有10个叶结点的二叉树中有（ B ）个度为2的结点。

A．8 B．9 C．10 D．112．树的后根遍历序列等同于该树对应的二叉树的( B )。

A. 先序序列B. 中序序列C. 后序序列3、二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK；中序遍历：HFIEJKG 。

该二叉树根的右子树的根是：( C )A. EB. FC. GD. H04、在下述结论中，正确的是（ D ）。

①具有n个结点的完全二叉树的深度k必为┌log2(n+1)┐；②二叉树的度为2；③二叉树的左右子树可任意交换；④一棵深度为k(k≥1)且有2k-1个结点的二叉树称为满二叉树。

A．①②③B．②③④C．①②④D．①④5、某二叉树的后序遍历序列与先序遍历序列正好相反，则该二叉树一定是（ D ）。

A．空或只有一个结点B．完全二叉树C．二叉排序树D．高度等于其结点数三、填空题1、对于一棵具有n个结点的二叉树，对应二叉链接表中指针总数为__2n____个，其中___n-1_____个用于指向孩子结点，___n+1___个指针空闲着。

2、一棵深度为k(k≥1)的满二叉树有_____2k-1______个叶子结点。

数据结构课程课后习题集答案解析

《数据结构简明教程》练习题及参考答案练习题11. 单项选择题（1）线性结构中数据元素之间是（）关系。

A.一对多B.多对多C.多对一D.一对一答：D（2）数据结构中与所使用的计算机无关的是数据的（）结构。

A.存储B.物理C.逻辑D.物理和存储答：C（3）算法分析的目的是（）。

A.找出数据结构的合理性B.研究算法中的输入和输出的关系C.分析算法的效率以求改进D.分析算法的易懂性和文档性答：C（4）算法分析的两个主要方面是（）。

A.空间复杂性和时间复杂性B.正确性和简明性C.可读性和文档性D.数据复杂性和程序复杂性答：A（5）计算机算法指的是（）。

A.计算方法B. 排序方法C.求解问题的有限运算序列D.调度方法答：C（6）计算机算法必须具备输入、输出和（）等5个特性。

A.可行性、可移植性和可扩充性B.可行性、确定性和有穷性C.确定性、有穷性和稳定性D.易读性、稳定性和安全性答：B2. 填空题（1）数据结构包括数据的①、数据的②和数据的③这三个方面的内容。

答：①逻辑结构②存储结构③运算（2）数据结构按逻辑结构可分为两大类，它们分别是①和②。

答：①线性结构②非线性结构（3）数据结构被形式地定义为（D,R），其中D是①的有限集合，R是D上的②有限集合。

答：①数据元素②关系数据结构简明教程（4）在线性结构中，第一个结点 ① 前驱结点，其余每个结点有且只有1个前驱结点；最后一个结点 ② 后继结点，其余每个结点有且只有1个后继结点。

答：①没有 ②没有 （5）在树形结构中，树根结点没有 ① 结点，其余每个结点有且只有 ② 个前驱结点；叶子结点没有 ③ 结点，其余每个结点的后继结点数可以是 ④ 。

答：①前驱 ②1 ③后继 ④任意多个（6）在图形结构中，每个结点的前驱结点数和后继结点数可以是（ ）。

答：任意多个（7）数据的存储结构主要有四种，它们分别是 ① 、 ② 、 ③ 和 ④ 存储结构。

答：①顺序 ②链式 ③索引 ④哈希（8）一个算法的效率可分为 ① 效率和 ② 效率。

数据结构c语言版课后习题答案

数据结构c语言版课后习题答案数据结构是计算机科学中的一个重要概念，它涉及到组织、管理和存储数据的方式，以便可以有效地访问和修改数据。

C语言是一种广泛使用的编程语言，它提供了丰富的数据结构实现方式。

对于学习数据结构的C语言版课程，课后习题是巩固理论知识和提高实践能力的重要手段。

数据结构C语言版课后习题答案1. 单链表的实现在C语言中，单链表是一种常见的线性数据结构。

它由一系列节点组成，每个节点包含数据部分和指向下一个节点的指针。

实现单链表的基本操作通常包括创建链表、插入节点、删除节点、遍历链表等。

答案：- 创建链表：定义一个链表结构体，然后使用动态内存分配为每个节点分配内存。

- 插入节点：根据插入位置，调整前后节点的指针，并将新节点插入到链表中。

- 删除节点：找到要删除的节点，调整其前后节点的指针，然后释放该节点的内存。

- 遍历链表：从头节点开始，使用指针遍历链表，直到达到链表尾部。

2. 二叉树的遍历二叉树是一种特殊的树形数据结构，其中每个节点最多有两个子节点。

二叉树的遍历是数据结构中的一个重要概念，常见的遍历方式有前序遍历、中序遍历、后序遍历和层序遍历。

答案：- 前序遍历：先访问根节点，然后递归遍历左子树，最后递归遍历右子树。

- 中序遍历：先递归遍历左子树，然后访问根节点，最后递归遍历右子树。

- 后序遍历：先递归遍历左子树，然后递归遍历右子树，最后访问根节点。

- 层序遍历：使用队列，按照从上到下，从左到右的顺序访问每个节点。

3. 哈希表的实现哈希表是一种通过哈希函数将键映射到表中一个位置来访问记录的数据结构。

它提供了快速的数据访问能力，但需要处理哈希冲突。

答案：- 哈希函数：设计一个哈希函数，将键映射到哈希表的索引。

- 哈希冲突：使用链地址法、开放地址法或双重哈希法等解决冲突。

- 插入操作：计算键的哈希值，将其插入到对应的哈希桶中。

- 删除操作：找到键对应的哈希桶，删除相应的键值对。

4. 图的表示和遍历图是一种复杂的非线性数据结构，由顶点（节点）和边组成。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
} return 2*r + ( n == 2 ); }
分析2
v1 v8
v6 v4
v2 v7
v5 v3
参考答案2
• 思路：直径是最长路径，从某点出发找距离最远的节点， 该节点必然位于直径的端点，从该端点出发找最长路径 即为直径。
pair<int, int > Graph_List::Farthest( int v ) {
Queue<pair<int, int >> q; pair<int, int > p(v, 0); q.QInsert( p ); while (!q.empty()) {
p = q.QDelete(); Edge * e = vertices[q.QDelete()].adjacent; for ( ; e != NULL; e = e->link ) {
6 63
5
4
16 1 11 2 5
6 63
18
5
4
第5章第19题
• 自由树（即无环连通图）T=(V, E)的直径是树中所有顶 点之间最短路径的最大值，试设计一个算法求T的直 径，并分析算法的时间复杂度。
• 【分级提示】
- （1）可用邻接表作为存储结构； - （2）引入一个辅助数组保存各顶点的度； - （3）执行删除过程； - （4）并修正各个顶点的度。
p next(p)
)
FirstSecond(v. first, second)
WHILE depth(first) > depth(second) + 1 DO (
DepthExp(v, first). v first
FirstSecond(v. first, second)
)
d depth(first) + depth(second) + 2 ▌
if ( e->verAdj == p->first ) continue; pair<int, int > pp( e->verAdj, p.second+1); q.QInsert( pp ); } } return p; }
扩展
• 在线性时间内求带权值的自由树的直径
分析
v1 v8
v6 v4
second vertex(p)
p next(p)
)
END
Algorithm Diameter(G. d)
IF |V(G)| < 2 THEN d 0. RETURN
v a vertex with more than two neighbors
p adjacent(v)
WHILE p
DO (
DepthExp(vertex(p), v)
Let v be the first vertex in G WHILE v is existed DO (
IF visited(v) = 1 THEN CONTINUE VCycle(v. flag) IF flag=TRUE THEN RETURN Reset the status of visited vertices Let v be the next vertex )▌
1
16
2
21
11
19
6
6
33
14
5
4
18
5
3
10
参考答案：prim算法
1 16 2
1 16 2 5 3
1 16 2 5
6
3
4
1 16 2
11
5
6
3
6
4
1 16 2
11
5
6
3
6
18
5
4
参考答案：Kruskal算法
1
25
6
3
5
4
1 6
2 5
63
5
4
1 11 2 5 6 63
5
4
16 1 11 2 5
if ( top == - 1 ) return true; // 图中有回路
else { int j=top; top=count[top]; //栈顶j Edge *p = head[j].Adjacent; // 以下把j的所有邻接顶点的入度减1 while( p != NULL ) { int k=p->VerAdj ; if ( --count[k]= = 0 ) {count[k]=top; top=k;} p=p->link ; }
• 如果图中有多个连通分支，需要对每个节点都判断是否 能引出回路。
v1
v2 v3
v5
v4
算法VCycle(v. flag) /*判断以v为起点的连通分支是否
有环，若有，flag为TRUE,否则FALSE. */
visited(v) -1
p adjacent(v).
WHILE p
DO (
IF visited(vertex(p))=-1 THEN (
IF depth(v) > max THEN d depth(v)
p next(p)
)
p next(p)
WHILE p
DO (
IF depth(v) = -1 THEN DepthExp( vertex(p), v)
IF depth(v) > max THEN d depth(v)
p next(p)
分析
v1 v8
v6 v4
v2 v7
v5 v3
参考答案
• 借鉴书后答案的思想，但书后答案时间复杂度不为O(n) • 删除所有叶子（最外层的节点），直径增加2 • 最后剩不多于2个节点的时候直接知道直径 • 最初始的时候计算所有节点的度，并保存所有叶子节点
（其度为1） • 与拓扑排序类似，不是真的删除节点，只是减少节点的
参考答案
• 从空间利用率的角度考虑，稠密图采用邻接矩阵，稀疏 图采用邻接表
第13题
• 设G＝(V, E)是有向图，请给出算法，判断G中是否有回 路，并要求算法的复杂性为O(n+e)。
方法一：深度优先搜索
• 思想：深搜时，每个结点有两个状态，标记是否被访问 过（0未访问，1已访问过）。判环时，多引入一个状态， 标记结点正在访问中（-1正在访问中）。如果一个结点 正在访问中，又遍历到该接点，那个存在环路。这种状 况是由于出现了反向边，即后代指向祖先的边。
flag=TRUE. RETURN)
IF visited(vertex(p))=0 THEN (
VCycle(vertex(p). flag).
IF flag=TRUE THEN RETURN.
)
p link(p).
)
visited(v) 1. flag FALSE. ▌
算法Cycle(G. flag)
方法二：拓扑排序
void Graph::Cycled( ) {
int top = - 1 ; for ( int i=0 ; i<n ; i + + ) {
if ( count[i] == 0 ) { count[i] = top; top = i;
} } for ( int i=0 ; i<n ; i + + ) {
v2 v7
v5 v3
参考答案（无权）
struct Vertex {
bool visited; int depth; //初始值为-1 };
function DepthExp( v, r)
p adjacent(v). max -1
WHILE vertex(p) r DO (
IF depth(v) = -1 THEN DepthExp( vertex(p), v)
IF depth(first) < depth(second) THEN
first second
WHILE p
DO (
IF depth(vertex(p)) depth(first) THEN
second first. first vertex(p)
ELSE IF depth(p) > depth(second) THEN
)
depth(v) max + 1
end DepthExp
function FirstSecond( v. first, second)
p adjacent(v). first vertex(p)
IF next(p) = THEN second
p next(p). second vertex(p). p next(p).
2
3
参考答案
10 15 35
20
20
30
4
5
6
15
3
1234
dis 35 0 10 15
path 4 -1 2 2
s
1111
56
30 ∞ 4 -1 10
最短路径 最短路径长度
2→3
10
2→4
15
2→4→5
30
2→4→1
35
2→6
∞
第16题
• 对于图5.39所示的无向网络，利用普里姆和克鲁斯卡尔 算法，分别求出其最小支撑树，并写出生成过程
} } return false; }
第5章第14题
• 对于下图所示的非负有向网络，给出Dijkstra算法产生的 由源点2到图中其它顶点的最短路径长度以及路径所经 历的顶点，并写出生成过程。
50
10
1
2
3
10 15 35