算法设计与分析试卷 小说

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

一、 选择题 （ 选择1-4个正确的答案, 每题2分，共20分）

（1）计算机算法的正确描述是： B、D

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

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

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

D．一个算法，它是满足5 个特性的程序，这5个特性是：有限性、确定性、能 行性、有0个或多个输入且有1个或多个输出。 （2）影响程序执行时间的因素有哪些？ C、D

A．算法设计的策略 B．问题的规模

C．编译程序产生的机器代码质量 D．计算机执行指令的速度 （3）用数量级形式表示的算法执行时间称为算法的 A

A．时间复杂度 B．空间复杂度 C．处理器复杂度 D．通信复杂度 （4）时间复杂性为多项式界的算法有：

A．快速排序算法 B．n-后问题 C．计算?值 D．prim算法 （5）对于并行算法与串行算法的关系，正确的理解是：

A．高效的串行算法不一定是能导出高效的并行算法 B．高效的串行算法不一定隐含并行性

C．串行算法经适当的改造有些可

算法设计与分析考试复习试卷

《算法设计与分析》试卷1

一、多项选择题（每空2分，共20分）：

1、以下关于算法设计问题的叙述中正确的是__________。

A、计算机与数值问题的求解——方程式求根、插值问题、数值积分、函数逼近等有关

B、利用计算机无法解决非数值问题

C、计算机在解决分类、语言翻译、图形识别、解决高等代数和组合分析等方面的数学问题、定理证明、公式推导乃至日常生活中各种过程的模拟等问题中，主要进行的是判断、比较，而不是算术运算

D、算法设计与分析主要研究对象是非数值问题，当然也包含某些数值问题

2、算法的特征包括_________。

A、有穷性 B、确定性

C、输入和输出 D、能行性或可行性

3、以下描述是有关算法设计的基本步骤：

①问题的陈述 ②算法分析 ③模型的拟制 ④算法的实现

⑤算法的详细设计 ⑥文档的编制，应与其它环节交织在一起

其中正确的顺序是__________。

A、①②③④⑤⑥ B、①③⑤②④⑥

C、②④①③⑤⑥ D、⑥①③⑤②④

4、以下说法正确的是__________。

A、数学归纳法可以证明算法终止性

B、良序原则是证明算法的正确性的有力工具

C、x = 小于或等于x的最大整数（x的低限）

D、x =

算法设计与分析考试复习试卷

《算法设计与分析》试卷1

一、多项选择题（每空2分，共20分）：

1、以下关于算法设计问题的叙述中正确的是__________。

A、计算机与数值问题的求解——方程式求根、插值问题、数值积分、函数逼近等有关

B、利用计算机无法解决非数值问题

C、计算机在解决分类、语言翻译、图形识别、解决高等代数和组合分析等方面的数学问题、定理证明、公式推导乃至日常生活中各种过程的模拟等问题中，主要进行的是判断、比较，而不是算术运算

D、算法设计与分析主要研究对象是非数值问题，当然也包含某些数值问题

2、算法的特征包括_________。

A、有穷性 B、确定性

C、输入和输出 D、能行性或可行性

3、以下描述是有关算法设计的基本步骤：

①问题的陈述 ②算法分析 ③模型的拟制 ④算法的实现

⑤算法的详细设计 ⑥文档的编制，应与其它环节交织在一起

其中正确的顺序是__________。

A、①②③④⑤⑥ B、①③⑤②④⑥

C、②④①③⑤⑥ D、⑥①③⑤②④

4、以下说法正确的是__________。

A、数学归纳法可以证明算法终止性

B、良序原则是证明算法的正确性的有力工具

C、x = 小于或等于x的最大整数（x的低限）

D、x =

算法设计与分析

1、(1) 证明：O(f)+O(g)=O(f+g)（7分） (2) 求下列函数的渐近表达式：（6分） ① 3n2+10n; ② 21+1/n;

2、对于下列各组函数f(n)和g(n)，确定f(n)=O(g(n))或f(n)=Ω(g(n))或f(n)=θ(g(n))，并简述理由。（15分）

2f(n)?logn;g(n)?logn?5; (1)

2f(n)?logn;g(n)?n; (2)

2f(n)?n;g(n)?logn; (3)

3、试用分治法对数组A[n]实现快速排序。（13分） 4、试用动态规划算法实现最长公共子序列问题。（15分）

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

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

(1)删除一个字符。 (2)插入一个字符。

(3)将一个字符改为另一个字符。

将字符串A变换为字符串B所用的最少字符操作数称为字符串A到B的编辑距离，记为d(A,B)。试设计一个有效算法，对任给的两个

考试课程： 班级： 姓名： 学号： 算法分析考试试卷（A卷） ------------------------------------------------- 密 ---------------------------------- 封 ----------------------------- 线 --------------------------------------------------------- 课程名称 算法分析 编号 题号 得分 评阅人 一 二 三 四 总分 一、填空题（每小题3分，共30分） 1、一个算法的优劣可以用 空间复杂度 与 时间复杂度 来衡量。 2、这种不断回头寻找目标的方法称为 回溯法 。 3、直接或间接地调用自身的算法称为 递归算法 。 4、? 记号在算法复杂性的表示法中表示 紧致界

&

湖南科技学院二○ 年 学期期末考试

信息与计算科学专业 年级《算法设计与分析》 试题

考试类型：开卷 试卷类型：C 卷 考试时量：120 分钟

1. 用O 、Ω和θ表示函数f 与g 之间的关系______________________________。

()()log log f n n n g n n ==

2. 算法的时间复杂性为1,

