算法分析与设计复习

一、选择题（本题共5小题，每小题3分，共15分）

1.关于算法

2.关于NP问题

3.关于查找的效率

4.关于排序的时间复杂度和空间复杂度

5.简单程序段的时间复杂度分析

for(int=0;i

{ C[i][j]=0;

for(k=0;k

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

}

s=0;

for(i=1;i<=n2;i++) for(j=1;j<=i;j++) s=s+i*j;

以下不是算法所必须具备的特征（）。

A有穷性 B确切性 C高效性 D可行性

（）不是衡量算法的标准。

A 时间效率

B 空间效率

C 问题的难度D适应能力

算法分析是（）。

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

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

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

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

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

A 单源最短路径问题

B N皇后问题

C 最小生成树问题

D 连续背包问题

下列算法中不能解决0-1背包问题的是（）

A 贪心法

B 动态规划

C 回溯法

D 分支限界法

若L是一个NP完全问题，L经过多项式时间变换后得到问题L’，则L’是一个

A P类问题

B NP类问题

C NP完全问题D不可解问题

下面关于NP问题说法正确的是（）

A NP问题都是不可能解决的问题

B P类问题包含在NP类问题中

C NP完全问题是P类问题的子集

D NP类问题包含在P类问题中

以下关于判定问题难易处理的叙述中正确的是（）。

A．可以由多项式时间算法求解的问题是难处理的

B．需要超过多项式时间算法求解的问题是易处理的

C．可以由多项式时间算法求解的问题是易处理的

D．需要超过多项式时间算法求解的问题是不能处理的

Prim算法求最小生成树采用的是（）算法思想。

A 贪心算法

B 动态规划法

C 回溯法

D 蛮力法

归并排序算法的时间复杂度和空间复杂度是（）

快速排序算法最差情况下的时间复杂度是（）

实现大整数的乘法的分治算法的时间复杂度是（）

有序表(12,24,36,48,60,72,84)中顺序、?分查找关键字72时所需进?的关键字?较次

数是（）

?某种排序?法对关键字序列（25,84,21,47,15,27,68,35,20）进?排序，序列的变化情况如下：

20,15,21,25,47,27,68,35,84

15,20,21,25,35,27,47,68,84

15,20,21,25,27,35,47,68,84

请问采?的是哪种排序算法（）

设某算法的时间复杂度为O(n3)。在某台计算机上实现并完成该算法的时间为t秒。现有另外一台计算机，其运行速度为第一台的64倍，那么在这台新机器上用同一算法在t秒内能解输入规模多大的问题？

1、一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

2、这种不断回头寻找目标的方法称为回溯法。

3、直接或间接地调用自身的算法称为递归算法。

二、求解或证明下面各式：（本题共4小题，共30分）

1.求和式的计算或证明

∑=

?-

n i

i i

1

3

)1

(

F(n) = bF(n-1) + G(n), F(0) = c

证明：F(n) = c b n +∑

=-?

n i

i

n i

G b

1

)(。由此，推导Hanoi塔问题的通项公式。

2.二阶常系数齐次线性递推关系求解

x(n) = 4x(n-1) - 3x(n-2), x(1)=1, x(2)=3

x(n) = 6x(n-1) - 9x(n-2) + n, x(0)=0，x(1)=1

a0=0，a1=1，an=5a n-1?6a n-2

3. 利用主定理，求T(n)增长的阶 T(n) = 25T(n/5)+n^2的时间复杂度 T(n) = 2T(n/3)+n^2的时间复杂度

4. 函数按照增长的速度从低到高排序

4n 2，logn ，3n ，n!，n 2/3

2+3n+4n 2，2logn ，2n +3n ，2^2^n ，2^n^2，sqrt （n ）

5. 证明：函数的复杂度 f (n)=n 3+ n 2log 100n

6. 已知函数 x(int n) { if (n <= 3) return 1; else return x(n - 2) + x(n - 4) + 1; } 求x(x(8)) 三、算法理解题（本题共4小题，共35分） 1. 运用分治法算法计算m*n 。 2. 运用俄罗斯农夫算法计算m*n 。 59 * 47

3. 运用两种不同的算法求2348和1776的最大公因子。

4. 利用减治法计算p n 除以q 的余数。31000%5

5. 利用Dijkstra 算法对下图结点a ，求a 到所有其他结点的最短路径。

6. 按照Johnson-Trotter 算法和字典序生成全排列的算法给出下面排列的后面10

个排列。42351

7.已知背包承重L，待放入背包的物品如下所示，用分支限界法求其最优解。

n=4个物品，大小分别为W={1,2,4,6}，价值分别为P={5,5,6,9}，背包容量

为M=10。

8.已知矩阵M1（25*10）、M2（10*5）、M3（5*30）、M4（30*20）、M5（20*15），

利用矩阵链相乘的动态规划算法，计算所需的最少乘法次数，并根据计算填写

下表。

四、算法设计与分析题：（本题共2小题，第1小题15分，第2小题5分，共20分）

1.对下面算法，分析该算法的复杂度。请改进该算法，使之更高效。

2.利用分治法或动态规划法设计算法。

利用动态规划设计算法，实现最大子段和的求解。如(-2,11,-4,13,-5,-2)

Sum(A[1..n])

//Input：整型数组A

max = 0

for i = 1 to n – 1 do

S[i，i] = A[i]

if max

for j = i + 1 to n do

S[i，j] = S[i，j – 1] + A[j]

if max

return max

利用分治法求给定数列的最大值。

Max(A[m..n])

//Input：整型数组A

if m==n return A[m]

else

S = Max(A[m..m+(n-m)/2])

T = Max(A[m+(n-m)/2+1..n])

if S

else return S

思考：

任意自然数n都可以分为若干组自然数的和，比如

4 = 1 + 1 + 1 + 1 = 2 + 1 + 1 = 3 + 1 = 2 + 2

共4种分解方法。设计算法，求n的不同分解方式。

算法分析与设计复习题及参考答案

网络教育课程考试复习题及参考答案算法分析与设计一、名词解释：1.算法 2.程序 3.递归函数 4.子问题的重叠性质 5.队列式分支限界法 6.多机调度问题7.最小生成树二、简答题： 1.备忘录方法和动态规划算法相 比有何异同？简述之。 2.简述回溯法解题的主要步骤。 3.简述动态规划算法求解的基本要素。 4.简述回溯法的基本思想。 5.简要分析在递归算法中消除递归调用，将递归算法转化为非递归算法的方法。 6.简要分析分支限界法与回溯法的异同。7.简述算法复杂性的概念，算法复杂性度量主要指哪两个方面？8.贪心算法求解的问题主要具有哪些性质？简述之。9.分治法的基本思想是什么？合并排序的基本思想是什么？请分别简述之。10.简述分析贪心算法与动态规划 算法的异同。三、算法编写及算法应用分析题： 1.已知有3个物品： (w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10),背包的容积M=20，根据0-1背包动态规划的递推式求出最优解。 2.按要求完成以下关于排序和查找的问题。①对数组A={15，29，135，18，32，1，27，25，5}，用快速排序方法将其排成递减序。②请描述递减数组进行二分搜索的基本思想，并给出非递归算法。③给出上述算法的递归算法。④使用上述算法对①所得到的结果搜索如下元素，并给出搜索过程：18，31，135。已知，=1，2，3，4，5，6，=5，=10，=3，=12，=5，=50，=6，kijr*r1234567ii1求矩阵链积A×A×A×A×A×A的最佳求积顺序（要求给出计算步骤）。1234564.根据分枝限界算法基本过程,求解0-1背包问题。已知n=3,M=20，(w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10)。 5.试用贪心算法求解汽车加油问题：已知一辆汽车加满油后可行驶n公里，而旅途中有若干个加油站。试设计一个有效算法，指出应在哪些加油站停靠加油，使加油次数最少，请写出该算法。6.试用动态规划算法实现下列问题：设A和B是两个字符串。我们要用最少的字符操作，将字符串A转换为字符串B，这里所说的字符操作包括：①删除一个字符。②插入一个字符。③将一个字符改为另一个字符。请写出该算法。7.对于下图使用Dijkstra算法求由顶点a到顶点h的最短路径。be2g212ad323182cf2h 8.试写出用分治法对数组A[n]实现快速排序的算法。9.有n个活动争用一个活动室。已知活动i占用的时间区域为[s，f ]，活动i,j相容的条件是：sj≥f ii，问题的解表示为(x| x =1，2…，n,)，x表示顺序为i的活动编号活动，求一个相容的活动子集，iiii且安排的活动数目最多。xxx10.设、、是一个三角形的三条边，而且x+x+x=14。请问有多少种不同的三角形？给出解答过程。12312311.

算法分析与设计(线下作业二)

《算法分析与设计》 学习中心： 专业： 学号： 姓名：

作业练习二 一、名词解释 1、MST性质 2、子问题的重叠性质 递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次，这种性质称为子问题的重叠性质。 二、简答题 1、简述动态规划算法求解的基本要素。 答：动态规划算法求解的基本要素包括： 1)最优子结构是问题能用动态规划算法求解的前提； 2)动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果，即重叠子问题。 2、备忘录方法和动态规划算法相比有何异同简述之。 答：备忘录方法是动态规划算法的变形。与动态规划算法一样，备忘录方法用表格保存已解决的子问题的答案，在下次需要解此问题时，只要简单地查看该子问题的解答，而不必重新计算。备忘录方法与动态规划算法不同的是，备忘录方法的递归方式是自顶向下的，而动态规划算法则是自底向上递归的。因此，备忘录方法的控制结构与直接递归方法的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同的子问题的重复求解，而直接递归方法没有此功能。

