算法设计与分析■期末考试题整理
1、 一个算法应有哪些主要特征？
又穷性，确定性，可行性，0个或多个输入，一个或多个输岀
2、 分治法(Divide and Conquer)与动态规划(Dynamic Programming)有什么不同？
分治算法会重复的求解公共了问题，会做许多不必要的T作，而动态规划对每个了问题Z求 解一次，将其结果存入一张表屮，从而避免了每次遇到各个了问题有从新求解。
3、 试举例说明贪心算法对有的问题是有效的，而对一些问题是无效的。
贪心算有效性：最小生成树、哈弟曼、活动安排、单元最短路径。
无效反例：0——I背包问题，无向图找嚴短路径问题。
4、 求解方程 fi[l)=f(2)=l。
由 f(n)=f(n-1 )+f(n-2) nJ'得
f(n)-f(n-l)-f(n-2)=0M得方程的特征方程为
/ _兀一 1 = 0,设特征方程的2个根本分别为"，兀2,则可得 尤]=心=匕二2,则有
- 2
1 4- V5 „ 1 — yl~5 n /S) = C|(—y—) +C2(—y—)
乂/•⑴= .f(2) “可得
可得 C] = a,c2 = h
f(n) = a(^y+b(^)
5、 求解方稈 T(n)=2T(n/2)+l, T(l)=l,设 尸2匚r(n) = 2r(n/2) + l
2T(n/2) = 22T(n/22) + 2
22T(/7/22) = 23T(A?/23) + 22
2iTS/2z) = 25S/2*) + 2"T
上面所有式子相加，相消得
T(n) = 2*7(1) + 2°+2,+22 + + 2^ -J-2*
=2k +1* -------- 1-2
=2A+, -1
6、 编写一个Quick Sorting算法，并分析时间复杂性。
int part(int *a,int p,int r){
int i,j,x,t;
x=a[r];
i=p-l；
精品文档
精品文档 西南交通大学2015－2016学年第(一)学期考试试卷
课程代码 3244152 课程名称 算法分析与设计 考试时间 120 分钟
题号 一
二 三 四 五 总成绩
得分 ·
阅卷教师签字：
一、 填空题（每空1分，共15分）
1、 程序是 （1）
用某种程序设计语言的具体实现。
2、 矩阵连乘问题的算法可由 （2） 设计实现。
3、 从分治法的一般设计模式可以看出，用它设计出的程序一般是 （3） 。
4、 大整数乘积算法是用 （4） 来设计的。
5、 贪心算法总是做出在当前看来 （5） 的选择。也就是说贪心算法并不从整体最优考虑，它所做出的选择只是在某种意义上的 （6） 。
6、 回溯法是一种既带有 （7） 又带有 （8） 的搜索算法。
7、 平衡二叉树对于查找算法而言是一种变治策略，属于变治思想中的 （9） 类型。
8、 在忽略常数因子的情况下，O、和三个符号中， （10） 提供了算法运行时间的一个上界。
9、 算法的“确定性”指的是组成算法的每条 (11) 是清晰的，无歧义的。
10、 问题的 (12) 是该问题可用动态规划算法或贪心算法求解的关键特征。
11、 算法就是一组有穷 (13) ，它们规定了解决某一特定类型问题的 (14) 。
12、 变治思想有三种主要的类型：实例化简，改变表现， (15) 。
二、 选择题（每题2分，共20分）
1、 二分搜索算法是利用（ ）实现的算法。
A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、 衡量一个算法好坏的标准是（ ）。
A、运行速度快 B、占用空间少 C、 时间复杂度低 D、代码短
内部资料，转载请注明出处，谢谢合作。
北京大学信息科学技术学院考试试卷
考试科目：算法设计与分析姓名：学号：
考试时间：2009年6月9日任课教师:
考场纪律1．请持学生证入场考试，并按指定座位就座；除必要的文具和教师指定的用具用书外，其他所有物品包括手机、呼机、MP3、电子词典、书籍、笔记、纸张等严禁带入座位，必须放在指定位置。凡有试卷印制问题请向监考教师提出，不得向其他考生询问。2．认真、诚实、独立并在规定时间内完成答卷，严禁任何形式的违纪作弊行为；否则，本答卷成绩以0分记，并根据《北京大学本科考试工作与学术规范条例》给予纪律处分。3．提前交卷的考生不要在考场逗留，不要在门口、窗外大声喧哗。考试结束时间到，请停止答卷，在座位等候监考教师收卷并清点完毕，方可离开考场；考题和试卷不得带出考场。
以下为试卷和答题纸，共 9 页。
一、填空题(选做5道，10分)
1．用矩阵幂的方法求斐波那契数，其运行时间为（）。题号一二三四五六七八总分
分数
阅卷人装
订
线
内
不
要
答
题
2．对于一个可以用动态规划法求解的问题，要求问题既要满足（）的特
性，又要具有大量的（）。
3．对于一个可以用贪心法求解的问题，不仅要求问题满足（）的特性，还
应证明其贪心策略的（）。
4．设有n个栈操作（PUSH、POP、MULTIPOP ）的序列，作用于初始为
空的栈S。不区分三种操作，则每个操作的最坏运行时间为（），平摊
运行时间为（）。
5．三种平摊分析的方法分别为（）、（）、（）。
6．四后问题的搜索空间为（）树；0-1背包问题的搜索空间为（）树；巡
回售货员问题的搜索空间为（）树。
7．（）法的求解目标是找出解空间树中满足约束条件的所有解，而（）法
的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解
中找出在某种意义下的最优解。
8．回溯法一般以（）优先的方式搜索解空间树，而分支限界法则一般以
（）优先或以最小耗费优先的方式搜索解空间树。
二、单项选择题 (10分)
湖南科技学院二○年学期期末考试
信息与计算科学专业年级《算法设计与分析》试题
考试类型：开卷试卷类型：C卷考试时量：120分钟
一、填空题（每小题3分，共计30分）
1.用O、Ω和θ表示函数f与g之间的关系______________________________。
2.算法的时间复杂性为1,1()8(3/7),2nfnfnnn，则算法的时间复杂性的阶为__________________________。
3.快速排序算法的性能取决于______________________________。
4.算法是_______________________________________________________。
5.在对问题的解空间树进行搜索的方法中，一个活结点最多有一次机会成为活结点的是_________________________。
6.在算法的三种情况下的复杂性中，可操作性最好且最有实际价值的是_____情况下的时间复杂性。
7.大Ω符号用来描述增长率的下限，这个下限的阶越___________，结果就越有价值。。
8.____________________________是问题能用动态规划算法求解的前提。
9.贪心选择性质是指____________________________________________________________________________________________________________________。
10.回溯法在问题的解空间树中，按______________策略，从根结点出发搜索解空间树。
二、简答题（每小题10分，共计30分）
1.试述回溯法的基本思想及用回溯法解题的步骤。
2.有8个作业{1,2,…,8}要在由2台机器M1和M2组成的流水线上完成加工。每个作业加工的顺序都是先在M1上加工，然后在M2上加工。M1和M2加工作业i所需的时间分别为：
