湖南大学算法设计与分析期中试题及答案

《算法设计与分析》考试题目及答案(DOC)D. 预排序与递归调用7. 回溯法在问题的解空间树中，按（D）策略，从根结点出发搜索解空间树。

A．广度优先B. 活结点优先 C.扩展结点优先 D. 深度优先8. 分支限界法在问题的解空间树中，按（A）策略，从根结点出发搜索解空间树。

A．广度优先B. 活结点优先 C.扩展结点优先 D. 深度优先9. 程序块（A）是回溯法中遍历排列树的算法框架程序。

A.B.C.D. void backtrack (int t){if (t>n) output(x);elsefor (int i=t;i<=n;i++) {swap(x[t], x[i]);if (legal(t)) backtrack(t+1); swap(x[t], x[i]);}}void backtrack (int t){if (t>n) output(x);elsefor (int i=0;i<=1;i++) {x[t]=i;if (legal(t)) backtrack(t+1); }}10. 回溯法的效率不依赖于以下哪一个因素？（C ）A.产生x[k]的时间；B.满足显约束的x[k]值的个数；C.问题的解空间的形式；D.计算上界函数bound的时间；E.满足约束函数和上界函数约束的所有x[k]的个数。

F.计算约束函数constraint的时间；11. 常见的两种分支限界法为（D）A. 广度优先分支限界法与深度优先分支限界法；B. 队列式（FIFO）分支限界法与堆栈式分支限界法；C. 排列树法与子集树法；D. 队列式（FIFO）分支限界法与优先队列式分支限界法；12. k带图灵机的空间复杂性S(n)是指（B）A.k带图灵机处理所有长度为n的输入时，在某条带上所使用过的最大方格数。

B.k带图灵机处理所有长度为n的输入时，在k条带上所使用过的方格数的总和。

C.k带图灵机处理所有长度为n的输入时，在k条带上所使用过的平均方格数。

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． 已知1()*()i i k k ij r r A a +=，k =1，2，3，4，5，6，r 1=5，r 2=10，r 3=3，r 4=8，r 5=5，r 6=20，r 7=6，求矩阵链积A 1×A 2×A 3×A 4×A 5×A 6的最佳求积顺序。

7． 给出城市网络图，售货员要从城市1出发，经过所有城市回到城市1，画出该问题的解空间树，描述出用优先队列式分支限界法求解时的搜索情况。

表示出优先队列、当前扩展结点等的变化情况。

8． 依据优先队列式分支限界法，求从s 点到t 点的单源最短路径，画出求得最优解的解空间树。

一、假设有7个物品，它们的重量和价值如下表所示。

若这些物品均不能被分割，且背包容量M＝150，使用回溯方法求解此背包问题。

请写出状态空间搜索树（20分）。

答：按照单位效益从大到小依次排列这7个物品为：FBGDECA 。

将它们的序号分别记为1～7。

则可生产如下的状态空间搜索树。

其中各个节点处的限界函数值通过如下方式求得：【排序1分】5x =6x =7x =17分，每个节点1分】a ．1501154040305035190.62540-++++⨯=7(1,1,1,1,,0,0)8b. 1501154040305030177.560-++++⨯=7(1,1,1,1,0,,0)12c ．4040305010170++++=(1,1,1,1,0,0,1)d. 1501054040303530167.560-++++⨯=3(1,1,1,0,1,,0)4e. 150130404050353017560-++++⨯=1(1,1,0,1,1,,0)3f. 1501304040503510170.7135-++++⨯=4(1,1,0,1,1,0,)7g. 40405030160+++=(1,1,0,1,0,1,0)h. 1501404040353010146.8535-++++⨯=2(1,1,0,0,1,1,)7i.1501254030503530167.560-++++⨯=5(1,0,1,1,1,,0)12 j. 1501454030503530157.560-++++⨯=1(0,1,1,1,1,,0)12在Q 1处获得该问题的最优解为(1,1,1,1,0,0,1)，背包效益为170。

chengcheng算法分析考试试卷（A卷）课程名称算法分析编号题号一二三四总分得分评阅人一、填空题（每小题3分，共30分）1、一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

2、这种不断回头寻找目标的方法称为回溯法。

3、直接或间接地调用自身的算法称为递归算法。

4、 记号在算法复杂性的表示法中表示紧致界。

5、由分治法产生的子问题往往是原问题较小模式，这就为使用递归技术提供了方便。

6、建立计算模型的目的是为了使问题的计算复杂性分析有一个共同的客观尺度。

7、下列各步骤的先后顺序是②③④①。

①调试程序②分析问题③设计算法④编写程序。

8、最优子结构性质的含义是问题最优解包含其子问题最优解。

