1- 6 算 法 考 试 试 卷 注 ： 此 页 不 作 答 题 纸 ， 请 将 答 案 写 在 答 题 纸 上 一、填空题（本题 15 分，每小题 1 分） 1、 算法就是一组有穷的 ，它们规定了解决某一特定类型问题的
2、 在进行问题的计算复杂性分析之前，首先必须建立求解问题所用的计算模型
3 个基本计算模型是 、 、
3、 算法的复杂性是 的度量，是评价算法优劣的重要依据
4、 计算机的资源最重要的是 和 资源
因而，算法的复杂性有 和 之分
5、 f(n)= 6×2n+n2，f(n)的渐进性态 f(n)= O( ) 6、 贪心算法总是做出在当前看来 的选择
也就是说贪心算法并不从整体最优考虑，它所做出的选择只是在某种意义上的
7、 许多可以用贪心算法求解的问题一般具有 2 个重要的性质： 性质和 性质
二、简答题（本题 25 分，每小题 5 分） 1、 简单描述分治法的基本思想
2、 简述动态规划方法所运用的最优化原理
3、 何谓最优子结构性质
4、 简单描述回溯法基本思想
5、 何谓 P、NP、NPC 问题 三、算法填空（本题 20 分，每小题 5 分） 1、n 后问题回溯算法 (1)用二维数组 A[N][N]存储皇后位置,若第i 行第j 列放有皇后,则A[i][j]为非0 值,否则值为0
(2)分别用一维数组 M[N]、L[2*N-1]、R[2*N-1]表示竖列、左斜线、右斜线是否放有棋子，有则值为1,否则值为0
for(j=0;j=0;r--) //自 底 向 上递 归 计算 2- 6 for(c=0; 1 ;c++) if( t[r+1][c]>t[r+1][c+1]) 2 ； else 3 ； 3、Hanoi 算法 Hanoi(n,a,b,c) if （n==1） 1 ； else { 2 ； 3 ； Hanoi(n-1,b,