3、贪心算法求解的问题主要具有哪些性质简述之。 答：贪心算法求解的问题一般具有二个重要的性质： 一是贪心选择性质，这是贪心算法可行的第一个基本要素； 另一个是最优子结构性质，问题的最优子结构性质是该问题可用贪心算法求解的关键特征。 三、算法编写及算法应用分析题 1、设计求解如下最大子段和问题的动态规划算法。只需给出其递推计算公式即可。 最大子段和问题：给定由n 个整数（可能为负整数）组成的序列a1a2 … an，求该序列形如Σi≤k≤j ak的子段和的最大值。当所有整数均为负整数时定义其最大子段和为0。依次定义，所求的最优值为max{0, max1≤i≤j≤n Σi≤k≤j ak }。

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

算法设计与分析考试题 及答案 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

2015年算法分析与设计期末考试试卷B卷

西南交通大学2015 — 2016学年第(一)学期考试试卷 课程代码 3244152课程名称 算法分析与设计 考试时间 120分钟 阅卷教师签字： __________________________________ 填空题(每空1分，共15分) 1、 程序是 (1) 用某种程序设计语言的具体实现。 2、 矩阵连乘问题的算法可由 (2) 设计实现。 3、 从分治法的一般设计模式可以看出，用它设计出的程序一般是 (3) 4、 大整数乘积算法是用 (4) 来设计的。 5、 贪心算法总是做出在当前看来 (5) 的选择。也就是说贪心算法并不从整体最优 考虑，它所做出的选择只是在某种意义上的 (6) o 6、 回溯法是一种既带有 (7) 又带有 (8) 的搜索算法。 7、 平衡二叉树对于查找算法而言是一种变治策略，属于变治思想中的 (9) 类型 8、 在忽略常数因子的情况下，0、门和0三个符号中， (10) 提供了算法运行时 间的一个上界。 9、 算法的“确定性”指的是组成算法的每条 (11) 是清晰的，无歧义的。 10、 冋题的(12) 是该冋题可用动态规划算法或贪心算法求解的关键特征。 11、 算法就是一组有穷 (13)，它们规定了解决某一特定类型问题的 (14) o 12、 变治思想有三种主要的类型：实例化简，改变表现， (15) o 、 ___________________________________________________________________________________ L 线订装封密 线订装封密 、 __________________ 二 线订装封密 级班 选择题(每题2分，共20 分)

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

