第1页 / 共13页
第2页 / 共13页
第3页 / 共13页
第4页 / 共13页
第5页 / 共13页
第6页 / 共13页
第7页 / 共13页
第8页 / 共13页
算法分析与设计考试复习题及参考答案.doc
A=(65,70,75,80,85,55,50,2)
dist(1,2)=6;dist(2,5)=3;dist(5,6)=6;dist(6,4)=2;di
dist(1,3)=1;dist(2,3)=5;dist(3,4)=5;dist(3,6)=4;di
13、有如下函数说明
int f(int x,int y)
{
f=x Mod y +1;
}
已知a=10,b=4,c=5 则执行k=f(f(a+c,b),f(b,c))后，k的值是多少并写出详
14、McCathy函数定义如下：
当x>100时 m(x)=x-10;
当x<=100时 m(x)=m(m(x+11));
编写一个递归函数计算给定x的m(x)值。
15、 设计一个算法在一个向量A中找出最大数和最小数的元素。
四、设计算法
参考答案
19.快速排序的基本思想是在待排序的N个记录中任意取一个记录，把该记录放在最终位置后，数据序列被此记
4、第一个分割元素为65
一共要要执行四次才能找到值为82的数。
dist(1,2)=6;dist(2,5)=3;dist(5,6)=6;dist(6,4)=2;di
dist(1,3)=1;dist(2,3)=5;dist(3,4)=5;dist(3,6)=4;di
13.有如下函数说明
int f(int x,int y)
{
f=x Mod y +1;
}
已知a=10,b=4,c=5 则执行k=f(f(a+c,b),f(b,c))后，k的值是多少并写出详
}
K的值是5
14.McCathy函数定义如下：
当x>100时 m(x)=x-10;
当x<=100时 m(x)=m(m(x+11));
编写一个递归函数计算给定x的m(x)值。
int m(int x)
{
int y;
if(x>100) return(x-100);
else
{
y=m(x+11);
return (m(y));
}
}
15 设计一个算法在一个向量A中找出最大数和最小数的元素。
Void maxmin(A,n)
Vector A;
int n;
{
int max,min,i;
max=A[1];min=A[1];
for(i=2;i<=n;i++)
if(A[i]>max)max=A[i];
else if(A[i]
printf(“max=%d,min=%d\n”,max,min);
}
四、设计算法
中南大学现代远程教育课程考试复习题及参考答案
算法分析与设计
一、简要回答下列问题 ：
1. 算法重要特性是什么？
2. 算法分析的目的是什么？
3. 算法的时间复杂性与问题的什么因素相关？
4. 算法的渐进时间复杂性的含义？
5. 最坏情况下的时间复杂性和平均时间复杂性有什么不同？
6. 简述二分检索（折半查找）算法的基本过程。
7. 背包问题的目标函数和贪心算法最优化量度相同吗？
8. 采用回溯法求解的问题，其解如何表示？有什么规定？
9. 回溯法的搜索特点是什么？
10. n 皇后问题回溯算法的判别函数 place 的基本流程是什么？
11. 为什么用分治法设计的算法一般有递归调用？
12. 为什么要分析最坏情况下的算法时间复杂性？
13. 简述渐进时间复杂性上界的定义。
14. 二分检索算法最多的比较次数？
15. 快速排序算法最坏情况下需要多少次比较运算？
16. 贪心算法的基本思想？
17. 回溯法的解（x1,x2,……xn）的隐约束一般指什么？
18. 阐述归并排序的分治思路。
19. 快速排序的基本思想是什么。
20. 什么是直接递归和间接递归？消除递归一般要用到什么数据结构？
21. 什么是哈密顿环问题？
22. 用回溯法求解哈密顿环，如何定义判定函数？
23. 请写出 prim 算法的基本思想。
二、复杂性分析
1、 MERGESORT(low，high)
if lowM then return
endif
1
a←a+i
i←i+1 ;
repeat
end
3.procedure PARTITION(m,p)
Integer m,p,i;global A(m:p-1)
v←A(m);i←m
loop
loop i←i+1 until A(i) ≥v
loop p←p-1 until A(p) ≤v
if i
xmax repeat end MAX then xmax←A(i); j←i;endif 6.procedure BINSRCH(A,n,x,j) integer low,high,mid,j,n; low←1;high←n while low≤high do mid←|_(low+high)/2_| case 2
:xA(mid):low←mid+1
:else:j←mid; return
endcase
repeat
j←0
end BINSRCH
三、算法理解
1、写出多段图最短路经动态规划算法求解下列实例的过程，并求出最优值。
1
2
3
4
5
6
7
8
各边的代价如下：
C(1,2)=3， C(1,3)=5 ，C(1,4)=2
C(2,6)=8 ，C(2,7)=4 ，C(3,5)=5 ，C(3,6)=4， C(4,5)=2，C(4,6)=1
C(5,8)=4， C(6,8)=5 ，C(7,8)=6
2、 写出 maxmin 算法对下列实例中找最大数和最小数的过程。
数组 A=(48,12,61,3,5,19,32,7)
3、 给出 5 个数(3,6,9,1,7),M=13，用递归树描述 sumofsub 算法求和数=M 的一个子集
的过程。
4、 快速排序算法对下列实例排序，算法执行过程中，写出数组 A 第一次被分割的过程。
A=(65,70,75,80,85,55,50,2)
5、 归并排序算法对下列实例排序，写出算法执行过程。
A=(48,12,61,3,5,19,32,7)
6、 写出图着色问题的回溯算法的判断 X[k]是否合理的过程。
7、 对于下图，写出图着色算法得出一种着色方案的过程。
2
1
3
3
4
8、 写出第 7 题的状态空间树。
9、 写出归并排序算法对下列实例排序的过程。
(6,2,9,3,5,1,8,7)
10、 写出用背包问题贪心算法解决下列实例的过程。
P=(18,12,4,1)
W=(12,10,8,3)
M=25
11、有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当使用
二分查找值为 82 的结点时，经过多少次比较后查找成功并给出过程。
12、使用 prim 算法构造出如下图 G 的一棵最小生成树。
1
3
4
6
2
5
dist(1,2)=6;dist(2,5)=3;dist(5,6)=6;dist(6,4)=2;dist(4,1)=5;
dist(1,3)=1;dist(2,3)=5;dist(3,4)=5;dist(3,6)=4;dist(5,3)=6
13、有如下函数说明
f(int x,int y)
int
{
f=x Mod y +1;
}
已知 a=10,b=4,c=5 则执行 k=f(f(a+c,b),f(b,c))后，k 的值是多少并写出详细过程。
14、McCathy 函数定义如下：
当 x>100 时 m(x)=x-10;
当 x<=100 时 m(x)=m(m(x+11));
编写一个递归函数计算给定 x 的 m(x)值。
15、 设计一个算法在一个向量 A 中找出最大数和最小数的元素。
四、设计算法
1. 设有 n 项独立的作业{1,2,…, n},由 m 台相同的机器加工处理。作业 i 所需要的处
理时间为 ti。约定：任何一项作业可在任何一台机器上处理，但未完工前不准中断处理；任
何作业不能拆分更小的子作业。
多机调度问题要求给出一种调度方案，使所给的 n 个作业在尽可能短的时间内由 m 台机
4
器处理完。设计算法，并讨论是否可获最优解。
2. 设有 n 种面值为:
d1≥d2≥……≥dn 的钱币，需要找零钱 M，如何选择钱币 dk，的数目 Xk，满足
d1×Xi＋……dn×XnM ，使得
Xi＋……Xn 最小
请选择贪心策略，并设计贪心算法。
3. 有 n 个物品，已知 n=7, 利润为 P=(10,5,15,7,6,18,3)，重量 W=(2,3,5,7,1,4,1)，
背包容积 M=15,物品只能选择全部装入背包或不装入背包，设计贪心算法，并讨论是否可获
最优解。
4. 设计只求一个哈密顿环的回溯算法。
5．利用对称性设计算法，求 n 为偶数的皇后问题所有解。
参考答案
一、简要回答下列问题 ：
1. 确定性、可实现性、输入、输出、有穷性
2. 分析算法占用计算机资源的情况，对算法做出比较和评价，设计出额更好的算法。
3. 算法的时间复杂性与问题的规模相关，是问题大小 n 的函数。
4．当问题的规模 n 趋向无穷大时，影响算法效率的重要因素是 T(n)的数量级，而其他
因素仅是使时间复杂度相差常数倍，因此可以用 T(n)的数量级(阶)评价算法。时间复杂
度 T(n)的数量级(阶)称为渐进时间复杂性。
5. 最坏情况下的时间复杂性和平均时间复杂性考察的是 n 固定时，不同输入实例下的
算法所耗时间。最坏情况下的时间复杂性取的输入实例中最大的时间复杂度：
W(n) = max{ T(n，I) } , I∈Dn
平均时间复杂性是所有输入实例的处理时间与各自概率的乘积和：
A(n) =∑P(I)T(n，I) I∈Dn
6. 设输入是一个按非降次序排列的元素表 A[i：j] 和 x，选取 A[(i+j)/2]与 x 比较，
如果 A[(i+j)/2]=x，则返回(i+j)/2，如果 A[(i+j)/2]
14 .二分检索算法的最多的比较次数为 log n 。
15．.最坏情况下快速排序退化成冒泡排序，需要比较 n2 次。
16. 是一种依据最优化量度依次选择输入的分级处理方法。基本思路是：首先根据题意，
选取一种量度标准；然后按这种量度标准对这 n 个输入排序，依次选择输入量加入部分解中。
如果当前这个输入量的加入，不满足约束条件，则不把此输入加到这部分解中。
17．回溯法的解（x1,x2,……xn）的隐约束一般指个元素之间应满足的某种关系。
18. 讲数组一分为二，分别对每个集合单独排序，然后将已排序的两个序列归并成一个
含 n 个元素的分好类的序列。如果分割后子问题还很大，则继续分治，直到一个元素。
19.快速排序的基本思想是在待排序的 N 个记录中任意取一个记录，把该记录放在最终
位置后，数据序列被此记录分成两部分。所有关键字比该记录关键字小的放在前一部分，所
有比它大的放置在后一部分，并把该记录排在这两部分的中间，这个过程称作一次快速排序。
之后重复上述过程，直到每一部分内只有一个记录为止。
20.在定义一个过程或者函数的时候又出现了调用本过程或者函数的成分，既调用它自
己本身，这称为直接递归。如果过程或者函数 P 调用过程或者函数 Q，Q 又调用 P，这个称
为间接递归。消除递归一般要用到栈这种数据结构。
21.哈密顿环是指一条沿着图 G 的 N 条边环行的路径，它的访问每个节点一次并且返回
它的开始位置。
22. 当 前 选 择 的 节 点 X[k] 是 从 未 到 过 的 节 点 , 即 X[k] ≠ X[i](i=1,2,…,k-1) ， 且
C(X[k-1], X[k])≠∞，如果 k=-1，则 C(X[k], X[1]) ≠∞。
23. 思路是：最初生成树 T 为空，依次向内加入与树有最小邻接边的 n-1 条边。处理过
程：首先加入最小代价的一条边到 T，根据各节点到 T 的邻接边排序，选择最小边加入，新
边加入后，修改由于新边所改变的邻接边排序，再选择下一条边加入，直至加入 n-1 条边。
二、复杂性分析
1、 递归方程
)(
nT
a
(2
nT
)2/
cn
n
n
1
1
设 n=2k
解递归方程：
2、
)2/
cn
)(
nT
)4/
cn
2)4/
cn
(2(2
nT
(4
nT
k
)1(
2
T
kcn
log
cn
an
n
i←1 ;s←0 时间为：O(1)
while
i≤ n do
循环 n 次
循环体内所用时间为 O(1)
所以 总时间为:
T(n)=O(1)+ nO(1)= O(n)
3、最多的查找次数是 p-m+1 次
4、F2（2，n,1,1）的时间复杂度为：
T(n)=O(n-2); 因为 i≤n 时要递归调用 F2，一共是 n-2 次
6
当 n＝1 时 F1(n)的时间为 O(1)
当 n>1 时 F1(n)的时间复杂度与 F2(2,n,1,1)的时间复杂度相同即为为 O(n)
5、
xmax←A(1);j←1
for i←2 to n do
所以 总时间为:
时间为：O(1)
循环最多 n-1 次
T(n)=O(1)+ (n-1)O(1)= O(n)
6、log2n+1
三、算法理解
1、
Cost(4,8)=0
Cost(3,7)= C(7,8)+0=6 ，D[5]=8
Cost(3,6)= C(6，8)+0=5, D[6]=8
Cost(3,5)= C(5，8)+0=4
D[7]=8
Cost(2,4)= min{C(4，6)+ Cost(3,6), C(4，5)+ Cost(3,5)}
D[4]=6
Cost(2,3)= min{C(3，6)+ Cost(3,6) }
= min{1+ 5, 2+4}=6
= min{4+5}=9
D[3]=5
Cost(2,2)= min{C(2，6)+ Cost(3,6), C(2，7)+ Cost(3,7)}
= min{8+5, 4+6}=10
D[2]=7
Cost(1,1)= min{C(1,2)+ Cost(2,2), C(1,3)+ Cost(2,3), C(1,4)+ Cost(2,4)}
= min{3+10, 5+9,2+6}= 8
D[1]=4
1→4→6→8
2、 写出 maxmin 算法对下列实例中找最大数和最小数的过程。
数组 A=()
1、 48,12,61,3,
5,19,32,7
2、48,12
61,3
5,19
32,7
3、 48～61, 12～3
19～32，5～7
4、 61～32
3～5
5、 61
3
3、 给出 5 个数(3,6,9,1,7),M=12，用递归树描述 sumofsub 算法求和数=M 的一个子集
7
的过程。
1，28，0
2，25，3
3，19，3
4，10，12
4、第一个分割元素为 65
(1)
(2)
(3)
(4)
(5)
(6)
(7)
(8)
65
65
65
65
55
70
2
2
2
70
75
75
50
50
75
80
80
80
55
80
85
85
85
85
85
55
55
55
80
65
50
50
75
75
50
2
70
70
70
2
i
2
3
4
4
p
8
7
6
6
5、
48,12,61,3
48,12
12,48
3, 12, 48, 61
61,3
3,61
5,19,32,7
5,19
5,19
5, 7, 19，32
32,7
7,32
3,5, 7,12，19，32，48,61
6、
i←0
while i
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
最新资料
2022-2023学年河北省唐山市高三上学期期末数学试题及答案.doc
2022-2023学年河北省张家口市高三上学期期末数学试题及答案.doc
2022-2023学年河北省衡水市高三上学期期末语文试题及答案.doc
2022-2023学年河北省保定市高三上学期期末数学试题及答案.doc
2022-2023学年河北省张家口市高三上学期期末语文试题及答案.doc
2022-2023学年河北省石家庄市高三上学期期末语文试题及答案.doc
2020-2021年四川省凉山州西昌市高一物理上学期期中试卷及答案.doc
2020-2021年四川省遂宁市安居区高一英语上学期期中试卷及答案.doc
2020-2021年四川省西昌市高一英语上学期期中试卷及答案.doc
2021-2022年四川省广安市岳池县高一地理上学期期中试卷及答案.doc
2021-2022年四川省成都市郫都区高一物理上学期期中试卷及答案.doc
2021-2022年四川省广安市岳池县高一物理上学期期中试卷及答案.doc