9、贪心算法从初始阶段开始，每一个阶段总是作一个使局部最优的贪心选择。

10、拉斯维加斯算法找到的解一定是正确的。

二、选择题（每小题2分，共20分）1、哈夫曼编码可利用（ C ）算法实现。

A、分治策略B、动态规划法C、贪心法D、回溯法2、下列不是基本计算模型的是（ B ）。

A、RAMB、ROMC、RASPD、TM3、下列算法中通常以自顶向下的方式求解最优解的是（ C）。

A、分治法B、动态规划法C、贪心法D、回溯法chengcheng 4、在对问题的解空间树进行搜索的方法中,一个活结点有多次机会成为活结点的是( A )A、回溯法B、分支限界法C、回溯法和分支限界法D、动态规划5、秦始皇吞并六国使用的远交近攻，逐个击破的连横策略采用了以下哪种算法思想？ BA、递归；B、分治；C、迭代；D、模拟。

6、FIFO是（ A ）的一搜索方式。

A、分支界限法B、动态规划法C、贪心法D、回溯法7、投点法是（ B ）的一种。

A、分支界限算法B、概率算法C、贪心算法D、回溯算法8、若线性规划问题存在最优解，它一定不在（ C ）A．可行域的某个顶点上 B．可行域的某条边上 C．可行域内部 D．以上都不对9、在一般输入数据的程序里，输入多多少少会影响到算法的计算复杂度，为了消除这种影响可用（ B ）对输入进行预处理。

算法分析与设计期中练习一、选择题1. 实践表明可操作性最好且最有实际价值的是（B）情况下的时间复杂性。

A.最好B.最坏C.平均D.特殊2. 算法的时间复杂性函数用T(n)表示，其中参数n是指（ A ）。

A.问题规模B.运行时间C.输入量D.输出量3. 函数105logn2+n2logn+n3的渐近表达式为（C）。

A.logn2B.n2lognC.n3D. 1054. 二分搜索算法中，如果待查找元素x不在已排好序的n个元素中，则完成该搜索任务需用（B）时间。

A.O(nlogn)B.O(logn)C.O(n)D.O(n2)5. Strassen矩阵乘法问题中，改进算法的计算复杂性关键在于（ A ）。

A.减少矩阵乘法B.增加矩阵乘法C.减少矩阵加法D.增加矩阵加法6. 最优子结构和重叠子问题是（A）算法的两个基本要素。

A.动态规划B. 贪心C.分支限界D. 分治7. 使用贪心算法解决活动安排问题时使用了（B）优先的贪心选择策略。

A.最早开始活动B.最早结束活动C.时间最短活动D.时间最长活动8. f(n)= log7n,g(n)= 100logn，满足f(n)= （ B ）(g(n))。

A. OB.ΩC.Θ9. f(n)= logn8,g(n)= log(100n)，满足f(n)= （C）(g(n))。

A. OB.ΩC.Θ10. f(n)= 30(logn)10,g(n)= 30n5,满足f(n)= （A）(g(n))。

A. OB.ΩC.Θ11. f(n)= 105n,g(n)= log10n,满足f(n)= （ C ）(g(n))。

A. OB.ΩC.Θ12. f(n)= 4n ,g(n)= 410(3n),满足f(n)= （B）(g(n))。

A. OB.ΩC.Θ13. 贪心法解装载问题时，采用的解题策略是（B）。

P95A.平均分配两艘轮船的载重B. 按集装箱重量从轻至重装船C. 将第一艘轮船尽可能装满D. 将第二艘轮船尽可能装满14. 用回溯法解0-1背包问题时，解空间可构造为（C）的形式。

《算法设计与分析》答卷说明： 1、考试方式闭卷2、满分100分题号一二三四五六七总分总分人分数得分评卷人一、单项选择题（每小题2分，共20分）1、下面关于NP问题说法正确的是（）。

A 、NP问题都是不可能解决的问题B 、P类问题包含在NP类问题中C 、NP完全问题是P类问题的子集D 、NP类问题包含在P类问题中2、能采用贪心算法求最优解的问题，一般具有的重要性质为：（）A、最优子结构性质与贪心选择性质B、重叠子问题性质与贪心选择性质C、最优子结构性质与重叠子问题性质D、预排序与递归调用3、实现合并排序利用的算法是（）。

A、分治策略B、动态规划法C、贪心法D、回溯法4、以下不可以使用分治法求解的是（）。

A、棋盘覆盖问题B、选择问题C、归并排序D、0/1背包问题5、记号O的定义正确的是（）。