一。选择题 1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ B ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4、在下列算法中有时找不到问题解的是（ B ）。 A、蒙特卡罗算法 B、拉斯维加斯算法 C、舍伍德算法 D、数值概率算法 5. 回溯法解旅行售货员问题时的解空间树是（ B ）。 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、下列随机算法中运行时有时候成功有时候失败的是（C ） A 数值概率算法 B 舍伍德算法 C 拉斯维加斯算法 D 蒙特卡罗算法 11．下面不是分支界限法搜索方式的是（ D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先12．下列算法中通常以深度优先方式系统搜索问题解的是（ D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 13.备忘录方法是那种算法的变形。（ B ）

算法分析与设计试卷

《算法分析与设计》试卷(A) （时间90分钟满分100分） 一、填空题（30分,每题2分）。 1．最长公共子序列算法利用的算法是（ B ）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法2．在对问题的解空间树进行搜索的方法中,一个活结点最多有一次机会成为活结点的是( B ). A.回溯法 B.分支限界法 C.回溯法和分支限界法 D.回溯法求解子集树问题 3．实现最大子段和利用的算法是（ B ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法4．.广度优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法5．衡量一个算法好坏的标准是（ C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 6．Strassen矩阵乘法是利用（ A）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 7. 使用分治法求解不需要满足的条件是（ A ）。 A 子问题必须是一样的 B 子问题不能够重复 C 子问题的解可以合并 D 原问题和子问题使用相同的方法解 8．用动态规划算法解决最大字段和问题，其时间复杂性为( B ). A.logn B.n C.n2 D.nlogn 9.解决活动安排问题，最好用（ B ）算法 A.分治 B.贪心 C.动态规划 D.穷举 10.下面哪种函数是回溯法中为避免无效搜索采取的策略（ B ） A．递归函数 B.剪枝函数C。随机数函数 D.搜索函数11. 从活结点表中选择下一个扩展结点的不同方式将导致不同的分支限界法,以下除( C )之外都是最常见的方式. A.队列式分支限界法 B.优先队列式分支限界法 C.栈式分支限界法 D.FIFO分支限界法 12. .回溯算法和分支限界法的问题的解空间树不会是( D ). A.有序树 B.子集树 C.排列树 D.无序树 13.优先队列式分支限界法选取扩展结点的原则是（ C ）。 A、先进先出 B、后进先出 C、结点的优先级 D、随机14．下面是贪心算法的基本要素的是（ C ）。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最优解15．回溯法在解空间树T上的搜索方式是( A ). A.深度优先 B.广度优先 C.最小耗费优先 D.活结点优先 二、填空题（20分,每空1分）。 1.算法由若干条指令组成的又穷序列，且满足输入、输出、 确定性和有限性四个特性。 2.分支限界法的两种搜索方式有队列式(FIFO)分支限界法、优先队列式分支限界法，用一个队列来存储结点的表叫活节点表。

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

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

