[清华大学-数据结构-王红梅]第6章-专题1-图的逻辑结构

2018/10/19
Chapter 6 Dynamic Programming
12
动态规划法的设计思想
例：计算斐波那契数 F ( n) 分治法求解 0 n0 n 1 n2 1 F ( n 1) F ( n 2)
F(5)
重复计算 F(4) F(3) F(2) F(1)
列产生的过程称为多阶段决策过程。 P2 A
初始状态
P6 P1 B P3 P4 C P5 D P7 E
最终状态
动态规划的决策过程
Chapter 6 Dynamic Programming 8
2018/10/19
最优性原理
多阶段决策过程满足最优性原理（Optimal Principle）：无论决策过程的初始状态和初始决策是 什么，其余的决策都必须相对于初始决策所产生的 当前状态，构成一个最优决策序列。各子问题的解 只与它前面的子问题的解相关，而且各子问题的解 都是相对于当前状态的最优解，整个问题的最优解 是由各个子问题的最优解构成。 如果一个问题满足最优性原理通常称此问题具 有最优子结构性质。
6.2.1 多段图的最短路径问题 6.2.2 多源点最短路径问题 6.2.3 TSP问题
2018/10/19
Chapter 6 Dynamic Programming
22
多段图的最短路径问题
多段图的最短路径问题？
设图G=(V, E)是一个带权有向连通图，如果把顶点集 合V 划分成k个互不相交的子集Vi（2≤k, 1≤i≤k）， 使得 E 中的任何一条边 (u, v) ，必有 u∈Vi ， v∈Vi+m （ 1≤i ＜ k, 1 ＜ m ），则称图 G 为多段图，称 s∈V1 为 源点，t∈Vk为终点。 多段图的最短路径问题： 是求从源点到终点的最小代价路径。

数据结构(第二版)课后习题答案(王红梅主编)第1 章绪论课后习题讲解1. 填空⑴（数据元素）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

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

，数据结构指的是数据元素以及数据元素之间的关系。

⑶ 从逻辑关系上讲，数据结构主要分为（集合）、（线性结构）、（树结构）和（图结构）。

，，，⑷ 数据的存储结构主要有（顺序存储结构）和（链接存储结构）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（数据元素）和（数据元素之间的关系）。

⑸ 算法具有五个特性，分别是（有零个或多个输入）、（有一个或多个输出）、（有穷性）、（确定性）、（可行性）。

，，，，⑹ 算法的描述方法通常有（自然语言）、（程序设计语言）、（流程图）和（伪代码）四种，其中，（伪代码）被称为算法语言。

，，，，⑺ 在一般情况下，一个算法的时间复杂度是（问题规模）的函数。

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

，用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。

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

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

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

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

A 树B 图C 线性表D 集合B将丈夫、妻子和子女分别作为数据元素，根据题意画出逻辑结构图。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

第六章v 图
6-1 图的提出
七巧板涂色问题
【问题】假设有下图所示七巧板，使用至多 4 种不同颜色对七巧板涂色，要求 每个区域涂一种颜色，相邻区域的颜色互不相同。求涂色方案。
【想法——数据模型】将七巧板的每个区域看成一个顶点，如果两个区域相邻，
数
则这两个顶点之间有边相连，从而将七巧板抽象为图结构。
据 结
念 到
实
现
）
清
【问题】排课问题。教室构成一
A
E
F
华 大 学
组顶点，课程构成一组顶点，如
V1={A, E, F}
出 版 社
果A教室可以安排B课程，则顶点
V2={B, C, D}
A和B之间有一条边。
B
C
D
农夫过河问题
【问题】农夫过河问题。一个农夫带着一只狼、一只羊和一筐菜，想从河一边
（左岸）乘船到另一边（右岸），由于船太小，农夫每次只能带一样东西过河，
先修课程
结 构
（
c1
程序设计基础
无
c2
电子技术基础
无
c3
离散数学
c1
c4
数据结构
c1
从
概
c3
c8
念 到 实
现
c1
） 清
华
c4
c6
大 学 出
版
c5
计算机原理
c1 c2
社
c6
操作系统
c3 c4 c5
c2
c5
c7
c7
计算机网络
c4 c5 c6
c8
数据库原理及应用 c4 c5
社交网络
数 据 结 构 （ 从 概 念 到 实 现 ） 清 华 大 学 出 版 社