当前位置:首页 >> IT/计算机 >>

算法设计与分析考试题及答案

一、填空题(20 分) 1.一个算法就是一个有穷规则的集合,其中之规则规定了解决某一特
殊类型问题的一系列运算,此外,算法还应具有以下五个重要特 性:_________,________,________,__________,__________。 2.算法的复杂性有_____________和___________之分,衡量一个算法 好坏的标准是______________________。 3. 某 一 问 题 可 用 动 态 规 划 算 法 求 解 的 显 著 特 征 是 ____________________________________。 4.若序列 X={B,C,A,D,B,C,D},Y={A,C,B,A,B,D,C,D},请给出序列 X 和 Y 的一个最长公共子序列_____________________________。 5.用回溯法解问题时,应明确定义问题的解空间,问题的解空间至少 应包含___________。 6. 动 态 规 划 算 法 的 基 本 思 想 是 将 待 求 解 问 题 分 解 成 若 干 ____________,先求解___________,然后从这些____________的 解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为_____________。 8.0-1 背包问题的回溯算法所需的计算时间为_____________,用动态 规划算法所需的计算时间为____________。 9.动态规划算法的两个基本要素是___________和___________。 10.二分搜索算法是利用_______________实现的算法。 二、综合题(50 分) 1.写出设计动态规划算法的主要步骤。

2.流水作业调度问题的 johnson 算法的思想。 3.若 n=4,在机器 M1 和 M2 上加工作业 i 所需的时间分别为 ai 和 bi, 且(a1,a2,a3,a4)=(4,5,12,10),(b1,b2,b3,b4)=(8,2,15,9)求 4 个作业 的最优调度方案,并计算最优值。 4.使用回溯法解 0/1 背包问题:n=3,C=9,V={6,10,3},W={3,4,4}, 其解空间有长度为 3 的 0-1 向量组成,要求用一棵完全二叉树表示其 解空间(从根出发,左 1 右 0),并画出其解空间树,计算其最优值 及最优解。 5.设 S={X1,X2,···,Xn}是严格递增的有序集,利用二叉树的结点 来存储 S 中的元素,在表示 S 的二叉搜索树中搜索一个元素 X,返回 的结果有两种情形,(1)在二叉搜索树的内结点中找到 X=Xi,其概率 为 bi。(2)在二叉搜索树的叶结点中确定 X∈(Xi,Xi+1),其概率为 ai。在表示 S 的二叉搜索树 T 中,设存储元素 Xi 的结点深度为 Ci;叶 结点(Xi,Xi+1)的结点深度为 di,则二叉搜索树 T 的平均路长 p 为多 少?假设二叉搜索树 T[i][j]={Xi,Xi+1,···,Xj}最优值为 m[i][j], W[i][j]= ai-1+bi+···+bj+aj,则 m[i][j](1<=i<=j<=n)递归关系表达 式为什么? 6.描述 0-1 背包问题。 三、简答题(30 分) 1.流水作业调度中,已知有 n 个作业,机器 M1 和 M2 上加工作业 i 所 需的时间分别为 ai 和 bi,请写出流水作业调度问题的 johnson 法则中 对 ai 和 bi 的排序算法。(函数名可写为 sort(s,n))

2.最优二叉搜索树问题的动态规划算法(设函数名 binarysearchtree)) 答案: 一、填空 1.确定性 有穷性 可行性 0 个或多个输入 一个或多个输出 2.时间复杂性 空间复杂性 时间复杂度高低 3. 该问题具有最优子结构性质 4.{BABCD}或{CABCD}或{CADCD} 5.一个(最优)解 6.子问题 子问题 子问题 7.回溯法 8. o(n*2n) o(min{nc,2n}) 9.最优子结构 重叠子问题 10.动态规划法 二、综合题 1.①问题具有最优子结构性质;②构造最优值的递归关系表达式;
③最优值的算法描述;④构造最优解; 2. ①令 N1={i|ai<bi},N2={i|ai>=bi};②将 N1 中作业按 ai 的非减序排
序得到 N1’,将 N2 中作业按 bi 的非增序排序得到 N2’;③N1’中作业 接 N2’中作业就构成了满足 Johnson 法则的最优调度。 3.步骤为:N1={1,3},N2={2,4};
N1’={1,3}, N2’={4,2}; 最优值为:38

4.解空间为{(0,0,0),(0,1,0),(0,0,1),(1,0,0),(0,1,1),(1,0,1), (1,1,0),(1,1,1)}。
解空间树为:

1

B 1
0

D

E

1

01

0

H

I

J

K

A 0

C

1

0

F

G

1

1

0

0

L

MN

O

该问题的最优值为:16 最优解为:(1,1,0)