算法设计与分析课程设计(完整版)

HUNAN CITY UNIVERSITY 算法设计与分析课程设计 题目：求最大值与最小值问题 专业： 学号： 姓名： 指导教师： 成绩： 二0年月日

一、问题描述 输入一列整数，求出该列整数中的最大值与最小值。 二、课程设计目的 通过课程设计，提高用计算机解决实际问题的能力，提高独立实践的能力，将课本上的理论知识和实际有机的结合起来，锻炼分析解决实际问题的能力。提高适应实际，实践编程的能力。在实际的编程和调试综合试题的基础上，把高级语言程序设计的思想、编程巧和解题思路进行总结与概括，通过比较系统地练习达到真正比较熟练地掌握计算机编程的基本功，为后续的学习打下基础。了解一般程序设计的基本思路与方法。 三、问题分析 看到这个题目我们最容易想到的算法是直接比较算法：将数组的第 1 个元素分别赋给两个临时变量：fmax:=A[1]; fmin:=A[1]; 然后从数组的第 2 个元素 A[2]开始直到第 n个元素逐个与 fmax 和 fmin 比较，在每次比较中，如果A[i] > fmax，则用 A[i]的值替换 fmax 的值；如果 A[i] < fmin，则用 A[i]的值替换 fmin 的值；否则保持 fmax（fmin）的值不变。这样在程序结束时的fmax、fmin 的值就分别是数组的最大值和最小值。这个算法在最好、最坏情况下，元素的比较次数都是 2(n-1)，而平均比较次数也为 2(n-1)。 如果将上面的比较过程修改为：从数组的第 2 个元素 A[2]开始直到第 n 个元素，每个 A[i]都是首先与 fmax 比较，如果 A[i]>fmax,则用 A[i]的值替换 fmax 的值；否则才将 A[i]与 fmin 比较，如果 A[i] < fmin，则用 A[i]的值替换 fmin 的值。 这样的算法在最好、最坏情况下使用的比较次数分别是 n-1 和 2(n-1),而平均比较次数是 3(n-1)/2,因为在比较过程中，将有一半的几率出现 A[i]>fmax 情况。

(完整版)算法设计与分析期末考试卷及答案a