A、O(g(n)) = { f(n) | 存在正常数c和n0使得对所有n≥n0有：0≤ f(n) ≤cg(n) }；B、O(g(n)) = { f(n) | 存在正常数c和n0使得对所有n≥n0有：0≤ cg(n) ≤f(n) }；C、O(g(n)) = { f(n) | 对于任何正常数c>0，存在正数和n>0使得对所有n≥n0有：0 ≤f(n)<cg(n) }；D、O(g(n)) = { f(n) | 对于任何正常数c>0，存在正数和n>0使得对所有n≥n0有：0 ≤cg(n) < f(n) }；6、使用分治法求解不需要满足的条件是（）。

A、子问题必须是一样的B、子问题不能够重复C、子问题的解可以合并D、原问题和子问题使用相同的方法解7、以下关于渐进记号的性质是正确的有：（）A、f(n)(g(n)),g(n)(h(n))f(n)(h(n))=Θ=Θ⇒=ΘB、f(n)O(g(n)),g(n)O(h(n))h(n)O(f(n))==⇒=C、O(f(n))+O(g(n)) = O(min{f(n),g(n)})D、f(n)O(g(n))g(n)O(f(n))=⇔=8、衡量一个算法好坏的标准是（）。

算法设计分析期中试题.pdf《算法设计与分析》期中试卷一、叙述分治算法的基本思想及一般算法设计模式；二、叙述动态规划算法的基本步骤及动态规划算法的基本要素；三、改进课本P74的Lcs算法，使改进算法不用数组b亦可在O（m+n）的时间内构造最长公共序列；四、求下列函数的渐近表达式(1). 3n2+10n(2).n2/10+2n(3)21+1/n(4)logn3(5)10log3n五、对于下列各组函数发f（n）和g（n），确定f（n）=O(（g(n)）)或者f（n）= (（g(n)）)或者f（n）=θ(（g(n)）)，并简述理由(1). f（n）=logn2 , g(n)=logn+5;(2). f（n）=logn2 , g(n)= √n;(3), f（n）=n, g(n)= logn2;(4). f（n）=nlogn+n,g(n)=logn;(5). f（n）=10.g(n)=log10;(6). f（n）=log2n g(n)=logn(7). f（n）=2n g(n)= 3n;(8). f（n）=2n g(n)= 100n2;六、设a[0:n-1]是已排好序的数组，请改写二分搜索算法，使得当搜索元素x不再数组中时，返回小于x的最大元素位置i和大于x 的最小元素位置j。

当搜索元素在数组中时，i和j相同，均为x 在数组中的位置七、设a[0:n-1]是有n个元素的数组，k（0<=k<=n-1）是非负整数。

试设计一个算法将子数组a[0:k]与a[k+1:n-1]换位。

要求算法在最坏的情况下耗时O(n),且只用到O(1)的辅助空间。

八、在一个由元素组成的表中出现次数最多的元素称为众数。

试写一个寻找众数的算法，并分析其计算复杂性。

九、设计一个O(n2)时间的算法，找出由n个数组成的序列的最长单调递增子序列。

十、给定n中物品和一背包，物品i的重量是ω，体积是b i，其价值为v i ，背包的容量为C，容积为D。

一、解答题1.机器调度问题。

问题描述：现在有n件任务和无限多台的机器，任务可以在机器上得到处理。

每件任务的开始时间为s i，完成时间为f i，s i<f i 。

[s i，f i]为处理任务i 的时间围。

两个任务i，j重叠指两个任务的时间围区间有重叠，而并非指i，j的起点或终点重合。

例如：区间[1，4]与区间[2，4]重叠，而与[4，7]不重叠。

一个可行的任务分配是指在分配中没有两件重叠的任务分配给同一台机器。

因此，在可行的分配中每台机器在任何时刻最多只处理一个任务。

最优分配是指使用的机器最少的可行分配方案。

问题实例：若任务占用的时间围是{[1，4]，[2，5]，[4，5]，[2，6]，[4，7]}，则按时完成所有任务最少需要几台机器？（提示：使用贪心算法）画出工作在对应的机器上的分配情况。

3. 单源最短路径的求解。

问题的描述：给定带权有向图（如下图所示）G =(V,E)，其中每条边的权是非负实数。

另外，还给定V中的一个顶点，称为源。

现在要计算从源到所有其它各顶点的最短路长度。

这里路的长度是指路上各边权之和。

这个问题通常称为单源最短路径问题。

解法：现采用Dijkstra算法计算从源顶点1到其它顶点间最短路径。

请将此过程填入下表中。

110030maxint10-{1}初始dist[5]dist[4]dist[3]dist[2]uS迭代7. 最长公共子序列问题：给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。

由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。

用c[i][j]记录序列Xi和Yj的最长公共子序列的长度。

