算法分析作业

东师21秋学期《算法分析与设计》在线作业1（答案）一、单选题1. 字符串”China Beijing”的长度是（）A.12B. 13C. 14D. 15正确答案. B2. 一棵二叉树中共有70个叶子结点与80个度为1的结点，则该二叉树的总结点数为（）。

A.219B. 221C. 229D. 231正确答案. A3. 栈和队列的共同点是（）A.都是先进先出B. 都是先进后出C. 只允许在端点处插入和删除元素D. 没有共同点正确答案. C4. 使用简单选择排序法对n个数进行排序要进行()趟比较。

A. NB. n-1C. n+1D. 不一定正确答案. B5. 下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是()。

A. 选择排序法B. 插入排序法C. 快速排序法D. 堆积排序法正确答案. A6. 图中有关路径的定义是（）。

A. 由顶点和相邻顶点序偶构成的边所形成的序列B. 由不同顶点所形成的序列C. 由不同边所形成的序列D. 上述定义都不是正确答案. A7. 执行memset(s,'a',4)后，s的值为（）。

A. "aaaa"B. "a4"C. "4a"D. "eeee"正确答案. A8. 一个算法的评价主要从空间复杂度和()来考虑。

A. 时间复杂度B. 算法有效性C. 算法有穷性D. 算法可读性正确答案. A9. 下面的时间复杂度按数量级递增的顺序排列，正确的是注释从功能上可以分为()。

A. 平方阶O(n2)，对数阶O(log2n)，指数阶O(2n)B. 线性对数阶O(nlog2n)，指数阶O(2n)，立方阶O(n3)C. 常数阶O(1)，线性阶O(n)，指数阶O(2n)D. k次方阶O(nk)，指数阶O(2n)，对数阶O(log2n)正确答案. C10. ()嵌在源程序体中，用于描述其后的语句或程序段做什么工作，也就是解释下面要做什么，或是执行了下面的语句会怎么样。

《算法分析与设计》作业( 一)本课程作业由两部分组成。

第一部分为”客观题部分”, 由15个选择题组成, 每题1分, 共15分。

第二部分为”主观题部分”,由简答题和论述题组成, 共15分。

作业总分30分, 将作为平时成绩记入课程总成绩。

客观题部分:一、选择题( 每题1分, 共15题)1、递归算法: ( C )A、直接调用自身B、间接调用自身C、直接或间接调用自身 D、不调用自身2、分治法的基本思想是将一个规模为n的问题分解为k个规模较小的字问题, 这些子问题: ( D )A、相互独立B、与原问题相同C、相互依赖D、相互独立且与原问题相同3、备忘录方法的递归方式是:( C )A、自顶向下B、自底向上C、和动态规划算法相同D、非递归的4、回溯法的求解目标是找出解空间中满足约束条件的:( A )A、所有解B、一些解C、极大解D、极小解5、贪心算法和动态规划算法共有特点是: ( A )A、最优子结构B、重叠子问题C、贪心选择D、形函数6、哈夫曼编码是: ( B)A、定长编码B、变长编码C、随机编码D、定长或变长编码7、多机调度的贪心策略是: ( A)A、最长处理时间作业优先B、最短处理时间作业优先C、随机调度D、最优调度8、程序能够不满足如下性质: ( D )A、零个或多个外部输入B、至少一个输出C、指令的确定性D、指令的有限性9、用分治法设计出的程序一般是: ( A )A、递归算法B、动态规划算法C、贪心算法D、回溯法10、采用动态规划算法分解得到的子问题:( C )A、相互独立B、与原问题相同C、相互依赖D、相互独立且与原问题相同11、回溯法搜索解空间的方法是: ( A )A、深度优先B、广度优先C、最小耗费优先D、随机搜索12、拉斯维加斯算法的一个显著特征是它所做的随机选性决策有可能导致算法: ( C )A、所需时间变化B、一定找到解C、找不到所需的解D、性能变差13、贪心算法能得到: ( C )A、全局最优解B、 0-1背包问题的解C、背包问题的解 D、无解14、能求解单源最短路径问题的算法是: ( A )A、分支限界法B、动态规划C、线形规划D、蒙特卡罗算法15、快速排序算法和线性时间选择算法的随机化版本是:( A )A、舍伍德算法B、蒙特卡罗算法C、拉斯维加斯算法D、数值随机化算法主观题部分:二、写出下列程序的答案( 每题2.5分, 共2题)1、请写出批处理作业调度的回溯算法。

