首页 > 算法分析与设计_西南科技大学试题单(G)

算法分析与设计_西南科技大学试题单(G)

发布时间：来源：文档文库

小中大

字号：

手机查看

西南科技大学试题单（G）
计算机学院:课程名称:《算法分析与设计》课程代码:14314025命题单位:软件教研室
学院：________专业班级：_______学号：□□□□□□□□命题共2页第1页

一、简答题（共23分）：
1．简述算法的复杂性分析主要是分析算法的什么耗费情况以及算法的时间复杂度用什么计量？（5分）
2．简述动态规划和贪心算法的基本思想。（10分）3．推导归并排序算法的时间复杂度。（8分）

二、解答题（要求给出解答步骤，尤其强调所用方法；共61分）1．写出分治策略的抽象化控制算法。（10分）
2．在下面的有向图中，利用贪心策略求出由结点1到其余各结点的最短路径长度。（15分）
25101520
304102144
151036
3．对于如下的0/1背包问题，n=4，P={15,10,6,4}，W={6,4,3,2}，M=22。（1）给出该问题动态规划方法解结构的形式和递推关系式。（6分）（2）写出算法的计算过程，并给出最优解（10分）
（3）试分析贪心策略和动态规划解决该问题得到的结果有何异同。（5分）
4．有n个程序和长度为L的磁带，程序i的长度为ai，已知
n
∑a
i=1
n
i
fL
，求
最优解(xi，x2，...，xi，…，xn，1,xi=1，表示程序i存入磁带，xi=0，表
示程序i不存入磁带，满足
∑xa
ii=1
i
≤L
，且使得磁带的利用率最大。（15分）
5．给定k个排好序的序列s1，s2，…，sk，现要用2路合并算法将这k个
序列合并成一个有序序列。假设所采用的2路合并算法合并两个长度分别为m

和n的序列需要m+n-1次比较。用贪心算法设计一个算法确定合并这个序列的最优合并顺序使得所需的总比较次数最少（要求：1）给出贪心选择策略；2）写出贪心算法；3）证明该问题满足贪心选择性质）。（16分）

本文来源：https://www.2haoxitong.net/k/doc/acaab53e0912a216147929cb.html