其中，Xi={x1,x2,…,xi}；Yj={y1,y2,…,yj}。

当i=0或j=0时，空序列是Xi和Yj的最长公共子序列。

故此时C[i][j]=0。

其它情况下，由最优子结构性质可建立递归关系如下：00,0 [][][1][1]1,0;max{[][1],[1][]},0;i ji ji jc i j c i j i j x yc i j c i j i j x y⎧==⎪=--+>=⎨⎪-->≠⎩在程序中，b[i][j]记录C[i][j]的值是由哪一个子问题的解得到的。

算法分析与设计试题及答案一、选择题1. 下列哪个是属于分治算法的例子？A. 冒泡排序B. 归并排序C. 顺序查找D. 选择排序答案：B2. 在排序算法中，时间复杂度最优的是：A. 冒泡排序B. 插入排序C. 归并排序D. 快速排序答案：C3. 哪个不是动态规划的特点？A. 具有重叠子问题B. 通过递归求解C. 需要保存子问题的解D. 具有最优子结构答案：B4. 在图的广度优先搜索算法中，使用的数据结构是：A. 栈B. 队列C. 数组D. 堆栈答案：B5. 在最小生成树算法中，下列哪个不属于贪心策略？A. Kruskal算法B. Prim算法C. Dijkstra算法D. Prim-Kruskal混合算法答案：C二、简答题1. 请简述分治算法的思想和应用场景。

答案：分治算法的思想是将原问题分解成若干个规模较小且类似的子问题，然后解决子问题，最后将子问题的解合并得到原问题的解。

其应用场景包括排序算法（如归并排序、快速排序）、搜索算法（如二分查找）等。

2. 什么是动态规划算法？请给出一个动态规划算法的示例。

答案：动态规划算法是一种通过将问题分解成子问题并解决子问题来解决复杂问题的方法。

它的特点是具有重叠子问题和最优子结构性质。

以斐波那契数列为例，可以使用动态规划算法求解每一项的值，而不需要重复计算。

3. 图的深度优先搜索和广度优先搜索有什么区别？答案：图的深度优先搜索（Depth First Search，DFS）是一种先访问子节点再访问兄弟节点的遍历算法，通常使用递归或者栈实现。

而广度优先搜索（Breadth First Search，BFS）则是以层次遍历的方式展开搜索，使用队列来实现。

DFS更适合用于搜索路径，BFS则适用于寻找最短路径等。

4. 请简述贪心算法的特点及其应用场景。

答案：贪心算法的特点是每一步都采取当前状态下最优的选择，以期望得到全局最优解。

然而，贪心算法并不一定能求解所有问题的最优解，但对于一些特定问题，贪心算法往往能得到近似最优解。

算法分析与设计试题 HEN system office room 【HEN16H-HENS2AHENS8Q8-HENH1688】一、选择题（20分）1．最长公共子序列算法利用的算法是（B ）。

A、分支界限法B、动态规划法C、贪心法D、回溯法2．实现棋盘覆盖算法利用的算法是（A ）。

A、分治法B、动态规划法C、贪心法D、回溯法3.下面是贪心算法的基本要素的是（C ）。

A、重叠子问题B、构造最优解C、贪心选择性质D、定义最优解4.回溯法的效率不依赖于下列哪些因素（ D ）A.满足显约束的值的个数B. 计算约束函数的时间C. 计算限界函数的时间D. 确定解空间的时间5.下面哪种函数是回溯法中为避免无效搜索采取的策略（B ）A．递归函数 B.剪枝函数C。

随机数函数 D.搜索函数6．采用最大效益优先搜索方式的算法是（A ）。

A、分支界限法B、动态规划法C、贪心法D、回溯法7．贪心算法与动态规划算法的主要区别是（B ）。

A、最优子结构B、贪心选择性质C、构造最优解D、定义最优解8. 实现最大子段和利用的算法是（B ）。

A、分治策略B、动态规划法C、贪心法D、回溯法9.优先队列式分支限界法选取扩展结点的原则是（C ）。

A、先进先出B、后进先出C、结点的优先级D、随机10.下列算法中通常以广度优先方式系统搜索问题解的是（A ）。

A、分支限界法B、动态规划法C、贪心法D、回溯法二、填空题（22分每空2分）1.算法是由若干条指令组成的有穷序列，且要满足输入、输出、确定性和有限性四条性质。

2、大整数乘积算法是用分治法来设计的。

3、以广度优先或以最小耗费方式搜索问题解的算法称为分支限界法。

4、舍伍德算法总能求得问题的一个解。

5、贪心选择性质是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。

