1 中南大学现代远程教育课程考试复习题及参考答案 算法分析与设计 一、简要回答下列问题 ： 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
M then return endif a←a+i 2 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 ixmax then xmax←A(i); j←i;endif repeat end MAX 6.procedure BINSRCH(A,n,x,j) integer low,hi...
