2014中南大学网络教育课程考试：算法分析与设计复习试题及答案解析

2014中南大学网络教育课程考试： 算法分析与设计复习试题及答案解析

算法分析与设计

一、简要回答下列问题 ：

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 low<high； then mid←(low，high)/2； MERGESORT(low，mid)； MERGESORT(mid+1，high)； MERGE(low，mid，high)；

endif

end MERGESORT

2、 procedure S1(P，W，M，X，n) i←1; a←0

while i≤ n do

if W(i)>M then return endif 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 repeat loop p←p-1 until A(p) ≤v repeat

if i<p

then call INTERCHANGE(A(i),A(p)) else exit endif repeat

A(m) ←A(p);A(p) ←v End PARTITION

4.procedure F1(n)

if n<2 then return(1)

else return(F2(2,n,1,1)) endif end F1

procedure F2(i,n,x,y) if i≤n

then call F2(i+1,n,y,x+y) endif return(y) end F2

5.procedure MAX(A,n,j) xmax←A(1);j←1 for i←2 to n do

if A(i)>xmax then xmax←A(i); j←i;endif repeat

end MAX

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_|

本文来源：https://www.bwwdw.com/article/pjim.html