6.快速排序template<class Type>void QuickSort (Type a[], int p, int r){if (p<r) {int q=Partition(a,p,r);QuickSort (a,p,q-1); 哈密顿环问题的算法可由回溯法设计实现。

一、函数渐进阶。

对于下列各组f(x)和g(x)，确定他们的关系（15分）a)f(x)=log n10+1；g(x)= log n – 10b)f(x)=5 n10；g(x)=10nc)f(x)=；g(x)= log n +5二、设n个不同的整数排好序后存于T[0:n-1]中。

若存在下标i，0≤i<n，使得T[i]=i，试设计一个时间复杂度为O(logn)的算法找到该下标（15分），并用C/C++编程实现（10分）。

三、分别用贪心算法（20分）、动态规划法（20分）设计求解0-1背包问题的算法。

要求：1.说明算法策略（每种方法5分）；2.主要算法步骤（10分）；3.分析算法的时间复杂度（5分）四、试设计解决TSP问题的贪心算法（10分），分析时间复杂度（5分），试分析是否存在O(n2log n)的有效算法（5分）。

1函数渐进阶。

对于下列各组f(x)和g(x)，确定他们的关系（15分）a)f(x)=log n10+1；g(x)= log n – 10b)f(x)=5 n10；g(x)=10nc)f(x)=；g(x)= log n +52设n个不同的整数排好序后存于T[0:n-1]中。

若下标i，0≤i<n，使得T[i]=i，试设计一个时间复杂度为O(logn)的存在算法找到该下标（15分），并用C/C++编程实现（10分）。

解答：由题可知，数组T[ ]是排列好的整数集。

可以用二分搜索的算法对问题进行操作。

取中间值T[mid],如果T[mid]=mid则可以返回mid；如果T[mid]<mid在mid+1到n-1之间进行上述操作；如果T[mid]>mid在0到mid-1之间进行上述操作。

Int Findi(int T[],int m,int n){Int mid=(m+n)/2;If (T[mid]==mid) return mid;else if(T[mid]>mid) return Findi(T[],m,mid-1);else return Findi(T[],mid+1,n);}算法设计：输入：一个数组T[ ]，起始地址m，末端地址n比较指定数组位置的中间元素T[(m+n)/2]与中间地址(m+n)/2.1）如果T[(m+n)/2]等于(m+n)/2，则返回(m+n)/2；2）如果T[(m+n)/2]大于(m+n)/2，则返回在数组T[ ]中m位到(m+n)/2-1之间进行此算法的返回值；3）如果T[(m+n)/2]小于(m+n)/2，则返回在数组T[ ]中(m+n)/2+1到n之间进行此算法的返回值；输出：一个值，若存在则返回i；若不存在则返回0.3分别用贪心算法（20分）、动态规划法（20分）设计求解0-1背包问题的算法。

《算法设计与分析》试卷及答案算法设计与分析考试复习试卷《算法设计与分析》试卷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 = 小于或等于x的最大整数（x的高限）5、汉诺塔（Hanoi）问题中令h（n）为从A移动n个金片到C 上所用的次数，则递归方程为__________，其初始条件为__________，将n个金片从A柱移到C柱上的移动次数是__________；设菲波那契（Fibonacci）数列中Fn为第n个月时兔子的对数，则有递归方程为__________，其中F1=F2=__________。

A、Fn=Fn-1+Fn-2B、h（n）= 2h（n-1）+1C、1D、h（1）= 1E、h（n）=2n-1F、06、在一个有向连通图中（如下图所示），找出点A到点B的一条最短路为____ ______。

A、最短路：1→3→5→8→10，耗费：20B、最短路：1→4→6→9→10，耗费：16。

算法设计与分析试卷一、填空题（20分，每空2分）1、算法的性质包括输入、输出、＿＿＿、有限性。

2、动态规划算法的基本思想就将待求问题＿＿＿＿＿、先求解子问题，然后从这些子问题的解得到原问题的解。

3、设计动态规划算法的4个步骤：（1）找出＿＿＿＿，并刻画其结构特征。

（2）＿＿＿＿＿＿＿。

（3）＿＿＿＿＿＿＿。

（4）根据计算最优值得到的信息，＿＿＿＿＿＿＿。

4、流水作业调度问题的johnson算法：（1）令N1=＿＿＿,N2={i|ai>=bj};（2）将N1中作业依ai的＿＿＿。

5、对于流水作业高度问题，必存在一个最优调度π，使得作业π（i）和π（i+1）满足Johnson 不等式＿＿＿＿＿。

6、最优二叉搜索树即是＿＿＿的二叉搜索树。

