自考 算法设计 试卷

算法设计与分析试卷A卷-20080525-参考答案-第二版-by zzm （含试题预测、课堂笔记）

试题答案：

一、简答题

1. 答：如果一个算法不需要额外的存储空间（除个别存储单元以外），我们把它称为是在

位的。 2. 答：如下图，求A到C的最短距离。Dijkstra算法只需一步，就计算出A到C最短路径

为A-C，长度为3；事实上，图中因为存在负权重的边，A到C的最短路径应是A-B-C，

长度为2。

A 3 C 4 B -2

3. 答：对问题的部分或全部输入做预处理，然后对获得的额外信息进行存储，以加速后面

问题的求解。我们把这个方法称为输入增强。

二、答： 解法一：

Mindist (A[0..n-1]) dist ← ∞

for i ← 0 to n-2 do for j ← i+1 to n-1 do if │A[i]-A[j]│

Mindist (A[0..n-1])

将数组A复制到数组B；

用O(nlog n)的排序算法对Ｂ进行升序排序； dist ← B[1]-B[0];

dist ← │A[i]-A[j]│

for i ← 1 to

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

全国2011年10月 一、单项选择题

1．荷载效应的标准组合适用于结构裂缝控制验算。

2.我国《建筑结构可靠度设计统一标准》规定，普通房屋和构筑物的设计使用年限为50年。 3.关于地震，下列说法中正确的是一次地震有一个震级和多个地震烈度。

4.抗震设计时，框架结构的“强柱弱梁”要求是梁柱节点处柱的总弯曲承载能力不低于梁的总弯曲承载能力。 5.地震时使用功能不能中断的建筑，其抗震设防类别为乙类建筑。 6.与结构自振周期有关的因素是结构自身的刚度与质量。 7.地震时，造成建筑物和地表破坏的地震波主要是面波 。

8.在罕遇地震作用下，框架结构抗震变形验算公式Δup≤[θp]h中，[θp]为层间弹塑性位移角限值，取1／50。

9.关于框架梁弯矩调幅，下列说法中正确的是弯矩调幅仅在竖向荷载作用下进行、弯矩调幅后，梁支座弯矩将减小、弯矩调幅后，梁跨中弯矩将增加、弯矩调幅系数β≤1.0。

10.水平荷载作用下，多层框架结构的侧移主要由梁、柱弯曲变形引起。 11.用D值法分析框架结构时，柱的反弯点高度与抗震设防烈度无关。

12.关于框架梁截面的最不利内力组合，下列选项正确的是梁端截面：+Mmax、Vmax 。

13.对于需要考虑风振的高层建筑，其他条件不

《算法分析与设计》2012-2013-2学期期中测试（信息安全专业DQ教学班）

姓名：学号：得分：

1. 证明O?f?n???O?g?n???O?f?n??g?n??。（10分）

证明：对于任意f1(n) ?O(f(n))，存在正常数c1和自然数n1，使得对所有n?n1，有f1(n) ?c1f(n)成立。 类似，对于任意g1(n) ?O(g(n))，存在正常数c2和自然数n2，使得对所有n?n2，有g1(n) ?c2g(n)成立。 令c3=max{c1, c2}，n3 =max{n1, n2}，则对所有的n ?n3，有 f1(n) +g1(n) ?c1f(n) + c2g(n) ?c3f(n) + c3g(n) = c3(f(n) + g(n))

即O?f?n???O?g?n???O?f?n??g?n??成立。

2. 将下列5个函数按渐近增长率由低至高进行排序，要求写出比较过程。（15分）

f1(n)?n(logn)n,??f2(n)?logn100logn,??f3(n)?n2logn,??f4(n)?2logn?loglogn,??f5(n)?10n

解：f2(n)?logn100logn?100log2n,??f4(n)?2log

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