算法设计与分析复习资料1
一
1.循环赛日程表问题的相关叙述。
2.算法运行时所需要占用的存储空间有？
3.动态规划法的求解步骤
4.解空间树是排列树的问题有。
5.分治法的步骤
6.就会场安排问题，贪心法的最佳贪心策略
7.快速排序法基准元素的选取方法
8.满足满m叉树的问题有？
9.分支限界法的解题步骤
10.事前分析法相关的影响因素有
11.用分治法求解的问题一般需要具备一些特征，主要有？
二
1．给定一个有向带权图G=(V，E)，其中每条边的权是一个非负实数，另外，给定V中的一个顶点，称为源点。现在要计算从源点到所有其它各个顶点的最短路径长度，这里的路径长度是指路径上经过的所有边上的权值之和，这个问题通常称为单源最短路径问题。
2．采用回溯法可以求解0-1背包问题，其解空间的形式为：（x1,x2,…,xn）或n 元组。
3．当所给的问题是从n个元素的排列中找出满足某种性质的一个排列时，相应的解空间树称为排列树。
4．一个正在生成孩子的结点称为扩展结点。
5．子集树是用回溯法解题时经常遇到的一种典型的解空间树。当所给的问题是从n个元素组成的集合S中找出满足某种性质的一个子集时，相应的解空间树称为子集树。
6．当所给问题的n个元素中每一个元素均有m种选择，要求确定其中的一种选择，使得对这n个元素的选择结果组成的向量满足某种性质，即寻找满足某种特性的n个元素取值的一种组合，这类问题的解空间树称为满m叉树。
7．一个自身已生成但其孩子还没有全部生成的结点称为活结点
8．回溯法中，对于问题的一个实例，解向量满足显约束的所有n元组构成了该实例的一个解空间
9．分支限界法有两种：队列式分支限界法和优先队列式分支限界法。
10．分支限界法采用的是宽度优先搜索。
11．时间复杂性的度量方法通常有两种：事后统计法和事前分析估算法
12．一个所有孩子已经生成的结点称做死结点
13．在最小生成树的生成方法中，Kruskal算法从边的角度出发，每一次将图中的权值最小的边取出来，在不构成环的情况下，将该边加入最小生成树。
三
1．分治法字面上的解释是分而治之，就是把一个复杂的问题分成两个或更多的相同子问题，子问题相互独立，如果子问题还是不容易解决，再把子问题分成更小的子问题…，直到最后各个子问题可以简单地直接求解，对各个子问题递归求解，将子问题的解进行合并即得原问题的解。
2．动态规划法要求将大问题分解成规模较小的子问题，经分解得到的各个子问题往往不是相互独立的。在求解过程中，将已解决的子问题的解进行保存，在需要时可以轻松找出。采
用自底向上的递归，由子问题的解得到原问题的解。
3．贪心法可以理解为以逐步的局部最优，达到最终的全局最优，而且不一定能达到全局最优。
4．子集树中的所有非叶子结点均有左右两个分支，左分支为1，右分支为0。
5．回溯法是一种“能进则进，进不了则换，换不了则退”的搜索方法。
6．最长公共子序列问题具有最优子结构性质。）
7．凸多边形最优三角剖分问题具有最优子结构性质。
8．时间复杂性是对算法运行时间的长短的度量。
9．贪心法是根据贪心策略来逐步构造问题的解，该算法的好坏关键在于正确地选择贪心策略。
10．当所给的问题是从n个元素的排列中找出满足某种性质的一个排列时，相应的解空间树称为排列树。
11．子集树的深度等于问题的规模
12．隐约束也叫剪枝函数，一般有两种：约束条件和限界条件。
13．加工顺序问题具有最优子结构性质。
14．包含元素最多的公共子序列即为最长公共子序列。
15．回溯法问题的解是一个n元组(x1,x2,…,x n)。
16．子集树中，从根结点到叶子结点的路径表示一个可行解。
17．针对问题的可能解是有限种的情况，逐一检查所有可能的情况，从中找到问题真正的解。18．子集树是用回溯法解题时经常遇到的一种典型的解空间树。当所给的问题是从n个元素组成的集合S中找出满足某种性质的一个子集时，相应的解空间树称为子集树。
19．动态规划法与分治法和贪心法类似，都是把待求解的问题分解为更小的、相同的子问题，然后对子问题进行求解，最终产生一个整体最优解。
20．快速排序法通过一趟扫描将待排序的元素分成独立的三个序列。
四
1 会场安排问题。
设有n个会议的集合C={1,2,…,n}，其中每个会议都要求使用同一个资源（如会议室），而在同一时间内只能有一个会议使用该资源。每个会议i都有要求使用该资源的起始时间b i 和结束时间e i，且b i 设有11个会议等待安排，如下表所示，用贪心法找出满足要求的会议集合（用箭头画出即可）。 1设G=(V，E)是无向连通带权图，V={1,2,…,6}，如下图所示，根据贪心策略写出用Prim 算法求解最小生成树的过程。 4. 图的m着色问题。给定无向连通图G=(V，E) 和3 种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。要求有边相连的两个顶点着不同颜色，找出所有不同的着色方法。要求给出最终的搜索树。 2．用分治法求解循环赛安排问题。 设有4个运动员要进行乒乓球循环赛，现要设计一个满足以下要求的比赛日程表：（1）每个选手必须与其它3个选手各赛一次； （2）每个选手一天只能比赛一次； （3）循环赛一共需要进行7天。 要求：安排4个选手的比赛日程表。 4．有7个工件，它们在第一台机器和第二台机器上的处理时间分别为： [t11,t12,t13,t14,t15,t16,t17]=[3,8,10,12,6,9,15， [t21,t22,t23,t24,t25,t26,t27]=[7,2,6, 18,3, 10,4] 求7个工件的最优加工顺序。 要求：用动态规划法按照算法步骤，求出问题的解。 5．布线问题。布线问题就是在N×M的方格阵列中，指定一个方格的中点为a，另一个方格的中点为b，如图所示，问题要求找出a到b的最短布线方案（即最短路径）。布线时只能沿直线或直角，不能走斜线，黑色的单元格代表不可以通过的封锁方格。 5．用优先队列式分支限界法求解0-1背包问题：n=4，W=[3，5，2，1] ， v=[9，10，7，4]，C=7。要求给出最终的搜索结果。 3 用二分查找算法在有序序列（6，12，15，18，22，25，28，35，46，58，60）中查找元素12，画出每次划分的示意图。 3. 已知待排序序列A=<8，3，2，9，7，1，5，4>，采用合并排序法进行排序，画出合并排序的过程示意图。 6. 用分支限界法求解旅行商问题。如图所示，n=4，城市1为售货员所在的住地城市，画出最终的搜索树。 2．已知某系统在通信联络中只可能出现8种字符，分别为a ，b ，c ，d ，e ，f ，g ，h ，其使用频率分别为0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11，用贪心法求解哈夫曼编码。要求：给出构造哈夫曼树的过程，并给出各个字符的编码。 6. 已知如图所示的无向图，用回溯法求解最大团。要求：（1）画出搜索树；（2）画出最大团。 《数据结构》必须掌握的知识点与算法 第一章绪论 1、算法的五个重要特性（有穷性、确定性、可行性、输入、输出） 2、算法设计的要求（正确性、可读性、健壮性、效率与低存储量需求） 3、算法与程序的关系： （1）一个程序不一定满足有穷性。例操作系统，只要整个系统不遭破坏，它将永远不会停止，即使没有作业需要处理，它仍处于动态等待中。因此，操作系统不是一个算法。 （2）程序中的指令必须是机器可执行的，而算法中的指令则无此限制。算法代表了对问题的解，而程序则是算法在计算机上的特定的实现。 （3）一个算法若用程序设计语言来描述，则它就是一个程序。 4、算法的时间复杂度的表示与计算（这个比较复杂，具体看算法本身，一般关心其循环的次数与N的关系、函数递归的计算） 第二章线性表 1、线性表的特点： （1）存在唯一的第一个元素；（这一点决定了图不是线性表） （2）存在唯一的最后一个元素； （3）除第一个元素外，其它均只有一个前驱（这一点决定了树不是线性表） （4）除最后一个元素外，其它均只有一个后继。 2、线性表有两种表示：顺序表示（数组）、链式表示（链表），栈、队列都是线性表，他们都可以用数组、链表来实现。 3、顺序表示的线性表（数组）地址计算方法： （1）一维数组，设DataType a[N]的首地址为A0，每一个数据（DataType类型）占m个字节，则a[k]的地址为：A a[k]＝A0+m*k（其直接意义就是求在数据a[k]的前面有多少个元素，每个元素占m个字节） （2）多维数组，以三维数组为例，设DataType a[M][N][P]的首地址为A000，每一个数据（DataType 类型）占m个字节，则在元素a[i][j][k]的前面共有元素个数为：M*N*i+N*j+k，其其地址为： A a[i][j][k]＝A000+m*(M*N*i+N*j+k)； 4、线性表的归并排序： 设两个线性表均已经按非递减顺序排好序，现要将两者合并为一个线性表，并仍然接非递减顺序。可见算法2.2 5、掌握线性表的顺序表示法定义代码，各元素的含义； 6、顺序线性表的初始化过程，可见算法2.3 7、顺序线性表的元素的查找。 8、顺序线性表的元素的插入算法，注意其对于当原来的存储空间满了后，追加存储空间（就是每次增加若干个空间，一般为10个）的处理过程，可见算法2.4 9、顺序线性表的删除元素过程，可见算法2.5 10、顺序线性表的归并算法，可见算法2.7 11、链表的定义代码，各元素的含义，并能用图形象地表示出来，以利分析； 12、链表中元素的查找 13、链表的元素插入，算法与图解，可见算法2.9 14、链表的元素的删除，算法与图解，可见算法2.10 15、链表的创建过程，算法与图解，注意，链表有两种（向表头生长、向表尾生长，分别用在栈、队列中），但他们的区别就是在创建时就产生了，可见算法2.11 16、链表的归并算法，可见算法2.12 17、建议了解所谓的静态单链表（即用数组的形式来实现链表的操作），可见算法2.13 18、循环链表的定义，意义 19、循环链表的构造算法（其与单链表的区别是在创建时确定的）、图解 习题1 1. 图论诞生于七桥问题。出生于瑞士的伟大数学家欧拉（Leonhard Euler ，1707—1783）提出并解决了该问题。七桥问题是这样描述的：一个人是否能在一次步行中穿越哥尼斯堡（现 在叫加里宁格勒，在波罗的海南岸）城中全部的七座桥后回到起点，且每座桥只经过一次， 图是这条河以及河上的两个岛和七座桥的草 图。请将该问题的数据模型抽象出来，并判断此问题是否有解。 七桥问题属于一笔画问题。 输入：一个起点 输出：相同的点 1， 一次步行 2， 经过七座桥，且每次只经历过一次 3， 回到起点 该问题无解：能一笔画的图形只有两类：一类是所有的点都是偶点。另一类是只有二个奇点的图形。 2．在欧几里德提出的欧几里德算法中（即最初的欧几里德算法）用的不是除法而是减法。请用伪代码描述这个版本的欧几里德算法 =m-n 2.循环直到r=0 m=n n=r r=m-n 3 输出m 3．设计算法求数组中相差最小的两个元素（称为最接近数）的差。要求分别给出伪代码和C++描述。 编写程序，求n 至少为多大时，n 个“1”组成的整数能被2013整除。 #include for(int n=1;n<=10000 ;++n) { value=value*10+1; if(value%2013==0) { cout<<"n至少为:"< 算法设计与分析的复习要点 第一章：算法问题求解基础 算法是对特定问题求解步骤的一种描述，它是指令的有限序列。 一．算法的五个特征： 1．输入：算法有零个或多个输入量； 2．输出：算法至少产生一个输出量； 3．确定性：算法的每一条指令都有确切的定义，没有二义性； 4．可行性：算法的每一条指令必须足够基本，它们可以通过已经实现的基本运算执行有限次来实现； 5．有穷性：算法必须总能在执行有限步之后终止。 二．什么是算法？程序与算法的区别 1．笼统地说，算法是求解一类问题的任意一种特殊的方法；较严格地说，算法是对特定问题求解步骤的一种描述，它是指令的有限序列。 2．程序是算法用某种程序设计语言的具体实现；算法必须可终止，程序却没有这一限制；即：程序可以不满足算法的第5个性质“有穷性”。 三．一个问题求解过程包括：理解问题、设计方案、实现方案、回顾复查。 四．系统生命周期或软件生命周期分为： 开发期：分析、设计、编码、测试；运行期：维护。 五．算法描述方法：自然语言、流程图、伪代码、程序设计语言等。 六．算法分析：是指对算法的执行时间和所需空间的估算。算法的效率通过算法分析来确定。 七．递归定义：是一种直接或间接引用自身的定义方法。一个合法的递归定义包括两部分：基础情况和递归部分； 基础情况：以直接形式明确列举新事物的若干简单对象； 递归部分：有简单或较简单对象定义新对象的条件和方法 八．常见的程序正确性证明方法： 1.归纳法：由基础情况和归纳步骤组成。归纳法是证明递归算法正确性和进行算法分析的强有力工具； 2.反证法。 第二章：算法分析基础 一．会计算程序步的执行次数（如书中例题程序2-1,2-2,2-3的总程序步数的计算）。二．会证明5个渐近记法。（如书中P22-25例2-1至例2-9） 三．会计算递推式的显式。（迭代法、代换法，主方法） 四．会用主定理求T(n)=aT(n/b)+f(n)。（主定理见P29，如例2-15至例2-18）五．一个好的算法应具备的4个重要特征： 1.正确性：算法的执行结果应当满足预先规定的功能和性能要求； 2.简明性：算法应思路清晰、层次分明、容易理解、利于编码和调试； 3.效率：算法应有效使用存储空间，并具有高的时间效率； 4.最优性：算法的执行时间已达到求解该类问题所需时间的下界。 六．影响程序运行时间的主要因素： 1.程序所依赖的算法； 2.问题规模和输入数据规模； 3.计算机系统性能。 七．1.算法的时间复杂度：是指算法运行所需的时间； 习题 1 1.图论诞生于七桥问题。出生于瑞士的伟大数学家欧拉（Leonhard Euler ，1707— 1783） 提出并解决了该问题。七桥问题是这样描述的：北区 一个人是否能在一次步行中穿越哥尼斯堡（现 东区在叫加里宁格勒，在波罗的海南岸）城中全部岛区 的七座桥后回到起点，且每座桥只经过一次， 图是这条河以及河上的两个岛和七座桥的草南区 图。请将该问题的数据模型抽象出来，并判断图七桥问题 此问题是否有解。 七桥问题属于一笔画问题。 输入：一个起点 输出：相同的点 1，一次步行 2，经过七座桥，且每次只经历过一次 3，回到起点 该问题无解：能一笔画的图形只有两类：一类是所有的点都是偶点。另一类是只有二个 奇点的图形。 2．在欧几里德提出的欧几里德算法中（即最初的欧几里德算法）用的不是除法而是减法。请用伪代码描述这个版本的欧几里德算法 =m-n 2.循环直到 r=0 m=n n=r r=m-n 3输出 m 3．设计算法求数组中相差最小的两个元素（称为最接近数）的差。要求分别给出伪代 码和 C++描述。 编写程序，求 n 至少为多大时， n 个“1”组成的整数能被2013 整除。 #include for(int n=1;n<=10000 ;++n) { value=value*10+1; if(value%2013==0) { cout<<"n 至少为 :"< 一 1.循环赛日程表问题的相关叙述。 2.算法运行时所需要占用的存储空间有？ 3.动态规划法的求解步骤 4.解空间树是排列树的问题有。 5.分治法的步骤 6.就会场安排问题，贪心法的最佳贪心策略 7.快速排序法基准元素的选取方法 8.满足满m叉树的问题有？ 9.分支限界法的解题步骤 10.事前分析法相关的影响因素有 11.用分治法求解的问题一般需要具备一些特征，主要有？ 二 1．给定一个有向带权图G=(V，E)，其中每条边的权是一个非负实数，另外，给定V中的一个顶点，称为源点。现在要计算从源点到所有其它各个顶点的最短路径长度，这里的路径长度是指路径上经过的所有边上的权值之和，这个问题通常称为单源最短路径问题。 2．采用回溯法可以求解0-1背包问题，其解空间的形式为：（x1,x2,…,xn）或n 元组。 3．当所给的问题是从n个元素的排列中找出满足某种性质的一个排列时，相应的解空间树称为排列树。 4．一个正在生成孩子的结点称为扩展结点。 5．子集树是用回溯法解题时经常遇到的一种典型的解空间树。当所给的问题是从n个元素组成的集合S中找出满足某种性质的一个子集时，相应的解空间树称为子集树。 6．当所给问题的n个元素中每一个元素均有m种选择，要求确定其中的一种选择，使得对这n个元素的选择结果组成的向量满足某种性质，即寻找满足某种特性的n个元素取值的一种组合，这类问题的解空间树称为满m叉树。 7．一个自身已生成但其孩子还没有全部生成的结点称为活结点 8．回溯法中，对于问题的一个实例，解向量满足显约束的所有n元组构成了该实例的一个解空间 9．分支限界法有两种：队列式分支限界法和优先队列式分支限界法。 10．分支限界法采用的是宽度优先搜索。 11．时间复杂性的度量方法通常有两种：事后统计法和事前分析估算法 12．一个所有孩子已经生成的结点称做死结点 13．在最小生成树的生成方法中，Kruskal算法从边的角度出发，每一次将图中的权值最小的边取出来，在不构成环的情况下，将该边加入最小生成树。 三 1．分治法字面上的解释是分而治之，就是把一个复杂的问题分成两个或更多的相同子问题，子问题相互独立，如果子问题还是不容易解决，再把子问题分成更小的子问题…，直到最后各个子问题可以简单地直接求解，对各个子问题递归求解，将子问题的解进行合并即得原问题的解。 2．动态规划法要求将大问题分解成规模较小的子问题，经分解得到的各个子问题往往不是相互独立的。在求解过程中，将已解决的子问题的解进行保存，在需要时可以轻松找出。采 HUNAN CITY UNIVERSITY 算法设计与分析课程设计 题目：求最大值与最小值问题 专业： 学号： 姓名： 指导教师： 成绩： 二0年月日 一、问题描述 输入一列整数，求出该列整数中的最大值与最小值。 二、课程设计目的 通过课程设计，提高用计算机解决实际问题的能力，提高独立实践的能力，将课本上的理论知识和实际有机的结合起来，锻炼分析解决实际问题的能力。提高适应实际，实践编程的能力。在实际的编程和调试综合试题的基础上，把高级语言程序设计的思想、编程巧和解题思路进行总结与概括，通过比较系统地练习达到真正比较熟练地掌握计算机编程的基本功，为后续的学习打下基础。了解一般程序设计的基本思路与方法。 三、问题分析 看到这个题目我们最容易想到的算法是直接比较算法：将数组的第 1 个元素分别赋给两个临时变量：fmax:=A[1]; fmin:=A[1]; 然后从数组的第 2 个元素 A[2]开始直到第 n个元素逐个与 fmax 和 fmin 比较，在每次比较中，如果A[i] > fmax，则用 A[i]的值替换 fmax 的值；如果 A[i] < fmin，则用 A[i]的值替换 fmin 的值；否则保持 fmax（fmin）的值不变。这样在程序结束时的fmax、fmin 的值就分别是数组的最大值和最小值。这个算法在最好、最坏情况下，元素的比较次数都是 2(n-1)，而平均比较次数也为 2(n-1)。 如果将上面的比较过程修改为：从数组的第 2 个元素 A[2]开始直到第 n 个元素，每个 A[i]都是首先与 fmax 比较，如果 A[i]>fmax,则用 A[i]的值替换 fmax 的值；否则才将 A[i]与 fmin 比较，如果 A[i] < fmin，则用 A[i]的值替换 fmin 的值。 这样的算法在最好、最坏情况下使用的比较次数分别是 n-1 和 2(n-1),而平均比较次数是 3(n-1)/2,因为在比较过程中，将有一半的几率出现 A[i]>fmax 情况。 ·算法是指解决问题的方法和过程。算法是由若干条指令组成的有穷序列。 ·算法特性：输入、输出、确定性、有限性（执行时间和执行次数）（有五个空再加上可行性）。 ·程序是算法用某种程序设计语言的具体实现，程序可不满足有限性的特性。 ·程序调试只能证明程序有错，不能证明程序无错误! ·算法复杂性= 算法所需要的计算机资源。 ·算法的复杂性取决于：(1)求解问题的规模N；(2)具体的输入数据I；(3)算法本身的设计A。·可操作性最好且最有实际价值的是最坏情况下的时间复杂性。 第二章递归与分治策略 二分搜索技术：O（logn）大整数乘法：O（n log3）=O（n1.59）Strassen矩阵乘法：O（n log7）=O(n2.81) 棋盘覆盖：O（4k）合并排序和快排：O（nlogn）线性时间选择：O(n) 最接近点对问题：O(nlogn) 循环赛日程表：O(n2) ·分治法思想：将一个难以解决的问题分割成一些规模较小的相同问题，以便逐个击破，分而治之。边界条件与递归方程是递归函数的两大要素。 递归优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。 ·分治法时间复杂度分析：T(n)<= O(1) n=n0 aT(n/b)+f(n) n>n0 若递归方式为减法：T(n) = O(a n) 若递归方式为除法： f(n)为合并为原问题的开销：f(n)为常数c时：T(n)=O(n p) f(n)为线性函数：O(n) ab,p=log b a f(n)为幂函数n x时：O(n x) a 《计算机算法设计与分析》习题及答案 一．选择题 1、二分搜索算法是利用（A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（A ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4. 回溯法解旅行售货员问题时的解空间树是（ A ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树 5．下列算法中通常以自底向上的方式求解最优解的是（ B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 6、衡量一个算法好坏的标准是（C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 7、以下不可以使用分治法求解的是（D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 8. 实现循环赛日程表利用的算法是（ A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 9．下面不是分支界限法搜索方式的是（ D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先 10．下列算法中通常以深度优先方式系统搜索问题解的是（ D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 11.备忘录方法是那种算法的变形。（B ） A、分治法 B、动态规划法 C、贪心法 D、回溯法 12．哈夫曼编码的贪心算法所需的计算时间为（ B ）。 A、O（n2n） B、O（nlogn） C、O（2n） D、O（n） 13．分支限界法解最大团问题时，活结点表的组织形式是（ B ）。 A、最小堆 B、最大堆 C、栈 D、数组 14．最长公共子序列算法利用的算法是（ B ）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 15．实现棋盘覆盖算法利用的算法是（ A ）。 A、分治法 B、动态规划法 C、贪心法 D、回溯法 16.下面是贪心算法的基本要素的是（ C ）。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最优解 17.回溯法的效率不依赖于下列哪些因素（ D ） A.满足显约束的值的个数 B. 计算约束函数的时间 C.计算限界函数的时间 D. 确定解空间的时间 18.下面哪种函数是回溯法中为避免无效搜索采取的策略（ B ） A．递归函数 B.剪枝函数C。随机数函数 D.搜索函数 19. （ D ）是贪心算法与动态规划算法的共同点。 第一章概述 算法的概念：算法是指解决问题的一种方法或过程，是由若干条指令组成的有穷序列。 算法的特征： 可终止性：算法必须在有限时间内终止； 正确性：算法必须正确描述问题的求解过程； 可行性：算法必须是可实施的； 算法可以有0个或0个以上的输入； 算法必须有1个或1个以上的输出。 算法与程序的关系： 区别：程序可以不一定满足可终止性。但算法必须在有限时间内结束； 程序可以没有输出,而算法则必须有输出； 算法是面向问题求解的过程描述，程序则是算法的实现。 联系：程序是算法用某种程序设计语言的具体实现； 程序可以不满足算法的有限性性质。 算法描述方式：自然语言，流程图，伪代码，高级语言。 算法复杂性分析： 算法复杂性的高低体现运行该算法所需计算机资源（时间，空间）的多少。 算法复杂性度量： 期望反映算法本身性能，与环境无关。 理论上不能用算法在机器上真正的运行开销作为标准（硬件性能、代码质量影响）。 一般是针对问题选择基本运算和基本存储单位，用算法针对基本运算与基本存储单位的开销作为标准。 算法复杂性C依赖于问题规模N、算法输入I和算法本身A。即C=F(N, I, A)。 第二章递归与分治 分治法的基本思想： 求解问题算法的复杂性一般都与问题规模相关，问题规模越小越容易处理。 分治法的基本思想是，将一个难以直接解决的大问题，分解为规模较小的相同子问题，直至这些子问题容易直接求解，并且可以利用这些子问题的解求出原问题的解。各个击破，分而治之。 分治法产生的子问题一般是原问题的较小模式，这就为使用递归技术提供了方便。递归是分治法中最常用的技术。 使子问题规模大致相等的做法是出自一种平衡(balancing)子问题的思想，它几乎总是比子问题规模不等的做法要好。 分治法所能解决的问题一般具有以下几个特征： 该问题的规模缩小到一定的程度就可以容易地解决； 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质； 利用该问题分解出的子问题的解可以合并为该问题的解； 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。（这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划较好。） 递归的概念： 华南农业大学期末考试试卷（A卷） 2008学年第一学期考试科目：算法分析与设计 考试类型：（闭卷）考试时间：120 分钟 学号姓名年级专业 一、选择题（20分，每题2分） 1.下述表达不正确的是。 A．n2/2 + 2n的渐进表达式上界函数是O(2n) B．n2/2 + 2n的渐进表达式下界函数是Ω(2n) C．logn3的渐进表达式上界函数是O(logn) D．logn3的渐进表达式下界函数是Ω(n3) 2.当输入规模为n时，算法增长率最大的是。 A．5n B．20log2n C．2n2 D．3nlog3n 3.T（n）表示当输入规模为n时的算法效率，以下算法效率最优的是。A．T（n）= T（n – 1）+1，T（1）=1 B．T（n）= 2n2 C．T（n）= T（n/2）+1，T（1）=1 D．T（n）= 3nlog2n 4.在棋盘覆盖问题中，对于2k×2k的特殊棋盘（有一个特殊方块），所需的L型骨牌 的个数是。 A．（4k– 1）/3 B．2k /3 C．4k D．2k 5.在寻找n个元素中第k小元素问题中，若使用快速排序算法思想，运用分治算法 对n个元素进行划分，应如何选择划分基准？下面答案解释最合理。A．随机选择一个元素作为划分基准 B．取子序列的第一个元素作为划分基准 C．用中位数的中位数方法寻找划分基准 D．以上皆可行。但不同方法，算法复杂度上界可能不同 6. 有9个村庄，其坐标位置如下表所示： 现在要盖一所邮局为这9个村庄服务，请问邮局应该盖在 才能使到邮局到这9个村庄的总距离和最短。 A ．（4.5，0） B ．（4.5，4.5） C ．（5，5） D ．（5，0） 7. n 个人拎着水桶在一个水龙头前面排队打水，水桶有大有小，水桶必须打满水， 水流恒定。如下 说法不正确？ A ．让水桶大的人先打水，可以使得每个人排队时间之和最小 B ．让水桶小的人先打水，可以使得每个人排队时间之和最小 C ．让水桶小的人先打水，在某个确定的时间t 内，可以让尽可能多的人打上水 D ．若要在尽可能短的时间内，n 个人都打完水，按照什么顺序其实都一样 8. 分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题，分 别解决子问题，最后将子问题的解组合起来形成原问题的解。这要求原问题和子问题 。 A ．问题规模相同，问题性质相同 B ．问题规模相同，问题性质不同 C ．问题规模不同，问题性质相同 D ．问题规模不同，问题性质不同 9. 对布线问题，以下 是不正确描述。 A ．布线问题的解空间是一个图 B ．可以对方格阵列四周设置围墙，即增设标记的附加方格的预处理，使得算法简化对边界的判定 C ．采用广度优先的标号法找到从起点到终点的布线方案（这个方案如果存在的话）不一定是最短的 D ．采用先入先出的队列作为活结点表，以终点b 为扩展结点或活结点队列为空作为算法结束条件 10. 对于含有n 个元素的子集树问题，最坏情况下其解空间的叶结点数目为 。 A ．n! B ．2n C ．2n+1 -1 D ．∑=n i i n 1 !/! 答案：DACAD CACCB 数据结构与算法设计知识点 试题类型： 本课程为考试科目（闭卷笔试），试题类型包括：概念填空题（10 %），是非判断题（10 %），单项选择题（40 %），算法填空题（10%），算法应用题（20 %)，算法设计题（10 %）。 第一章绪论 重点容及要求： 1、了解与数据结构相关的概念（集合、数据、数据元素、数据项、关键字、元 素之间的关系等）。 数据：所有能被输入到计算机中，且能被计算机处理的符号的 集合。是计算机操作的对象的总称。是计算机处理的信息的某种特定 的符号表示形式。 数据元素：是数据（集合）中的一个“个体”，数据结构中的基 本单位，在计算机程序常作为一个整体来考虑和处理。 数据项：是数据结构中讨论的最小单位，数据元素可以是一个或 多个数据项的组合 关键码：也叫关键字（Key），是数据元素中能起标识作用的数据 项。 其中能起到唯一标识作用的关键码称为主关键码（简称主码）； 否则称为次关键码。通常，一个数据元素只有一个主码，但可以有多 个次码。 关系：指一个数据集合中数据元素之间的某种相关性。 数据结构：带“结构”的数据元素的集合。这里的结构指元素之 间存在的关系。 数据类型：是一个值的集合和定义在此集合上的一组操作的总 称。 2、掌握数据结构的基本概念、数据的逻辑结构（四种）和物理结构（数据元素 的表示与关系的表示、两类存储结构：顺序存储结构和链式存储结构）。 数据结构包括逻辑结构和物理结构两个层次。 数据的逻辑结构：是对数据元素之间存在的逻辑关系的一种抽象的描述，可以用一个数据元素的集合和定义在此集合上的若干关系来表示 逻辑结构有四种：线性结构、树形结构、图状结构、集合结构数据的物理结构：是其逻辑结构在计算机中的表示或实现，因此又称其为存储结构。 存储结构：顺序存储结构和链式存储结构 顺序存储结构：利用数据元素在存储器中相对位置之间的某种特定的关系来表示数据元素之间的逻辑关系； 链式存储结构：除数据元素本身外，采用附加的“指针”表示数据元素之间的逻辑关系。 3、了解算法分析的基本方法，掌握算法时间复杂度相关的概念。 算法：是为了解决某类问题而规定的一个有限长的操作序列 或处理问题的策略 一个算法必须满足以下五个重要特性：1．有穷性2．确定性3．可行性4．有输入 5．有输出 设计算法时，通常还应考虑满足以下目标： 1.正确性， 2.可读性， 3.健壮性 4.高效率与低存储量需求 第一章 1. 算法分析题 算法分析题1－1 求下列函数的渐进表达式 (1). 3n^2 + 10n < 3n^2 + 10n^2 = 13n^2 = O(n^2) (2). n^2 / 10 + 2^n 当n>5是，n^2 < 2 ^n 所以，当n >= 1时，n^2/10 < 2 ^n 故: n^2/10 + 2^n < 2 ^n + 2^n = 2*2^n = O(2^n) (3). 21 + 1/n < 21 + 1 = 22 = O(1) (4). log(n^3)=3log(n)=O(log(n)) (5). 10log(3^n) = (10log3)n = O(n) 算法分析题1-6 (1)因为：f(n)=log(n^2) = 2log(n); g(n) = log(n) + 5 所以：f(n)=Θ(log(n)+5) =Θ(g(n)) (2)因为：log(n) < √n; f(n) = 2log(n); g(n)= √n 所以：f(n) = O(g(n)) (3)因为：log(n) < n; f(n) = n; g(n) = log(n^2) = 2log(n) 所以；f(n) = Ω(g(n)) (4)因为：f(n) = nlogn +n; g(n) = logn 所以：f(n) =Ω(g(n)) (5)因为: f(n) = 10; g(n) = log(10) 所以:f(n) =Θ(g(n)) (6)因为: f(n)=log^2(n); g(n) = log(n) 所以: f(n) ==Ω(g(n)) (7)因为: f(n) = 2^n < 100*2^n; g(n)=100n^2; 2^n > n ^2 所以: f(n) = Ω(g(n)) (8)因为：f(n) = 2^n; g(n) = 3 ^n; 2 ^n < 3 ^n 所以: f(n) = O(g(n)) 习题1－9 证明：如果一个算法在平均情况下的计算时间复杂性为Θ(f(n)),该算法在最坏情况下所需的计算时间为Ω(f(n)). 分析与解答： 因此，Tmax(N) = Ω(Tavg(N)) = Ω(Θ(f(n)))=Ω(f(n)). 第二章 算法分析题 ●通俗地讲，算法是解决问题的方法，严格地说，算法是对特定问题求解步骤的一种描述， 是指令的有限序列。 ●算法还必须满足一下五个重要特性：输入、输出、有穷性、确定性、可行性。 ●程序（Program）是对一个算法使用某种程序设计语言的具体实现，原则上，算法可以 用任何一种程序设计语言来实现。 什么是算法的计算复杂性？ ●算法分析指的是对算法所需要的两种计算机资源——时间和空间(时间复杂性和空间复 杂性进行估算，所需要的资源越多，该算法的复杂性就越高。 ●表示计算复杂性的O你掌握了？ 若存在两个正的常数c和n0，对于任意n≥n0，都有T(n)≤c×f(n)，则称T(n)=O(f(n))（或称算法在O(f(n))中）。 我们主要介绍了哪几种算法设计方法？ 分治法：将一个难以直接解决的大问题，分割成一些规模较小的子问题，以便各个击破，分而治之。 减治法：减治法在将原问题分解为若干个子问题后，利用了规模为n的原问题的解与较小规模（通常是n/2）的子问题的解之间的关系，这种关系通常表现为： （1）原问题的解只存在于其中一个较小规模的子问题中； （2）原问题的解与其中一个较小规模的解之间存在某种对应关系。 由于原问题的解与较小规模的子问题的解之间存在这种关系，所以，只需求解其中 一个较小规模的子问题就可以得到原问题的解。 动态规划法、贪心算法、回溯算法、概率 RAM程序 分治法------合并排序 设算法4.3对n个元素排序的时间复杂性为T(n)，则该二路归并排序算法存在如下递推式： 二路归并排序的时间代价是O(nlog2n)。 所需空间只要O(m+n+min(m, n))的空间就够了(假设两个合并串的长度分别为m和n)。 分治法------快速排序 Ex.1(p20)若将y ← uniform(0, 1) 改为 y ← x, 则上述的算法估计的值是什么？ 解：若将y ←uniform(0, 1) 改为 y ←x，此时有 ，则k++，即 ，此时k++，由于此时x ← uniform(0, 1)，所以k/n=，则此时4k/n=2。所以上述算法估计的值为2。 Ex.2(p23) 在机器上用 估计π值，给出不同的n值及精度。 解：由ppt上p21可知，的大小 ，其中k为落入圆内的数目，n为总数，且π=，即需要计算4k/n。我们先令x ← uniform(0, 1)，y ← uniform(0, 1)。 计算的值，如果小于等于1，那么此时k++。最后计算4k/n的值即可估计此时的π值。代码的主要部分为： 执行结果为： 结果分析：随着N的取值不断地增加，得到的π值也就越来越精确。 Ex.3(p23) 设a, b, c和d是实数，且a ≤ b, c ≤ d, f:[a, b] → [c, d]是一个连续函数，写一概率算法计算积分： 注意，函数的参数是a, b, c, d, n和f, 其中f用函数指针实现，请选一连续函数做实验，并给出实验结果。 解：的值为y=，y=0，x=a，x=b围成的面积。根据之前的例子我们可以知道= k(b-a)d/n。其中k是落在函数y=，x=a，x=b以及y=0所包围区间内的个数。 代码的主要部分为： 运行结果为： 结果分析： 随着N的取值不断地增加，得到的积分值越来越精确。 Ex4(p24). 设ε,δ是(0,1)之间的常数，证明：若I是的正确值，h是由HitorMiss算法返回的值，则当n ≥ I(1-I)/ε2δ时有： Prob[|h-I| < ε] ≥ 1 –δ 上述的意义告诉我们：Prob[|h-I| ≥ε] ≤δ, 即：当n ≥ I(1-I)/ ε2δ时，算法的计算结果的绝对误差超过ε的概率不超过δ，因此我们根据给定ε和δ可以确定算法迭代的次数 () 解此问题时可用切比雪夫不等式，将I看作是数学期望。 证明：由切比雪夫不等式可知： P( | X - E(X) | < ε ) ≥ 1 - D(X) / ε2 由题目知，E(X)=I。且根据题意，我们可知，在HotorMiss算法中，若随机选取n个点，其中k个点在积分范围内，则 。且k的分布为二项分布B(n，I)（在积分范围内或者不在 积分范围内），则 。又因为k=x*n，所以D(X)=I(1-I)/n。再将E(X)和D(X)带入切比雪夫不等式中即可得到 Ex5(p36). 用上述算法，估计整数子集1~n的大小，并分析n对估计值的影响。 解：由题知，集合的大小，通过计算新生成的集合中元素的个数来估计原集合的大小，代码的主体部分如下： 算法与程序设计知识点汇总 第一章 计算机解决问题的基本过程 一、开始 分析问题 设计算法 编写程序 调试、运行程序 问题解决 二、算法-----程序设计的“灵魂 ” 1、定义：就是解决问题的方法和步骤 2 1、确定性：每一步都有确切的含义 2、有穷性：执行的步骤和每一步执行的时间都是有限的 3、输入：有零个或多个输入 4、输出：至少产生一个输出 5、可行性：原则上可精确运行 3、算法的描述：1、自然语言 2、流程图(P11) 3、伪代码（p12） 4、计算机语言 三：程序设计语言的发展： 须经过转换处理。 高级语言：更接近于自然语言（英语）和数学语言的编程语言，容易掌握和使用，也不能直接识别，必须经过转换才能被计算机执行。 第二章 一、visiual basic 可视化程序开发工具，主要是让程序设计人员利用软件本身所提供的各种控件，像搭积木一样构造应用程序的各种界面，然后再编写少量的代码就可以构建应用程序，提供了程序设计，编辑，调试，运行于一体的集成开发环境。 二、VB6.0的集成开发环境 三个工作栏： 标题栏 菜单栏 工具栏 六个基本窗口： 主窗口(main) 窗体窗口(form) 工具箱窗口(toolbox) 工程窗口(project) 属性窗口(properties) 窗体布局窗口(formlayout) 三、属性---用来描述对象的外部特征 四、常用控件 熟悉常用控件(标签、文本框、命令按钮)的作用，图标及其属性 五、数据的表示与处理 1、Vb 数据类型 2、常量与变量的说明： 常量说明：Const a=3.14 const a as single=3.14 变量说明： Dim a As integer Dim b As integer Dim a,b As integer 3、运算符 (1) 算术运算符 (2)字符串运算符 ＆、+字符串连接 " 123 " + " 456 "结果 " 123456 " " 123 " & " 456 " 结果 " 123456 " 区别: + 两边必须是字符串, & 不一定 例如: "abcdef" & 12345 ' 结果为 "abcdef12345 " "abcdef " + 12345 ' 出错 "123" & 456 ' 结果为" 123456 " “123” + 456 ' 结果为 579 注意： "123 " + True'结果为 122 True转换为数值-1，False转换为数值0 (3)关系运算符 a、将两个操作数进行大小比较,结果为逻辑量。如：3>2结果为True。 b、字符串比较,则按字符的ASCII码值从左到右一一比较,直到出现不同的字符为止.。 例： " ABCDE " > " ABRA " 结果为 False 注释：A—Z的ASCII码值为65—90； a—z的ASCII码值为97—122；(选修教材124页) 1.15练习 1.1（a） 1)A[1…60] = A[(1+60)/2]=A[30]=40 由于33<40，舍弃A[30…60]; 2)A[1…29] = A[(1+29)/2]=A[15]=25 由于33>25，舍弃A[1…15]; 3) A[16…29]= A[(16+29)/2]=A[22]=32 由于33>32，舍弃A[16…22]; 4) A[23…29] = A[(23+29)/2]=A[26]=36 由于33<36，舍弃A[26…29]; 5) A[23…25] = A[(23+25)/2]=A[24]=34; 由于33<34，舍弃A[24, 25]; 6) A[23] = 11 12 13 … 68 69 70 11 12 13 … 37 38 39 26 27 28 … 37 38 39 33 34 35 36 37 38 39 33 34 35 33 由于33=33，搜索完毕。 综上，搜索33共执行了6次比较。 同理可得（b ）搜索7共执行了5次比较。 （c ）搜索70共执行了6次比较。 （d ）搜索77共执行了6次比较。 1.10 对11 12 1 5 15 3 4 10 7 2 16 9 8 14 13 6用bottomupsort 算法，按非降序排列。 解：用图示，如下进行。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 3 4 5 10 11 12 15 1 5 11 1 2 1.15用Θ表示函数。 (b) 2 6 7 8 9 1 3 1 4 16 3 4 10 1 5 2 7 9 1 6 6 8 13 14 11 12 1 5 15 3 4 10 2 7 9 16 8 14 6 13 算法与程序设计知识点 汇总 Document serial number【KKGB-LBS98YT-BS8CB-BSUT-BST108】 算法与程序设计知识点汇总 第一章 计算机解决问题的基本过程 一、开始分析问题 设计算法 编写程序 调试、运行程序 问题解决 二、算法-----程序设计的“灵魂” 1、定义：就是解决问题的方法和步骤 2、特征： 1、确定性：每一步都有确切的含义 2、有穷性：执行的步骤和每一步执行的时间都是有限的 3、输入：有零个或多个输入 4、输出：至少产生一个输出 5、可行性：原则上可精确运行 3、算法的描述：1、自然语言 2、流程图(P11) 3、伪代码（p12） 4、计算机语言 算机直接执行，必须经过转换处理。 高级语言：更接近于自然语言（英语）和数学语言的编程语言，容易掌握和使用，也不能直接识别，必须经过转换才能被计算机执行。 第二章 一、visiual basic 可视化程序开发工具，主要是让程序设计人员利用软件本身所提供的各种控件，像搭积木一样构造应用程序的各种界面，然后再编写少量的代码就可以构建应用程序，提供了程序设计，编辑，调试，运行于一体的集成开发环境。 二、的集成开发环境 三个工作栏： 标题栏 菜单栏 工具栏 六个基本窗口： 主窗口(main) 窗体窗口(form) 工具箱窗口(toolbox) 工程窗口(project) 属性窗口(properties) 窗体布局窗口(formlayout) 熟悉常用控件(标签、文本框、命令按钮)的作用，图标及其属性 五、数据的表示与处理 1、 Integer整型 2 Byte-32768～32767(-215～215-1) Long长整型 4 Byte(-231～231-1) Single单精度实型 4 Byte ～～ Double双精度实型8 Byte String字符串型10 Byte＋串长 度 0～约20亿个字符 Boolean布尔型 2 Byte True或False Date日期型8 Byte100/1/1～9999/12/31 2 常量说明：Const a= const a as single= 变量说明： Dim a As integer Dim b As integer Dim a,b As integer 3、运算符 (1) 算术运算符 (2)字符 串运算符 ＆、+ 字符串连接 " 123 " + " 456 " 结果 " 123456 " " 123 " & " 456 " 结果 " 123456 " 区别: + 两边必须是字符串, & 不一定 例如: "abcdef" & 12345 ' 结果为 "abcdef12345 " "abcdef " + 12345 ' 出错 "123" & 456 ' 结果为" 123456 " “123” + 456 ' 结果为 579 注意： "123 " + True '结果为 122 True转换为数值-1，False转换为数值0 (3)关系运算符考研数据结构必须掌握的知识点与算法-打印版
算法设计与分析习题答案1-6章
最新算法设计与分析复习要点(1)
算法设计与分析习题答案1-6章.docx
算法设计与分析复习资料1
算法设计与分析课程设计(完整版)
算法设计与分析复习要点
计算机算法设计与分析习题和答案解析
算法分析与设计知识点总结
2009.1算法设计与分析报告课程期末试卷-A卷(自测 )
大数据结构与算法设计知识点
算法设计与分析课后习题
算法设计与分析报告期末备考知识点总结材料
算法设计与分析
算法程序设计知识点汇总
算法设计与分析第一章习题解1.1,1.10,1.15
算法与程序设计知识点汇总
相关文档
- 算法设计与分析报告1
- (完整版)算法设计与分析考试题及答案
- 算法设计与分析课程设计(完整版)
- 计算机算法设计与分析第1章 算法概述PPT课件
- 算法设计与分析(1)
- 算法设计与分析-f (1)
- 算法设计与分析(第2版)-郑宗汉-第1章-1PPT课件
- 算法设计与分析1_Moving2
- 算法设计与分析习题答案1-6章
- 计算机算法设计与分析 第3章(1)
- 算法设计与分析习题答案1-6章.docx
- 最新算法设计与分析复习要点(1)
- 算法设计与分析第一讲
- 算法设计与分析1_Difference
- 2009.1算法设计与分析报告课程期末试卷-A卷(自测 )
- 算法设计与分析1
- 算法设计与分析 第1章
- 算法设计与分析1_Huffman
- 算法设计与分析习题答案1-6章
- 算法设计与分析