n

n

5.二叉树 T 的平均路长 P= ? bi * (1 ? Ci) + ? aj* dj

i ?1

j?0

? m[i][j]=W[i][j]+min{m[i][k]+m[k+1][j]} (1<=i<=j<=n,m[i][i-1]=0) m[i][j]=0 (i>j)

6.已知一个背包的容量为 C,有 n 件物品,物品 i 的重量为 Wi,价值

为 Vi,求应如何选择装入背包中的物品,使得装入背包中物品的总

价值最大。

三、简答题

1.

void sort(flowjope s[],int n)

{

int i,k,j,l; for(i=1;i<=n-1;i++)//-----选择排序 { k=i; while(k<=n&&s[k].tag!=0) k++; if(k>n) break;//-----没有 ai,跳出 else {
for(j=k+1;j<=n;j++) if(s[j].tag==0) if(s[k].a>s[j].a) k=j;
swap(s[i].index,s[k].index); swap(s[i].tag,s[k].tag); } } l=i;//-----记下当前第一个 bi 的下标 for(i=l;i<=n-1;i++) { k=i; for(j=k+1;j<=n;j++) if(s[k].b<s[j].b) k=j; swap(s[i].index,s[k].index); //-----只移动 index 和 tag

swap(s[i].tag,s[k].tag); } } 2. void binarysearchtree(int a[],int b[],int n,int **m,int **s,int **w) {
int i,j,k,t,l; for(i=1;i<=n+1;i++) {
w[i][i-1]=a[i-1]; m[i][i-1]=0; } for(l=0;l<=n-1;l++)//----l 是下标 j-i 的差 for(i=1;i<=n-l;i++) {
j=i+l; w[i][j]=w[i][j-1]+a[j]+b[j]; m[i][j]=m[i][i-1]+m[i+1][j]+w[i][j]; s[i][j]=i; for(k=i+1;k<=j;k++) {
t=m[i][k-1]+m[k+1][j]+w[i][j];

} } }

if(t<m[i][j]) {
m[i][j]=t; s[i][j]=k; }

一、填空题(本题 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<N;j++)

if( 1 ) /*安全检查*/

{ A[i][j]=i+1; /*放皇后*/

2;

if(i==N-1) 输出结果;

else 3 ;; /*试探下一行*/

4;

/*去皇后*/

5 ;;

}

2、数塔问题。有形如下图所示的数塔,从顶部出发,在每一结点可以选择向左走或是向

右走,一起走到底层,要求找出一条路径,使路径上的值最大。

for(r=n-2;r>=0;r--) //自底向上递归计算

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)

1. Init-single-source(G,s)

2. S=Φ

3. Q=V[G]

4.while Q<> Φ

do u=min(Q)

S=S∪{u}

for each vertex

3

do 4

四、算法理解题(本题 10 分) 根据优先队列式分支限界法,求下 图中从 v1 点到 v9 点的单源最短路 径,请画出求得最优解的解空间树。 要求中间被舍弃的结点用×标记, 获得中间解的结点用单圆圈○框 起,最优解用双圆圈◎框起。
五、算法理解题(本题 5 分) 设有 n=2k 个运动员要进行循环赛,
现设计一个满足以下要求的比赛日程表: ①每个选手必须与其他 n-1 名选手比赛各一次; ②每个选手一天至多只能赛一次; ③循环赛要在最短时间内完成。
(1)如果 n=2k,循环赛最少需要进行几天; (2)当 n=23=8 时,请画出循环赛日程表。

六、算法设计题(本题 15 分)

