算法分析与设计期末试题

复习

一、简答题（每小题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

诚信 保证

本人知晓我校考场规则和违纪处分条例的有关规定，保证遵守考场规则，诚实做人。本人签名： 班 级 ： 学 号 ： 装 订 姓 名 ： 线

编号： 西北工业大学考试试题（卷） 20 －20 学年第 学期 成 绩 开课学院 课程 学时 开A考试日期 考试时间 小时 考试形式()()卷 闭B一、简答题（除第2题外每小题9分共55分） 1． 请阐述算法的基本概念、特征，及其与程序的区别和联系。 2． 什么是算法的复杂性? 如何度量？什么是算法渐进性态的阶？ 试估计如下二重循环算法在最坏情况下时间复杂性T(n)的阶.（10分） for i:= 1 to n do for j:=1 to i do { s1, s2, s3, s4 } ; s1,s2,s3,s4为单一赋值语句 3．简述动态规

第 1 页 （共 4 页） 算法分析与设计期末考试模拟试题一

课程名称：__ 算法分析与设计 考试形式： 闭 卷

学习中心：_________ 考试时间： 90分钟

姓 名：_____________ 学 号：

一、填空题（每小题4分，共计40分）

1. 通常只考虑三种情况下的时间复杂度，即 情况、

情况和 情况下的时间复杂度，分别记为T max (N)、T min

(N) 和T avg (N)，实践表明可操作性最好且最有实际价值的是 情况下的时间复杂度。

2. n n 1032 的渐近表达式是 ，

)log(3n 的渐近表达式是 。

3. 根据符号O 的定义易知O(1)=O(2)，用O(1)和O(2)表示同一个方法

时，差别仅在于其中的 。

4. 递归算法是指 的算法，递归函数

是指

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

1． 算法有哪些特点？为什么说一个具备了所有特征的算法，不一定就是使用的算法?

2． 证明下面的关系成立：(参考例题1.5--1.6)

（1）logn!=Θ(nlogn) (2)2n=Θ(2n+1)

(3)n!= Θ(nn) (4)5n2-6n=Θ(n2)

1

3.考虑下面的算法：

输入：n个元素的数组A

输出：按递增顺序排序的数组A

1. void sort(int A[],int n) 2. { 3. int i,j,temp; 4. for(i=0;i

（1） 什么时候算法所执行的元素赋值的次数最少？最少多少次？

（2） 什么时候算法所执行的元素赋值的次数最多？最多多少次？

4.考虑下面的算法：

输入：n个元素的数组A

输出：按递增顺序排序的数组A

1. void bubblesort(int A[],int n) 2. { 3. int j,i,sorted; 4. i=sorted=0; 5. while(ii;j--)

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

1． 算法有哪些特点？为什么说一个具备了所有特征的算法，不一定就是使用的算法?

2． 证明下面的关系成立：(参考例题1.5--1.6)

（1）logn!=Θ(nlogn) (2)2n=Θ(2n+1)

(3)n!= Θ(nn) (4)5n2-6n=Θ(n2)

1

3.考虑下面的算法：

输入：n个元素的数组A

输出：按递增顺序排序的数组A

1. void sort(int A[],int n) 2. { 3. int i,j,temp; 4. for(i=0;i

（1） 什么时候算法所执行的元素赋值的次数最少？最少多少次？

（2） 什么时候算法所执行的元素赋值的次数最多？最多多少次？

4.考虑下面的算法：

输入：n个元素的数组A

输出：按递增顺序排序的数组A

1. void bubblesort(int A[],int n) 2. { 3. int j,i,sorted; 4. i=sorted=0; 5. while(ii;j--)

1． 按分治策略求解棋盘覆盖问题时，对于如图所示的24×24的特殊棋盘，共需要多少个L型骨

牌；并在棋盘上填写L型骨牌的覆盖情况。

2． 假设有7个物品，给出重量和价值。若这些物品均不能被分割，且背包容量M＝140，使用回

溯方法求解此0-1背包问题。请画出状态空间搜索树。

3． 假设有7个物品，它们的重量和价值如下表所示。若这些物品均可以被分割，且背包容量M

＝140，使用贪心算法求解此背包问题。请写出求解策略和求解过程。 W（35,30,50,60,40,10,25）p（10,40,30,50,35,40,30）

4． 在给出的电路板中，阴影部分是已作了封锁标记的方格，请按照队列式分支限界法在图中确定

a到b的最短布线方案，要求布线时只能沿直线或直角进行，在图中标出求得最优解时各方格情况。

5． 画出字符表的哈夫曼编码对应的二叉树。

6． 已知Ak?(aij(k))ri*ri?1，k=1，2，3，4，5，6，r1=5，r2=10，r3=3，r4=8，r5=5，r6=20，r7=6，求

矩阵链积A1×A2×A3×A4×A5×A6的最佳求积顺序。

7． 给出城市网络图，售货员要从城市1出发，经过所有城市回到城市1，画出该问题的解空间树，

描述出用优先队列

第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）在最