一．填空题(每空 2 分，共30分) 1．算法的时间复杂性指算法中的执行次数。 2．在忽略常数因子的情况下，O、和三个符号中，提供了算法运行时间的一个上界。 3．设D n表示大小为n的输入集合，t(I)表示输入为I时算法的运算时间, p(I)表示输入 I 出现的概率，则算法的平均情况下时间复杂性A(n)= 。 4．分治算法的时间复杂性常常满足如下形式的递归方程： f (n) d , n n0 f(n) af(n/c) g(n) , n n0 其中，g(n)表示。 5. 分治算法的基本步骤包括。6．回溯算法的基本思想是。 7．动态规划和分治法在分解子问题方面的不同点是。 8．贪心算法中每次做出的贪心选择都是最优选择。 9．PQ 式的分支限界法中，对于活结点表中的结点，其下界函数值越小，优先级 10．选择排序、插入排序和归并排序算法中，算法是分治算法。 11．随机算法的一个基本特征是对于同一组输入，不同的运行可能得到的结果。12. 对于下面的确定性快速排序算法，只要在步骤3 前加入随机 化步骤，就可得到一个随机化快速排序算法，该随机化步骤的功能是。 算法QUICKSORT 输入：n 个元素的数组A[1..n] 。 输出：按非降序排列的数组 A 中的元素

1. quicksort(1, n) end QUICKSORT ＿ ＿ 过程 quicksort(A, low, high) ＿ ＿ // 对 A[low..high] 中的元素按非降序排序。 ＿ 号 学 2. if low