分别用贪心算法、动态规划法、回溯法设计 0-1 背包问题。要求:说明所使用的算法策 略;写出算法实现的主要步骤;分析算法的时间。 七、算法设计题(本题 10 分)
通过键盘输入一个高精度的正整数 n(n 的有效位数≤240),去掉其中任意 s 个数字后, 剩下的数字按原左右次序将组成一个新的正整数。编程对给定的 n 和 s,寻找一种方案,使 得剩下的数字组成的新数最小。
【样例输入】 178543 S=4 【样例输出】 13
一、填空题(本题 15 分,每小题 1 分) 1.规则 一系列运算 2. 随机存取机 RAM(Random Access Machine);随机存取存储程序机 RASP(Random Access Stored Program Machine);图灵机(Turing Machine) 3. 算法效率 4. 时间 、空间、时间复杂度、 空间复杂度 5.2n 6. 最好 局部最优选择 7. 贪心选择 最优子结构 二、简答题(本题 25 分,每小题 5 分)
6、 分治法的基本思想是将一个规模为 n 的问题分解为 k 个规模较小的子问题,这些子问 题互相独立且与原问题相同;对这 k 个子问题分别求解。如果子问题的规模仍然不够 小,则再划分为 k 个子问题,如此递归的进行下去,直到问题规模足够小,很容易求 出其解为止;将求出的小规模的问题的解合并为一个更大规模的问题的解,自底向上 逐步求出原来问题的解。
7、 “最优化原理”用数学化的语言来描述:假设为了解决某一优化问题,需要依次作出 n 个决策 D1,D2,…,Dn,如若这个决策序列是最优的,对于任何一个整数 k,1 < k < n,不论前面 k 个决策是怎样的,以后的最优决策只取决于由前面决策所确定的当前 状态,即以后的决策 Dk+1,Dk+2,…,Dn 也是最优的。
8、 某个问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。 9、 回溯法的基本思想是在一棵含有问题全部可能解的状态空间树上进行深度优先搜索,
解为叶子结点。搜索过程中,每到达一个结点时,则判断该结点为根的子树是否含有 问题的解,如果可以确定该子树中不含有问题的解,则放弃对该子树的搜索,退回到 上层父结点,继续下一步深度优先搜索过程。在回溯法中,并不是先构造出整棵状态 空间树,再进行搜索,而是在搜索过程,逐步构造出状态空间树,即边搜索,边构造。 10、 P(Polynomial 问题):也即是多项式复杂程度的问题。

NP 就是 Non-deterministic Polynomial 的问题,也即是多项式复杂程度的非确定性 问题。 NPC(NP Complete)问题,这种问题只有把解域里面的所有可能都穷举了之后才能得出 答案,这样的问题是 NP 里面最难的问题,这种问题就是 NPC 问题。 三、算法填空(本题 20 分,每小题 5 分) 1、n 后问题回溯算法 (1) !M[j]&&!L[i+j]&&!R[i-j+N] (2) M[j]=L[i+j]=R[i-j+N]=1; (3) try(i+1,M,L,R,A) (4) A[i][j]=0 (5) M[j]=L[i+j]=R[i-j+N]=0 2、数塔问题。 (1)c<=r (2)t[r][c]+=t[r+1][c] (3)t[r][c]+=t[r+1][c+1] 3、Hanoi 算法 (1)move(a,c) (2)Hanoi(n-1, a, c , b) (3)Move(a,c) 4、(1)p[v]=NIL (2)p[v]=u (3) v∈adj[u] (4)Relax(u,v,w) 四、算法理解题(本题 10 分)

五、(1)8 天(2 分); (2)当 n=23=8 时,循环赛日程表(3 分)。
六、算法设计题(本题 15 分)

1234 2143 3412 4321 5678 6587 7856 8765

5678 6587 7856 8765 1234 2143 3412 4321

(1)贪心算法 O(nlog(n)) ? 首先计算每种物品单位重量的价值 Vi/Wi,然后,依贪心选择策略,将尽可能多的
单位重量价值最高的物品装入背包。若将这种物品全部装入背包后,背包内的物品

总重量未超过 C,则选择单位重量价值次高的物品并尽可能多地装入背包。依此策 略一直地进行下去,直到背包装满为止。

? 具体算法可描述如下:

void Knapsack(int n,float M,float v[],float w[],float x[])

{Sort(n,v,w);

int i;

for (i=1;i<=n;i++) x[i]=0;

float c=M;

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

{if (w[i]>c) break;

x[i]=1;

c-=w[i];

}

if (i<=n) x[i]=c/w[i];

} (2)动态规划法 O(nc) m(i,j)是背包容量为 j,可选择物品为 i,i+1,…,n 时 0-1 背包问题的最优值。由 0-1 背包问题的最优子结构性质,可以建立计算 m(i,j)的递归式如下。

m(i,

j)

?

?max{m(i ? ?

?1, j),m(i ?1, m(i ?1, j)

j

?

wi )

?

vi }

j ? wi 0 ? j ? wi

m(n, j) ? ???v0n

j ? wn 0 ? j ? wn

void KnapSack(int v[],int w[],int c,int n,int m[][11])

{int jMax=min(w[n]-1,c);

for (j=0;j<=jMax;j++) /*m(n,j)=0 0=<j<w[n]*/

m[n][j]=0;

for (j=w[n];j<=c;j++) /*m(n,j)=v[n] j>=w[n]*/

m[n][j]=v[n];

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

{ int jMax=min(w[i]-1,c);

for (j=0;j<=jMax;j++) /*m(i,j)=m(i+1,j) 0=<j<w[i]*/

m[i][j]=m[i+1][j];

for (j=w[i];j<=c;j++)/*m(n,j)=v[n] j>=w[n]*/

m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);

}

m[1][c]=m[2][c];