作业调度之最短作业优先算法5例题解析例题一、某系统采用不能移动已在主存储器中作业的可变分区方式管理主存储器，现有供用户使用的主存空间100K,系统配有4台磁带机，有一批作业见下表：作业序号进输入井时间要求计算时间需要主存容量申请磁带机数110:0025分钟15K2台210:2030分钟60K1台310:3010分钟50K3台410:3520分钟10K2台510:4015分钟30K2台按计算时间最短者优先算法如下表：我的解释：系统首先装入1、2、4,但1结束时4沿未到达，因此先执行2;2执行完毕后，资源可以分配给3或5,考虑5的时间短优先分配5并执行，执行完5后，主存中只有4已就绪并等待执行，因此开始执行4,执行4的同时系统会将作业3装入主存，最后自然执行作业3;因此最后的顺序是：1\2\5\4\3作业序号进输入井时间进入主存时间开始计算时间结束计算时间周转时间解释110:0010:1010:00102525此时输入井中只有一个作业且满足资源要求，因此被选中运行。

2102010：2010：2510：5535作业2到达输入井，满足资源要求，装入主存，等到作业1运行完毕进入运行。

510:4010:5510:5511：1030由于作业3要求主存空间无法满足，因此作业4先行一步装入主存，当作业2让出处理器的同时，作业5满足资源要求进入主存就绪。

根据算法作业5先进入处理器运行最后作业3装入主存并运行平均周转时间：（25+35+30+55+70/5=43分钟 ［分析］解答本题时应注意如下几个问题：第一，系统采用的是多道程序设计技术，但没有限定并行工作的道数，因此， 只要当前尚未分配的资源可以满足在输入井中等待的某些作业的要求时，作业 调度可以按照给定的算法从中选择一个或多个作业装人主存储器；第二，采用可变分区方式管理主存储器，但没给出主存空间的分配算法，因而,只要有合适的空间就可分配，题中还规定可用移动技术来合并分散的空闲区； 第三，对磁带机采用静态分配；第四，进程调度采用可抢占的最高优先级调度算法，即对已被装人主存储器的作业而言优先级高的作业可抢占处理器执行；第五，虽然作业需要使用磁带机，但题意中已提示忽略磁带机和调度所花的时问，所以，解题时不必考虑外围设备的启动二八D 中断等复杂情况，只需把它们当作纯计算型的作业； 第六，由于没有规定什么时候开始进行作业调度，故在一般情况下只要输入井中有等待处理的作业就可按选定的算法去选择满足必要条件的作业。

《算法分析与设计》各章课后作业第一章 课后作业1. 设某算法在输入规模为n 时的计算时间为T(n)=10*2n。

若在甲台计算机上实现并完成该算法的时间为t 秒，现有一台运行速度是甲的64倍的另一台计算机乙，问在乙计算机上用同一算法在t 秒内能解决的问题的规模是多大？2.按照渐近阶从低到高的顺序排列以下表达式：4n 2，logn ，3n，20n ，2，n 2/3。

