范文一：算法设计与分析试卷

算法设计与分析试卷

一、 选择题 (每题 2分,共 20分)

(1)计算机算法的正确描述是 ( )

A .一个算法是求特定问题的运算序列

B .算法是一个有穷规则的集合,其中之规则规定了一个解决某一特定类型 的问题的运算序列

C .算法是一个对任一有效输入能够停机的图灵机

D .一个算法,它是满足 5 个特性的程序,这 5个特性是:有限性、确定性、 可行性、有 0个或多个输入且有 1个或多个输出

(2) Hanoi 塔问题如下图所示。现要求将塔座 A 上的的所有圆盘移到塔座 B 上, 并仍按同样顺序叠置。 移动圆盘时遵守 Hanoi 塔问题的移动规则。 由此设计出解 Hanoi 塔问题的递归算法正确的为:()

Hanoi 塔

(3)最长公共子序列利用的算法是()

A 、分治法 B 、动态规划法 C 、贪心法 D 、回溯法 (4)最大效益优先是()的一搜索方式。

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

(5)实现合并排序利用的算法是()

A 、分治法 B 、动态规划法 C 、贪心法 D 、回溯法 (6)分治法的适用条件是,所解决的问题一般具有这些特征()

A .该问题的规模缩小到一定的程度就可以容易地解决;

B .该问题可以分解为若干个规模较小的相同问题;

C .利用该问题分解出的子问题的解可以合并为该问题的解

D .该问题所分解出的各个子问题是相互独立的。

(7)分支限界法在问题的解空间树中,按()策略,从根结点出发搜索 解空间树。

A .广度优先 B. 活结点优先 C.扩展结点优先 D. 深度优先

(8)分支限界法解旅行售货员问题时,活结点表的组织形式是()

A 、最小堆 B 、最大堆 C 、栈 D 、数组

(9)回溯法解旅行售货员问题时的解空间树是() 。

A 、子集树 B 、排列树 C 、深度优先生成树 D 、 广度优先生成树 D. 预排序与递归调用

(10)以深度优先方式系统搜索问题解的算法称为 ( ) A 、分支界限算法 B、概率算法 C、贪心算法 D、回溯法

答案:1.D 2.B 3.B 4.A 5.A

6.B 7.A 8.A 9.A 10.D

二、填空题(每空 2分,共 30分)

1、一个算法是对特定问题求解的一种描述,它是 。

2、矩阵乘法如下:

for(int=0;i<>

for(j=0;j<>

C[i][j]=0;

for(k=0;k<>

C[i][j]+=a[i][k]*b[k][j];

}

程序中所有语句的执行次数为 T (n ) = ,它的渐进时间复 杂度为

3、一个无向连通图不是双向连通图的充要条件是图中存在 。

4、二分搜索过程的算法行为可以用一颗 来描述。

5、用贪心法求解背包问题时, 为了使收益最大化要选择 _________的物品装入背 包。

6、多段图问题中,结点 S 是起点,结点 T 是终点,则 cost(i,j)的含义

是 。

7、使用 的深度优先生成状态空间树中结点的求解方法称为回溯法。

8、使用回溯法进行状态空间树裁剪分支时一般有两个标准:约束条件和目标函 数的界, N 皇后问题和 0/1背包问题正好是两种不同的类型,其中同时使用约束 条件和目标函数的界进行裁剪的是 ,只使用约束条件进行裁剪的是 9、用分支限界法求解最优化问题的三种形

式:、 、 。

10、在 15谜问题中,对给定的初始状态,当且仅当 为偶数时, 可以由此初始状态到达目标状态,其中, i 和 j 分别是空格在棋盘上的行和列下 标。

二、答案:

1、(答案:指令的有限序列) 。

2、(答案是:T(n)=2n3+3n2+2n+1,O(n3) )

3、(答案:关节点)

4、(答案:二叉判定树)

5、(答案:单位重量收益最大)

6、第 i 阶段结点 j 到 T 的最短距离的成本。

7、剪枝函数

8、 0/1背包问题 、 N皇后问题

9、 (答案:FIFO 分支限界法、 LIFO 分支限界法、 LC 分支限界法) 。

10、∑ Less (k ) +i+j

三、算法设计题(每题 10分,共 20分)

1、用分治法求最大元、最小元

template

void SortableList::MaxMin(int i ,int j ,Type& max,Type& min)const

{

Type min1,max1;

if(i==j) max=min=l[i];

else if(i==j-1)

if(l[i]<>

max=l[i];min=l[j];

}

else {

max=l[i];min=l[j];

}

else{

int m=(i+j)/2;

MaxMin(i,m,max,min);

MaxMin(m+1,j,max1,min1);

if(max

if(min>min1) min=min1;

}

}

2、用动态规划法编写最长公共子序列问题:给定 2个序列 X={x1,x2,… ,xm}和 Y={y1,y2,… ,yn},找出 X 和 Y 的最长公共子序的长度。

void LCSLength(int m, int n, char *x, char *y, int **c, int **b) {

int i, j;

for (i = 1; i <= m;="" i++)="" c[i][0]="">

for (i = 1; i <= n;="" i++)="" c[0][i]="">

for (i = 1; i <= m;="">

for (j = 1; j <= n;="" j++)="">

if (x[i]==y[j]) {

c[i][j]=c[i-1][j-1]+1; b[i][j]=1;}

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

c[i][j]=c[i-1][j]; b[i][j]=2;}

else { c[i][j]=c[i][j-1]; b[i][j]=3; }

}

}

四、应用题(每题 10分,共 30分)

1、识别下面的图(a ) (b)的图的关节点,画出它们的双连通分图。

图(a ) 图(b )

答案:

图(a )的深度优先生成树为:

(1)根结点 1只有一个孩子,故不是关节点

(2)DFN(2) <= l(3)="" dfn(3)=""><= l(4)=""><=l(7) 故此图的关节点为="" 2、="" 3、="">

图(b )的深度优先生成树为:

(1) 根结点 1只有一个孩子,不是关节点;

(2) 除根以外的任何一个结点 u 和他的孩子 w 都不存在 DFN (u ) <=>

故无关节点

图(a )的双连通分图为:

图(b )的双连通分图为:

2、假设有 7个物品, 它们的重量和价值如下表所示。 若这些物品均可以被分割, 且背包容量 M =150,如果使用贪心方法求解此背包问题,请回答:(20分) 。

(1) 对各个物品进行排序时,依据的标准都有哪些?

(2) 使用上述标准分别对 7个物品进行排序, 并给出利用各个顺序进行贪 心求解时获得解。

(3) 上述解中哪个是最优的?

答:

(1)标准:重量、价值和单位价值。

(2)使用重量从小到大:FGBAEDC 。得到贪心解为:FGBAE 全部放入,而 D 放入 20%,得到价值为 165。

使用价值从大到小:DFBEGCA ,得到贪心解为:DFBE 全部放入,而 G 放入 80%, 得到价值为:189。

使用单位价值从大到小:FBGDECA , 得到贪心解为:FBGD 全部放入, 而 E 放入 87.5%,

得到价值为 190.625。

(3)显然使用单位价值作为标准得到的是最优解。

3、设有子集和数问题的实力 W=(W0,W1,W2,W3,W4)=(2,5,6,9,12)和 M=35。求 W 中元素之和等于 M 的所有子集。画出对于这一实例由 SumOfSub 算法实际生成的 那部分状态空间树。

答案:对于上面的实力执行 SumOfSub 函数,将实际生成如下图所示的状态空间 树上的结点,图中 A 、 B 为三个答案状态,它们分别代表可行点(1,0,1,1) , (0,1,0,0,1) 。

范文二：算法设计与分析试卷

《2012学年--算法分析试卷》

一、选择题（15*2分）

1、最大效益优先是（ A ）的一搜索方式。

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

2．下列算法中通常以自底向上的方式求解最优解的是（ B ）。

A、备忘录法 B、动态规划法 C、贪心法 D、回溯法

3、衡量一个算法好坏的标准是（C ）。

A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短

4．哈弗曼编码的贪心算法所需的计算时间为（ B ）。

A、O（n2n） B、O（nlogn） C、O（2n） D、O（n）

5．分支限界法解最大团问题时，活结点表的组织形式是（ B ）。

A、最小堆 B、最大堆 C、栈 D、数组

6．最长公共子序列算法利用的算法是（ B ）。

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

7.回溯法的效率不依赖于下列哪些因素（ D ）

A.满足显约束的值的个数

C. 计算限界函数的时间 B. 计算约束函数的时间 D. 确定解空间的时间

8. 矩阵连乘问题的算法可由（ B）设计实现。

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

9. 分支限界法解旅行售货员问题时，活结点表的组织形式是（ A ）。

A、最小堆 B、最大堆 C、栈 D、数组

10、使用分治法求解不需要满足的条件是（A ）。

A 子问题必须是一样的

B 子问题不能够重复

C 子问题的解可以合并

D 原问题和子问题使用相同的方法解

11、下面问题（B ）不能使用贪心法解决。

A 单源最短路径问题 B N皇后问题

C 最小花费生成树问题 D 背包问题

12．实现大整数的乘法是利用的算法（ C ）。

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

D、定义最优13．贪心算法与动态规划算法的主要区别是（ B ）。 A、最优子结构 B、贪心选择性质 C、构造最优解

解

14. 以深度优先方式系统搜索问题解的算法称为 ( D ) 。

A、分支界限算法 B、概率算法 C、贪心算法 D、回溯算法

15. 实现最长公共子序列利用的算法是（ B ）。

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

二、填空题（15*2分）

1.算法的复杂性有 时间 复杂性和 空间 复杂性之分。

2、程序是 算法 用某种程序设计语言的具体实现。

3、算法的“确定性”指的是组成算法的每条 指令 是清晰的，无歧义的。

4.矩阵连乘问题的算法可由 动态规划 设计实现。

5、拉斯维加斯算法找到的解一定是 正确解。

6、算法是指解决问题的 一种方法 或 一个过程 。

7、从分治法的一般设计模式可以看出，用它设计出的程序一般是 递归算法 。

8、问题的 最优子结构性质 是该问题可用动态规划算法或贪心算法求解的关键特征。

9、以深度优先方式系统搜索问题解的算法称为 回溯法 。

10、计算一个算法时间复杂度通常可以计算 循环次数 、 基本操作的频率 或计算步。

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

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

三、算法设计题（27分）

1、（7分）写出欧几里得迭代算法(注意是迭代算法)

int Gcd(int m,int n)

{

If(m==0)return n;

If(n==0)return m;

while(m>0)

{

int c=n%m;

n=m;

m=c;

}

Return n;

}

2. （9分）给定已按升序排好序的n个元素a[0:n-1]，现要在这n个元素中找出一特

定元素x，返回其在数组中的位置，如果未找到返回-1。

写出二分搜索的算法，并分析其时间复杂度。

template

int BinarySearch(Type a[], const Type& x, int n)

{//在a[0:n]中搜索x，找到x时返回其在数组中的位置，否则返回-1

int left=0; int right=n-1;

While (left<>

int middle=(left+right)/2;

if (x==a[middle]) return middle;

if (x>a[middle]) left=middle+1;

else right=middle-1;

}

Return -1;

}

时间复杂性为O(logn)

3、（11分）写出对下图所示的多段图采用向前递推动态规划算法求解的计算过程。

第一段 BCOST(1,1)=0

第2段 BCOST(2,2) = 9

BCOST(2,3) = 7

BCOST(2,4) = 3

BCOST(2,5) = 2

第3段 BCOST(3,6) = min{BCOST(2,2)+4,BCOST(2,3)+2} = 9

BCOST(3,7) = min{BCOST(2,2)+2,BCOST(2,3)+7,

BCOST(2,5)+11} = 11 BCOST(3,8) = min{BCOST(2,4)+11, BCOST(2,5)+8} = 10

第4段 BCOST(4,9) = min{BCOST(3,6)+6,BCOST(3,7)+4} = 15

BCOST(4,10) = min{BCOST(3,6)+5,BCOST(3,7)+3,

BCOST(3,8)+5} = 14 BCOST(4,11) = min{BCOST(3,8)+6} = 16

第5段 BCOST(5,12) = min{BCOST(4,9)+4,BCOST(4,10)+2,

BCOST(4,11)+5}

= 16

S到t的最小成本路径的成本 ＝ 16

最小成本路径的求取

记 BD(i,j)＝每一COST(i,j)的决策

即，使COST(i-1,l)+c(l,j)取得最小值的l值。

例：BD(3,6) = 3, BD(3,7)= 2 ,BD(3,8) = 5

BD(4,9) = 6, BD(4,10) = 7, BD(4,11) = 8

BD(5,12) = 10

根据D(5,12)的决策值向前递推求取最小成本路径：

● v4 = BD(5,12)=10

● v3 = BD(4,BD(5,12)) = 7

● v2 = BD(3,BD(4,BD(5,12))) = BD(3,7) = 2

故由s到t的最小成本路径是：1→2→7→10→12

四、算法应用题（13分）

如图所示的数字三角形，请编写一个程序计算从顶到底的一条路径（路径是指上一层的一个数字到下一层两个数字连线的任一条），并找出数字和最大的路径。输出该最大路径数字和。

输出：30

#include

using namespace std;

const int M=100;

int n;

int a[M][M];

int func()

{

int i,j;

for(i=n-1;i>=1;i--)

for(j=1;j<>

{

if(a[i+1][j]>a[i+1][j+1]) a[i][j]+=a[i+1][j];

else a[i][j]+=a[i+1][j+1];

}

return a[1][1];

}

int main()

{

int i,j,max; cin>>n;

for(i=1;i<=n;i++) for(j=""><=i;j++) cin="">>a[i][j]; max=func();

cout<>

范文三：算法分析与设计试卷

算法分析与设计试卷

2008冬, 计算机科学系

姓名: 学号: 专业:

一. 翻译并解释以下专业词汇: (21分)

1. Dynamic programming

2. Candidate solutions

3. Transformation

4. Greedy algorithms

5. Instances

6. Intractability

7. Optimization problems

二. 请回答以下问题: (32分)

1. 为什么说在算法的时间和空间关系上, 时间是决定性因素(dominant factor)?

2. 我们通常所说的有效 (efficient) 算法或实际可行算法是指何种算法? 3. 字符串的子串 (substring) 和 子序列 (subsequence) 有何不同? 4. 完整的动态规划方法由哪三部分组成,通常，我们描述一个动态规划算法只需要给

出哪一部分内容,

5. 每一个NP问题都是难解的吗?

6. 如果从问题,多项式时间归约为问题问题,, 说明问题,比问题,难还是简单? 12127. NP-hard 问题一定是NP 问题吗, 如何证明一个问题是NP-hard, 8. 一个最小化问题的近似比为C的相对近似算法可以给我们什么样的保证?

三. (12分)

1. 对于任何正整数n以下算法计算m=?i. 其时间复杂性几何? 是多项式时间的(1?i?n)

吗?

m=0

For i=1 to n do

m=m+i

Endfor

Output m

2. 以下算法依据公式?i=n(n+1)/2计算同样的的问题，它的时间复杂性又是多(1?i?n)

少,

m= n(n+1)/2

Output m

四. 画出字符串S=abbababb的后缀树(suffix tree).(9分)

五. 关于NP-Completeness: (12分)

1. 写出通常证明一个问题 , 是NP-complete的过程.

2. 论述使用限制(restriction)技术证明NP-completeness的合理性。 3. 分别用限制技术和非限制技术两种方法证明如下问题的NP-completeness。

Hitting Set

Instance: Collection C of subsets of a set S, positive integer K.

集合S上的一些子集的集合C， 及正整数K。

Question: is there a subset S’,S with |S’|,K and such that S’, c , , for every c,C?

是否存在S 的子集S’满足|S’|,K 并且对C中每一个c,C有S’, c , , ,

六. 关于近似算法: (14分)

1. 优化形式的划分问题叙述为:将n个正整数划分k组，使得每一组的成员之和相同,

要求k>1且达到最小。(假设问题总有k?n的解)

(1). 证明该问题是NP-hard问题

(2). 证明该问题不存在多项式时间近似比<3 的近似算法。="" 2.="" 背包问题的优化版本可如下描述:="">

KNAPSACK

++Instance: 项目集U，总投资额度B,Z，对每个项目u,U有所需投资s(u),Z 和预

+ 计收益v(u) ,Z两项指标， 其中s(u) , B。

Objective: 求U’,U 使得 , s(u) , B 并且 , v(u) 达到最大。 u,U’u,U’

证明对于该问题不存在多项式时间绝对近似算法。

3. 证明以下算法是对以上背包问题的一个性能比为2的近似算法。 i. 将U中项目按照收益/投资比率从大到小排序，设排序结果为 u, u,…, u, 满足 12n

v(u)/ s(u) , v(u)/ s(u) ,…, v(u)/ s(u). 1122nn

ii. U’=,, i=1，p=0，

iii. For i=1 to n do

a) If s(u) , B then i

i. U’= U’,{u}, p=p + s(u), B=B - s(u) iii

b) Endif

2. EndFor

iv. 求出满足 v(u)=max{ v(u), v(u),…, v(u)} 的整数j j12n

v. If P < v(u)="" then="" u’="{u}">

vi. Output U’

范文四：算法设计与分析试卷

算法设计与分析试卷

1,Hanoi,.(20

)2,F(n) (15)F(n)=...

,

Niudown.COM

Niudown.COM

Niudown.COM

Niudown.COM

1、编写Hanoi算法，写出递推方程并用母函数求解。（20分）

2、用特征方程求解下列递归方程F(n)的解析表达式 （15分）

1n,0,

,0n,1,,1n,2,F(n)= ,2n,3,

,,F(n,1)，3F(n,2)，5F(n,3)，2F(n,4)n,3,

3、设二分树T有n个叶子，叶子到树根的路径长度为L(1?i?n)。（15分） i

T()*minmax{L},logn，，i2证明： 其中T为具有n个叶子结点的二分树*vT,TT,i

集合，v为叶结点。 i

4、已知如下图，写出用动态规划求最短路径的递推关系式，并写出求从源点A0

到终点A 的最短路径过程。（15分） 3

6

AA 1 2

5 5 2

A A 0 3

3 4 4

B B 12

5

5、写出求最小生成树的Kruskal算法。 （20分）

6、试将下列关键字依序插入到初始为空的2_3树中。 （15分） f,s,q,k,c,l,h,t,v,w,m,r,n,p,a,b,x,y,d,z,e. 只须画出结点分裂的情况和最后的情况。

范文五：算法设计与分析试卷

算法设计与分析期末试卷

一(选择题(15*2分)

1.下列不属于一个好的算法应具有的特性的是(C)

A.正确性 B.简明性 C无限性 D最优性

2.矩阵连乘问题的算法可由(B)设计实现。

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

3.广度优先是(A)的一搜索方式。

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

4.学校要举行运动会，请你设计一个能够对运动员分数自动排序的软件，如果要设计此软件，以下最好的方法和步骤是(C)

A.分析问题，编写程序，设计算法，调试程序

B.设计算法，编写程序，提出问题，调试程序

C.提出问题，设计算法，编写程序，调试程序

,.设计算法，提出问题，编写程序，调试程序

5.用计算机程序解决实际问题的过程中，需要进行算法设计，算法指的是(A)

A、解决问题的方法和步骤

B、数值计算的方法

C、实际问题的描述

D、最终结果

6.算法分析是( C)。

A( 将算法用某种程序设计语言恰当地表示出来

B( 在抽象数据集合上执行程序，以确定是否会产生错误的结果

C( 对算法需要多少计算时间和存储空间作定量分析

D( 证明算法对所有可能的合法输入都能算出正确的答案

7.用贪心法设计算法的关键是( B )。

A(将问题分解为多个子问题来分别处理 B(选好贪心准则

C(获取各阶段间的递推关系式 D(满足最优性原理

8.考虑背包问题:n=6，M=10，V(1:6)=(15,59,21,30,60,5)，

W(1:6)=(1,5,2,3,6,1)。该问题的最大效益值为(C )。若把它看着是0/1 背包问题，则最大效益值为( B )。

A(101 B(110 C(115 D(120

9.每个归并步恰包含k 个文件的归并模式被称为k 元归并模式。考虑用贪心法

求解文件序列的最优2 元归并问题。当要对8 个长度为L(1:8)=(3,7,8,9,14,18,25,28)文件进行归并时，记录移动的总数是( D )。

A(198 B(112 C(210 D(310

10.找最小生成树的算法Kruskal的时间复杂度为( D )。

A(O(n2) B(O(mlogn) C(O(nlogm) D(O(mlogm)

11.算法确认是(B )。

A(将算法用某种程序设计语言恰当地表示出来

B(证明算法对所有可能的合法输入都能算出正确的答案

C(对算法需要多少计算时间和存储空间作定量分析

D(在抽象数据集合上执行程序，以确定是否会产生错误的结果

12.算法与程序的区别在于算法具有(C )。

A(能行性 B(确定性 C(有穷性 D(输入和输出

13.设A[1..60]={11,12,?,70}。算法折半查找在A 上搜索x=33、7、70、77 时执行的元素比较次数分别为a、b、c、d，则( C)。

a<b<c<d B(a>b=c=d C(a<b=c=d D(a<c<b=d A(

14.算法直接插入排序在A[1..8]={45,33,24,45,12,12,24,12}上运行时执行的元素比较次数为( D)。

A(14 B(28 C(7 D(22

15.二分搜索算法是利用(A)实现的算法。

A.分治法 B.动态规划法 C.贪心法 D.回溯法

二、填空题(每空2分，共15个空)

1(算法一般分为:________算法和________算法。

2. 一个合法的递归定义包括两部分:_________和_________。

3. 一个算法的______________是指算法运行所需要的时间。

4. 如果无向连通图G中不包含任何关节点，则称该图G为___________。

5. _________的基本运算是把两个或多个有序序列合并成一个有序序列。

6. _________和_________要求问题最优解具有最优子结构特性。

7. 使用剪枝函数的深度优先生成状态空间树中结点的求解方法称为___________

8.下面程序段的所需要的计算时间为___________

int MaxSum(int n, int *a, int &besti, int &bestj) {

int sum=0;

for(int i=1;i<=n;i++){

int thissum=0;

for(int j=i;j<=n;j++){

thissum+=a[j];

if(thissum>sum) {

sum=thissum;

besti=i;

bestj=j;

}

}

}

return sum;

}

9.所谓最优子结构性质是指___________

10.回溯法的算法框架按照问题的解空间一般分为___________ 算法框架与

___________算法框架

11..若序列A={xzyzzyx}，B={zxyyzxz}，请给出序列A和B的一个最长公共子

序列__________________。

填空题答案:

1、精确 启发式。

递归部分。 2、基础情况

3、时间复杂度

4、双连通图。

5、合并排序

6、贪心法 动态规划法

7、回溯法。

8、O(n2)

9、问题的最优解包含了其子问题的最优解

10、子集树 排列树

11、XYZZ

三(算法设计

1.用欧几里德迭代算法求两个数的最小公倍数

#include<iostream>

using namespace std;

int Gcd(int m,int n)

{

if(m==0)

return n;

if(n==0)

return m;

int t=m>n?n:m;

while(m%t||n%t)

t--;

return t;

}

int main()

{

int a,b;

cout<<"Input a & b (0<=a<b) :";

cin>>a>>b;

int m=a*b/Gcd(a,b);

cout<<"The Least Common Multiple is:"<<m<<endl;

return 0;

}

2. 用分治法求第K小元素

#include <iostream>

using namespace std;

void swap(int *a,int *b)

{

int temp;

temp=*a;

*a=*b;

*b=temp;

}

int Partition(int R[],int low,int high) {

int i=low,j=high,pivot=R[low]; while(i<j)

{

while(i<j&&R[j]>=pivot) {

j--;

}

if(i<j)

{

swap(R[i++],R[j]); }

while(i<j&&R[i]<=pivot) {

i++;

}

if(i<j)

{

swap(R[i],R[j--]);

}

}

return j;

}

int Select(int a[],int p,int r,int k) {

if (p==r) return a[p];

int i=Partition(a,p,r), j=i-p+1;

if (k<=j)

return Select(a,p,i,k);

else

return Select(a,i+1,r,k-j);

}

int main()

{

int n,k;//n为数的总个数，k为第几小

cout<<"n=";

cin>>n;

int *a=new int[n];

cout<<"The number is:";

for(int i=0;i<n;i++)

{

cin>>a[i];

}

cout<<"k=";

cin>>k;

cout<<"第"<<k<<"小为:"<<Select(a,0,n-1,k);

cout<<endl;

return 0;

}

四(算法应用题

1.假设有7个物品，它们的重量和价值如下表所示。若这些物品均不能被分割，且背包容量M,150，使用回溯方法求解此背包问题。请写出状态空间搜索树(10分)。

答:按照单位效益从大到小依次排列这7个物品为:FBGDECA。将它

们的序号分别记为1,7。则可生产如下的状态空间搜索树。其中各个节点处的限界函数值通过如下方式求得:

x5 x6 x7 150,1157 190.625(1,1,1,1,,0,0)408 a(40,40,30,50,35

b.

c(40,40,30,50,10 170 (1,1,1,1,0,0,1)

d. e. 40,40,30,35,30 40,40,50,35,30

40,40,50,35,10 40,40,30,50,30 150,1157 177.5(1,1,1,1,0,,0)6012

150,105 167.5(1,1,1,0,1,3,0)604 150,130 175(1,1,0,1,1,1,0)603 f.

g. 40,40,50,30 160

h.

i.40,40,35,30,10 150,130 170.71(1,1,0,1,1,0,4)357 (1,1,0,1,0,1,0)

150,1402 146.85(1,1,0,0,1,1,)357

40,30,50,35,30 150,125 167.5(1,0,1,1,1,5,0)6012

j.

在Q1处获得该问题的最优解为(1,1,1,1,0,0,1)，背包效益为170。即在背包中装入物品F、B、G、D、A时达到最大效益，为170，重量为150。

，2，3，4，5，6，r1=5，r2=10，r3=3，r4=12，r5=5，r6=50，r7=6， 2.已知，k=1

求矩阵链积A1×A2×A3×A4×A5×A6的最佳求积顺序。(要求:给出计算步骤)(20分)

Ak (aij(k))ri*ri,140,30,50,35,30 150,145 157.5(0,1,1,1,1,1,0)6012

答:使用动态规划算法进行求解。

因此，最佳乘积序列为(A1A2)((A3A4)(A5A6))，共执行乘法2010次。

转载请注明出处范文大全网 » 算法设计与分析试卷