if(c>=w[1])

m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]);

}

(3)回溯法 O(2n) cw:当前重量 cp:当前价值

bestp:当前最优值

void backtrack(int i)

//回溯法 i 初值 1

{ if(i > n) //到达叶结点

{ bestp = cp;

return;

}

if(cw + w[i] <= c) //搜索左子树

{ cw += w[i];

cp += p[i];

backtrack(i+1);

cw -= w[i];

cp -= p[i];

}

if(Bound(i+1)>bestp)

//搜索右子树

backtrack(i+1);

}

七、算法设计题(本题 10 分) 为了尽可能地逼近目标,我们选取的贪心策略为:每一步总是选择一个使剩下的数最
小的数字删去,即按高位到低位的顺序搜索,若各位数字递增,则删除最后一个数字,否 则删除第一个递减区间的首字符。然后回到串首,按上述规则再删除下一个数字。重复以 上过程 s 次,剩下的数字串便是问题的解了。
具体算法如下: 输入s, n; while( s > 0 )
{ i=1; //从串首开始找 while (i < length(n)) && (n[i]<n[i+1]) {i++;} delete(n,i,1); //删除字符串n的第i个字符 s--; }
while (length(n)>1)&& (n[1]=‘0’) delete(n,1,1); //删去串首可能产生的无用零 输出n;


相关文章:
算法设计与分析考试题及答案.doc
算法设计与分析考试题及答案 - 1.一个算法就是一个有穷规则的集合,其中之规则规
算法设计与分析试卷及答案.doc
算法设计与分析试卷及答案 - 算法设计与分析 算法设计与分析 设计与 1、(1)
《算法设计与分析》考试题目及答案...doc
《算法设计与分析》考试题目及答案.._幼儿读物_幼儿教育_教育专区。《算法设计与分析》考试题目及答案..,算法设计与分析复习题目及答案,算法设计与分析 pdf,算法...
《算法设计与分析》考试题目及答案.doc
算法设计与分析考试题目及答案 - 《算法分析与设计》期末复习题 一、 选择题
算法设计与分析考试题及答案.doc
算法设计与分析考试题及答案 - 一、填空题(20 分) 填空题 1.一个算法就是
《算法设计与分析》考试题目及答案解析.doc
算法设计与分析考试题目及答案解析 - 《算法分析与设计》期末复习题 一、 选
算法设计与分析期末考试卷及答案a.doc
算法设计与分析期末考试卷及答案a - 一.填空题(每空 2 分,共 30 分)
2015算法设计与分析复习试题及答案.pdf
2015算法设计与分析复习试题及答案 - 1. 一个算法就是一个有穷规则的集合,
算法设计与分析试题及答案.doc
算法设计与分析试题及答案 - 一、填空题(20 分) 1.一个算法就是一个有穷规
算法设计与分析复习题参考答案.doc
算法设计与分析复习题参考答案 - 《算法设计与分析》复习题参考答案 一、 概念题
算法设计与分析考试题及答案.doc
算法设计与分析考试题及答案 - 一、填空题(20 分) 1.一个算法就是一个有穷
算法设计与分析考试题及答案.doc
算法设计与分析考试题及答案 - 1.一个算法就是一个有穷规则的集合, 其中之规则
【免费下载】算法设计与分析考试题目及答案_图文.pdf
【免费下载】算法设计与分析考试题目及答案 - 一、 选择题 《算法分析与设计》期
算法设计与分析考试题及答案.doc
算法设计与分析考试题及答案 - 一、填空题(20 分) 1.一个算法就是一个有穷
算法设计与分析试卷及答案.doc
算法设计与分析试卷及答案 - 湖南科技学院二○ 年 学期期末考试 信息与计算科学专业 年级《算法设计与分析试题 考试类型:开卷 试卷类型:C 卷 题号 一二三四...
算法设计与分析复习题目及答案.doc
算法设计与分析复习题目及答案 - 一。选择题 1、二分搜索算法是利用( A、分治
2014-2015算法设计与分析考试题.doc
2014-2015算法设计与分析考试题_工学_高等教育_教育专区。计算机算法设计
湖南大学2014算法设计与分析期中试题(及答案).doc
湖南大学2014算法设计与分析期中试题(及答案) - 一、 函数渐进阶。对于下列
算法设计和分析复习试题目及答案解析.doc
算法设计和分析复习试题及答案解析 - 范文范例 学习指导 分治法 1、二分搜索
算法设计与分析基础习题参考答案.doc
算法设计与分析基础习题参考答案_IT/计算机_专业资料...考虑用于解决第 8 题问题的另一个算法,该算法递归...Hints: a. 第 i 趟冒泡可以表示为: 如果没...