1.已知有
3
个物品：(w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10),背包的容积
M=20，根据
0-1
背
包动态规划的递推式求出最优解。
2.按要求完成以下关于排序和查找的问题。
①对数组
A={15，29，135，18，32，1，27，25，5}，用快速排序方法将其排成递减序。
②请描述递减数组进行二分搜索的基本思想，并给出非递归算法。
③给出上述算法的递归算法。
④使用上述算法对①所得到的结果搜索如下元素，并给出搜索过程：18，31，135。
3.已知
1
(
)
*
(
)
i
i
k
k
ij
r
r
A
a
+
=
，
k
=1，2，3，4，5，6，
r
1
=5，
r
2
=10，
r
3
=3，
r
4
=12，
r
5
=5，
r
6
=50，
r
7
=6，
求矩阵链积
A
1
×A
2
×A
3
×A
4
×A
5
×A
6
的最佳求积顺序（要求给出计算步骤）
。
4.
根
据
分
枝
限
界
算
法
基
本
过
程
,
求
解
0-1
背
包
问
题
。
已
知
n=3,M=20
，
(w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10)。
5.试用贪心算法求解汽车加油问题：
已知一辆汽车加满油后可行驶
n
公里，
而旅途中有若干个加油站。
试设计一个有效算法，指出应在哪些加油站停靠加油，使加油次数最少，请写出该算法。
6.试用动态规划算法实现下列问题：设
A
和
B
是两个字符串。我们要用最少的字符操作，将字符串
A
转换为字符串
B，这里所说的字符操作包括：
①删除一个字符。
②插入一个字符。
③将一个字符改为另一个字符。
请写出该算法。
7.对于下图使用
Dijkstra
算法求由顶点
a
到顶点
h
的最短路径。
8.试写出用分治法对数组
A[n]实现快速排序的算法。
9.有
n
个活动争用一个活动室。
已知活动
i
占用的时间区域为[s
i
，
f
i
]，
活动
i,j
相容的条件是：
sj≥f
i
，问题的解表示为(x
i
|
x
i
=1，2…，n,)，x
i
表示顺序为
i
的活动编号活动，求一个相容的活动子
集，且安排的活动数目最多。
10.设
x
1
、
x
2
、
x
3
是一个三角形的三条边，而且
x
1
+x
2
+x
3
=14。请问有多少种不同的三角形？给出解答过
程。
11.设数组
A
有
n
个元素，需要找出其中的最大最小值。
①请给出一个解决方法，并分析其复杂性。
②把
n
个元素等分为两组
A1
和
A2，分别求这两组的最大值和最小值，然后分别将这两组的最大值
和最小值相比较，求出全部元素的最大值和最小值。如果
A1
和
A2
中的元素多于两个，则再用上述
方法各分为两个子集。直至子集中元素至多两个元素为止。这是什么方法的思想？请给出该方法的
算法描述，并分析其复杂性。
12.有
n
个程序和长度为
L
的磁带，
程序
i
的长度为
a
i
，
已知
L
a
n
i
i
≻
∑
=
1
，
求最优解(x
i
，
x
2
，
...，
x
i
，
…，
x
n
)，x
i
=0，1,
x
i
=1，表示程序
i
存入磁带，x
i
=0，表示程序
i
不存入磁带，满足
L
a
x
n
i
i
i
≤
∑
=
1
，
且存放的程序数目最多。
13.试用分治法实现有重复元素的排列问题：设
)
,...,
,
{
2
1
n
r
r
r
R
=
是要进行排列的
n
个元素，其中元素
n
r
r
r
,...,
,
2
1
可能相同，试设计计算
R
的所有不同排列的算法。
14.试用动态规划算法实现
0-1
闭包问题，请写出该算法。
15.试用贪心算法求解下列问题：将正整数
n
分解为若干个互不相同的自然数之和，使这些自然数的乘
积最大，请写出该算法。
16.试写出用分治法对一个有序表实现二分搜索的算法。
17.试用动态规划算法实现最长公共子序列问题，请写出该算法。
18.假设有
7
个物品，它们的重量和价值如下表所示。若这些物品均不能被分割，且背包容量
M＝150，
使用回溯方法求解此背包问题，请写出状态空间搜索树。
物品
A
B
C
D
E
F
G
重量
35
30
60
50
40
10
25
价值
10
40
30
50
35
40
30
19.求解子集和问题：对于集合
S={1，2
，6，8}，求子集，要求该子集的元素之和
d=9。
①画出子集和问题的解空间树；
②该树运用回溯算法，写出依回溯算法遍历节点的顺序；
③如果
S
中有
n
个元素，指定
d，用伪代码描述求解子集和问题的回溯算法。
20.求解填字游戏问题：在
3×3
个方格的方阵中要填入数字
1
到
N（N≥10）内的某
9
个数字，每个方
格填一个整数，似的所有相邻两个方格内的两个整数之和为质数。试采用回溯法写出满足这个要求
的一种数字填法的算法和满足这个要求的全部数字填法的算法。
21.试用动态规划算法实现最大子矩阵和问题：
求
n
m
×
矩阵
A
的一个子矩阵，
使其各元素之和为最大。
22.试用回溯法解决下列整数变换问题：关于整数
i
的变换
f
和
g
定义如下：
⎣
⎦
2
/
)
(
;
3
)
(
i
i
g
i
i
f
=
=
。
对于给定的两个整数
n
和
m
，要求用最少的变换
f
和
g
变换次数将
n
变为
m
。
23.关于
15
谜问题。在一个
4×4
的方格的棋盘上，将数字
1
到
15
代表的
15
个棋子以任意的顺序置入
各方格中，空出一格。要求通过有限次的移动，把一个给定的初始状态变成目标状态。移动的规则
是：每次只能把空格周围的四格数字（棋子）中的任意一个移入空格，从而形成一个新的状态。为
了有效的移动，设计了估值函数
C
1
(x)，表示在结点
x
的状态下，没有到达目标状态下的正确位置
的棋子的个数。
内容全部来源于网络收集，如有侵权，请联系网站删除：QQ：24596024