又n!应该排在哪一位？第二章 课后作业1. 用展开法求解下列递推关系：T(n)=⎩⎨⎧>+=1n )()2/(20n )1(n O n T O，写出T(n)的大O 记号表示。

2. 下面是实现在a[0]<=a[1]<=…<=a[n-1]中搜索x 的二分搜索算法，请根据二分 搜索技术在下划线处填充语句。

算法描述如下： template<class Type>public static int BinarySearch(int []a, int x, int n) { //在a[0]<=a[1]<=…<=a[n-1]中搜索 x // 找到x 时返回其在数组中的位置，否则返回-1 int left = 0; int right = n - 1; while ( ) {int middle = ;if(x == a[middle]) return ; if(x > a[middle]) left = middle + 1; else right= ; }return -1; // 未找到x}第三章课后作业1、选择题。

（1）下列算法中通常以自底向上的方式求解最优解的是（）。

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

（）A、分治法B、动态规划法C、贪心法D、回溯法（3）矩阵连乘问题的算法可由（）设计实现。

A、分支界限算法B、动态规划算法C、贪心算法D、回溯算法2．计算题。

算法分析作业 IMB standardization office【IMB 5AB- IMBK 08- IMB 2C】算法分析练习题（一）一、选择题1、二分搜索算法是利用（A ）实现的算法。

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

A、找出最优解的性质B、构造最优解C、算出最优解D、定义最优解3．下列算法中通常以自底向上的方式求解最优解的是（B ）。

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

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

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

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

（ B ）A、分治法B、动态规划法C、贪心法D、回溯法8．最长公共子序列算法利用的算法是（B ）。

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

A、分治法B、动态规划法C、贪心法D、回溯法10. 矩阵连乘问题的算法可由（B）设计实现。

A、分支界限算法B、动态规划算法C、贪心算法D、回溯算法11、Strassen矩阵乘法是利用（A ）实现的算法。

A、分治策略B、动态规划法C、贪心法D、回溯法12、使用分治法求解不需要满足的条件是（A ）。

A 子问题必须是一样的B 子问题不能够重复C 子问题的解可以合并D 原问题和子问题使用相同的方法解13、下列算法中不能解决0/1背包问题的是（A ）A 贪心法B 动态规划C 回溯法D 分支限界法14．实现合并排序利用的算法是（A ）。

A、分治策略B、动态规划法C、贪心法D、回溯法15．下列是动态规划算法基本要素的是（D ）。

A、定义最优解B、构造最优解C、算出最优解D、子问题重叠性质16．下列算法中通常以自底向下的方式求解最优解的是（B ）。

算法理论、教改类题目学习大量相关算法（程序），总结出对应方法的一些特点，将其写成论文形式，并以足够的例子作为佐证。

24.论分治法、动态规划、贪心法的区别 25.论递归程序向非递归程序的转换 26.论应用型本科院校算法课程的教学目标和教学方法 27.论二叉树在计算机科学与技术中的应用 28.数据库索引的算法解释 29.论贪心法的适用范围 30.解空间搜索方法的选择依据 31.分治法算法分析综述
算法应用、算法研究类题目查阅大量相关资料，对相关内容给出初步的结果。

31.基于UCCI的中国象棋对弈引擎开发技术研究 32.五子棋对弈关键技术研究33.黑白棋对弈关键技术研究 34.数独初始局面生成算法研究 35.支持按文件名搜索的索引构造技术研究 36.通用回溯算法演示系统设计 37.通用分支限界算法演示系统设计 38.通用排序算法演示系统设计 39.通用动态规划算法演示系统设计
40.论文阅读和翻译类题目• 给出一个英文文献，用准确的语言将其翻译为中文，不需要逐字逐句翻译，但主要观点、算法思想和算法过程表述清楚、准确、充分。

格式要求• 论文正文中不得出现大段代码（超过10行）• 标题样式需规范• 参考文献不低于10篇，参考文献格式和标注位置须规范。

算法分析与设计作业及参考答案作业题目1、请分析冒泡排序算法的时间复杂度和空间复杂度，并举例说明其在实际中的应用场景。

2、设计一个算法，用于在一个未排序的整数数组中找到第二大的元素，并分析其时间复杂度。

3、比较贪心算法和动态规划算法的异同，并分别举例说明它们在解决问题中的应用。

参考答案1、冒泡排序算法时间复杂度：冒泡排序的基本思想是通过相邻元素的比较和交换，将最大的元素逐步“浮”到数组的末尾。

在最坏情况下，数组完全逆序，需要进行 n 1 轮比较和交换，每一轮比较 n i 次（i 表示当前轮数），所以总的比较次数为 n(n 1) ／ 2，时间复杂度为 O(n^2)。

在最好情况下，数组已经有序，只需要进行一轮比较，时间复杂度为 O(n)。

平均情况下，时间复杂度也为 O(n^2)。

空间复杂度：冒泡排序只在原数组上进行操作，不需要额外的存储空间，空间复杂度为 O(1)。

应用场景：冒泡排序算法简单易懂，对于规模较小的数组，或者对算法的简单性要求较高而对性能要求不是特别苛刻的场景，如对少量数据进行简单排序时，可以使用冒泡排序。

例如，在一个小型的学生成绩管理系统中，需要对一个班级的少量学生成绩进行排序展示，冒泡排序就可以满足需求。

2、找到第二大元素的算法以下是一种使用遍历的方法来找到未排序整数数组中第二大元素的算法：｀｀｀pythondef find_second_largest(arr)：largest ＝ arr0second_largest ＝ float(＇inf'）for num in arr:if num ＞ largest:second_largest ＝ largestlargest ＝ numelif num ＞ second_largest and num!＝ largest:second_largest ＝ numreturn second_largest｀｀｀时间复杂度分析：这个算法需要遍历数组一次，所以时间复杂度为O(n)。

CS330:Introduction To Algorithm Spring2014Lecture2:Asymptotic AnalysisTF:Xianrui Meng Scribes:Raman Bahdanouski,Ellie VialExercise1Suppose you have algorithms with thefive running times listed below.How much slower do each of these algorithms get when you(a)double the input size,or(b)increase the input size by one?1.n2;2.n3;3.100n2;4.nlog(n);5.2n;SolutionFor doubling the input:1.f(n)=n2;f (2n)=4n2.;So the running time of the algorithm gets4times slower.2.f(n)=n3;f (2n)=8n3.;So the running time of the algorithm gets8times slower.3.f(n)=100n2;f (2n)=400n2.;So the running time of the algorithm gets4times slower.4.f(n)=nlog(n);f (2n)=2n∗log(2n)=2n∗(log(n)+log(2))=2n∗log(n)+2n∗log(2).;So the runningtime of the algorithm increases by2n∗log(n)+2n∗log(2).5.f(n)=2n;f (2n)=22n;f(2n)−f(n)=22n−2n=(2n)∗(2n−1);So the running time of the algorithmgets slower by the factor of(2n−1).For increasing the input by one:1.f(n)=n2;f (n+1)=n2+2n+1.;So the running time of the algorithm increases by2n+1.2.f(n)=n3;f (n+1)=n3+3n2+3n+1.;So the running time of the algorithm increases by3n2+3n+1.3.f(n)=100n2;f (n+1)=100(n2+2n+1).;So the running time of the algorithm increases by100(2n+1).4.f(n)=nlog(n);f(n+1)=(n+1)∗log(n+1);f(n+1)−f(n)=(n+1)∗log(n+1)−nlog(n)=n∗log(n+1)+log(n+1)−nlog(n)=log(n+1)+n∗(log(n+1)−log(n));So the running time increases by log(n+1)+n∗(log(n+1)−log(n)).5.f(n)=2n;f (n+1)=2n+1=2∗2n;So the running time of the algorithm doubles.2-12-2Lecture 2:Asymptotic Analysis Exercise 3Take the following list of functions and arrange them in ascending order of growth rate.That is,if function g(n)immediately follows function f(n)in your list,it should be the case that f(n)is O(g(n)).•f 1(n )=n 2.5•f 2(n )=√2n•f 3(n )=n +10•f 4(n )=10n•f 5(n )=100n•f 6(n )=n 2log (n )SolutionWe can start approaching this problem by putting f 4and f 5at end of the list,because these functions are exponential and will grow the fastest.f 4<f 5because 10<100.Other four functions are polynomial and will grower slower then exponential.We can represent f 1and f 2as:n 2.5=n 2∗√2n ;and √2n =2n 0.5.Now,we can say that out of all polynomial functions f 2will be the slowest because it has the smallest degree.Morover,and will be bounded by f 3because it has a higher degree of 1.Furthermore,f 1and f 6will be beween exponential f 4and f 5and polynomial f 2and f 3,because polynomial functions grow slower and both f 4and f 5and have the highest degree of 2out of all other polynomial functions.And f 6will be bounded by f 1because f 6=n 2log (n )and f 1=n 2√2n and log (n )=O (√2n ).Therefore the final order will be:f 2(n )<f 3(n )<f 6(n )<f 1(n )<f 4(n )<f 5(n )Lecture2:Asymptotic Analysis2-3Exercise5Assume you have functions f and g such that f(n)is O(g(n)).For each of the following statemenets,decided whether you think it is true or false and give a proof or counterexample.1.log f(n)is O(log g(n)).2.2f(n)is O(2g(n)).3.f(n)2is O(g(n)2).Solution1.False.Disprove by counterexample.Suppose f(n)=2and g(n)=1.This holds under the assumtion stated that f(n)is O(g(n))for all n, then2<C1for any constant C>2.However,log f(n)is not in O(log g(n))in the case that f(n)=2 and g(n)=1since log2>C∗log(1)=1>C∗0for any n and any constant C.To make the statement hold,assume there exists n1such that g(n)>2for all n>n1.By this assumption,there exists some n0for all n1>n0,such that f(n)<C∗g(n)for some constant C.Thus,when n>max(n0,n1),then log f(n)<log C+log g(n)<log C∗log O(g(n)),which means that log f(n))=O(log g(n)).2.False.Disprove by counterexample.Suppose f(n)=2n and g(n)=n.This holds under the assumtion that f(n)is O(g(n))for all n, 2n<Cn for any constant C>3.However,22n is not in O(2n)in the case if f(n)=2n and g(n)=n because22n>>C∗2n⇒1>C∗0for any n>0and any constant C.Thus2f(n)>O(2g(n))3.True.∃some n0∀n>n0,s.t.f(n)<C∗g(n)for some constant C,Therefore,for any positive n,f(n)2<(C∗g(n))2because f(n)2<C2∗g(n)2for all C>0.。