算法设计与分析试卷(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

算法设计心得体会(2)

算法设计心得体会 算法设计与分析学习心得 班级：物联网1201 姓名：刘潇学号：29 一、实验内容： 这学期的算法与设计课，老师布置了这四个问题，分别是货郎担问题，动态生成二维数组，对话框下拉列表，排序问题。 二、学习掌握： 基本程序描述： 货郎担问题：货郎担问题属于易于描述但难于解决的著名难题之一，至今世界上还有不少人在研究它。货郎担问题要从图g的所有周游路线中求取具有最小成本的周游路线，而由始点出发的周游路线一共有！条，即等于除始结点外的n一1个结点的排列数，因此货郎担问题是一个排列问题。货郎担的程序实现了利用穷举法解决货郎担问题，可以在城市个数和各地费用给定的情况下利用穷举法逐一计算出每一条路线的费用，并从中选出费用最小的路线。从而求出问题的解 费用矩阵：费用矩阵的主要内容是动态生成二维数组。首先由键盘输入自然数，费用矩阵的元素由随机数产生，并取整，把生成的矩阵存放在二维数组中，最后把矩阵内容输出到文件和屏幕上。它采用分支界限法，分支限界法的基本

思想是对包含具有约束条件的最优化问题的所有可行解的解空间进行搜索。该算法在具体执行时，把全部可行的解空间不断分割为越来越小的子集，并为每个子集内的解计算一个下界或上界。动态生成二维n*n的数组程序利用指针表示数组的行和列，并逐一分配空间，在输入n的数值后，系统自动分配空间，生成n*n的数组，并产生随机数填充数组，最后将结果输入到指定文件中。 Mfc：在下拉列表框中添加内容程序，在下拉列表对应的函数中利用addstring添加需要的内容。首先定义下拉列表框为ccombox型，并定义其属性名，利用addstring函数可以任意添加需要的内容。a排序问题:快速排序的运行时间与划分是否对称有关，其最坏情况发生在划分过程中产生的两个区域分别包含n-1个元素和1个元素的时候。其算法的时间复杂度为O(n 2),在最好的情况下每次划分的基准恰好为中值，可得其算法时间复杂度为O(n㏒n)。算法的实现和理解和代码实现完全是两回事，想要完全掌握一种算法，需要动手实践，用代码实现，才能理解透彻，真正掌握。b 对话框下拉列表：这个项目简单易懂，轻松实现。 三.疑问与总结： 货郎担的问题，我认为穷举法相对比而言是比较初级的方法，费时耗力，适合在练习时选用，但是在实际问题中不建议采用。克鲁斯卡尔或者普里姆算法求取最小生成树的方

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

湖南科技学院二○年学期期末考试 信息与计算科学专业年级《算法设计与分析》试题 考试类型:开卷试卷类型: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

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

算法分析与设计复习题及答案一、单选题 1．D 2．B 3．C 4．D 5．D 6．D 7．C 8．D 9．B 10．C 11．D 12．B 13．D 14．C 15．C 16．D 17．D 18．D 19．D 20．C 1．与算法英文单词algorithm具有相同来源的单词是（）。 A logarithm B algiros C arithmos D algebra 2．根据执行算法的计算机指令体系结构，算法可以分为（）。 Ａ精确算法与近似算法Ｂ串行算法语并行算法 Ｃ稳定算法与不稳定算法Ｄ３２位算法与６４位算法 3．具有１0个节点的完全二叉树的高度是（）。 Ａ６Ｂ５Ｃ3Ｄ 2 4．下列函数关系随着输入量增大增加最快的是（）。 Ａlog2n B n2 C 2n D n! 5．下列程序段的S执行的次数为( )。 for i ←0 to n-1 do for j ←0 to i-1 do s //某种基本操作 A.n2 B n2/2 C n*(n+1) D n(n+1)/2 6．Fibonacci数列的第十项为( )。 A 3 B 13 C 21 D 34 7．4个盘子的汉诺塔，至少要执行移动操作的次数为( )。 A 11次 B 13次 C 15次 D 17次 8．下列序列不是堆的是（）。 A 99，85，98，77，80，60，82，40，22，10，66 B 99，98，85，82，80，77，66，60，40，22，10 C 10，22，40，60，66，77，80，82，85，98，99 D 99，85，40，77，80，60，66，98，82，10，22 9．Strassen矩阵乘法的算法复杂度为（）。 ＡΘ(n3)ＢΘ(n2.807) ＣΘ(n2) ＤΘ(n) 10．集合A的幂集是（）。 A．A中所有元素的集合 B. A的子集合 C． A 的所有子集合的集合 D. 空集 11．与算法英文单词algorithm具有相同来源的单词是（）。 A logarithm B algiros C arithmos D algebra 12．从排序过程是否完全在内存中显示，排序问题可以分为（）。 Ａ稳定排序与不稳定排序Ｂ内排序与外排序 Ｃ直接排序与间接排序Ｄ主排序与辅助排序 13．下列（）不是衡量算法的标准。 Ａ时间效率Ｂ空间效率 Ｃ问题难度Ｄ适应能力 14．对于根树，出度为零的节点为（）。 Ａ０节点Ｂ根节点Ｃ叶节点Ｄ分支节点 15．对完全二叉树自顶向下，从左向右给节点编号，节点编号为１0的父节点编号为（）。 Ａ０Ｂ２Ｃ４Ｄ６ 16．下列程序段的算法时间的复杂度为（）。 for i ←0 to n do for j ←0 to m do

算法设计与分析基础课后习题答案

Program算法设计与分析基础中文版答案 习题 5..证明等式gcd(m,n)=gcd(n,m mod n)对每一对正整数m,n都成立. Hint: 根据除法的定义不难证明: 如果d整除u和v, 那么d一定能整除u±v; 如果d整除u,那么d也能够整除u的任何整数倍ku. 对于任意一对正整数m,n,若d能整除m和n,那么d一定能整除n和r=m mod n=m-qn；显然，若d能整除n和r，也一定能整除m=r+qn和n。 数对(m,n)和(n,r)具有相同的公约数的有限非空集，其中也包括了最大公约数。故gcd(m,n)=gcd(n,r) 6.对于第一个数小于第二个数的一对数字,欧几里得算法将会如何处理?该算法在处理这种输入的过程中,上述情况最多会发生几次? Hint: 对于任何形如0<=m

设sqrt(x)是求平方根的函数) 算法Quadratic(a,b,c) 描述将十进制整数表达为二进制整数的标准算法 a.用文字描述 b.用伪代码描述 解答： a.将十进制整数转换为二进制整数的算法 输入：一个正整数n 输出：正整数n相应的二进制数 第一步：用n除以2，余数赋给Ki(i=0,1,2...)，商赋给n 第二步：如果n=0，则到第三步，否则重复第一步 第三步：将Ki按照i从高到低的顺序输出 b.伪代码 算法 DectoBin(n) .n]中 i=1 while n!=0 do { Bin[i]=n%2; n=(int)n/2; i++; } while i!=0 do{ print Bin[i]; i--; } 9.考虑下面这个算法,它求的是数组中大小相差最小的两个元素的差.(算法略)对这个算法做尽可能多的改进. 算法 MinDistance(A[0..n-1])

算法设计与分析学习总结

算法分析与设计 学习总结 题目:算法分析与设计学习总结 学院信息科学与工程学院专业2013级计算机应用技术 届次 学生姓名 学号2０１31１0６57 二○一三年一月十五日

