算法设计与分析期末试卷A卷

A卷

一、选择题

1.二分搜索算法是利用（A ）实现的算法。

A、分治策略

B、动态规划法

C、贪心法

D、回溯法

2. 回溯法解旅行售货员问题时的解空间树是（ A ）。

A、子集树

B、排列树

C、深度优先生成树

D、广度优先生成树

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

A、备忘录法

B、动态规划法

C、贪心法

D、回溯法4．下面不是分支界限法搜索方式的是（ D ）。

A、广度优先

B、最小耗费优先

C、最大效益优先

D、深度优先5．采用贪心算法的最优装载问题的主要计算量在于将集装箱依其重量从小到大排序，故算法的时间复杂度为 ( B ) 。

A、O（n2n）

B、O（nlogn）

C、O（2n）

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

A、最小堆

B、最大堆

C、栈

D、数组

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

A 单源最短路径问题

B N皇后问题

C 最小花费生成树问题

D 背包问题

8.下列算法中不能解决0/1背包问题的是（A ）

A 贪心法

B 动态规划

C 回溯法

D 分支限界法

9.背包问题的贪心算法所需的计算时间为（ B ）

A、O（n2n）

B、O（nlogn）

C、O（2n）

D、O（n）

10.背包问题的贪心算法所需的计算时间为（B ）。

A、O（n2n）

B、O（nlogn）

C、O（2n）

D、O（n）

二、填空题

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

2.算法是由若干条指令组成的有穷序列，且要满足输入、、确定性和四条性质。其中算法的“确定性”指的是组成算法的每条是清晰的，无歧义的。

3.解决0/1背包问题可以使用动态规划、回溯法和分支限界法，其中不需要排序的是，需要排序的是，。

4.动态规划算法的两个基本要素是. 性质和性质。

5.回溯法是一种既带有又带有的搜索算法；分支限界法是一种既带有又带有的搜索算法。

6. 用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常

为。

7.用回溯法解图的m着色问题时，使用下面的函数OK检查当前扩展结点的每一个儿子所相应的颜色的可用性，则需耗时（渐进时间上限）。

Bool Color::OK(int k)

{//

for(int j=1;j<=n;j++)

if((a[k][j]= =1)&&(x[j]= =x[k])) return false;

return true;

}

8.用回溯法解布线问题时，求最优解的主要程序段如下。如果布线区域划分为 的方格阵列，扩展每个结点需O(1)的时间，L为最短布线路径的长度，则n m

算法共耗时，构造相应的最短距离需要时间。

for (int i = 0; i < NumOfNbrs; i++) {

nbr.row = here.row + offset[i].row;

nbr.col = here.col + offset[i].col;

if (grid[nbr.row][nbr.col] == 0) {

// 该方格未标记

grid[nbr.row][nbr.col]

= grid[here.row][here.col] + 1;

if ((nbr.row == finish.row) &&

(nbr.col == finish.col)) break; // 完成布线

Q.Add(nbr);}

}

9.快速排序算法是基于的一种排序算法。

10. 是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别

三．简答题

1.设计动态规划算法的主要步骤是怎么的？请简述。

2.分治法所能解决的问题一般具有哪几个特征？请简述。

3.分支限界法的搜索策略是什么？

四．计算题

1.已知非齐次递归方程：f (n)bf (n 1)g(n)

f (0)c =-+??

=?

，其中，b 、c 是常数，g(n)

是n 的某一个函数。则f(n)的非递归表达式为：n

n

n i i 1

f (n)cb b g(i)-==+∑。

现有Hanoi 塔问题的递归方程为：h(n)2h(n 1)1

h(1)1=-+??

=? ，求h(n)的非递归表达式。

2.给定带权有向图（如下图所示）G =(V,E)，其中每条边的权是非负实数。

另外，还给定V 中的一个顶点，称为源。现在要计算从源到所有其它各顶点的最短路长度。这里路的长度是指路上各边权之和。现采用Dijkstra 算法计算从源顶点1到其它顶点间最短路径。请将此过程填入下表中。

五．程序题

4

3 2 1 {1} 初始 dist[5]

dist[4] dist[3] dist[2] u S 迭代

1.试用贪心算法求解汽车加油问题：已知一辆汽车加满油后可行驶n公里，而旅途中有若干个加油站。试设计一个有效算法，指出应在哪些加油站停靠加油，使加油次数最少，请写出该算法。

2.试用动态规划算法实现下列问题：设A和B是两个字符串。我们要用最少的字符操作，将字符串A转换为字符串B，这里所说的字符操作包括：

（1）删除一个字符。

（2）插入一个字符。

（3）将一个字符改为另一个字符。

请写出该算法。

答案：

一、AABDB BBABB

二、

1.时间空间

2.输出有限性指令

3.动态规划回溯法分支限界法

4.最优子结构重叠子问题

5.系统性跳跃性系统性跳跃性

6. （O(h(n))）

7.O（mn）

8. O(mn) O(L)

9.分治策略

10.贪心选择性质

三、

1.（1）找出最优解的性质，并刻划其结构特征。

（2）递归地定义最优值。

（3）以自底向上的方式计算出最优值。

（4）根据计算最优值时得到的信息，构造最优解。

2. （1）该问题的规模缩小到一定的程度就可以容易地解决；

（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质;

（3） 利用该问题分解出的子问题的解可以合并为该问题的解；

（4）原问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。

