没有合适的资源?快使用搜索试试~ 我知道了~
算法设计与分析试卷A卷-20080525-参考答案-第二版-by+zzm.doc
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 134 浏览量
2022-05-06
22:15:39
上传
评论
收藏 160KB DOC 举报
温馨提示
试读
9页
算法设计与分析试卷A卷-20080525-参考答案-第二版-by+zzm.doc
资源推荐
资源详情
资源评论
算法设计与分析试卷 A 卷-20080525-参考答案-第二版-by zzm
(含试题预测、课堂笔记)
试题答案:
一、 简答题
1. 答:如果一个算法不需要额外的存储空间(除个别存储单元以外),我们把它称为是
在位的。
2. 答:如下图,求 A 到 C 的最短距离。Dijkstra 算法只需一步,就计算出 A 到 C 最短路径
为 A-C,长度为 3;事实上,图中因为存在负权重的边,A 到 C 的最短路径应是 A-B-
C,长度为 2。
3. 答:对问题的部分或全部输入做预处理,然后对获得的额外信息进行存储,以加速后
面问题的求解。我们把这个方法称为输入增强。
二、 答:
解法一:
Mindist (A[0..n-1])
dist ← ∞
for i ← 0 to n-2 do
for j ← i+1 to n-1 do
if │A[i]-A[j]│<dist
dist ← │A[i]-A[j]│
Return dist
解法二:
Mindist (A[0..n-1])
将数组 A 复制到数组 B;
用 O(nlog n)的排序算法对B进行升序排序;
dist ← B[1]-B[0];
for i ← 1 to n-2 do
if B[i+1]-B[i]<dist
dist ← B[i+1]-B[i]
Return dist
解析:解法一将基本操作│A[i]-A[j]│<dist 的运算次数从 n
2
将为(n
2
-n)/2;解法二采用输入
增强技术,算法的效率取决于排序算法的效率。原题并没有明确说明算法要改进到什么程
度。
三、 答:
(1) 求数组 A 中两个元素的最大差值;
(2) 基本操作是:A[i]<min 和 A[i]>max;
(3) 函数中循环体共循环 n 次,每次都执行两个基本操作,所以基本操作执行次数为
A
C
B
3
4
-2
1
资源评论
老帽爬新坡
- 粉丝: 79
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功