算法分析与设计学习总结 本学期通过学习算法分析与设计课程，了解到:算法是一系列解决问题的清晰指令,代表着用系统的方法描述解决问题的策略机制。算法能够对一定规范的输入,在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合某个问题,执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂性和时间复杂度来衡量。算法可以使用自然语言、伪代码、流程图等多种不同的方法来描述。计算机系统中的操作系统、语言编译系统、数据库管理系统以及各种各样的计算机应用系统中的软件，都必须使用具体的算法来实现。算法设计与分析是计算机科学与技术的一个核心问题。 设计的算法要具有以下的特征才能有效的完成设计要求，算法的特征有：（1）有穷性。算法在执行有限步后必须终止。(2)确定性。算法的每一个步骤必须有确切的定义。(3)输入。一个算法有0个或多个输入,作为算法开始执行前的初始值，或初始状态。(4）输出。一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的。 (5)可行性。在有限时间内完成计算过程。 算法设计的整个过程,可以包含对问题需求的说明、数学模型的拟制、算法的详细设计、算法的正确性验证、算法的实现、算法分析、程序测试和文档资料的编制。算法可大致分为基本算法、数据结构的算法、数论与代数算法、计算几何的算法、图论的算法、动态规划以及数值分析、加密算法、排序算法、检索算法和并行算法。 经典的算法主要有: 1、穷举搜索法 穷举搜索法是对可能是解的众多候选解按某种顺序进行逐一枚举和检验，bing从中找出那些符合要求的候选解作为问题的解。 穷举算法特点是算法简单，但运行时所花费的时间量大。有些问题所列举书来的情况数目会大得惊人，就是用高速计算机运行,其等待运行结果的时间也将使人无法忍受。我们在用穷举算法解决问题是，应尽可能将明显不符合条件的情况排除在外，以尽快取得问题的解。 2、迭代算法 迭代法是数值分析中通过从一个初始估计出发寻找一系列近似解来解决问题（一般是解方程或方程组)的过程，为实现这一过程所使用的方法统称为迭代法。迭代法是用于求方程或方程组近似根的一种常用的算法设计方法。设方程为ｆ(ｘ)=0,用某种数学方法导出等价的形式x=g(x),然后按以下步骤执行： （1）选一个方程的近似根，赋给变量x0。 (2)将ｘ0的值保存于变量x1，然后计算g(x1),并将结果存于变量x0。 (3）当x0与x1的差的绝对值还小于指定的精度要求时，重复步骤（２）的计算。 若方程有根，并且用上述方法计算出来的近似根序列收敛,则按上述方法求得的x0就认为是方程的根。 3、递推算法 递推算法是利用问题本身所具有的一种递推关系求问题解的一种方法。它把问题分成若干步，找出相邻几步的关系,从而达到目的。 4、递归算法 递归算法是一种直接或间接的调用自身的算法。 能采用递归描述的算法通常有这样的特征：为求解规模为ｎ的问题，设法将它分解成规模较小的问题，然后从这些小问题的解方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法,分解成规模更小的问题,并从这些更小问题的解构造出规模

《算法分析与设计》期末试题及参考答案

《算法分析与设计》期末试题及参考答案 一、简要回答下列问题： 1.算法重要特性是什么？ 1.确定性、可行性、输入、输出、有穷性 2. 2.算法分析的目的是什么？ 2.分析算法占用计算机资源的情况，对算法做出比较和评价，设计出额更好的算法。 3. 3.算法的时间复杂性与问题的什么因素相关？ 3. 算法的时间复杂性与问题的规模相关，是问题大小n的函数。 4.算法的渐进时间复杂性的含义？ 4．当问题的规模n趋向无穷大时，影响算法效率的重要因素是T(n)的数量级，而其他因素仅是使时间复杂度相差常数倍，因此可以用T(n)的数量级(阶)评价算法。时间复杂度T(n)的数量级(阶)称为渐进时间复杂性。 5.最坏情况下的时间复杂性和平均时间复杂性有什么不同？ 5. 最坏情况下的时间复杂性和平均时间复杂性考察的是n固定时，不同输入实例下的 算法所耗时间。最坏情况下的时间复杂性取的输入实例中最大的时间复杂度： W(n) = max{ T(n，I) } , I∈Dn 平均时间复杂性是所有输入实例的处理时间与各自概率的乘积和： A(n) =∑P(I)T(n，I) I∈Dn 6.简述二分检索（折半查找）算法的基本过程。 6. 设输入是一个按非降次序排列的元素表A[i：j] 和x，选取A[(i+j)/2]与x比较， 如果A[(i+j)/2]=x，则返回(i+j)/2，如果A[(i+j)/2]

《算法分析与设计》课程教学大纲概要

一． 《算法分析与设计》课程教学大纲 Algorithms Analysis and Design 课程教学目标： 1．任务和地位： 《算法分析与设计》是计算机应用与技术专业（本科）的一门专业课，其内容是研究计算机领域及其它有关领域中的一些常用算法，它是计算机科学通常要解决的主要问题之一，因而也是各专业方向可以选修的一门重要的专业基础课。 通过本课程的学习，使学生掌握算法设计的常用方法，以便运用这些方法来设计解决一些常用的或较为复杂的实际问题的算法，并力争做到快捷、有效，从而提高程序设计的质量。除此，还要使学生学会分析算法、估计算法的时空复杂性，以便理解并科学评估有关算法。因而，对于计算机专业的技术人员，学习和掌握这方面的知识是很有必要的。 2．知识要求：通过一学期学习要达到如下要求 1)掌握算法的定义及基本概念、计算模型和复杂度的质量； 2)为分析算法的复杂性作准备，要了解相应的数学知识； 3)了解各种分类方法，重点是学会分析分类方法的复杂性。 3．能力要求： 通过本课程的学习，学生要掌握几种常用的算法设计策略，包括递归与分治策略、动态规划算法、贪心算法、回溯法和分支限界法等，并会分析算法的效率。能够 用所学方法解决实际问题。 二、教学内容的基本要求和学时分配 1