二、综合题（50分）1、当（a1,a2,a3,a4,a5,a6）=(-2,11,-4,13,-5,-2)时，最大子段和为∑ak(2<=k<=4)＿＿＿＿（5分）2、由流水作业调度问题的最优子结构性质可知，T（N，0）=＿＿＿＿＿＿（5分）3、最大子段和问题的简单算法(10分)int maxsum(int n,int *a,int & bestj){intsum=0;for (int i=1;i<=n;i++)for (int j=i;j<=n;j++)int thissum=0;for(int k=i;k<=j;k++)＿＿＿＿＿;if(thissum>sum){sum=thissum;＿＿＿＿＿＿；bestj=j;}}return sum;}4、设计最优二叉搜索树问题的动态规划算法OptimalBinarysearchTree? (15分)Void OptimalBinarysearchTree(int a,int n,int * * m, int * * w){for(int i=0;i<=n;i++) {w[i+1][i]=a[i]; m[i+1][i]=＿＿＿＿;}for(int r=0;r<n;r++)for(int i=1;i<=n-r;i++){int j=i+r;w[i][j]=w[i][j-1]+a[j]+b[j];m[i][j]=＿＿＿＿＿＿;s[i][j]=i;for(int k=i+1;k<=j;k++){int t=m[i][k-1]+m[k+1][j];if(＿＿＿＿＿) {m[i][j]=t; s[i][j]=k;}}m[i][j]=t; s[i][j]=k;}}5、设n=4, (a1,a2,a3,a4)=(3,4,8,10), (b1,b2,b3,b4)=(6,2,9,15) 用两种方法求4个作业的最优调度方案并计算其最优值？（15分）三、简答题（30分）1、将所给定序列a[1:n]分为长度相等的两段a[1:n/2]和a[n/2+1:n]，分别求出这两段的最大子段和，则a[1:n]的最大子段和有哪三种情形？(10分)答：2、由0——1背包问题的最优子结构性质，可以对m（i,j）建立怎样的递归式? (10分)3、0——1背包求最优值的步骤分为哪几步？（10分）参考答案：填空题：确定性分解成若干个子问题最优解的性质递归地定义最优值以自底向上的方式计算出最优值构造最优解{i|ai<bi} ai的非减序排序；将N2中作业依bi的非增序排序min{bπ(i),aπ(i+1)}≥min{bπ(i+1),aπ(i)}最小平均查找长度综合题：20 min{ai+T(N-{i},bi)}(1=<i<=n) thissum+=a[k] besti=i 0 m[i+1][j] t<m[i][j]法一：min(ai,bj)<=min(aj,bi)因为min(a1,b2)<=min(a2,b1) 所以1→2 (先1后2) 由min(a1,b3)<=min(a3,b1) 得1→3 （先1后3）同理可得：最后为1→3→4→2法二：johnson算法思想 N1＝{1，3，4} N2＝{2} N¹1＝{1，3，4} N¹2＝{2} 所以 N¹1→N¹2 得：1→3→4→2简答题：1 、（1）a[1:n]的最大子段和与a[1:n/2]的最大子段和相同。

算法设计与分析试卷(一)及答案算术分析试卷(卷一)课程名称算术分析编号问题编号1234总分评估师一、填空(每题3分，共30分)1.算法的优点和缺点可以用总和来衡量。

2.这种不断回头寻找目标的方法叫做。

3.直接或间接调用自己的算法称为。

4.q符号用算法复杂性的表示来表示。

5.分治法产生的子问题通常是它提供了使用的便利。

6.建立计算模型的目的是使。

7.以下步骤的顺序是。

①调试程序②分析问题③设计算法④编程。

8.最优子结构性质的含义是。

9.贪婪算法从初始阶段开始，每个阶段总是做出贪婪的选择。

10.拉斯维加斯算法一定找到了解决方案。

二、选择题(每题2分，共20分)1.霍夫曼编码可以用()算法实现。

分治策略b，动态规划方法c，贪婪方法d，回溯方法2、以下不是基本的计算模型()。

随机存取存储器、只读存储器、只读存储器3.在以下算法中，最佳解决方案通常是从上到下求解()。

一、分治法b、动态规划法c、贪心法d、回溯法考试科目: 类别:姓名:学生编号:-一、填空(每题3分，共30分)1.算法的优点和缺点可以用总和来衡量。

2.这种不断回头寻找目标的方法叫做。

3.直接或间接调用自己的算法称为。

4.q符号用算法复杂性的表示来表示。

5.分治法产生的子问题通常是它提供了使用的便利。

6.建立计算模型的目的是使。

7.以下步骤的顺序是。

①调试程序②分析问题③设计算法④编程。

8.最优子结构性质的含义是。

9.贪婪算法从初始阶段开始，每个阶段总是做出贪婪的选择。

10.拉斯维加斯算法一定找到了解决方案。

