1 一、简要回答下列问题：1.算法重要特性是什么？2.算法分析的目的是什么？3.算法的时间复杂性与问题的什么因素相关？4.算法的渐进时间复杂性的含义？5.最坏情况下的时间复杂性和平均时间复杂性有什么不同？6.简述二分检索（折半查找）算法的基本过程。7.背包问题的目标函数和贪心算法最优化量度相同吗？8.采用回溯法求解的问题，其解如何表示？有什么规定？9.回溯法的搜索特点是什么？10. n 皇后问题回溯算法的判别函数place 的基本流程是什么？11. 为什么用分治法设计的算法一般有递归调用？12. 为什么要分析最坏情况下的算法时间复杂性？13. 简述渐进时间复杂性上界的定义。14. 二分检索算法最多的比较次数？15. 快速排序算法最坏情况下需要多少次比较运算？16. 贪心算法的基本思想？17. 回溯法的解（ x1,x 2, ⋯⋯ xn）的隐约束一般指什么？18. 阐述归并排序的分治思路。19. 快速排序的基本思想是什么。20. 什么是直接递归和间接递归？消除递归一般要用到什么数据结构？21. 什么是哈密顿环问题？22. 用回溯法求解哈密顿环，如何定义判定函数？23. 请写出 prim 算法的基本思想。二、复杂性分析1、 MERGESORT(low，high) if low
M then return endif a←a+i i←i+1 ; repeat end 3.procedure PARTITION(m,p) 2 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,high,mid,j,n; low←1;high ←n while low≤high do mid←|_(low+high)/2_| case :x