2．具体要求 第一章算法概述 [目的要求] 掌握算法基本概念及算法复杂性分析。 [教学内容] 算法与程序、算法复杂性分析。 [重点难点] 让同学们了解本门学科在科技发展中地位和作用，增强学好本课程的信心。 [教学方法] 课堂讲授与自学（课外）相结合。 [课时] 3 学时。 第二章递归与分治策略 [目的要求] 掌握递归与分治策略设计算法。 [教学内容] 递归的概念、分治法的基本思想、及分治算法实例。 [重点难点] 分治法的基本思想的具体实现及时间复杂度分析。 [教学方法] 课堂讲授与自学结合。 [课时] 14 学时。 第三章动态规划 [目的要求] 掌握用动态规划法设计算法。 [教学内容] 动态规划算法的基本要素、基本思想及算法实例。 [重点难点] 动态规划算法基本思想的具体实现及时间复杂度分析。 [教学方法] 课堂讲授与自学结合。 [课时] 9 学时。 第四章贪心算法 [目的要求] 掌握用贪心算法设计算法。 [教学内容] 贪心算法的基本要素、基本思想及算法实例。 [重点难点] 贪心算法基本思想的具体实现及时间复杂度分析。 [教学方法] 课堂讲授与自学结合。 [课时] 6 学时。 第五章回溯法 [目的要求] 掌握回溯法算法的基本模式。 [教学内容] 回溯法的算法框架及算法实例。 [重点难点] 算法框架的具体应用。 [教学方法] 课堂讲授与自学结合。 [课时] 11 学时。 第六章分支限界法[目的 要求] 了解分支限界法

《算法分析与设计》期末复习题

一、选择题 1．一个.java文件中可以有（）个public类。 A．一个B．两个C．多个D．零个 2．一个算法应该是（） A．程序B．问题求解步骤的描述 C．要满足五个基本特性D．A和C 3．用计算机无法解决“打印所有素数”的问题，其原因是解决该问题的算法违背了算法特征中的（）A．唯一性B．有穷性C．有0个或多个输入D．有输出 4．某校有6位学生参加学生会主席竞选，得票数依次为130，20，98，15，67，3。若采用冒泡排序算法对其进行排序，则完成第二遍时的结果是（） A．3，15，130，20，98，67B．3，15，20，130，98，67 C．3，15，20，67，130，98 D．3，15，20，67，98，130 5．下列关于算法的描述，正确的是（） A．一个算法的执行步骤可以是无限的B．一个完整的算法必须有输出 C．算法只能用流程图表示D．一个完整的算法至少有一个输入 6．Java Application源程序的主类是指包含有（）方法的类。 A、main方法 B、toString方法 C、init方法 D、actionPerfromed方法 7．找出满足各位数字之和等于5的所有三位数可采用的算法思路是（） A．分治法B．减治法C．蛮力法D．变治法 8．在编写Java Application程序时，若需要使用到标准输入输出语句，必须在程序的开头写上( )语句。 A、import java.awt.* ; B、import java.applet.Applet ; C、import java.io.* ; D、import java.awt.Graphics ; 9．计算某球队平均年龄的部分算法流程图如图所示，其中：c用来记录已输入球员的人数，sum用来计算有效数据之和，d用来存储从键盘输入的球员年龄值，输入0时表示输入结束。