算法分析与设计 第十次理论作业
一. 填空题（共1题，20分）
-
(填空题) 根据本课程的学习内容，列举出一种既可以用动态规划算法、也可以用回溯法和分支限界法求解的问题：____。
正确答案： (1) 0-1背包问题，装载问题
二. 判断题（共3题，60分）
-
(判断题) 利用优先队列式分支限界法求单源最短路径问题时，用数组p记录从源到各顶点的路径上的前驱顶点。
利用前驱顶点数组p记录的信息可以求出最短路径。
A. 对
B. 错正确答案: 对
-
(判断题) 在布线问题中，要构造出与最短距离相应的最短路径，可以从目标方格开始向起始方格回溯，每次向标记距离比当前方格标记距离少1的相邻方格移动，直至达到起始方格为止。
A. 对
B. 错正确答案: 对
-
(判断题) 装载问题既可以用回溯法求解，也可以用分支限界法求解。
A. 对
B. 错正确答案: 对
三. 单选题（共1题，20分）
-
(单选题) 下列问题中，不能用分支限界法求解的是（ ）。
A.旅行售货员问题
B.0-1背包问题
C.矩阵乘法
D.最大团问题正确答案: C :矩阵乘法 ;