算法设计与分析考试试题

1n211、选择正确的组合对于2( B )

(n2)2222①o ②O(n) ③(n) ④(n) ⑤(n) A、①③④ B、②③④ C、③④⑤ D、①⑤ n22、①

OO(n2)i1i(n) ②nO(n)O(n) ③O(logn)O(n)2.9999 ④nO(n3)2 ⑤n/logn(n)其中正确的有（B ） A、5组 B、4组 C、3组 D、没有正确的

3、n2/102n=（B ） A、O(n2)n2 B、

O(2) C、O(2nn2) D、o(n)

4、（ D ）是贪心算法与动态规划算法的共同点。

A、重叠子问题 B、构造最优解 C、贪心选择性质 D、最优子结构性质

5、背包问题的贪心算法所需的计算时间为（ B ）。 A、O（n2n） B、O（nlogn） C、O（2n） D、O（n）

6、广度优先是（ A ）的一搜索方式。

A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 7、

10logn3 (B ) A、O(nlogn)logn B、

O(logn) C、

O(n3) D、

O(n)

8、211/n ( D )

A、O(n) B、o(n) C、(n) D、O(1)

第九组算法设计与分析考试试题

组成员：0982030古明冬 0982054吴昊 0982035许文龙 0982032王勇 0982044储斌斌 时间：2012/5/11 0：42

1

9、动态规划算法的基本要素为（C） A、最优子结构性质与贪心选择性质 B、重叠子问题性质与贪心选择性质 C、最优子结构性质与重叠子问题性质 D、预排序与递归调用

10、能采用贪心算法求最优解的问题，一般具有的重要性质为：（A） A、最优子结构性质与贪心选择性质 B、重叠子问题性质与贪心选择性质 C、最优子结构性质与重叠子问题性质 D、预排序与递归调用

11、回溯法在问题的解空间树中，按（D）策略，从根结点出发搜索解空间树。 A、广度优先 B、活结点优先 C、扩展结点优先 D、深度优先

12、分支限界法在问题的解空间树中，按（A）策略，从根结点出发搜索解空间树。A、广度优先 B、活结点优先 C、扩展结点优先 D、深度优先

13、常见的两种分支限界法为（D）

A.、广度优先分支限界法与深度优先分支限界法； B、队列式（FIFO）分支限界法与堆栈式分支限界法； C、排列树法与子集树法；

D、队列式（FIFO）分支限界法与优先队列式分支限界法；

14、哈夫曼编码可利用（ C ）算法实现。

A、分治策略 B、动态规划法 C、贪心法 D、回溯法

15、下列算法中通常以自顶向下的方式求解最优解的是（C ）。 A、分治法 B、动态规划法 C、贪心法 D、回溯法

第九组算法设计与分析考试试题

组成员：0982030古明冬 0982054吴昊 0982035许文龙 0982032王勇 0982044储斌斌 时间：2012/5/11 0：42

2

二、填空题

16、快速排序算法是基于 分治策略 的一种排序算法。

17、动态规划算法的两个基本要素是 最优子结构 性质和 重叠子问题 性质。

18、回溯法是一种既带有 系统性 又带有 跳跃性 的搜索算法。

19、分支限界法主要有 队列式（FIFO）分支限界法和 优先队列式 分支限界法。 20、一个算法的优劣可以用 空间复杂度 与 时间复杂度 与来衡量。 21、这种不断回头寻找目标的方法称为 回溯法 。 22、直接或间接地调用自身的算法称为 递归算法 。

23、贪心算法从初始阶段开始，每一个阶段总是作一个使 局部最优 的贪心选择。

T(n)2T(n/2)n的一个渐进上界为 O(nlogn ) 。

24、

25、分治限界法主要按照 广度 优先原则以及使用 剪枝 函数，产生状态空间数的节点。 三、算法设计

26、试用分治法对数组A[n]实现快速排序。 解：

