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, a, c); } 4、Dijkstra 算法求单源最短路径 d[u]:s 到u 的距离 p[u]:记录前一节点信息 Init-single-source(G,s) for each vertex v∈V[G] do { d[v]=∞; 1 } d[s]=0 Relax(u,v,w) if d[v]>d[u]+w(u,v) then { d[v]=d[u]+w[u,v]; 2 } dijkstra(G,w,s...
