第7章算法程序与计算系统之灵魂练习题答案解析
胃病治疗-
第
7
章
算法
:
程序与计算系统之灵魂
1
、算法就是一个有穷规则的集
合，其中之规则规定了解决某一特定类型问题的一个运算序
列。回答下列问题。
(1)
关于算法的特性，下列说法不正确的是
_____
。
(A)
算法必须有明确的结束条件，即算法应该能够结束，此即算法的有穷性；
(B)
算法的步骤必须要确切地定义，不能
有歧义性，此即算法的确定性；
(
C)
算法可以有零个或多个输入，也可以有零个或多个输出，此即算法的输入输出性；<
/p>
(D)
算法中有待执行的运算和操作必
须是相当基本的，可以由机器自动完成，进一步，
算法应能在有限时间内完成，此即算法
的能行性；
(E)
上述说法有不正确的；
答案：
C
解释：
本题考查对算法基本性质的理解
<
/p>
（
C
）算法的输出性：算法有一个或多个
的输出
/
结果，即与输入有某个特定关系的量。
因此（
C
）选项错误。其余选项，
（
A
）
（
B
）
（
D
）分
别是对算法的有穷性，确定性和能行性
的正确描述。
具体内容参考第七章视频之“算法与算法类问题的求解”以及第七章课件。
(2)
关于算法的命题，下列说
法不正确的是
_____
。
(A)
算法规定了任务执行
/
< br>问题求解的一系列、有限的步骤。
(B)
算法所规定的计算
/
处理步骤是有限的，
但算法实际执行的计算
/
处理步骤可以是无限
的。
(C)
算法
可以没有输入，但必须有输出。
(D)
算法的每一个步骤必须确切地定义，且其运算和操作必须相当基本，可以由机器自
动完
成。
答案：
B
解释：
本题考查对算法基本性质的理解
<
/p>
（
B
）违反了算法的有穷性：一个算法在
执行有穷步规则之后必须结束。因此（
B
）选项错
误。其余选项，
（
A
）
（
C
）
（
D
）分别是对算法的有穷性，输入输出性和确定性的正确描述。
具体内容参考第七章视频之“算法与算法类问题的求解”以及第七章课
件。
(3)
关于算法与程序、计算机语言之间的关系，下列说法不正确的是
_____
。
(A)
算法是解决问
题的步骤，某个问题可能有多个求解算法；
(B)
算法不能直接由计算机执行，必须将其转换为程序才能够由计算机执行；
(C)
算法只能由高级（计算机）语言实现，不能通过机器语言
实现；
(D)
求解问题的多个算法不
一定获得相同的解。
答案：
C
解释：
本题考查对算法基本性质的理解
<
/p>
（
C
）算法是解决问题的步骤，执行的语
言是步骤书写的规范、语法规则、标准的集合
是人和计算机都
能理解的语言，不仅是高级语言。因此（
C
）选项错误。其余选
项，
（
A
）正
确，解决问题的算法可以有多个。
（
B
）选项，程序是算法的实现方式，正确。
（
D
< br>）选项，
算法有优劣，对于同一个问题，获得的解可能不同。
具体内容参考第七章视频之“算法与算法类问题的求解”以及第七章课件。
(4)
算法是计
算系统的灵魂，为什么？不正确的是
_____
。
(A)
计算系统是执行程序的系统，而程序是用计
算机语言表达的算法；
(B)
一个问
题的求解可以通过构造算法来解决，
“是否会编程序”本质上章是“能否想出
求解该问题的算法”
；
(C)
一个算法不仅可以解决一个具体问题，它可以在变换输入
输出的情况下，求解一个
问题系列；
(D)
问题求解都可以归结到算法的构造与设计，系统和算法的关系是：算法是龙，而系
统是睛，画龙要点睛。
(E)
上述说法有不正确的；
答案：
D
解释：
本题考查算法、程序与系统之间的关系
（
D
）选项，算法是计算系统的灵魂，因此系统和算法的关系
是：系统是龙，算法是睛，好
的算法能起到画龙点睛的效果。
（
A
）
（
B
）
（
C
）选项描述
正确。
具体内容参考第七章视频之“算法与算法类问题的求解
”以及第七章课件。
2
、哥尼斯堡七桥问题，是一个经典问题，如下图
(a)
所示，描述为“由河流隔开的四块陆地
上建造了七座桥，寻找走遍这七座桥且只许走
过每座桥一次最后又回到原出发点的路径”
。
关于哥尼斯堡七桥
问题，著名数学家欧拉对该问题做了一个抽象：
“顶点”为陆地，
“边”为
连接两块陆地的桥梁。这个抽象被称为“图”
，并定
义了顶点的“度”为连接一个顶点的边
的数量。关于此问题回答下列问题。
//
本题考查问题及其数学建模的作用
(a)
(1)
哥尼斯堡七桥问题的路径能够找到吗？
_____
。
(A)
一定能够找到；
(B)
一定不能找到；
(C)
不确定能不能找到。
(b)
答案：
B
解释：
本题考查问题及其数学建模的作用
选
择（
B
）
，根据欧拉回路关系可知，要
是一个图形可以一笔画，需要满足：
1
）图形必须是
连通的；
2
）
途中的
“奇点”
（相连的边的个数为奇数的点）
个
数是
0
或
2
（
该题中应为
0
个）
。
< br>该问题中将四个岛抽象成
4
个点，
每条桥抽象成边，
可知图中奇点个数是
4
个，
因此不可能
找到。
具体内容参考第七章视频之“数学建模与算法策略设计
--
算法思想”
，第七章课件或查
阅欧拉回路相关资料。
(2)
对
河流隔开的
m
块陆地上建造的
n
座桥梁，能否找到走遍这
n
座桥且只许走过每
座桥一
次最后又回到原出发点的路径呢？
_____
。
(A)
一定能够找到；
(B)
一定不能找到；
(C)
不确定能不能找到。
答案：
C
解释：
本题考查问题及其数学建模的作用
选
择（
C
）根据欧拉回路关系可知，要是一个图形可以一笔画，需
要满足：
1
）图形必
须是连通的；
2
）途中的“奇点”
（相连的边的个数为奇
数的点）个数是
0
或
2
（该题中因为
起点和终点是一个，所以奇点个数应为
0
个）
。该问题中将
m
< br>个岛抽象成
m
个点，每条桥
抽象
成边，但图中奇点个数未知，因此不能做判断。
具体内容参考
第七章视频之
“算法与算法类问题的求解，
第七章课件或查阅欧
拉回路相
关资料。
(3)
对河流隔开的
m
块陆地
上建造的
n
座桥梁，若要找到走遍这
n
座桥且只许走过每座桥一
次最后又回到原出发点的路径，则需满
足以下条件
_____
。
(A)m
个顶点
n
条边的
图应是连通的，
即由一个顶点出发可沿边到达任何一个其他顶点；
(B)
每个顶点的度应为偶数；
(C)
既
需要满足
(A)
又需要满足
(B)
；
(D)
上述条
件还不够，还需满足更多条件。
答案：
C
解释：
本题考查问题及其数学建模的作用
选
择（
C
）根据欧拉回路关系可知，要是一个图形可以一笔画，需
要满足：
1
）图形必
须是连通的；
2
）途中的“奇点”
（相连的边的个数为奇
数的点）个数是
0
或
2
（该题中因为
起点和终点是一个，所以奇点个数应为
0
个）
。该问题中将
m
< br>个岛抽象成
m
个点，每条桥
抽象
成边，因此应该选择
C
。
具体内容参考第七章视频之“数学建模与算法策略设计
--
算法思想”
，第七章课件或查
阅欧拉回路相关资料。<
/p>
(4)
下面
所示的图
(c)
，能否找到走遍每一座桥，且每座桥仅走过一次
、最后又回到原出发点
的路径呢？
(c)
(A)
一定能够找到；
(B)
一定不能找到；
(C)
不确定能不能找到。
答案：
B
解释：
本题考查问题及其数学建模的作用
选
择（
B
）根据欧拉回路关系可知，要是一个图形可以一笔画，需
要满足：
1
）图形必
须是连通的；
2
）途中的“奇点”
（相连的边的个数为奇
数的点）个数是
0
或
2
（该题中因为
起点和终点是一个，
所以奇点个数应为<
/p>
0
个）
。
图中奇
点是
C
与
G
，
个数为
2
，
不
符合要求，
因此应该选择
B
。
具体内容参考第七章视频之“数学建模与算法策略设计
--
算法思想”
，第七章课件或查
阅欧拉回路相关资料。
(5)
参见图
(c)
，增加哪些边，使得能够
找到走遍每一座桥，且每座桥仅走过一次、最后又回
到原出发点的路径呢？
(A)BG
边；
(B)AG
边；
(C)CG
边；
(D)AD
边；
(E)DE
边。
答案：
C
解释：
本题考查问题及其数学建模的作用
选
择（
C
）根据欧拉回路关系可知，要是一个图形可以一笔画，需
要满足：
1
）图形必
须是连通的；
2
）途中的“奇点”
（相连的边的个数为奇
数的点）个数是
0
或
2
（该题中因为
起点和终点是一个，
所以奇点个数应为<
/p>
0
个）
。
图中奇
点是
C
与
G
，
个数为
2
，
不
符合要求，
因此在
CG
间增加一条边，
将寄点数变成
0
可满足要求，因此应该选择
C
。
具体内容参考第七章视频之
“数学建模与算法策略设计
--
算法思想”
，第七章课件或查阅欧
拉回路相关资料。
(6-1)
对河流隔开的
m
块陆地上建造的
n
座桥
梁，若要找到走遍这
n
座桥且只许走过每座桥
< br>一次的路径，则需满足以下条件
_____
。
(A)m
个顶点
n
条边的图应是连通的，
即由一个顶点出发可沿边到达任何一个其他顶
点；
(B)
每个顶点的度应为偶数；
(C)
既
需要满足
(A)
又需要满足
(B)
；
(D)
不满足
上述条件
(A)(B)(C)
的图也能找出满足题目规定要求的
路径；
答案：
D
解释：
本题考查问题及其数学建模的作用
选
择（
D
）
，此题未要求回到原地，即起
点和终点可以不是一个，那么可以有
2
个奇数
< br>点作为起点和终点。根据欧拉回路关系可知，要是一个图形可以一笔画，需要满足：
1
）图
形必须是连通的；
2
）途中的“奇点”
（相连的边的个数为奇数的点）个数是
0
或
2
。不同时
满足（
A
）
（
B
）
，可以有
2
个顶点的度为奇数，也可以满足题目要求，因此应该选择
D
。
具体内容参考第七章视频之“数学建模与算法策略
设计
--
算法思想”
，第七章课件或查
阅欧拉回路相关资料。
(6-2)
对河流隔开的
m
块陆地上建造的
n
座桥梁，若要找到走遍这
< br>n
座桥且只许走过每座桥
一次的路径，则需满足以下条件
_____
。
(A)m
个顶点
n
条边的图应是连通
的，
即由一个顶点出发可沿边到达任何一个其他顶点；
(B)
每
个顶点的度应为偶数，
或者，
只有两个顶点的度为奇数而其他顶
点的度均为偶数；
(C)
既需要满足
(A)
又需要满足
(B)
；
(D)
不满足上述条件
(A)(B)(C)
的图也能找出满足题目规定要求的路径；<
/p>
答案：
C
解释：
本题考查问题及其数学建模的作用
选
择（
C
）
，此题未要求回到原地，即起
点和终点可以不是一个，那么可以有
2
个奇数
< br>点作为起点和终点。根据欧拉回路关系可知，要是一个图形可以一笔画，需要满足：
1
）图
形必须是连通的；
2
）途中的“奇点”
（相连的边的个数为奇数的点）个数是
0
或
2
。因此应
该选择
C
。
具体内容参考第七章视频之“数学建模与算法策略设计
--
< br>算法思想”
，第七章课件或查
阅欧拉回路相关资料。
(7)
下面所
示的图
(d)
和图
(e)
，问能否找到走遍每一座桥，且每座桥仅走过一次的路径呢？
(d)
(A)
图
(d)
和图
(e)
都一定不能找到；
(B)
图
(d)
一定能够找到；图
(e)
一定不能找到；
(C)
< br>图
(d)
一定不能找到；图
(e
)
一定能够找到；
(D)
图
(d)
和图
(e)
都一定能够找到；
(e)
答案：
C
解释：
本题考查问题及其数学建模的作用
选
择（
C
）根据欧拉回路关系可知，要是一个图形可以一笔画，需
要满足：
1
）图形必
须是连通的；
2
）途中的“奇点”
（相连的边的个数为奇
数的点）个数是
0
或
2
。
d
图有
FGE
三个奇点，一定不能找到，而
e
图有
FG
两个奇点，一定能找到，因此应该选择
C
。
具体内容参考第七章视频之“数学建模与算
法策略设计
--
算法思想”
，第七章课
件或查
阅欧拉回路相关资料。
(8)
参见下图
(f)
，下列说法正确的是
_____
。
(f)
(A)
对
{A
、
B
、
C
、
D
、
E
、
F
、
G}<
/p>
中的任意两个顶点
X
和
< br>Y
，都可以找到一条路径，从
X
出发
走遍每一座桥，且每座桥仅走过一次，最后终止于
Y
；
(B)
对两个顶点
A
和
B<
/p>
，可以找到一条路径，从
A
出发
走遍每一座桥，且每座桥仅走
过一次，最后终
止于
B
；
(
C)
对两个顶点
D
和
< br>G
，可以找到一条路径，从
D
出
发
走遍每一座桥，且每座桥仅走
过一
次，最后终止于
G
；
(D)
对
{
A
、
B
、
C<
/p>
、
D
、
E
、
F
、
G}
中的任意两个顶点
X
和
Y
，都找不到一条路径，从
X
出发
走遍每一座桥，且每座桥仅走过一次，最后终止于
Y
；
答案：
C
解释：
本题考查问题及其数学建模的作用
选
择（
C
）根据欧拉回路关系可知，要是一个图形可以一笔画，需
要满足：
1
）图形必
须是连通的；
2
）途中的“奇点”
（相连的边的个数为奇
数的点）个数是
0
或
2
。该图奇点为
G
和
D
，
因此可以找到一条欧拉回路，
并且只能以此两
点作为起点和终点，
因此应该选择
C
。
具体内容参考第七章视频之“数学建模与算法策略设计
--
算法思想”
，第七章课件或查
阅欧拉回路相关资料。
(9)
哥尼斯堡七桥问题，给我们的启示是
_____
。
(A)
一个具体
问题应该进行数学抽象，基于数学抽象进行问题求解；
(B)
一个具体问题的求解，进行数学建模后，通过模型中的性质分析可以判断该问题是
否有解，如果有解，则可以进行计算；而如果无解，则无需进行计算；
(C)
一个具体问题的求解方法，进行数学建模后，可反映出一
类问题的求解方法，例如
哥尼斯堡七桥问题的求解方法，建立“图”后，可反映任意
n
座桥的求解方法；
(D)
上述全部；
答案：
D
解释：
本题考查问题及其数学建模的作用
以
上说明都正确，
对一个具体问题的求解，
可先进行数学建模，<
/p>
将具体问题转化成抽象
问题，再进行判断是否有解，若有解则计算
，若无解则无需计算。
具体内容参考第七章视频之“数学建模
与算法策略设计
--
算法思想”
，第七
章课件或查
阅欧拉回路相关资料。
(10)
哥尼斯堡七桥问题，推而广之就是
m
个顶点
n
条边的图的“一笔画”
问题，我们可以给
出一个算法来求解该问题，即“对河流隔开的
m
块陆地上建造的
n
座桥梁，若要找到
走遍
这
n
座桥且只许走过每座桥一次的
路径”
。
关于该算法的基本思想，<
/p>
下列说法正确的是
_____
。
(A)
以任何一个顶点为起点，按照图的“边
”的指示，找到按该边与该顶点相连的下一
个顶点，并标记该边为“已访问”
，依次循环，直到所有的边都被访问过为止，便可找到给
定问题的解；
(B)
以任何一个顶点为起点，按照图的
未访问过“边”的指示，找到按该边与该顶点相
连的下一个顶点，并标记该边为“已访问
”
，依次循环，直到所有的边都被访问过为止，便
可找到给定问
题的解；
(C)
首先判断该问题是否
有解，若无解，则直接退出；若有解，则以任何一个顶点为起
点，按照图的未访问过“边
”的指示，找到按该边与该顶点相连的下一个顶点，并标记该边
为“已访问”
，依次循环，直到所有的边都被访问过为止，便可找到给定问题的解；
<
/p>
(D)
首先判断该问题是否有解，若无解，则直接退出；若有解，
则选择一个奇数度的顶
点为起点，按照图的未访问过“边”的指示，找到按该边与该顶点
相连的下一个顶点，并标
记该边为“已访问”
，依次循环，直到
所有的边都被访问过为止，便可找到给定问题的解；
(E)
上述都不正确。
答案：
D
解释：
本题考查问题及其数学建模的作用
选
择（
D
）根据欧拉回路关系可知，要是一个图形可以一笔画，需
要满足：
1
）图形必须是
连通的；
2
）
途中的
“奇点
”
（相连的边的个数为奇数的点）
个数是
0
或
2
。
因
此，
若有奇点，
则起点和终点必须是奇点，若无，则任意，因此
（
A
）
（
B<
/p>
）
（
C
）
，因此应该选择
D
。
具体内容参考第七章视频之“数学建模与算法策略设计
--
算法思想”
，第七章课件或查
阅欧拉回路相
关资料。
3
、背包问题的定义是：给定一组物品，每种物品都有自己的重量和价格，在限定的总
重量
内，
我们如何选择，
才能使得物品
的总价格最高。
问题的名称来源于如何选择最合适的物品
放置于
给定背包中。
背包问题的一个例子：应该选择哪些盒子，才能使价格尽可能地大，而
保持重量小于或等于
15
kg
？其示意图如下：
(1)
该背包问题的可能解的数量是
_____<
/p>
。
(A) 5
(B) 10
(C) 32
(D) 64
答案：
C
解释：
本题考查问题及其数学建模的作用
由
题意可知，只要可放入背包的状态都算是可能解，可以按背包容量由
1
< br>到
15
遍历可
能性。答案为（<
/p>
C
）
32
个。<
/p>
具体内容查阅背包问题相关资料。
(2)
假定求解该问题的一种贪心策
略是：优先选择能装下盒子中价格最高的，依据该算法策
略所得到的解的总价值是
_____
。
(A) 16
(B) 15
(C)
14
(D) 13
答案：
B
解释：
本题考查问题及其数学建模的作用
由
题意可知使用贪心算法，从价值最高的开始放入，第一个放入价值
$$10
的
4kg
物品，
接下来价值最
大的是
$$4
，但再加上
12kg
已经超过了背包的限度，所以不可放入，接下来放
入其余的
3
个可满足重量限制的物品，总价值是
15
，所以选择（
B
）
。
具体内容查阅背包问题相关资料。
(3)
假定求解该问题的一种贪心策
略是：优先选择能装下盒子中单位重量价值最高的，依据
该算法策略所得到的解的总价值
是
_____
。
(A) 16
(B) 15
(C) 14
(D)
13
答案：
B
解释：
本题考查问题及其数学建模的作用
由
题意可知使用贪心算法，
从单位价值最高的开始放入，
五个物品
单位价值从大到小依
次为：
2.5,2,1,1,1/3
，
依次放入并验证是否超出背包重量限制：
$$
10-4kg, $$2-1kg,$$1-1kg,$$2-2kg
，
之后放不下
$$4-12kg
的物品，到此总价值是
15
，所以选择（
B
）<
/p>
。
具体内容查阅背包问题相关资料。
(4)
假定求解该问题的一种贪心策略是：最大程度地利用背
包的容量（
15kg
）
，依据该算法<
/p>
策略所得到的解的总价值是
_____
。
(A) 8
(B)
15
(C) 14
(D)
13
答案：
A
解释：
本题考查问题及其数学建模的作用
由
题
意
可
知
使
用
贪
心
算
法
，
需
要
让
剩
余
< br>空
间
最
小
，
那
么
可
以
得
到
的
组
合
是
，
12kg+
2kg+1kg=15kg
，重量得到最大利用，总价值是
8<
/p>
，所以选择（
A
）
。
具体内容查阅背包问题相关资料。
(5)
使用遍历算法策略所得到的
解的总价值是
_____
。
(A) 8
(B) 15
(C) 14
(D)
13
答案：
B
解释：
本题考查问题及其数学建模的作用
用
遍历算法策略，状态转移方程：
f[v]=max{f[v],f[v-c[i]]+w
[i]}
，即
f[i][v]
表示前<
/p>
i
件物
品恰放入一个容量为
v
的背包可以获得的最大价值，
第
< br>i
件物品的重量是
c[i]
，<
/p>
价值是
w[i]
。
“
将前
i
件物品放入容量为
v
的背包中
”
这个子问
题，
若只考虑第
i
件物品的策略
（放或不放）
，
那么就可以转化为一个只牵扯
前
i-1
件物品的问题。如果不放第
i
件物品，那么问题就转化
为
“
前
i-1
件物品放入
容量为
v
的背包中
”
< br>，价值为
f[i-1][v]
；如果放第
i
件物品，那么问题就
转化为
“
前
i-1
件物品放
< br>
入剩下的容量为
v-c[i]
的背包中
”
，此时能获得的最大价值就是
f
[i-1][v-c[i]]
再加上通过放入第
i
件物品获得的价值
w[i]
< br>。按此方法，可得总价值是
15
，所以
< br>选择（
B
）
。
< br>
具体内容查阅背包问题相关资料。
(6)
假定有
N
个物品，其价值分别为
V1, V2, ...,
VN
，重量分别为
W1, W2, ..., WN
，背包所
能承受的总重量为
Wmax
，为物品
i
定义一个决策变量
xi
，
其中
xi=1
表示选择该物品，
xi=0
表示不选择该物品。下面哪
个描述共同构成了该问题的数学模型
_____
。
(A)
问题的目标函数是
max
x
V
；
i
i
i
< br>1
N
i
i
N
(B)
问题的目标函数是
max
x
W
；
i
1
(C)
问题解所应满足的约束是
x
W
W
i
i
i
< br>1
N
N
max
< br>；
(D)
问题解所应满足的约束是
x
V
i
1
i
i
< br>W
max
；
(E)
前述
(A)
< br>和
(C)
；
答案：
E
解释：
本题考查问题及其数学建模的作用
该问题有两个条件：
1
）物品不能超过背包所能承受的重量，即（
C
）选项
：
x
W<
/p>
W
i
i
i
1
N
max
2
）背包内物品
价值最大，即（
A
）选项目标函数为
m
ax
x
i
V
i
i
1<
/p>
N
（
B
）和（
D
）选项明显错误，将质量和价值比较
。
所以选择（
E
）
。
具体内容查阅背包问题相关资料。
4
、
TSP-
旅行商问题，是一个经典问题，如下图所示，描述为“
有
n
个城市，任何两个城市
之间的距离都是确定的，
现要求一旅行商从某城市出发必须经过每一个城市且只能在每个城
市逗留一次，
最后回到原出发城市，
问如何事先确定好一条最短的路线使其旅行的
费用最少”
。
围绕
TSP
，回答下列问题。
(1
)
关于
TSP
问题的遍历算法和贪心算
法，下列说法正确的是
_____
。
(A)
对
TSP
问题而言，遍历算法和贪心算法求得的解是一样的，所不同的是贪心算法更
快一些，而
遍历算法更慢一些；
(B)
对
TSP
问题而言，遍历算法和贪心算法求得的解是一样的，所不同的是
遍历算法更
快一些，而贪心算法更慢一些；
< br>(C)
对
TSP
问题而言，
遍历算法和贪心算法求得的解是不一样的，
贪心算法是求近似解，<
/p>
执行更快一些，而遍历算法是求精确解，执行更慢一些；
(D)
对
TSP
问题
而言，
遍历算法和贪心算法求得的解是不一样的，
贪心算法是求
精确解，
执行更快一些，而遍历算法是求近似解，执行更慢一些；
答案：
C
解释：
本题考查对贪心算法与遍历算法的简单理解
< br>贪心算法：一定要做当前情况下的最好选择，否则将来可能会后悔，故名“贪心”
。如
果以
A
城市为起点，
选择最近的下一点，
为
B
城
市。以
B
城市为起点，
选择最近的下一
个城
市，可以选择
C
或
D
，以选择
D
为例。以
D
为起点，选择最近的下一点，为
C
城市。最后回
到
A
。整
个过程的花费为：
14
。于是，该贪心算法的解为
14
。而通过遍历可知，该问题的最
优解为
A-B-C-D-A
，
花费为
< br>13
。
可见，贪心算法与遍历算法的解不会总是完全相同
。而贪心
3
算法只会做当前情况下最优选择，其时间复杂度为
n
级别。而遍历则会将各种情况考虑在
内，其时间复杂度为（
n-1
）
！级别
当城市的数量变多时，遍历算法将会出现组合爆炸。故，
相比之下，贪心算法的计算速度
更快。所以
(C)
选项是正确的。
<
/p>
详细内容请参考第七章视频“算法，程序与计算系统之灵魂”与第七章课件。
(2)
关于
TSP
，下列说法不正确的是
_____
。
(A)TSP
问题
的一个可能解就是
n
个城市的一个组合
i ( -- <
br>TSP <
br>。 <
br>问题，使用了美国
1
,
t
2
,
…
,
t
n<
/p>
>
，其中任何两个
t
，
t
j
都对应不同的城市。若要求得最优解，则必须对所有的组合，即所有可能解进行比较。
(B)TSP
问题的难点是当
n
值很大时，组合数目非常庞大
(
组合数目为<
/p>
n!)
，以致于计算
机不能在有限时间内
完成所有的组合；
(C)TSP
问题
的难点是当
n
值很大时，组合数目非常庞大
组合数目为
n!)
，虽如此，计
算机仍然能够在有限时间内完成所有的组合；
(D)
上述思想
对所有组合进行比较的思想，即是所谓的遍历算法策略，它仅仅对
n
值
很小的
TSP
问题是能行的。
答案：
C
解释：
本题考查对
组合优化问题的理解
对
所有组合进行比较的思想，即所谓的遍历算法策略，其组合数目为
n!
2001
年解决
了德国
15112
个城市的
TSP
Rice
大学和普林斯顿大学之间互连
的、速度
为
500MHz
的
Compaq EV6 Alpha
处理器组成的
110
台计算机，所有计算机花费的时间之和<
/p>
为
22.6
年。由此可见，当
n
巨大时，
用遍历算法解决
TSP
问题是不现实的。
所以
(C)
选项错
误。
详细内容请参考第七章视频“算法，程序与计算系统之灵魂”与第七章课件。
(3)
关于
TSP
的贪心算法的求解思想，下列说法不正确的是
_____
。
(A)
无
需对所有组合
(
所有可能解
)
进行比较，而仅需依照某种办法确定其中的一个组合
即可，该组合不一定
是最优解，但却是一个较优解或次优解；
(B)
在确定一个组合
1
,
t
2
,
…
,
t
n
>
时，
t
k+1
是与
t
k
相连接的城市中与
t
k
距离最短的城市，
即
t
k+
1
是由
t
k
确
定的，与
t
k
连接的若干城市中的特性
最优的城市；
(C)
贪心算法确定的
路径，是由局部最优
(
即
t
k+1
在
t
k
看来是最优的
)
组合起来的路径，该
路径从全局角度也一定是最优的；
(D)
对一个具体的
TSP
问题，每次执行贪心算法，所求得的最终解可能是不同的。
答案：
C
解释：
本题考查对
< br>TSP
贪心算法的理解
（
A
）
(B)
选项都
是对贪心算法的描述，
贪心算法的核心就是：
只考虑当前情况下
得最优
解。故（
A
）
< br>（
B
）正确。贪心算法得到的解释可行解，但不一定是最
优解，故
(C)
错误。在执
行贪心算法
的过程中，
会遇到下一步有两个最优选项的情况，
所以每次执行
贪心算法的最终
解的结果可能是不同的。故
(D)
正确。
详细内容请参考第七章视频“算法，程序与
计算系统之灵魂”与第七章课件。
(4)
下列哪些问题可应用求解
TSP
的算法，正确的是
_____
。
(A)
电路板上需要钻
n
< br>个孔，选择一条最短路径使机器移动并完成所有孔的钻孔工作的
问题
(
机器在电路板上钻孔的调度问题
)
；
(B) n
个盘子在三个
柱子上的移动问题
(
梵天塔问题或者说汉诺塔问题
)
；
(C)
n
座桥，
走过每座桥且仅走过一次的
问题
(
图的遍历问题
)
；
(D)
上述
(A)(B)(C)
都可以。
答案：
A
解释：
本题考查对
< br>TSP
问题抽象的理解
求解
TSP
问题采用的是贪心算法。
(A)
选项所描述的问题其实就是
TSP
问题。
（
B
）选项
所描述的问题是梵天塔问题，应该采用的是递归的思想。
（
C
）选项所描述的图的遍历问题，
主要有深
度优先搜索，
和广度优先搜索两种解决方法，
不是贪心算法。<
/p>
综上，
（
A
）<
/p>
选项正确。
详细内容请参考第七章视频
“算法，程序与计算系统之灵魂”与第七章课件。
(5)
关于下列四个数学抽象，说法正确的是
_
____
。
(
数学抽象
I)
城市记为：
V={
v
1
,
v
2
,
…
,
v
n
}
，
< br>任意两个城市
v
i
,
v
j
∈
V
之间的距离记为：
d
v
i
v
j
，
问题的解是
寻找所有城市的一个访问顺序
T={
t
1
,
t
2
,<
/p>
…
,
t
n
}
，
其中
t
i
∈
V
，
使得
min
n
i=1
d
t
i
t
i+1
，
这里假定除<
/p>
t
n+1
=
t<
/p>
1
外，
t
i
t
j
(i
j
时
)
。
(
数学抽象<
/p>
II)
电路元件记为：
V={
v
1
,
v
2
,
…
,
v
n
}
，
任意两个元件
v
i
,
< br>v
j
∈
V
之间的距离记为：
d
v
i
v
j
，问题的解是寻找所有元件之间的一个访问顺
序
T={
t
1
,
t
2
,
…<
/p>
,
t
n
}
，其中
t
i
∈
V
，使得
min
<
/p>
n
i=1
d
t<
/p>
i
t
i+1
，这
里假定除
t
n+1
=
< br>t
1
外，
t
i
t
j
(i
j
时
)
。
(
数
学抽象
III)
图的结点记为：
V={
v
1
,
v
2
,
…
,
v
n
}
，
任意两个结点
v
i
,
v
j
∈
V
的边的权值记为：
d
v
i
v
j
，问题的解是寻找所有结点之间的
一个访问顺序
T={
t
1
,
t
2
,
< br>…
,
t
n
}
，其中
t
i
∈
V
，使得
min
< br>
n
i=1
d
< br>t
i
t
i+1
< br>，这里假定除
t
n+1
=
t
1
外，
t
i
t
j
(i
j
时
)
。
(
数学抽象
IV)
图的结点记
为：
N = {1,2
，
…
，
n}
，任意两个结点
i
，
j
的边的权值记为：
d
ij
，问题的解是寻找所有结点之间的一个访问顺序
t={t
1
,t
2
,
…
,t
n
}
，其中
t
i
V
，使得
min
min
n
< br>i=1
d
t
i
< br>t
i+1
，这里假定除
t
n+1
=
t
1
外，
t
i
t
j
(i
j
时
)
。
(A)
只有数
学抽象
I
是
TSP
问题，数学抽象
II
和
III
不是；
(B)
数
学抽象
I
和
III
可以被认为是
TSP
问题，数学抽象
II
和
IV
不是；
< br>
(C)
数学抽象
I
、
II
、
III
和
IV
都可以被认为是
TSP
问题；
(D)
上述说法都不正确。
答案：
C
解释：
本题考查对
< br>TSP
问题抽象的理解
I
就是对最原始的
TSP
问题的抽象描述。<
/p>
II
也是对
TSP
问题的描述，
只是将城市换成了
电子元件。
< br>III
和
IV
是对同一问题的不
同表述罢了，都是
TSP
问题，只是将城市换为了图。
四个数学抽象都可以被认为是
TSP
问题。故选
项（
C
）正确。
详细内容请参考第七章视频“算法，程序与计算系统之灵魂”与第七章课件。
5
、数据结构是算法设计的重要步骤
，针对不同问题的算法设计应该选择适当的数据结构，
不同的数据结构会使得解决问题的
算法的性能有所不同。回答下列问题。
(1)
关于数据结构，下列说法不正确的是
_____
。
(A)
数据结构是问题域数学模型中各种
数据的存储结构；
(B)
数据结构是
将逻辑上有一定语义关系的数据，
转换成计算机可以存储和处理的变量，
便于算法和程序进行处理；
(C)
数据结构是将具有一定语义关
系的变量进行命名，以便隐藏数据结构内部的操作细
节，便于算法按逻辑语义通过操控该
名字来操控该数据结构；
(D)
数据结构包含了数据的逻辑结构、存储结构及其操作；
(E)
上述说法有不正确的。
答案：
E
解释：
本题考查对数据结构的理解
数据结构
是数据的逻辑结构、存储结构及其操作的总称，它提供了问题求解
/
算法的数
据操纵机制。
(A) (B) (C)(D)
的说法都没有问题。所以（
E
）是不正确的
。
详细内容请参考第七章视频“算
法，程序与计算系统之灵魂”与第七章课件。
(2)
关于数据结构，下列说法不正确的是
____
__________
？
(A) <
/p>
数据结构由逻辑结构、存储结构及运算
3
部分组成；
(B)
存储结构定义了数据在存储器中的存储方式；
(C)
向量使用顺序存储结构，
并借
助元素在存储器中的相对位置来表示数据元素的逻辑
关系；
(D)
在树结构中，
指针用于表达元
素之间的逻辑关系——父子关系，
每个元素的指针指
向其父节点
，因此一个元素可以有一个或多个指针。
答案：
D
解释：
本题考查对数据结构的理解
数据结构是数据的逻辑结构、存储结构及其操作的总称。
（
A
）正确。数据的存储结构
也就是在反映数据逻辑
关系的原则下，数据在存储器中的存储方式。
（
B
）正确。向量确实
是使用顺序存储结构，并且借助元素在存储器中的相对位置
来表示数据元素的逻辑关系的，
（
C
）
正确。在树结构中，如果每个元素的指针都指向其父节点，那么每个元素只能有一个
指针
。因为每个元素只有一个父亲。故（
D
）错误。
详细内容请参考第七章视频“算法，程序与计算系
统之灵魂”与第七章课件。
6.
数据通常要存储在存储器中，存储器是按地址访问的存储单元的集合，因此存储器可被<
/p>
认为是按线性方式组织数据。
数组是高级语言中经常使用的一种数
据结构，
其按照不同的下
标可访问数组的不同的元素。如下图所
示：
(1)
关于数组和存储器，下列说法不正确的是
_____
。
(A)
和存储器一样，数组是按线性方式组
织数据；
(B)
和存储器一样，一维数组是按线性方式组织数据，一个数据元素需要一个存储单
元
来存储，一个下标即相当于一个存储单元的地址；
(C)
和存储器一样，一维数组是按
线性方式组织数据，一个数据元素需要一个或多个存
储单元来存储，一个下标即相当于一
个存储单元的地址；
(D)
和存储器一样，一维数组是按线性方式组织数据，一个数据元素需要一个或多个存
储单元来存储，一个下标即相当于一个或多个存储单元的地址；
答案：
C
解释：
本题考查对存储器和数组的理解。
数
组是按照线性方式组织数据的。
当一个数据元素需要多个存储单元存储时，
一个下标
代表的就是多个存储单元的地址，所以
(C
)
的说法不准确。其余说法都对。
详
细内容请参考第七章视频“算法，程序与计算系统之灵魂”与第七章课件。
(2)
请
对照上图的左子图和右子图来观察，右子图的二维数组是按左图的形式存储在存储器
中。
则
D[4][2]
元素所对应的存储单元的存储地址为
_____
。
(A)00000000
00000101
；
(B)00000000
00001000
；
(C)00000000
00001010
；
(D)
上述都不正确；
答案：
B
解释：
本题考查对存储器和数组的理解。
图中，二维数组中，
D[4][2]
对
应的元素是
80
，而且是第二个
80.
在存储器中，找到第二
个
80
的位置，其所对应的地址为：
00000000 00001000
；
（
B
）正确。<
/p>
详细内容请参考第七章视频“算法，程序与计算系统之灵魂”与
第七章课件。
(3)
请参照上图的左子图和右子图来观察，右子图的二维数组是按左图的形式存储在存储器
中。则
D[i][j]
元素，与对应存储单元的存储地
址的转换关系正确的为
_____
。
(A)
D[i][j]
元素的存储地址
=
数组的起始地址
+((i-1)*<
/p>
每行的列数
+j-1)*
单一元素占用存
储单元的数目
；
< br>(B)
D[i][j]
元素的存储地址
< br>=
数组的起始地址
+(i-1)*
每行的列数
+j-1
；此公式在任何情况下都正确
；
(C)
D[i][j]
元素的存储地址
=
数组的起始地址
+((j-1)*
每行的列数
+i-1)*
单一元素占用存储单元的数目
；<
/p>
(D)
D[
i][j]
元素的存储地址
=
数组的起
始地址
+(j-1)*
每行的列数
+i
-1
；
此公式在任何情况下都正确
；<
/p>
答案：
A
解释：
本题考查对存储器和二维数组的理解。
记住数组的下标是从
0
开始编号的。
((i-1)*
每行的列数
+j-1)
得到二维数组中，所求的元
素的下标偏
移量。
((i-1)*
每行的列数
+j
-1)
*
单一元素占用存储单元的数
目得到地址的偏移量。
再加上数组的起始地址，便可得到所求元素的地址。
（
A
）正确。
详细内容请参考第七章视频“算法，程序与计算系统之灵魂”
与第七章课件。
7.
“树”是一种典型的数据结构，在很多算法中都应用树来组织相关的数据。树是组织层次
型数据的一种存储结构，它将每一个数据称为一个数据元素。见下图
I.
示意，采用三个数组
来存储树型数据，一个数组
TreeElement[]
存放数据元素本身，一个数组
LeftPointer[]
存放该
数据元素的左侧子元素的存
放地址
(
简称为左指针
)
，
另一个数组
RightPointer[]
存放该数据元
素的右侧子元素的存放地址
(<
/p>
简称为右指针
)
。参照图
I.
，回答下列问题。
图
I.
(
1)
关于“树”这种数据结构，下列说法不正确的是
_____
。
(A)
“
树”既需要存储数据元素本身即数据，还需要存储数据元素之间的关系；
(B)
“树”可以采用两个数组来组织树型数据，其中一个数组用于存储数据
元素本身，
另一个数组用于存储与该数据元素发生某种关系的另一个数据元素的存储位置
；
(C
)
“树”可以采用三个数组来组织树型数据，其中一个数组用于存储数据元素本身，
另外两个数组用于存储与该数据元素发生某种关系的另外两个数据元素的存储位置；
(D)
不仅可以采用
(B)(C)
的方式组织树型数据
，还有其他的方式；
(E)
上述说法有不正确的。
答案：
E
解释：