中南大学现代远程教育课程考试复习试题及参考答案
- 格式：doc
- 大小：101.50 KB
- 文档页数：19
中南大学现代远程教育课程考试复习试题及参考答案
《算法分析与设计》
一 简答题
1. 算法的复杂性分析主要是分析算法的什么耗费情况？
2. 算法的重要特性是什么？
3. 算法的时间复杂度用什么计量？
4. 用比较树模型描述三个数排序的过程。
5. 分治法的基本思想。
6. 二分检索算法为什么可以提高查找的效率？
7. 简述顺序选择select算法的基本流程。
8. 简述顺序选择select2算法的改进思路。
9. 简述快速排序的基本思想。
10. 快速排序算法的最坏时间复杂性和平均时间复杂性函数。
11. 快速排序算法怎样抽取分割元素？
12. partition怎样将数组划分成3段？
13. 分治合并排序的是怎样分治的？
14. 分治合并排序的二分归并过程在最坏情况下花费多少时间？
15. 分治合并排序的二分归并过程在最好情况下花费多少时间？
16. MaxMin算法是怎样分治的？
17. 贪心法的基本思路是什么？
18. 用贪心法求解的问题有什么特点？
19. 背包问题的目标函数是什么，最优量度是什么？
20. 带限期的作业调度的贪心策略是什么？约束条件是什么？
21. 说明n皇后问题的解（x1,x2,….,xn）的含义。
22. 简述n皇后算法的place函数的功能。
23. 简述动态规划方法所运用最优化原理。
24. 用多段图说明最优化原理。
二 解释下列动态规划优解的一般递归形式。
1） 0/1背包
2） 货郎担问题
3） 流水作业调度
三 算法分析。
1． 分析汉诺塔算法的时间复杂性。
2． 计算冒泡排序算法时间复杂性的阶。
3． 分析maxmin算法的时间复杂性。
4． 分析分治合并排序算法的时间复杂性。
5． 分析二分检索的时间复杂性。
6． 背包问题贪心算法的时间复杂性。
7． 快速排序的partition过程中，进行了多少次元素之间的比较。 8． 多段图算法的时间复杂性。
四 算法段填空。
1． MaxMin 算法
Maxmin(i,j,max,min)
if
then 对两元素进行比较;return;
else
{
maxmin(i,m,max1,min1); //其中max1和min1为解子问题1的解
}
2． Hanoi算法
Hanoi(n,a,b,c)
If n=1 then
Else
{
;
Hanoi(n-1,b, a, c);
}
3． 二分检索
BINSRCH(A,n,x,j)
low←1;high←n;
while low
{ ________________ mid←(low+high)/2;
case
：x=A[mid] ：j←mid; return;
：x< A[mid]：_________________high←mid-1;
：x> A[mid]：_________________low←mid+1;
endcase
}
j←0;
end
4． 快速排序
Quicksort(p,q)
if p>q then_____________
{call partition(p,j);
call _______________________
call _______________________
}
end
5． 贪心方法的抽象化控制
procedure GREEDY(A，n)
//A(1：n)包含n个输入//
solutions← ；
for i←1 to do
{x←SELECT(A)
if FEASIBLE(solution，x)
then solutions← ；
endif
}
return(solution)
end GREEDY
6． 背包问题贪心算法
procedure GREEDY-KNAPSACK(P，W，M，X，n)
X←0 ；
cu←M ；
for i←1 to n do
{ if then exit endif
X(i) ← _ ；
cu← ；
}
if i ≤n then X(i) ← ；
endif
end GREEDY-KNAPSACK
7． 分治合并排序算法
procedure MERGESORT(low,high)
if low < high then
mid ←_______________
____________________
____________________
MERGE(low,mid,high)
endif
end MERGESORT
8． 多段图动态规划算法
procedure FGRAPH(E，k，n，P)
1 real COST(n)，integerD(n一1)，P(k)，r，j，k，n
2 ；
3 for to 1 by－1do
4 设r是一个这样的结点，(j，r)E且使c(j，r)+COST(r)取最小值
5 COST(j)← ；
6 ；
7 repeat
8 P(1)←1；P(k)←n；
9 for do
10 P(j)←D ( P(j-1) )
11 repeat
12 end FGRAPH
9． n后问题递归算法
procedure RNQUEENS(K)
global x( 1:m ),n;
for x(k)←1 to _____ do
if place( k )= true then
if k = n then ________
else
_____________
endif
endif
repeat
end ENQUEENS
1． 写递归形式的二分检索算法
2． 设计三分检索算法
3． 有n个大小相同而重量不同的集装箱，重量分别为(w1,w2,……,wn)，已知货船的额定载重量为M，Σwi>M,i=1,2,3，…，n。最优解是货船能够装载最多的集装箱。设计贪心算法。
4． 有n 个程序和长度为L的磁带，程序i的长度为ai，已知Lanii1，求最优解(xi，x2 ，...，xi，…， xn)，1, xi =1，表示程序i存入磁带，xi =0，表示程序i不存入磁带，满足Laxniii1，且存放的程序数目最多。
参考答案
一、简答题
1. 算法的复杂性是算法运行所需要的计算机资源的耗费量，需要的时间资源的耗费量称作时间复杂性。
2. 有5个基本特性是：确定性、能行性、输入给定、产生输出、有穷性。
3. 算法复杂性用算法的基本运算步骤计量，运算步骤与算法要解的问题的规模、算法的输入有关。
4. 比较树模型
5. 分治的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。找出各部分的解，然后把各部分的解组合成整个问题的解。
6. 分治算法时间是这样确定的：解决子问题所需的工作总量由子问题的个数、解决每个子问题的工作量、合并所有子问题所需的工作量所决定。折半查找最坏情况下，也只需要在原问题一半大小的子问题中查找，而且不需要合并子问题。
7. 首先对于数组a[p：q]进行划分，以元素v为基准元素将a划分为三段a[p：j-1]，a[j]和a[j+1：q]，使得a[p：j-1]中任何一个元素都小于v，a[j+1：q]中任何一个元素大于等于v，下标j在划分中确定。
如果 k = j ，则返回v；
如果 k < j ，则在a[p：j-1]中选择；
如果 k> j ，则在a[j+1：q]中选择；
8. select算法的最坏情况下的时间复杂性的阶为O(n2)，其原因是a[p：j-1]和a[j+1：q]的大小不是均衡的。Select2算法的基本思路就是改随即抽取v为经过经处理产生，保证在最坏情况下a[p：j-1]和a[j+1：q]的元素个数不会小于原规模的1/4。
9. 快速排序是基于分治策略的一个排序算法。基本思路：
a) 分解(Divide) 以元素v为基准元素将a划分为三段a[p：j-1]，a[j]和a[j+1：q]，使得a[p：j-1]中任何一个元素都小于v，a[j+1：q]中任何一个元素大于等于v，下标j在划分中确定。
b) 递归求解，通过递归调用快速排序算法分别对a[p:j-1] 和a[j+1:q]进行排序。
不必进行任何合并操作。
10. 快速排序算法的最坏情况下的时间复杂性的阶为O(n2)，其原因是a[p：j-1]和a[j+1：q]的大小不是均衡的。快速排序算法的平均时间复杂性的阶为O(n log n)。
11. 采用随机抽取。对于数组a[p：q]，用v= a[p]作为分割元素。
12. 使v= a[p]，q=q+1
while (p
{ do p++; while (a[p] < v);
do q++; while (a[q] > v);
if (p
}