3. 在扩展结点处，先生成其所有的儿子结点（分支），然后再从当前的活结点表中选择下一个扩展结点。为了有效地选择下一扩展结点，加速搜索的进程，在每一个活结点处，计算一个函数值（限界），并根据函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间上有最优解的分支推进，以便尽快地找出一个最优解。 四、

1.解：利用给出的关系式，此时有：b=2, c=1, g(n)=1, 从n 递推到1，有：

n 1

n 1

n 1i i 1

n 1n 22n h(n)cb

b g(i)

22 (22121)

----=--=+=+++++=-∑ 2.

五．程序题

1.解：int greedy(vecterx,int n)

{

60

30

50

10

5

{1，2，3，4，5}

4

60 30 50 10 3 {1，2，4，3} 3 90 30 50 10 4 {1，2，4} 2 100 30 60 10 2 {1，2} 1 100 30 10 - {1} 初始 dist[5] dist[4] dist[3]

dist[2] u S 迭代

int sum=0,k=x.size();

for(int j=0;j

if(x[j]>n){

cout<<”No solution”<

return -1;

}

For(int i=0,s=0;i

S+=x[i];

if(s>n){sum++;s=x[i];}

}

return sum;

}

2.

解：此题用动态规划算法求解：

int dist()

{

int m=a.size();

int n=b.size();

vectord(n+1，0);

for(int i=1;i<=n;i++)d[i]=i;

for(i=1;i<=m;i++){

int y=i-1;

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

int x-y;

y=d[j];

int z=j>1?d[j-1]:i;

int del=a[i-1]==b[j-1]?0:1;

d[j]=min(x+del,y+1,z+1);

}

}

return d[n];

}

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

算法设计与分析考试题 及答案 Company number：【WTUT-WT88Y-W8BBGB-BWYTT-19998】