int partition(float A[],int p,int r) {

int i=p,j=r+1; float x=a[p]; while (1) {

while(a[++i]x); if(i>=j) break;

a[i]a[j]; }; a[p]=a[j];

a[j]=x; return j;

}

void Quicksort( float a[], int p, int r ) {

if( pint q=partition(a,p,r); Quicksort(a,p,q-1); Quicksort(a,q+1,r); } };

Quicksort(a,0,n-1);

第九组算法设计与分析考试试题

组成员：0982030古明冬 0982054吴昊 0982035许文龙 0982032王勇 0982044储斌斌 时间：2012/5/11 0：42

3

27、试用动态规划算法实现最长公共子序列问题。 解：

用动态规划算法求解的算法代码如下：

int lcs_len(char *a,char *b,int c[][N]) {

int m=strlen(a),n=strlen(b),i,j; for(i=0;i<=m;i++) c[i][0]=0; for(j=1;j<=n;j++) c[0][j]=0; for(i=1;i<=m;i++) for(j=1;j<=n;j++)

if(a[i-1]= =b[j-1]) c[i][j]=c[i-1][j-1]+1; else if(c[i-1][j]>=c[i][j-1]) c[i][j]=c[i-1][j];

else c[i][j]=c[i][j-1]; return c[m][n]; };

char *build_lcs(char s[],char *a,char *b) {

int k,i=strlen(a),j=strlen(b),c[N][N]; k=lcs_len(a,b,c); s[k]=’\\0’;

while(k>0){

if(c[i][j]= =c[i-1][j]) i--;

else if(c[i][j]= =c[i][j-1]) j--; else{

s[--k]=a[i-1]; i--,j--; } }

return s;

}

四、算法应用

1、识别下图的关节点，画出它的双连通分图

第九组算法设计与分析考试试题

组成员：0982030古明冬 0982054吴昊 0982035许文龙 0982032王勇 0982044储斌斌 时间：2012/5/11 0：42

4

0 6 1 3 7 2 4 5 解：

第九组算法设计与分析考试试题

组成员：0982030古明冬 0982054吴昊 0982035许文龙 0982032王勇 0982044储斌斌 时间：2012/5/11 0：42

5

0 (0,0) (1,1) 1 (2,0) 2 3 (3,0) (4,2)

4 5 (5,0) 7 (6,0) 6 (7,0) 无关节点

双连通分图为：

第九组算法设计与分析考试试题

组成员：0982030古明冬 0982054吴昊 0982035许文龙 0982032王勇 0982044储斌斌 时间：2012/5/11 0：42

6

0 6 1 3 7 2 4 5

2、设有4个矩阵连乘积ABCD，设它们的维数分别为A:45*8,B:8*40,C:40*25,D:25*10,请求出它们的最优计算次序和计算量 解：

P0=45,P1=8,P2=40,P3=25,P4=10 0 1 2 3 0 1 2 3 0 0 1 0 0 2 0 1 0 3 0 1 2 0 0 0 1 14400 0 2 17000 8000 0 3 13600 10000 10000 0

m[0,1]=min{m[0,0]+m[1,1]+P0P1P2}=14400 m[1,2]=8000

m[2,3]=10000

m[0,2]=min{m[0,0]+m[1,2]+P0P1P3,m[0,1]+m[2,2]+P0P2P3}=17000

m[1,3]=min{m[1,1]+m[2,3]+P1P2P4,m[1,2]+m[3,3]+P1P2P4}=10000

m[0,3]=min{m[0,0]+m[1,3]+P0P1P4,m[0,1]+m[2,3]+P0P2P4,m[0,2]+m[3,3]+P0P3P4}=13600 最优计算次序：A(B(CD)) 计算量为：13600

第九组算法设计与分析考试试题

组成员：0982030古明冬 0982054吴昊 0982035许文龙 0982032王勇 0982044储斌斌 时间：2012/5/11 0：42

7