大学算法设计与分析期末试题

复习

一、简答题（每小题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章 绪论 考点：

1、算法的5个重要特性。（P3）

答：输入、输出、有穷性、确定性、可行性

2、 描述算法的四种方法分别是什么，有什么优缺点。（P4） 答：

1.自然语言 优点：容易理解；缺点：容易出现二义性，并且算法都很冗长。 2.流程图 优点：直观易懂；缺点：严密性不如程序语言，灵活性不如自然语言。 3.程序设计语言 优点：用程序语言描述的算法能由计算机直接执行；缺点：抽象性差，是算法设计者拘泥于描述算法的具体细节，忽略了“好”算法和正确逻辑的重要性，此外，还要求算法设计者掌握程序设计语言及其编程技巧。 4.伪代码 优点：表达能力强，抽象性强，容易理解

3、了解非递归算法的时间复杂性分析。(P13)

要点：对非递归算法时间复杂性的分析，关键是建立一个代表算法运行时间的求和表达式，然后用渐进符号表示这个求和表达式。 非递归算法分析的一般步骤是：

（1）决定用哪个（或哪些）参数作为算法问题规模的度量。 （2）找出算法的基本语句。

（3）检查基本语句的执行次数是否只依赖问题规模。 （4）建立基本语句执行次数的求和表达式。 （5）用渐进符号表示这个求和表达式。

[例1.4]：求数组最小值算法 in

大学算法分析与设计复习总结

第1章 绪论 考点：

1、算法的5个重要特性。（P3）

答：输入、输出、有穷性、确定性、可行性

2、 描述算法的四种方法分别是什么，有什么优缺点。（P4） 答：

1.自然语言 优点：容易理解；缺点：容易出现二义性，并且算法都很冗长。 2.流程图 优点：直观易懂；缺点：严密性不如程序语言，灵活性不如自然语言。 3.程序设计语言 优点：用程序语言描述的算法能由计算机直接执行；缺点：抽象性差，是算法设计者拘泥于描述算法的具体细节，忽略了“好”算法和正确逻辑的重要性，此外，还要求算法设计者掌握程序设计语言及其编程技巧。 4.伪代码 优点：表达能力强，抽象性强，容易理解

3、了解非递归算法的时间复杂性分析。(P13)

要点：对非递归算法时间复杂性的分析，关键是建立一个代表算法运行时间的求和表达式，然后用渐进符号表示这个求和表达式。 非递归算法分析的一般步骤是：

（1）决定用哪个（或哪些）参数作为算法问题规模的度量。 （2）找出算法的基本语句。

（3）检查基本语句的执行次数是否只依赖问题规模。 （4）建立基本语句执行次数的求和表达式。 （5）用渐进符号表示这个求和表达式。

[例1.4]：求数组最小值算法 in

第 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年代，但他们至今仍被人