一、填空题（20分） 1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性:确定性 有穷性 可行性 0个或多个输入 一个或多个输出 2.算法的复杂性有时间复杂性 空间复杂性之分，衡量一个算法好坏的标准是 时间复杂度高低 3.某一问题可用动态规划算法求解的显着特征是 该问题具有最优子结构性质 4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X 和Y 的一个最长公共子序列{BABCD}或{CABCD}或{CADCD ｝ 5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含一个（最优）解 6.动态规划算法的基本思想是将待求解问题分解成若干_子问题 ，先求解_子问题 ，然后从这些子问题 的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为回溯法 背包问题的回溯算法所需的计算时间为o(n*2n ) ,用动态规划算法所需的计算时间为o(min{nc,2n }) 9.动态规划算法的两个基本要素是最优子结构 _和重叠子问题 10.二分搜索算法是利用动态规划法实现的算法。 二、综合题（50分） 1.写出设计动态规划算法的主要步骤。 ①问题具有最优子结构性质；②构造最优值的递归关系表达式； ③最优值的算法描述；④构造最优解； 2. 流水作业调度问题的johnson 算法的思想。 ①令N 1={i|a i =b i }；②将N 1中作业按a i 的非减序排序得到N 1’，将N 2中作业按b i 的非增序排序得到N 2’；③N 1’中作业接N 2’中作业就构成了满足Johnson 法则的最优调度。 3. 若n=4，在机器M1和M2上加工作业i 所需的时间分别为a i 和b i ，且 (a 1,a 2,a 3,a 4)=(4,5,12,10)，(b 1,b 2,b 3,b 4)=(8,2,15,9)求4个作业的最优调度方案，并计算最优值。 步骤为：N1={1，3}，N2={2，4}； N 1’={1，3}， N 2’={4，2}； 最优值为：38 4. 使用回溯法解0/1背包问题：n=3，C=9，V={6,10,3}，W={3,4,4},其解空间有长度为3的0-1向量组成，要求用一棵完全二叉树表示其解空间（从根出发，左1右0），并画出其解空间树，计算其最优值及最优解。 解空间为{(0,0,0),(0,1,0),(0,0,1),(1,0,0),(0,1,1),(1,0,1), (1,1,0),(1,1,1)}。 解空间树为： 该问题的最优值为：16 最优解为：（1，1，0） 5. 设S=｛X 1，X 2，···，X n ｝是严格递增的有序集，利用二叉树的结点来存储S 中的元素，在表示S 的二叉搜索树中搜索一个元素X ，返回的结果有两种情形，（1）在二叉搜索树的内结点中找到X=X i ，其概率为b i 。（2）在二叉搜索树的叶结点中确定X ∈（X i ，X i+1），其概率为a i 。在表示S 的二叉搜索树T 中，设存储元素X i 的结点深度为C i ；叶结点（X i ，X i+1）的结点深度为d i ，则二叉搜索树T 的平均路长p 为多少假设二叉搜索树T[i][j]=｛X i ，X i+1，···，X j ｝最优值为m[i][j]，W[i][j]= a i-1+b i +···+b j +a j ，则m[i][j](1<=i<=j<=n)递归关系表达式为什么 .二叉树T 的平均路长P=∑=+n i 1 Ci)(1*bi +∑=n j 0 dj *aj

应用文写作第一学期期末考试题及答案

职业中专应用文写作期末试题 一、选择题（每题1分，共10分）请把选项填在表格中。 题号 1 2 3 4 5 6 7 8 9 10 答案 1. 应用文是直接用于处理公私事务的实用性文章，其行文的目的是（ ） A ．说服阅读者 B. 解决实际问题 C. 与阅读者互通信息 D. 表现作者的文学功底 2．对于材料的选择，应该（ ） A.越多越好，详细全面 B.尽力生动形象 C.以少胜多，以一当十 D.只选择新近发生的事实 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.国办发﹝2012﹞第10号 B. 国办发﹝2012﹞ 10号 C.国办发（2012）第10号 D. 国办发（2012）10号 10.应用文语言要求用词造句要规范，符合现代语法规律，要求语言（） A. 生动 B. 真实 C. 完整 D.准确 二．判断题（10分）请把“√”或“×”填在表格中。 题号 1 2 3 4 5 6 7 8 9 10 答案 1. 应用文的宣传、教育作用主要体现在上级党政机关颁发的各类公文中。（） 2. 真实性是应用文最根本的特点，是应用文的生命线。（） 3. 不同文体对主题的提法不同：在新闻和文学作品中一般用“主题” ；在理论文章 中通常称为“基本观点”或“中心论点” ；在应用性文章中称为“中心思想”或“中心”。( ) 4. 在选择材料时，要做到材料统帅观点，观点表现材料。（） 5. 主题是文章的灵魂、统帅，因此，结构布局要为主题服务。（ ） 6. 批复是下行文，具有指示性、针对性和简要性等特点，是针对请示做出答复的公文。（） 7. 会议纪要按会议的的形式可以分为决议性会议纪要、部署性会议纪要、情况性会 议纪要等。（） 8. 函的标题中应该写明发文机关名称、事由、文种名称，文种名称应点明是“函” 还是“复函” 。（ ） 9. 公文标题中除法规、规章名称加书名号外，一般不用标点符号。（） 10. 公文的成文时间要用数字把年、月、日标全。（） 题号 1 2 3 4 5 6 7 8 9 10 答案 1. 下列说法正确的是（） A ．附件如有序号，使用阿拉伯数码 B. 附件名称后不加标点符号 C. 附件应该与公文一起装订 D. 附件的序号和名称前后标识应一致 2．搜集、积累材料的途径主要有（ ） A.观察 B.感受 C.调查 D. 想象 E.阅读 3．谋篇的原则有（ ） A.服从表现主旨的需要 B. 为读者着想 C.最好采用总横式结构 D.反映客观事物的发展规律和内部联系 E.适应不同文体的要求 4.下列属于应用文结尾专用语言的是（ ） A.鉴于 B.兹 C. 当否，请批示 D.盼复5. 下列各句适合作请示结尾的有（ ） A.“以上当否，请批复” B.“以上如无不妥，请予批准” 姓名 学校 班级 ………………装………………………………………………….订…………………………………………………线……………..

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

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算法的思想。

《现代应用文写作》期末考试试卷及答案(A卷)

《现代应用文写作》期末考试试卷及答案（A卷）（本试卷共六大题，总分100分，考试时间120分钟） 一、单项选择题（每小题1分，共10分） 1、公文标题，要能够显示文件的( ) A、性质和特点 B、内容和形式 C、目的和要求 D、特色和风格 2、总结的最基本的特点是（） A、简明性 B、时效性 C、客观性 D、理论性 3、求职信的写作关键是（） A、求职目标 B、求职缘起 C、求职条件 D、附件 4、诉状的制作要严格遵循“以事实为根据，以法律为准绳”的原则，因此诉状的写作要（） A、表达清楚 B、内容真实 C、体例规范 D、陈述周详 5、公文的生效标识是（） A、领导签字 B、会议通过 C、加盖印章 D、上级批准 6、行政机关公文成文日期写法正确的是（）。 A、二○○四年一月六日 B、二零零四年一月六日 C、2004年1月6日 D、2004、1、6 7、写作广告固然要重视其艺术性，但是也不可以夸大其词，脱离商品的实际情况，因此商品广告要求（） A、针对性强 B、新颖别致 C、突出重点 D、实事求是 8、行政机关“不相隶属机关之间商洽工作，询问和答复问题”用（） A、报告 B、通报 C、函 D、简报 9、和通讯相比，消息更具有（） A、文学性 B、评述性 C、主观性 D、时效性 10、主办隆重会议的单位邀请的人员或主要领导或主要领导在开会之初对与会者发表的讲话称为（） A、开幕词 B、欢迎词 C、慰问词 D、演讲稿 二、填空题（每小题1分，共5分） 1、行政机关的公文（包括电报），是行政机关在行政管理过程中形成的具有和 的文书，是依法行政和进行公务活动的重要工具。 2、在广告文案中最重要。 3、一份完整的计划一般由、、三部分构成。 4、调查报告的文章式标题由的正题和的副题组成。 5、起诉状的核心内容是。 三、简答题（每小题5分，共20分） 1、简述公文上行文中请示的行文规则。 1

算法设计与分析实验报告

本科实验报告 课程名称：算法设计与分析 实验项目：递归与分治算法 实验地点：计算机系实验楼110 专业班级：物联网1601 学号： 05 学生姓名：俞梦真 指导教师：郝晓丽 2018年 05月 04 日 实验一递归与分治算法 实验目的与要求

1．进一步熟悉C/C++语言的集成开发环境； 2．通过本实验加深对递归与分治策略的理解和运用。 实验课时 2学时 实验原理 分治（Divide-and-Conquer）的思想：一个规模为n的复杂问题的求解，可以划分成若干个规模小于n的子问题，再将子问题的解合并成原问题的解。 需要注意的是，分治法使用递归的思想。划分后的每一个子问题与原问题的性质相同，可用相同的求解方法。最后，当子问题规模足够小时，可以直接求解，然后逆求原问题的解。 实验题目 1．上机题目：格雷码构造问题 Gray码是一个长度为2n的序列。序列无相同元素，每个元素都是长度为n的串，相邻元素恰好只有一位不同。试设计一个算法对任意n构造相应的Gray码（分治、减治、变治皆可）。 对于给定的正整数n，格雷码为满足如下条件的一个编码序列。 （1）序列由2n个编码组成，每个编码都是长度为n的二进制位串。 （2）序列中无相同的编码。 （3）序列中位置相邻的两个编码恰有一位不同。 2．设计思想： 根据格雷码的性质，找到他的规律，可发现，1位是0 1。两位是00 01 11 10。三位是000 001 011 010 110 111 101 100。n位是前n-1位的2倍个。N-1个位前面加0，N-2为倒转再前面再加1。 3．代码设计： 归式，就是如何将原问题划分成子问题。 2.递归出口，递归终止的条件，即最小子问题的求解，可以允许多个出口。 3.界函数，问题规模变化的函数，它保证递归的规模向出口条件靠拢（2）递归与非递归之间如何实现程序的转换？ （3）分析二分查找和快速排序中使用的分治思想。 答： 1．一般根据是否需要回朔可以把递归分成简单递归和复杂递归，简单递归一般就是根据递归式来找出递推公式（这也就引申出分治思想和动态规划）。 2．复杂递归一般就是模拟系统处理递归的机制，使用栈或队列等数据结构保存回朔点来求解。 （4）分析二次取中法和锦标赛算法中的分治思想。 二次取中法：使用快速排序法中所采用的分划方法，以主元为基准，将一个表划分为左右两个子表，左子表中的元素均小于主元，右子表中的元素均大于主元。主元的选择是将表划分为r

算法设计与分析实验报告

算法设计与分析课程实验项目目录 学生姓名：学号： *实验项目类型：演示性、验证性、综合性、设计性实验。 *此表由学生按顺序填写。 本科实验报告专用纸

课程名称算法设计与分析成绩评定 实验项目名称蛮力法指导教师 实验项目编号 201 实验项目类型设计实验地点机房 学生姓名学号 学院信息科学技术学院数学系信息与计算科学专业级 实验时间 2012年 3月 1 日～6月30日温度24℃ 1.实验目的和要求： 熟悉蛮力法的设计思想。 2.实验原理和主要内容： 实验原理：蛮力法常直接基于问题的描述和所涉及的概念解决问题。 实验内容：以下题目任选其一 1).为蛮力字符串匹配写一段可视化程序。 2).写一个程序，实现凸包问题的蛮力算法。 3).最著名的算式谜题是由大名鼎鼎的英国谜人给出的： S END +MORE MONEY . 这 里有两个前提假设：第一，字母和十进制数字之间一一对应，也就是每个字母只代表一个数字，而且不同的字母代表不同的数字；第二，数字0不出现在任何数的最左边。求解一个字母算术意味着找到每个字母代表的是哪个数字。请注意，解可能并不是唯一的，不同人的解可能并不相同。 3.实验结果及分析： （将程序和实验结果粘贴，程序能够注释清楚更好。） 本科实验报告专用纸(附页) 该算法程序代码如下：