二、选择题(每题2分，共20分)1.霍夫曼编码可以用()算法实现。

分治策略b，动态规划方法c，贪婪方法d，回溯方法2、以下不是基本的计算模型()。

随机存取存储器、只读存储器、只读存储器3.在以下算法中，最佳解决方案通常是从上到下求解()。

一、分治法b、动态规划法c、贪心法d、回溯法考试科目:类别:姓名:学生编号:最佳解决方案是:参考答案我填补空白1.空间复杂性时间复杂性2.追溯方法3.递归算法4.渐进定边界还是紧致边界5、小模式递归技术的原始问题6.问题的计算复杂性分析有一个共同的客观标准。

算法设计与分析复习题目及答案一、算法的基本概念1、什么是算法？算法是指解决特定问题的一系列明确步骤，它具有确定性、可行性、有穷性、输入和输出等特性。

例如，计算两个数的最大公约数的欧几里得算法，就是通过反复用较小数去除较大数，然后将余数作为新的较小数，直到余数为 0，此时的除数就是最大公约数。

2、算法的复杂度包括哪些？它们的含义是什么？算法的复杂度主要包括时间复杂度和空间复杂度。

时间复杂度是指算法执行所需要的时间量，通常用大 O 记号来表示。

例如，一个算法的时间复杂度为 O(n)，表示其执行时间与输入规模 n成正比。

空间复杂度则是算法在运行过程中所需要的额外存储空间的大小。

比如说，一个算法需要创建一个大小为 n 的数组来存储数据，那么其空间复杂度就是 O(n)。

二、分治法1、分治法的基本思想是什么？分治法的基本思想是将一个规模为 n 的问题分解为 k 个规模较小的子问题，这些子问题相互独立且与原问题结构相同。

然后分别求解这些子问题，最后将子问题的解合并得到原问题的解。

2、请举例说明分治法的应用。

例如归并排序算法。

将一个未排序的数组分成两半，对每一半分别进行排序，然后将排好序的两部分合并起来。

其时间复杂度为 O(nlogn)，空间复杂度为 O(n)。

三、动态规划1、动态规划的基本步骤有哪些？动态规划的基本步骤包括：（1）定义问题的状态。

（2）找出状态转移方程。

（3）确定初始状态。

（4）计算最终的解。

2、解释最长公共子序列问题，并给出其动态规划解法。

最长公共子序列问题是指找出两个序列的最长公共子序列的长度。

假设我们有两个序列 X 和 Y，用 dpij 表示 X 的前 i 个字符和 Y 的前 j 个字符的最长公共子序列长度。

状态转移方程为：如果 Xi 1 ＝＝ Yj 1，则 dpij ＝ dpi 1j 1 ＋ 1否则 dpij ＝ max(dpi 1j, dpij 1)四、贪心算法1、贪心算法的特点是什么？贪心算法在每一步都做出当前看起来最优的选择，希望通过这种局部最优选择达到全局最优解。

试题纸（A卷）课程名称：算法设计与分析适用专业年级： 2008级计算机、电本考生学号：考生姓名：………………………………………………………………………………………………………………………题号一二三四总分分数一、填空题（10空×2分，共20分）1、算法在运行时占有的机器资源的量称为算法复杂性，主要包括（时间）和（空间）。

2、当一个算法的运行时间为n2+n+1时，由于n2+n+1与n2的数量级相等，则称n2为这个算法的（时间复杂度）。

3、多项式A(n)=a m n m+…+ a2n2+ a1n+ a0的上界为（）。

4、递归算法设计的关键在于找出（递归关系）和（最小问题的解）。

5、（无后向性）是问题能用贪婪算法或动态规划方法求解的前提。

6、拆半查找、合并排序、二叉树遍历等算法中均采用了（分而治之）策略。

7、回溯算法是尝试搜索算法中最为基本的一种算法，其采用了一种走不通就掉头的思想作为其控制结构。

8、用分支限界法解决布线问题时，对问题解空间搜索尝试结束的标志是（）。

二、判断题（10题×2分，共20分）1.若c是正常数，则O(cf(n))=O(f(n))。

v2.在最好情况下、最坏情况下、平均情况下的时间复杂度中，可操作性最好的且最有实际价值的，是最坏情况下的时间复杂度。

x3.好的算法在很大程度上取决于问题中数据所采用的数据结构。

v4.迭代模型是通过小规模问题的解逐步求解大规模问题的解，正好与递归算法设计相反。

v5.用贪婪算法解决零钱兑换问题时，总能找到问题的最优解。

x6.适用动态规划算法解决问题应该具有最优化原理和子问题重叠。

x7.深度优先搜索算法可以搜索到问题所有可能的解方案。

