没有合适的资源?快使用搜索试试~ 我知道了~
算法分析与设计复习题及参考答案.doc
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 58 浏览量
2022-05-30
18:08:00
上传
评论
收藏 1.05MB DOC 举报
温馨提示
试读
19页
算法分析与设计复习题及参考答案.doc
资源推荐
资源详情
资源评论
网络教育课程考试复习题及参考答案
算法分析与设计
一、名词解释:
1.算法 2.程序
3.递归函数 4.子问题的重叠性质
5.队列式分支限界法 6.多机调度问题
7.最小生成树
二、简答题:
1.备忘录方法和动态规划算法相比有何异同?简述之。
2.简述回溯法解题的主要步骤。
3.简述动态规划算法求解的基本要素。
4.简述回溯法的基本思想。
5.简要分析在递归算法中消除递归调用,将递归算法转化为非递归算法的方法。
6.简要分析分支限界法与回溯法的异同。
7.简述算法复杂性的概念,算法复杂性度量主要指哪两个方面?
8.贪心算法求解的问题主要具有哪些性质?简述之。
9.分治法的基本思想是什么?合并排序的基本思想是什么?请分别简述之。
10.简述分析贪心算法与动态规划算法的异同。
三、算法编写及算法应用分析题:
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. 已 知 ,
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
,已知 ,求最优解(x
i
,x
2
,...,x
i
,
… , x
n
), x
i
=0 , 1, x
i
=1 , 表 示 程 序 i 存 入 磁 带 , x
i
=0 , 表示 程 序 i 不 存 入 磁 带 , 满 足
,且存放的程序数目最多。
13. 试 用 分 治 法 实 现 有 重 复 元 素 的 排 列 问 题 : 设 是 要 进 行 排 列 的 个 元 素 , 其 中 元 素
可能相同,试设计计算 的所有不同排列的算法。
14.试用动态规划算法实现 0-1 闭包问题,请写出该算法。
15.试用贪心算法求解下列问题:将正整数 n 分解为若干个互不相同的自然数之和,使这些自然数的乘积
最大,请写出该算法。
16.试写出用分治法对一个有序表实现二分搜索的算法。
17.试用动态规划算法实现最长公共子序列问题,请写出该算法。
18.假设有 7 个物品,它们的重量和价值如下表所示。若这些物品均不能被分割,且背包容量 M=150,
使用回溯方法求解此背包问题,请写出状态空间搜索树。
物品
A B C D E F G
重量
3
5
3
0
6
0
5
0
4
0
1
0
2
5
价值 1 4 3 5 3 4 3
0 0 0 0 5 0 0
19.求解子集和问题:对于集合 S={1,2 ,6,8},求子集,要求该子集的元素之和 d=9。
① 画出子集和问题的解空间树;
② 该树运用回溯算法,写出依回溯算法遍历节点的顺序;
③ 如果 S 中有 n 个元素,指定 d,用伪代码描述求解子集和问题的回溯算法。
20.求解填字游戏问题:在 3×3 个方格的方阵中要填入数字 1 到 N(N≥10)内的某 9 个数字,每个方
格填一个整数,似的所有相邻两个方格内的两个整数之和为质数。试采用回溯法写出满足这个要求的
一种数字填法的算法和满足这个要求的全部数字填法的算法。
21.试用动态规划算法实现最大子矩阵和问题:求 矩阵 A 的一个子矩阵,使其各元素之和为最大。
22.试用回溯法解决下列整数变换问题:关于整数 的变换 和 定义如下: 。
对于给定的两个整数 和 ,要求用最少的变换 和 变换次数将 变为 。
23.关于 15 谜问题。在一个 4×4 的方格的棋盘上,将数字 1 到 15 代表的 15 个棋子以任意的顺序置入
各方格中,空出一格。要求通过有限次的移动,把一个给定的初始状态变成目标状态。移动的规则是 :
每次只能把空格周围的四格数字(棋子)中的任意一个移入空格,从而形成一个新的状态。为了有效
的移动,设计了估值函数 C
1
(x),表示在结点 x 的状态下,没有到达目标状态下的正确位置的棋子的
个数。
请使用该估计函数,对图示的初始状态,给出使用分支限界方法转换到目标状态的搜索树。
初 始 状 态 目标状态
1 2 4
5 6 3 7
9
1
0
1
2
8
1
3
1
4
1
1
1
5
1 2 3 4
5 6 7 8
9
1
0
1
1
1
2
1
3
1
4
1
5
剩余18页未读,继续阅读
资源评论
老帽爬新坡
- 粉丝: 83
- 资源: 2万+
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功