#include "" #include "" int main(int argc, char* argv[]) { int x[100],y[100]; int a,b,c,i,j,k,l,m,n=0,p,t1[100],num; int xsat[100],ysat[100]; printf("请输入点的个数：\n"); scanf("%d",&num); getchar(); clock_t start,end; start=clock(); printf("请输入各点坐标:\n"); for(l=0;l

《应用文写作》期未试卷A试卷及答案

南昌现代科技职业中等专业学校 《 应用文写作 》课程期末考试卷 A卷 B卷 2015 ~2016 学年 第1学期 考试方式： 开卷闭卷 其他 考试时间： 100 分钟 一、填空题：（每空1分，共15分） 1、应用文写作的基本要素包括：（ ）、（ ）、（ ）、（ ）。 2、决定具有（ ）、（ ）、（ ）的特点。 3、商业广告按广告的传播媒介来分（ ）、（ ）、（ ）。 4、经济合同是（ ）之间横向财产、经济关系的法律表现形式。 5、演讲稿是对（ ）和（ ）的提示，是进行演讲的依据，它体现演讲的（ ）和（ ），再现演讲的内宅和形式。 二、单项选择题：（每小题1分，共10分） 1、请示属于:（ ） A.公文 B.机关文书 C.下行文 D.上行文 2、不相隶属的机关、单位、团体之间商洽工作,询问和答复问题,向有关主管部门请求批准和答复审批事项时，可采用的公文是:（ ） A.请示 B.函 C.报告 D.通报 3、公文中一般不采用的表达方式是（ ）。 A ．议论 B ．说明 C ．叙述 D ．描写 4、某某县人民政府拟表彰全市双增双节先进集体和先进个人，形成公文用（ ）。 A ．通知 B ．通报 C ．通告 D ．报告 5、下列材料适合写感谢信的是（ ） A ．王X 生病，团支书代表全体团员去看望。 B ．某教授逝世，校党委、校行政、校工会及治丧委员会的代表去××教授家里悼唁，并安慰家属。 C ．工人刘X 骑自行车去上班，快到厂门口时，被一辆飞驰而来的摩托车撞伤头部，当场晕倒在地，肇事者将其送去医治。 D ．X 希望小学获得XX 大学学生会赠送的图书两千册。 6．下列标题中，书写正确的是（ ）。 A ．XX 县政府转发《XX 省人民政府关于加强城市规划工作的通知》的通知 B ．XX 县人民政府转发XX 省人民政府关于加强城市规划工作的通知的通知 C ．XX 县人民政府转发XX 省人民政府关于加强城市规划工作的通知 D ．XX 县人民政府转X 府[2015]32号文的通知 7．XX 市因为道路整修，需要将两条公交汽车行驶路线进行改变，拟行文将 此事告之市民，应使用的文种是（ ） A ．报告 B ．通告 C ．命令 D ．通知 8、某某厂拟向市工业局汇报该厂遭受火灾的情况，形成公文用（） A ．报告 B ．请示 C ．通报 C ．简报 9、下面会议通知的地点，撰写得最不妥当的是( )。 A.××区××街××单位 B.××单位小礼堂 C.××区××街××单位小礼堂 D.××区××街××单位×号楼四楼小礼堂 10、“意见”这一文种适用于 ( )。 A.对重要事项或者重大行动作出安排 B.对重要问题提出见解和处理办法 C.宣布重要事项 D.向上级提出工作意见 三、多项选择题（每小题2分，共10分） 1、公文按行文关系分类: （ ） A 上行文 B.下行文 C. 平行文 D.直行文 2、报告的正文一般由下列内容组成: A.开头 B.报告事项 C.结语 D.主送机关 3、下列属于应用文的是：（ ） A ．公告 B.通告 C.报告 D.散文 4、下列文种中，属于下行公文的有（ ） A ．命令 B ．决定 C ．通告 D ．请示 E ．批复 5、应用文文章写作的要素有（ ） A ．重点 B. 材料 C. 主题 D. 结构 E.语言 学校 专业、班 年级 学号 姓名 公平竞争、诚实守信、严肃考纪、拒绝作弊 封 线 密