x8.解决马的遍历问题采用回溯法，对解空间树的搜索采用广度优先搜索方式v9.分支限界法的求解目标是找出满足约束条件的一个解或是在满足约束条件的解中找出使用某一目标函数值达到极大或极小的解。

x三、简答题（3题×6分，共18分）1、叙述分治算法和动态规划算法的基本思想，并比较两种算法的异同。

《算法分析与设计》一、解答题 1. 机器调度问题。

问题描述：现在有n 件任务和无限多台的机器，任务可以在机器上得到处理。

每件任务的开始时间为s i ，完成时间为f i ，s i <f i 。

[s i ，f i ]为处理任务i 的时间范围。

两个任务i ，j 重叠指两个任务的时间范围区间有重叠，而并非指i ，j 的起点或终点重合。

例如：区间[1，4]与区间[2，4]重叠，而与[4，7]不重叠。

一个可行的任务分配是指在分配中没有两件重叠的任务分配给同一台机器。

因此，在可行的分配中每台机器在任何时刻最多只处理一个任务。

最优分配是指使用的机器最少的可行分配方案。

问题实例：若任务占用的时间范围是{[1，4]，[2，5]，[4，5]，[2，6]，[4，7]}，则按时完成所有任务最少需要几台机器？（提示：使用贪心算法）画出工作在对应的机器上的分配情况。

2. 已知非齐次递归方程：f (n)bf (n 1)g(n)f (0)c =-+⎧⎨=⎩，其中，b 、c 是常数，g(n)是n 的某一个函数。

则f(n)的非递归表达式为：nnn i i 1f (n)cb b g(i)-==+∑。

现有Hanoi 塔问题的递归方程为：h(n)2h(n 1)1h(1)1=-+⎧⎨=⎩，求h(n)的非递归表达式。

解：利用给出的关系式，此时有：b=2, c=1, g(n)=1, 从n 递推到1，有：n 1n 1n 1i i 1n 1n 22n h(n)cbb g(i)22 (22121)----=--=+=+++++=-∑3. 单源最短路径的求解。

问题的描述：给定带权有向图（如下图所示）G =(V,E)，其中每条边的权是非负实数。

另外，还给定V 中的一个顶点，称为源。

现在要计算从源到所有其它各顶点的最短路长度。

这里路的长度是指路上各边权之和。

这个问题通常称为单源最短路径问题。

解法：现采用Dijkstra 算法计算从源顶点1到其它顶点间最短路径。

一。

选择题1、二分搜索算法是利用（ A ）实现的算法。

A、分治策略B、动态规划法C、贪心法D、回溯法2、下列不是动态规划算法基本步骤的是（ A ）。

A、找出最优解的性质B、构造最优解C、算出最优解D、定义最优解3、最大效益优先是（ A ）的一搜索方式。

A、分支界限法B、动态规划法C、贪心法D、回溯法4、在下列算法中有时找不到问题解的是（ B ）。

A、蒙特卡罗算法B、拉斯维加斯算法C、舍伍德算法D、数值概率算法5. 回溯法解旅行售货员问题时的解空间树是（ B ）。

A、子集树B、排列树C、深度优先生成树D、广度优先生成树6．下列算法中通常以自底向上的方式求解最优解的是（ B ）。

A、备忘录法B、动态规划法C、贪心法D、回溯法7、衡量一个算法好坏的标准是（C ）。

A 运行速度快B 占用空间少C 时间复杂度低D 代码短8、以下不可以使用分治法求解的是（D ）。

A 棋盘覆盖问题B 选择问题C 归并排序D 0/1背包问题9. 实现循环赛日程表利用的算法是（ A ）。

A、分治策略B、动态规划法C、贪心法D、回溯法10、下列随机算法中运行时有时候成功有时候失败的是（C ）A 数值概率算法B 舍伍德算法C 拉斯维加斯算法D 蒙特卡罗算法11．下面不是分支界限法搜索方式的是（ D ）。

A、广度优先B、最小耗费优先C、最大效益优先D、深度优先12．下列算法中通常以深度优先方式系统搜索问题解的是（ D ）。

A、备忘录法B、动态规划法C、贪心法D、回溯法13.备忘录方法是那种算法的变形。

（ B ）A、分治法B、动态规划法C、贪心法D、回溯法14．哈弗曼编码的贪心算法所需的计算时间为（ B ）。

A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）15．分支限界法解最大团问题时，活结点表的组织形式是（ B ）。

A、最小堆B、最大堆C、栈D、数组16．最长公共子序列算法利用的算法是（ B ）。

A、分支界限法B、动态规划法C、贪心法D、回溯法17．实现棋盘覆盖算法利用的算法是（ A ）。