算法设计与分析微课视频版试题

诚信 保证

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

编号： 西北工业大学考试试题（卷） 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． 按分治策略求解棋盘覆盖问题时，对于如图所示的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个子集合，分别对两个子集合排序，最终将排好序的子集合合并成为所要求的集合。

诚信保证

本人知晓我校考场规则和违纪处分条例的有关规定，保证遵守考场规则，诚实做人。 本人签字： 编号：

西北工业大学考试试题（卷）

2013－2014学年第2 学期

成绩 开课学院 计算机学院 课程 算法设计与分析 学时 48 开A考试日期 2014.6.30 考试时间 2 小时 考试形式（）（）卷 闭B考生班级 学 号 姓 名 一、简答题，共5题，每题8分（40分） 1. 简述分治法的基本思想。 2. 简述回溯算法的基本思想及其一般模式。 3. 简述分支限界法的基本思想。 4. 简述贪心算法的基本思想。 5. 简述分治法与动态规划的区别与联系。 二、应用题，共5题，每题12分（60分） 1、设有8个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表： (1)每个选手必须与其他7个选手各赛一次； (2)每个选手一天只能参赛一次； (3)循环赛在7天内结束。 2、设有 n 个顾客同时等待一项服务。顾客 i 需要的服务时间为t i ，

最接近点对问题

问题

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

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

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

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

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

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

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

基本思想

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

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

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

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

《算法设计与分析》实验报告

学号： 姓名：

实验一 分治法求解**问题

一、实验目的

1.掌握分治法的设计思想并能熟练应用；

2.理解分治与递归的关系。

二、实验题目

在有序序列中(r1,r2,…,rn)中,存在序号i（1≤i≤n）,使得ri=i。请设计一个分治算法找到这个元素，要求算法在最坏情况下的时间性能为O(log2n).

三、实验程序

//以(0,2,3,3,5,7,8,10,12,13)为例

#include<iostream>

using namespace std;

void PrintData(int data[],int length)

{

}

int Bisearch(int data[],int begin ,int last)

{

if ( mid < data[mid] ) int mid=(begin + last) /2; if (mid+1 == data[mid]) { } return mid; cout<<"有序序列是："; for (int i=0;i

算法分析与设计基础 （清华版）

Taken from \节选自《算法设计与分析基础》潘彦 译 蛮力法

就像宝剑不是撬棍一样，科学也很少使用蛮力。

——Edward Lytton (1830 - 1873)，leila，第二卷，第一章 认真做事常常是浪费时间。

——Robert Byrne，撞球大师，台球选手和作家

人们是这样描述它的：蛮力法是一种简单直接地解决问题的方法，常常直接基于问题的描述和所涉及的概念定义。这里的“力”是指计算机的能“力”，而不是人的智“力”。我们也可以用“直接做吧！”来描述蛮力法的策略。而且一般来说，蛮力策略也常常是最容易应用的方法。虽然巧妙和高效的算法很少来自于蛮力法，但我们不应该忽略它作为一种重要的算法设计策略的地位。第一，和其他某些策略不同，我们可以应用蛮力法来解决广阔领域的各种问题（实际上，它可能是惟一一种几乎什么问题都能解决的一般性方法）。具体来说，蛮力法常常用于一些非常基本、但又十分重要的算法，比如计算n个数字的和，求一个列表的最大元素，等等。第二，对于一些重要的问题来说（比如：排序、查找、矩阵乘法和字符串匹配），蛮力法可以产生一些合理的算法，它们多少具备一些实用价值，而且并不限制实例的规模。第三，

最接近点对问题

问题

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

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

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

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

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

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

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

基本思想

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

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

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

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

算法设计与分析期末作业

算法设计与分析期末作业

学校 专业班级 学号 学院 任课教师 学生姓名 第一题：简述递归算法、分治算法、动态规划算法、回溯算法的基本思想和步骤。

第二题：自拟一组数据，从插入排序、选择排序、合并排序、快速排序四种算法中任选两种算法，以图示描述方式描述算法求解过程。

第三题：从以下高级图算法(即宽度优先搜索算法、深度优先搜索算法、Kruskal算法、Prim算法、BellmanFord算法 、Dijkstra算法)中任选一种，结合现实情况构造一具体案例，并使用所选择的图算法以图示描述方式予以求解。

要求：在此作业模板下答题，电子文档及其打印文档均需上交，其中，电子文档发送至duyuanwei@foxmail.com，打印文稿于16周上课时上交。

1

算法设计与分析期末作业

第一题

答：一、递归算法：

（1）基本思想：把一个问题划分为一个或多个规模更小的子问题，然后用同样的方法解规模更小的子问题。(递归=递推+回归) （2）步