算法设计与分析试卷(2010)

内部资料，转载请注明出处，谢谢合作。 算法设计与分析试卷(A 卷) 一、 选择题 （ 选择1-4个正确的答案, 每题2分，共20分） （1）计算机算法的正确描述是： A ．一个算法是求特定问题的运算序列。 B ．算法是一个有穷规则的集合，其中之规则规定了一个解决某一特定类型的问题的运算序列。 C ．算法是一个对任一有效输入能够停机的图灵机。 D ．一个算法，它是满足5 个特性的程序，这5个特性是：有限性、确定性、能 行性、有0个或多个输入且有1个或多个输出。 （2）影响程序执行时间的因素有哪些？ A ．算法设计的策略 B ．问题的规模 C ．编译程序产生的机器代码质量 D ．计算机执行指令的速度 （3）用数量级形式表示的算法执行时间称为算法的 A ．时间复杂度 B ．空间复杂度 C ．处理器复杂度 D ．通信复杂度 （4）时间复杂性为多项式界的算法有： A ．快速排序算法 B ．n-后问题 C ．计算π值 D ．prim 算法 （5）对于并行算法与串行算法的关系，正确的理解是： A ．高效的串行算法不一定是能导出高效的并行算法 B ．高效的串行算法不一定隐含并行性 C ．串行算法经适当的改造有些可以变化成并行算法 D. 用串行方法设计和实现的并行算法未必有效 （6）衡量近似算法性能的重要标准有： A ．算法复杂度 B ．问题复杂度 C ．解的最优近似度 D ．算法的策略 （7）分治法的适用条件是，所解决的问题一般具有这些特征： A ．该问题的规模缩小到一定的程度就可以容易地解决； B ．该问题可以分解为若干个规模较小的相同问题； C ．利用该问题分解出的子问题的解可以合并为该问题的解 D ．该问题所分解出的各个子问题是相互独立的。 （8）具有最优子结构的算法有： A ．概率算法 B ．回溯法 C ．分支限界法 D ．动态规划法 （9）下列哪些问题是典型的NP 完全问题： A ．排序问题 B ．n-后问题 C ．m-着色问题 D ．旅行商问题 （10）适于递归实现的算法有： A ．并行算法 B ．近似算法 C ．分治法 D ．回溯法 二、算法分析题（每小题5分，共10分） （11）用展开法求解递推关系： （12）分析当输入数据已经有序时快速排序算法的不足，提出算法的改进方案。 ???>+-==1 1)1(211)(n n T n n T

《算法设计与分析》实验一

学号1607070212 《算法设计与分析》 实验报告一 学生姓名张曾然 专业、班级16软件二班 指导教师唐国峰 成绩 计算机与信息工程学院软件工程系 2018 年9 月19 日

实验一：递归策略运用练习 一、实验目的 本次实验是针对递归算法的算法设计及应用练习，旨在加深学生对该算法原理的理解，提高学生运用该算法解决问题的能力。 二、实验步骤与要求 1．实验前复习课程所学知识以及阅读和理解指定的课外阅读材料； 2．学生独自完成实验指定内容； 3．实验结束后，用统一的实验报告模板编写实验报告。 4．提交说明： （1）电子版提交说明： a 需要提交Winrar压缩包，文件名为“《算法设计与分析》实验一_学号_姓名”， 如“《算法设计与分析》实验一_09290101_张三”。 b 压缩包内为一个“《算法设计与分析》实验一_学号_姓名”命名的顶层文件夹， 其下为两个文件夹，一个文件夹命名为“源程序”，另一个文件夹命名为“实验 报告电子版”。其下分别放置对应实验成果物。 （2）打印版提交说明： a 不可随意更改模板样式。 b 字体：中文为宋体，大小为10号字，英文为Time New Roman，大小为10号 字。 c 行间距：单倍行距。 （3）提交截止时间：2018年10月10日16:00。 三、实验项目 1．运用递归策略设计算法实现下述题目的求解过程。 题目列表如下： 【必做题】 （1）运动会开了N天，一共发出金牌M枚。第一天发金牌1枚加剩下的七分之一枚，第二天发金牌2枚加剩下的七分之一枚，第3天发金牌3枚加剩下的七分之一枚，以后每天都照此办理。到了第N天刚好还有金牌N枚，到此金牌全部发完。编程求N和M。 （2）国王分财产。某国王临终前给儿子们分财产。他把财产分为若干份，然后给第一个儿子一份，再加上剩余财产的1/10；给第二个儿子两份，再加上剩余财产的1/10；……；给第i 个儿子i份，再加上剩余财产的1/10。每个儿子都窃窃自喜。以为得到了父王的偏爱，孰不知国王是“一碗水端平”的。请用程序回答，老国王共有几个儿子？财产共分成了多少份？

算法设计与分析试卷及答案

湖南科技学院二○年学期期末考试 信息与计算科学专业年级《算法设计与分析》试题 考试类型:开卷试卷类型:C卷考试时量:1２０分钟 题号一二三四五总分统分人 得分 阅卷人 复查人 一、填空题(每小题3 分，共计30 分) １、用O、Ω与θ表示函数f与g之间得关系＿__________＿__＿_＿_＿＿_＿__＿___＿＿。 2、算法得时间复杂性为,则算法得时间复杂性得阶为_＿__＿＿____＿_＿_＿____＿＿_＿__＿。 3、快速排序算法得性能取决于_＿_____＿_______＿__＿__＿_＿___＿__。 4、算法就是__＿_＿______＿＿_＿＿__＿________＿___＿___＿___＿___＿_＿_＿_＿＿_＿__。 5、在对问题得解空间树进行搜索得方法中,一个活结点最多有一次机会成为活结点得就是＿_______＿__＿____________＿。 6、在算法得三种情况下得复杂性中,可操作性最好且最有实际价值得就是__＿_＿情况下得时间复杂性。 7、大Ω符号用来描述增长率得下限,这个下限得阶越__＿________,结果就越有价值。。 8、_＿_＿__＿_＿____＿________＿_____就是问题能用动态规划算法求解得前提。 9、贪心选择性质就是指_＿____________＿______＿_＿__＿__＿______＿________________＿__＿_____＿____＿____＿_＿______＿__＿__＿___＿_＿__＿___＿_＿＿＿________＿__。 1０、回溯法在问题得解空间树中,按______＿＿＿_＿__＿策略,从根结点出发搜索解空间树。 二、简答题(每小题10分,共计3０分) １、试述回溯法得基本思想及用回溯法解题得步骤。 2、有８个作业{１,２,…,8}要在由2台机器M1与Ｍ２组成得流水线上完成加工。每个作业加工得顺序都就是先在M1上加工,然后在M2上加工。M１与M2加工作业ｉ所需得时间分别为: M１10 2 8 12 6 ９４14

计算机算法设计与分析习题及答案

计算机算法设计与分析习 题及答案 Prepared on 24 November 2020

《计算机算法设计与分析》习题及答案 一．选择题 1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ A ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4. 回溯法解旅行售货员问题时的解空间树是（ A ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树 5．下列算法中通常以自底向上的方式求解最优解的是（B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 6、衡量一个算法好坏的标准是（ C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 7、以下不可以使用分治法求解的是（ D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 8. 实现循环赛日程表利用的算法是（A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 9．下面不是分支界限法搜索方式的是（D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先

10．下列算法中通常以深度优先方式系统搜索问题解的是（D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 11.备忘录方法是那种算法的变形。（ B ） A、分治法 B、动态规划法 C、贪心法 D、回溯法 12．哈夫曼编码的贪心算法所需的计算时间为（B ）。 A、O（n2n） B、O（nlogn） C、O（2n） D、O（n） 13．分支限界法解最大团问题时，活结点表的组织形式是（B ）。 A、最小堆 B、最大堆 C、栈 D、数组 14．最长公共子序列算法利用的算法是（B）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 15．实现棋盘覆盖算法利用的算法是（A ）。 A、分治法 B、动态规划法 C、贪心法 D、回溯法 16.下面是贪心算法的基本要素的是（C ）。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最优解 17.回溯法的效率不依赖于下列哪些因素（ D ） A.满足显约束的值的个数 B. 计算约束函数的时间 C.计算限界函数的时间 D. 确定解空间的时间 18.下面哪种函数是回溯法中为避免无效搜索采取的策略（B ） A．递归函数 B.剪枝函数 C。随机数函数 D.搜索函数 19. （D）是贪心算法与动态规划算法的共同点。

《应用文写作》期末试题及答案(A卷)

《应用文写作》期末试题及答案（A卷） （考试时间：120分钟） 专业年级姓名成绩阅卷人 一、单项选择题（本大题共22小题，每小题1分，共22分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.陈述事件的来龙去脉，记叙人物的活动、经历、行为的一种表达方式是（） A.说明 B.叙述 C.解释 D.归纳 2.材料具有多义性，提炼主旨时，应把材料本身的特点与解决具体问题的实际需要结合起来，对材料进行（） A.对比筛选 B.分析归纳 C.集思广益 D.修改润色 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.开幕词

计算机算法设计与分析期末考试复习题

1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ A ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4、最长公共子序列算法利用的算法是（ B ）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 5. 回溯法解TSP问题时的解空间树是（ A ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树6．下列算法中通常以自底向上的方式求解最优解的是（ B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 7、衡量一个算法好坏的标准是（C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 8、以下不可以使用分治法求解的是（D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 9. 实现循环赛日程表利用的算法是（ A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 10、实现最长公共子序列利用的算法是（ B ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法11．下面不是分支界限法搜索方式的是（ D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先 12．下列算法中通常以深度优先方式系统搜索问题解的是（ D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 13. 一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（ B ）。 A、重叠子问题 B、最优子结构性质 C、贪心选择性质 D、定义最优解14．广度优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 15．背包问题的贪心算法所需的计算时间为（ B ）。

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

《算法分析与设计》期末复习题 一、选择题 1.应用Johnson法则的流水作业调度采用的算法是（D） A. 贪心算法 B. 分支限界法 C.分治法 D. 动态规划算法 塔问题如下图所示。现要求将塔座A上的的所有圆盘移到塔座B上，并仍按同样顺序叠置。移动圆盘时遵守Hanoi塔问题的移动规则。由此设计出解Hanoi塔问题的递归算法正确的为：（B） " ; | A. void hanoi(int n, int A, int C, int B) 《 { if (n > 0) { hanoi(n-1,A,C, B); move(n,a,b); hanoi(n-1, C, B, A); B. void hanoi(int n, int A, int B, int C) { if (n > 0) { hanoi(n-1, A, C, B); ] move(n,a,b); hanoi(n-1, C, B, A); } C. void hanoi(int n, int C, int B, int A) { if (n > 0) { hanoi(n-1, A, C, B); move(n,a,b); hanoi(n-1, C, B, A); } }

3. 动态规划算法的基本要素为（C ） A. 最优子结构性质与贪心选择性质 B ．重叠子问题性质与贪心选择性质 C ．最优子结构性质与重叠子问题性质 D. 预排序与递归调用 4. 算法分析中，记号O 表示（B ）， 记号Ω表示（A ）， 记号Θ表示（D ）。 … A.渐进下界 B.渐进上界 C.非紧上界 D.紧渐进界 E.非紧下界 5. 以下关于渐进记号的性质是正确的有：（A ） A.f (n)(g(n)),g(n)(h(n))f (n)(h(n))=Θ=Θ?=Θ B. f (n)O(g(n)),g(n)O(h(n))h(n)O(f (n))==?= C. O(f(n))+O(g(n)) = O(min{f(n),g(n)}) D. f (n)O(g(n))g(n)O(f (n))=?= D. void hanoi(int n, int C, int A, int B) { if (n > 0) { | hanoi(n-1, A, C, B); move(n,a,b); hanoi(n-1, C, B, A); }

应用文写作期末试卷A卷

一．判断题：（对的打√，错的打×，每题1分，共10分） 1．批复是主动行文。（） 2．因时间紧迫，可在同一份请示中向上级机关请求拨款建办公楼和买汽车。（） 3．某市教育局向市财政局申请普九教育经费，用请示行文。（）4．桂洲市人民政府办公室2002年第5号文的发文字号为桂市办〔2002〕第5号。（） 5．2001年1月1日起施行的《国家行政机关公文处理办法》是我国目前关于行政公文处理的一份最具权威的文件。（） 6．宁波市海曙区白云街道宣布新当选的领导班子成员名单，用通报行文。（） 7．总结和计划的写作目的都是为了指导未来实践。（） 8．联合行文的发文字号应该并排写在一起。（） 9．机关单位对社会的某一现象、某一事件或对本单位的内部事件、问题进行调查研究后写出的书面报告，可称为调查报告。（） 10．会议纪要就是对会议全程的如实纪录。（） 二．单项选择题：（每题2分，共30分） 1．为及时简要地汇报工作情况，反映情况和交流信息，各级行政机关、企事业单位、社会团体经常定期 或不定期编发（）。 A．通报 B．通知 C．意见 D．简报2．浙江省人民政府向所属县、市人民政府下发《财政部关于严格控制各级行政机关、事业单位发放奖金 的紧急通知》，用（）行文。 A、指示通知 B、批转通知 C、转发通知 D、知照通知3．商贸学院学生李茗救了一个落水儿童，学校决定发文进行表彰，于是发了一篇（） A.通告 B.通报 C.通知 D.决定 4. 下列关于“批复”文种的论述，正确的是（） A．平行文 B．指挥下级机关布置工作，提出工作原则和要求 C．答复同级机关询问事项 D．态度要鲜明，措辞要明确 5. 发文字号的位置应在（）。 A．版尾、抄送机关与印发机关之间，居中。 B．主体、标题与主送机关之间，居中。 C．眉首，红色隔离线以上，发文机关标识以下，居中。 D．眉首，红色隔离线以上右侧。 6.公文的制发者是____。 A．合法存在的机关和组织 B．个人 C．单位领导人 D．公民7. 请示结尾常见的习惯用语是。答案：B A．“特此报告”或“专此报告” B．以上请示，请批复 C．请批复 D．以上意见当否，请批准 8.按规定，要写签发人的公文是______。

《计算机算法设计与分析》习题及答案.doc

《计算机算法设计与分析》习题及答案 一．选择题 1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ A ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4. 回溯法解旅行售货员问题时的解空间树是（ A ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树 5．下列算法中通常以自底向上的方式求解最优解的是（ B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 6、衡量一个算法好坏的标准是（ C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 7、以下不可以使用分治法求解的是（ D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 8. 实现循环赛日程表利用的算法是（ A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 9．下面不是分支界限法搜索方式的是（ D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先 10．下列算法中通常以深度优先方式系统搜索问题解的是（ D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 11.备忘录方法是那种算法的变形。（ B ） A、分治法 B、动态规划法 C、贪心法 D、回溯法 12．哈夫曼编码的贪心算法所需的计算时间为（ B ）。 A、O（n2n） B、O（nlogn） C、O（2n） D、O（n） 13．分支限界法解最大团问题时，活结点表的组织形式是（ B ）。 A、最小堆 B、最大堆 C、栈 D、数组 14．最长公共子序列算法利用的算法是（ B ）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 15．实现棋盘覆盖算法利用的算法是（ A ）。 A、分治法 B、动态规划法 C、贪心法 D、回溯法 16.下面是贪心算法的基本要素的是（ C ）。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最优解 17.回溯法的效率不依赖于下列哪些因素（ D ） A.满足显约束的值的个数 B. 计算约束函数的时间 C.计算限界函数的时间 D. 确定解空间的时间 18.下面哪种函数是回溯法中为避免无效搜索采取的策略（ B ） A．递归函数 B.剪枝函数 C。随机数函数 D.搜索函数 19. （ D ）是贪心算法与动态规划算法的共同点。

南京邮电大学算法设计实验报告——动态规划法

实验报告 （2009/2010学年第一学期） 课程名称算法分析与设计A 实验名称动态规划法 实验时间2009 年11 月20 日指导单位计算机学院软件工程系 指导教师张怡婷 学生姓名丁力琪班级学号B07030907 学院(系) 计算机学院专业软件工程

实验报告 实验名称动态规划法指导教师张怡婷实验类型验证实验学时2×2实验时间2009-11-20一、实验目的和任务 目的：加深对动态规划法的算法原理及实现过程的理解，学习用动态规划法解决实际应用中的最长公共子序列问题。 任务：用动态规划法实现求两序列的最长公共子序列，其比较结果可用于基因比较、文章比较等多个领域。 要求：掌握动态规划法的思想，及动态规划法在实际中的应用；分析最长公共子序列的问题特征，选择算法策略并设计具体算法，编程实现两输入序列的比较，并输出它们的最长公共子序列。 二、实验环境(实验设备) 硬件：计算机 软件：Visual C++

三、实验原理及内容（包括操作过程、结果分析等） 1、最长公共子序列（LCS）问题是：给定两个字符序列X={x1,x2,……,x m}和Y={y1,y2,……,y n}，要求找出X和Y的一个最长公共子序列。 例如：X={a,b,c,b,d,a,b},Y={b,d,c,a,b,a}。它们的最长公共子序列LSC={b,c,d,a}。 通过“穷举法”列出所有X的所有子序列，检查其是否为Y的子序列并记录最长公共子序列并记录最长公共子序列的长度这种方法，求解时间为指数级别的，因此不可取。 2、分析LCS问题特征可知，如果Z={z1,z2,……，z k}为它们的最长公共子序列，则它们一定具有以下性质： （1）若x m=y n，则z k=x m=y n，且Z k-1是X m-1和Y n-1的最长公共子序列； （2）若x m≠y n且x m≠z k，则Z是X m-1和Y的最长公共子序列； （3）若x m≠y n且z k≠y n，则Z是X和Y的最长公共子序列。 这样就将求X和Y的最长公共子序列问题，分解为求解较小规模的问题： 若x m=y m，则进一步分解为求解两个（前缀）子字符序列X m-1和Y n-1的最长公共子序列问题； 如果x m≠y n，则原问题转化为求解两个子问题，即找出X m-1和Y的最长公共子序列与找出X 和Y n-1的最长公共子序列，取两者中较长者作为X和Y的最长公共子序列。 由此可见，两个序列的最长公共子序列包含了这两个序列的前缀的最长公共子序列，具有最优子结构性质。 3、令c[i][j]保存字符序列X i={x1,x2,……,x i}和Y j={y1,y2,……,y j}的最长公共子序列的长度，由上述分析可得如下递推式： 0 i=0或j=0 c[i][j]= c[i-1][j-1]+1 i,j>0且x i=y j max{c[i][j-1],c[i-1][j]} i,j>0且x i≠y j 由此可见，最长公共子序列的求解具有重叠子问题性质，如果采用递归算法实现，会得到一个指数时间算法，因此需要采用动态规划法自底向上求解，并保存子问题的解，这样可以避免重复计算子问题，在多项式时间内完成计算。 4、为了能由最优解值进一步得到最优解（即最长公共子序列），还需要一个二维数组s[][]，数组中的元素s[i][j]记录c[i][j]的值是由三个子问题c[i-1][j-1]+1,c[i][j-1]和c[i-1][j]中的哪一个计算得到，从而可以得到最优解的当前解分量（即最长公共子序列中的当前字符），最终构造出最长公共子序列自身。