1()8(3/7),

2

n f n f n n n =?=?

+≥?，则算法的时间复杂性的阶

为__________________________。

3. 快速排序算法的性能取决于______________________________。

4. 算法是_______________________________________________________。

5. 在对问题的解空间树进行搜索的方法中，一个活结点最多有一次机会成为活结点的

是_________________________。

"

6. 在算法的三种情况下的复杂性中，可操作性最好且最有实际价值的是_____情况下的时间复杂性。

7. 大Ω符号用来描述增长率的下限，这个下限的阶越___________，结果就越有价值。。 8. __

第1章 绪 论

算法理论研究的是算法的设计技术和算法的分析技术，前者是指面对一个问题，如何设计一个有效的算法，后者则是对已设计的算法，如何评价或判断其优劣。二者是相互依存的，设计出的算法需要检验和评价，对算法的分析反过来又将改进算法的设计。

1.1 算法的基本概念

算法的概念在计算机科学领域几乎无处不在，在各种计算机软件系统的实现中，算法设计往往处于核心地位。例如，操作系统是现代计算机系统中不可缺少的系统软件，操作系统的各个任务都是一个单独的问题，每个问题由操作系统中的一个子程序根据特定的算法来实现。用什么方法来设计算法，如何判定一个算法的优劣，所设计的算法需要占用多少时间资源和空间资源，在实现一个软件系统时，都是必须予以解决的重要问题。

1.1.1 为什么要学习算法

用计算机求解任何问题都离不开程序设计，而程序设计的核心是算法设计。一般来说，对程序设计的研究可以分为四个层次：算法、方法学、语言和工具，其中算法研究位于最高层次。算法对程序设计的指导可以延续几年甚至几十年，它不依赖于方法学、语言和工具的发展与变化。例如，用于数据存储和检索的Hash算法产生于20世纪50年代，用于排序的快速排序算法发明于20世纪60年代，但他们至今仍被人

一 填空题

1. 一个计算机算法的指令序列需要满足性质的是输入、输出、确定性、有限性。

输入、输出、确定性、有限性

2.9n?10n的渐近表达式是 O(n)

22

3 . 下面程序段的时间复杂度是 O(n)

for (i=0; i

for (j=0; j

4．求两个n阶矩形的乘法C=A*B,其算法如下：

#define MAX 100

voidmaxtrixmult( int n, float a[MAX][MAX], float c[MAX][MAX]) { int i, j, k; float x; for( i=1; i<=n; i++)8 { for( j=1; j<=n; j++)

{ x=0;

for( k=1; k<=n; k++) x+=a[i][k]*b[k][j];

c[i][j]=x;

}

}

} 该算法的时间复杂度为 O(n)

5．通常用来表示时间算法的有以下六种多项式：

3

2

6．快速排序算法是基于分治策略的一个算法。其基本思想是，对于输入的子数组a[p:r],按以下3个步骤进行排序： 分解、递归求解、合并。

7. 合并排序算法的基本思想是 将待排序的元素分成大小大致相等的2个子集合，分别对两个子集合排序，最终将排好序的子集合合并成为所要求的集合。

华南农业大学期末考试试卷（A卷）

2004学年第二学期(2005.6) 考试科目： 算法设计与分析 考试类型：（开卷） 考试时间： 120 分钟

学号 姓名 年级专业 题号 得分 评阅人 一 二 三 四 总分 一、选择题（30分，每题2分）

1、一个算法应该包含如下几条性质，除了 A 。

（A）二义性 （B）有限性 （C） 正确性

（D）可终止性

2、解决一个问题通常有多种方法。若说一个算法“有效”是指 D 。 （A）这个算法能在一定的时间和空间资源限制内将问题解决 （B）这个算法能在人的反应时间内将问题解决 （C）这个算法比其他已知算法都更快地将问题解决 （D）A和C

3、当输入规模为n时，算法增长率最小的是 B 。 （A）5n （B）20log2n （C）2n2 （D）3nlog3n

4、渐进算法分析是指 B 。

（A）算法在最佳情况、最差情况和平均情况下的代价

（B）当规模逐步往极限方向增大时，对算法资源开销“增长率”上的简化分析 （C）数据结构所占用的空间

（D）在最

最接近点对问题

问题

此问题分为一维，二维，三维的情况

1. 一维: 给定直线上n个点，找其中一对点，使得在n个点组成的所有点对中，该点对间

的距离最小，这个问题比较简单，是引出二维解法的一个引子，因为一维的直线上的点，相邻点的距离肯定小于相隔的点的距离，只需要考虑相邻点即可。

2. 二维：给定平面上n个点，找其中一对点，使得在n个点组成的所有点对中，该点对间

的距离最小，这是我们这一问题的重点

3. 三维：给定空间上n个点，找其中一对点，使得在n个点组成的所有点对中，该点对间

的距离最小，此问题是二维的解法的复杂化，具体可以在飞机航线等问题上运用，但在此不多做介绍。

基本思想

由于该问题的基本解法是去考察每个点和其他所有点的距离。因此它的时间复杂度是

O(n2),这样做的效率太低，我们就要去寻找一个更高效的办法：分治法。

1. 因二维的情况太过复杂，先考虑一维的情况中，可以用分治法对其进行分部计算： 把直线分成两部分, s1s2,分别求出其最接近点的距离d1 d2。但分割开的地方的两点距离可能小于这两个值，这三个值进行比较之后，得到最后结果。 2. 鉴于此，二维的也可以用此方法进行计算：

把待计算的点s分成两部分s1 s2，分别求出其最接近点