算法设计与分析期末试卷

华南农业大学期末考试试卷（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）在最

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

2012学年第1学期 考试科目： 算法设计与分析 考试类型：（闭卷）考试 考试时间： 120 分钟

学号 姓名 年级专业

题号

装

一(20)

二(25)

三(16)

四(24)

五(15)

总分

得分 评阅人

订

说明：

（1）请勿漏填学号姓名等信息。本试卷仅一份，请将答案直接填于试卷上，莫将试卷当草稿，想好了再写，若空白的位置不够，标注清楚后可以写反面；

（2）答题时，对算法的描述可以采用文字、公式、图、伪代码、实例说明等混合形式。请注意表达应条理清晰，思想简洁，勿长篇累述不得要领。

得分

线

一、填空题（1~3题每空1分，第4题每空2分，共20分，结果直接填于划线处） 1、化简下面f(n)函数的渐进上界表达式。（5分） f1(n) n2/2 3n， 则O(f1(n)) O(_____________) f2(n) 2n 3，

f3(n) logn3，

则O(f2(n)) O(_____________) 则O(f3(n)) O(_____________) 则O(f4(n)) O(_____________) 则O(f5(n))

算法设计与分析试卷(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．串行算法经适当的改造有些可

复习

一、简答题（每小题5分，选答2题，共10分）

1. 什么是算法？试说明算法设计分析过程的一般框架和主要步骤。 2. 简述非递归算法时间效率分析的通用方案。 3. 简述递归算法时间效率的通用方案。

4. 简述蛮力法、分治法、减治法，变治法、时空权衡、动态规划、贪婪技术、迭代改进八种算法设计技术中至少三种技术基本思想或原理。

二、分析题（每小题10分，共20分） 1. 考虑下面的算法。P52

算法 Mystery(n) //输入：非负整数n

S=0

for i ? 1 to n do

S ? S + i*i Return S

a. 该算法求的是什么？ b. 它的基本操作是什么？ c. 该基本操作执行了多少次？ d. 该算法的效率类型是什么？

2. 考虑下面的递归算法。P52

算法 Secret(A[0..n-1]) //输入：包含n个实数的数组A[0..n-1] minval ? A[0]; maxval ? A[0] for i ?1 to n-1 do if A[i] < minval minval ? A[i] if A[i] > maxval maxval ? A[i] re

复习

一、简答题（每小题5分，选答2题，共10分）

1. 什么是算法？试说明算法设计分析过程的一般框架和主要步骤。 2. 简述非递归算法时间效率分析的通用方案。 3. 简述递归算法时间效率的通用方案。

4. 简述蛮力法、分治法、减治法，变治法、时空权衡、动态规划、贪婪技术、迭代改进八种算法设计技术中至少三种技术基本思想或原理。

二、分析题（每小题10分，共20分） 1. 考虑下面的算法。P52

算法 Mystery(n) //输入：非负整数n

S=0

for i ? 1 to n do

S ? S + i*i Return S

a. 该算法求的是什么？ b. 它的基本操作是什么？ c. 该基本操作执行了多少次？ d. 该算法的效率类型是什么？

2. 考虑下面的递归算法。P52

算法 Secret(A[0..n-1]) //输入：包含n个实数的数组A[0..n-1] minval ? A[0]; maxval ? A[0] for i ?1 to n-1 do if A[i] < minval minval ? A[i] if A[i] > maxval maxval ? A[i] re

2014-2015年度第一学期

12级_ 网页设计与制作 课程期末试卷

一、判断题（15分）

（ ）1、在一个WEB站点中，主页就是网页，两者是一致的。 （ ）2、表格是一种Web页面布局的常用方法。

（ ）3、网站的多个网页有相同的头部和脚注，可以利用库实现。（ ）4、一般来说，整个站点就是一个大的文件夹。

（ ）5、CSS样式表可以从外部导入，通过链接的形式，使用样式定义。

（ ）6、动态网页就是网页中有许多多媒体元素和一些动的效果，使用户感觉页面非常有活力。

（ ）7、站点中的文件夹可以使用中文名称。

（ ）8、框架网页能够在窗口的不同框架内打开链接的目标文件。 （ ）9、框架的不同区域可以显示不同的网页。

（ ）10、CSS样式，只能通过外部导入，并链接到网页，网页才能有效果。

（ ）11、在网页制作中，我们经常用表单办法进行页面布 （ ）12、在IE浏览器中预览网页的快捷键是F10 （ ）13、添加背景音乐的HTML标签是。 （ ）

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

《算法设计与分析》试卷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、? 记号在算法复杂性的表示法中表示 紧致界