《南邮算法分析与设计综合练习册期末复习题.docx》由会员分享，可在线阅读，更多相关《南邮算法分析与设计综合练习册期末复习题.docx（37页珍藏版）》请在三一办公上搜索。
1、南京邮电大学高等函授算法分析与设计综合练习习题与解答南京邮电大学继续教育学院2021年2月算法分析与设计综合练习注：此版本的综合练习册对应教材是计算机算法设计与分析，王晓东主编，电子工业出版社，2018年8月第五版，ISBN9787121344398o第一章算法概述一、填空题1.算法的复杂性有和之分。2.衡量一个算法好坏的标准是。3.某一问题可用动态规划算法求解的显著特征是.4.若序列X=B,C,A,D,B,C,D,Y=A,C,B,A,B,D,C,D,请给出序列X和Y的一个最长公共子序列。5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含。二、选择题1.最长公共子序列算法利用
2、的算法是OA.分枝界限法B.动态规划法C.贪心法D.回溯法2.实现棋盘覆盖算法利用的算法是OA.分治法B,动态规划法C.贪心法D.回溯法3.下面是贪心算法基本要素的是OA.重叠子问题B.构造最优解C.贪心选择性质D.定义最优解4.回溯法的效率不依赖于下列哪个因素OA.满足显约束的值的个数B.计算约束函数的时间C.计算限界函数的时间D.确定解空间的时间5,下面哪种函数是回溯法中为避免无效搜索采取的策略OA.递归函数B.剪枝函数C.随机数函数D.搜索函数6.关于0/1背包问题，以下描述正确的是OA.可以使用贪心法找到最优解B.能找到多项式时间的有效算法C.使用教材介绍的动态规划法可以求解任意0-1
3、背包问题D.对于同一背包与相同的物品，背包问题取得的总价值一定大于等于做0-1背包问题7.关于回溯法，下列叙述不正确的是OA.回溯法有通用解题法”之称，它可以系统地搜索一个问题的所有解或任意解B.回溯法是一种既带有系统性又带有跳跃性的搜索算法C.回溯算法需要借助队列这种结构来保存从根节点到当前节点的路径D.回溯算法在生成树解空间任一节点时，先判断该结点是否可能包含问题的解，如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向祖先结点回潮8.下面叙述正确的是OA.算法的执行效率与数据的存储结构无关B.算法的空间复杂度是指算法程序中指令（或语句）的条数C.算法的有穷性是指算法必须能在执行有限个步
4、骤之后终止D.以上三种描述都不对9.下面描述中，符合结构化程序设计风格的是OA.使用顺序、选择和重夏（循环）三种基本控制结构表示程序的控制逻辑B.模块只有一个入口，可以有多个出口C.注重提高程序的执行效率D.不使用goto语句10.下面概念中，不属于面向对象方法的是OA.对象B.继承C.类D.过程调用11.在计算机中，算法是指()A.查询方法B.加工方法C.解题方案的准确而完整的描述D.排序方法12.栈和队列的共同点是OA.都是先进后出B.都是先进先出C.只允许在端点处插入和删除元素D.没有共同点13.己知二叉树后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是OA.ced
5、baB.acbedC.decabD.deabc14.在下列几种排序方法中，要求内存量最大的是()A.插入排序B.选择排序C.快速排序D.归并排序15.在设计程序时，应采纳的原则之一是OA.程序结构应有助于读者理解B.不限制goto语旬的使用C.减少或取消注解行D.程序越短越好三、简答题1.简述算法的五个重要特性。2.写出动态规划算法的主要步骤。3.什么足哈密顿环问题？4.Prim算法的基本思想。第二章递归与分治策略一、选择题1.二分搜索算法是利用O实现的算法。A.分治策略B.动态规划法C1贪心法D.回溯法2使用分治法求解不需要满足的条件是OA.子问题必须是一样的B.子问题不能够重复C.子问题的
6、解可以合并D.原问题和子问题使用相同的方法解3.实现合并排序利用的算法是OA.分治策略B.动态规划法C.贪心法D.回溯法4.以下不属于贪心算法的是OA.Prim算法B.Kruskal算法C.Dijkstra算法D.深度优先遍历5.下面问题O不能使用贪心法解决。A.单源最短路径问题B.N皇后问题C.最小生成树问题D.背包问题6.在结构化方法中，用数据流程图(DFD)作为描述工具的软件开发阶段是OA.可行性分析B.需求分析C.详细设计D.程序编码7.在软件开发中，下面任务不属于设计阶段的是()A.数据结构设计R.给出系统模块结构C.定义模块算法D.定义需求并建立系统模型&数据库系统的核心是OA.数
7、据模型B.数据库管理系统C.软件工具D.数据库9.下列叙述中正确的是OA.数据库是一个独立的系统，不需要*作系统的支持B.数据库设计是指设计数据库管理系统C.数据库技术的根本目标是要解决数据共享的问题D.数据库系统中，数据的物理结构必须与逻辑结构一致10.下列模式中，能够给出数据库物理存储结构与物理存取方法的是OA.内模式B.外模式C.概念模式D.逻辑模式11.数据结构中，与所使用的计算机无关的是数据的()A.存储结构B.物理结构C.逻辑结构D.物理和存储结构12.栈底至栈顶依次存放元素A、B、C、D,在第五个元素E入栈前，栈中元素可以出栈，则出栈序列可能是0A.ABCEDB.DBCEAC.C
8、DABED.DCBEA13.线性表的顺序存储结构和线性表的链式存储结构分别是0A.顺序存取的存储结构、顺序存取的存储结构B.随机存取的存储结构、顺序存取的存储结构C.随机存取的存储结构、随机存取的存储结构D.任意存取的存储结构、任意存取的存储结构14.在单链表中，增加头结点的目的是OA.方便运算的实现B.使单链表至少有一个结点C.标识表结点中首结点的位置D.说明单链表是线性表的链式存储实现15.软件设计包括软件的结构、数据接口和过程设计，其中软件的过程设计是指()A.模块间的关系B.系统结构部件转换成软件的过程描述C.软件层次结构D.软件开发过程二、简答题1描述OT背包问题。2.描述分治法的基
9、本思想。3.陈述算法再最坏情况下的时间复杂度和平均复杂度，这两种评估算法复杂性的方法各有什么意义？三、分析设计题1.用分治法在互不相同的n个数xl,x2,，xn中，找出最大和最小的数。第三章动态规划一、选择题1.从排序过程是否完全在内存中显示，排序问题可分为OA.稳定排序与不稳定排序B.内排序与外排序C.直接排序与间接排序D.主排序与辅助排序2.下列O不是衡量算法的标准。A.时间效率B.空间效率C.问题难度D.适应能力3.下列叙述正确的是OA.算法的执行效率与数据的存储结构无关B.算法的空间复杂度指算法程序中指令的条数C.算法的有穷性指算法必须能在执行有限个步骤之后终止D.以上三种描述都不对4
10、.以下数据结构中不属于线性数据结构的是OA,队列B.线性表C.二叉树D.栈5.分治法设计的思想是将一个难以解决的大问题分割成规模较小的子问题，分别解决子问题，最后将子问题的解组合起来形成原问题的解。这要求原问题和子问题（）A.问题规模相同，问题性质相同B.问题规模相同，问题性质不同C.问题规模不同，问题性质相同D.问题规模不同，问题性质不同6.结构化程序设计主要强调的是OA.程序的规模B.程序的易读性C.程序的执行效率D.程序的可移植性7.在软件生命周期中，能准确地确定软件系统必须做什么和必须具备哪些功能的阶段是OA.概要设计B.详细设计C.可行性分析D.需求分析8.数据流图用于抽象描述一个软
11、件的逻辑模型，数据流图由一些特定的图符构成。下列图符名标识的图符不属于数据流图合法图符的是OA.控制流B.加工C.数据存储D.源和潭9.软件需求分析阶段的工作，可以分为四个方面：需求获取、需求分析、编写需求规格说明书以及OA.阶段性报告B.需求评审C.总结D.都不正确10.算法的空间复杂度是指OA.算法程序的长度B.算法程序中的指令条数C.算法程序所占的存储空间D.算法执行过程中所需要的存储空间IL算法分析的目的是0A.找出数据结构的合理性B.找出算法中输入和输出之间的关系C.分析算法的易懂性和可靠性D.分析算法的效率以求改进12.n个顶点的强连通图的边数至少有()A.n-tB.n(n-l)C
12、.nD.nl13.已知数据表A中每个元素距其最终位置不远，为节省时间，应采用的算法是OA.堆排序B.直接插入排序C.快速排序D.直接选择排序14.用链表表示线性表的优点是OA.便于插入和删除*作B.数据元素的物理顺序与逻辑顺序相同C.花费的存储空间较顺序存储少D.便于随机存取15下列不属于结构化分析的常用工具的是OA.数据流图B.数据字典C.判定树D.PAD图二、简答题1.为什么用分治法设计的算法一般有递归调用？2.什么是直接递归和间接递归？三、算法分析设计题1.设在顺序表中有一个对象序列V0,Vl,-,Vn-lo其中，V0,Vl,，Vi-1是己经排好序的对象。在插入Vi时，利用对半搜索寻找V
13、i的插入位置。请实现该算法VoidBInsSort(TV,intn)第四章贪心算法一、选择题1.采用最大效率优先搜索方式的算法是）A.分枝界限法B.动态规划法C1贪心法D.回溯法2.贪心算法与动态规划算法的主要区别是OA.最优子结构B.贪心选择性质C构造最优解D.定义最优解3.优先队列式分枝限界法选取扩展结点的原则是OA.先进先出B.后进先出C.结点的优先级D.随机4.应用JOhnSon法则的流水作业调度采用的算法是OA.贪心算法B-分枝限界法C.分治法D.动态规划法5.能用贪心算法求最优解的问题，一般具有的重要性质是OA.最优子结构性质与贪心选择性质B.重叠子问题性质与贪心选择性质C.最优子
14、结构性质与重叠子问题性质D.预排序与递归调用6.对建立良好的程序设计风格，下面描述正确的是()A.程序应简单、清晰、可读性好B.符号名的命名要符合语法C.充分考虑程序的执行效率D.程序的注释可有可无7.下面对对象概念描述错误的是OA.任何对象都必须有继承性B.对象是属性和方法的封装体C对象间的通讯靠消息传递D.*作是对象的动态性属性8,下面不属于软件工程的3个要素的是OA.工具B.过程C,方法D.环境9.程序流程图(PFD)中的箭头代表的是OA.数据流B.控制流C.调用关系D.组成关系10.算法一般都可以用哪几种控制结构组合而成OA.循环、分支、递归区顺序、循环、嵌套C.循环、递归、选择D.顺
15、序、选择、循环11.需求分析阶段的任务是确定OA.软件开发方法B.软件开发工具C.软件开发费用D.软件系统功能12.软件开发的结构化生命周期方法将软件生命周期划分成()A.定义、开发、运行维护B.设计阶段、编程阶段、测试阶段C总体设计、详细设计、编程调试D.需求分析、功能定义、系统设计13.在软件工程中，白箱测试法可用于测试程序的内部结构。此方法将程序看做是A.循环的集合B.地址的集合C.路径的集合D.目标的集合14.在数据管理技术发展过程中，文件系统与数据库系统的主要区别是数据库系统具有OA.数据无冗余B.数据可共享C.专门的数据管理软件D.特定的数据模型15.分布式数据库系统不具有的特点是
16、OA.分布式B.数据冗余C.数据分布性和逻辑整体性D.位置透明性和复制透明性二.填空题1.按条件f对关系R进行选择，其关系代数表达式为c2.软件调试技术集成测试法。3.在数据流图（DFD）中，带有名字的箭头表示。4.为了避免流程图在描述程序逻辑时的灵活性，提出了用方框图来代替传统的程序流程图，通常也把这种图称为O5.数据处理的最小单位是。三、简答题1.简述归并排序算法和快速排序算法的分治方法。2.背包问题的目标函数和贪心算法最优化量度相同吗？第五章回溯法一、选择题1.回溯法在问题的解空间树中，按O策略，从根结点出发搜索解空间树A.广度优先B.活结点优先C.扩展结点优先D.深度优先2.常见的两种
17、分枝限界法为OA.广度优先分枝限界法与深度优先分枝限界法B.队列式分枝限界法与堆栈式分枝限界法C.排列树法与子集树法D.队列式分枝限界法与优先队列式分枝限界法3.与算法英文单词algorithm具有相同来源的单词是OA.LogarithmB.AlgirosC.ArithmosD.Algebra4.根据执行算法的计算机指令体系结构，算法可分为OA.精确算法与近似算法B.串行算法与并行算法C.稳定算法与不稳定算法D.32位算法与64位算法5.具有10个节点的完全二叉树的高度是OA.6B.5C.3D.26.检查软件产品是否符合需求定义的过程称为0A.确认测试B.集成测试C.验证测试D.验收测试7.下
18、列工具中属于需求分析常用工具的是0A.PADB.PFDC.N-SD.DFD8.下面不属于软件设计原则的是0A.抽象B.模块化C.自底向上D.信息隐蔽9.希尔排序法属于哪一种类型的排序法0A.交换类排序法B.入类排序法C.选择类排序法D.建堆排序法10.下列关于队列的叙述中正确的是OA.在队列中只能插入数据B.在队列中只能删除数据C.队列是先进先出的线性表D.队列是先进后出的线性表11.对长度为N的线性表进行顺序查找，在最坏情况下所需要的比较次数为OA.N+1B.NC.(N+l)2D.N/212.信息隐蔽的概念与下述哪一种概念直接相关OA.软件结构定义B.模块独立性C.模块类型划分D.模拟耦合度
19、13.面向对象的设计方法与传统的的面向过程的方法有本质不同，它的基本原理是A.模拟现实世界中不同事物之间的联系B.强调模拟现实世界中的算法而不强调概念C.使用现实世界的概念抽象地思考问题从而自然地解决问题D.鼓励开发者在软件开发的绝大部分中都用实际领域的概念去思考14.在结构化方法中，软件功能分解属于下列软件开发中的阶段是()A.详细设计B.需求分析C.总体设计D.编程调试15.软件调试的目的是OA.发现错误B.改正错误C.改善软件的性能D.挖掘软件的潜能二.填空题1.以深度优先方式系统搜索问题解的算法称为o2.二分搜索算法是利用实现的算法。3.算法总是做出当前看来的选择。4.大整数乘积算法是
20、用来设计的。5.以广度优先或以最小耗费方式搜索问题解的算法称6.舍伍德算法总能求得问题的。7.贪心算法产生最优解。8.旅行售货员问题的解空间树是。三、简答题1简述最优子结构性质。2.简述回溯法的基本思想。四、算法分析设计题1.实现图着色算法。算法分析与设计综合练习参考答案薄：小参考眷案鸟锦声系符，11i4O第一章算法概述1.时间复杂性、空间复杂性2.时间复杂度高低3.该问题具有最优子结构性质4.BABCD5.一个（最优）解BACDBD4.5.6.CCA7-QQDccO.LZADA3.4.5.-x-T一1.答；确定性、有穷性、可行性、O个或多个输入、一个或多个输出。2.答：（1）问题具有最优子结
21、构性质；（2）构造最优值的递归关系表达式；（3）算法的算法描述；（4）构造最优解.3.答：一条沿着图G的N条边环行的路径，它的访问每个节点-次并且返回它的开始位置。4.答：最初生成树T为空，一次向内加入与树有最小邻边的nT条边。处理过程:首先加入代价最小一条边到T,根据各节点到T的邻接边排序，选择最小边加入。新边加入后，修改由于新边所改变的邻接边排序，再选择下一条边加入，直至加入nl条边。第二章递归与分治策略2.A3.A4.D5.B6,B7.D8.B9.C10.A11.C12.D13.B14.A15.B1.答：己知一个背包的容量C,有n件物品，物品i的重量为Wi,价值为Vi,求应如何选择装入背
22、包中的物品，使得装入背包中物品的总价值最大。2.答：将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同；对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止；将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。3.答：最坏情况下的时间复杂度称最坏时间复杂度。一般不特别说明，讨论的时间复杂度均是最坏情况下的时间复杂度。这样做的原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界，这就保证了算法的运行时间不会比这个更长。平均复杂度是指所有可能的
23、输入实例均以等概率出现的情况下，算法的期望运行时间。答：voidSortableList:MaxMin(inti,intj,T&max,T&min)constTmaxi,mini;if(i=j)max=min=li;表中只有一个元素elseif(i=j-l)表中只有两个元素if(1i1j)max=lj：min=li;else(max=li;min=lj;else表中有多个元素intm=(i+j)2;对半分割MaxMin(i,m,max,min);MaxMin(ml,j,maxi,mini);if(maxminl)min=minl;两子表最小元合并第三章动态规划2.D3.CC5.C6,B7.D8
24、.A9.B10.D11.D12.C13.B14.A15.D1.答：子问题的规模还很大时，必须继续使用分治法，反复分治，必然用到递归。2.答：在定义一个过程或者函数的时候又出现了调用本过程或者函数的成分，即调用它自己本身，称为直接递归；如果过程或函数P调用函数Q，Q又调用P，这个称为间接递归。答：typedefintT;voidBInsSort(TV,intn)Ttemp;intLeft,Right;for(inti=1;in;i+)1.eft=O;Right=il;temp=Vi;while(Left=Right)对半搜索intmid=(Left+Right)/2;if(temp=Left;k
25、)Vk+1=Vk;记录后移VLeft=temp;插入第四章贪心算法B5.A8.D9.BDAB6RR)集成测试法数据的流向4.N-S图数据项I答：归并排序的分治是招数组从中间分开，分别对前后两个部分进行排序，将排序后的两个数组合并成整个数组的排序。这样分治为递归过程，直到一个元素时返回；快速排序的分治是选取分割元素，以分割元素为界，将数组分成两部分,一部分小于分割元素，一部分大于分割元素，分别对两部分排序。2.答：不相同。目标函数：获得最大利润。最优量度：最大利润/重量比。第五章回溯法1.回溯法2.动态规划法3.最好4,分治法5.分枝限界法6.一个解7,不一定8.排列树1答：某个问题的最优解包含
26、其子问题的最优解。2.答：在一棵含有问题全部可能解的状态空间树上进行深度优先搜索，解为叶子结点。搜索过程中，每到达一个结点时，则判断该结点为根的子树是否含有问题的解，如果可以确定该子树中不含有问题的解，则放弃对该子树的搜索，退回到上层父结点，继续下一步深度优先搜索过程。在回溯法中，并不是先构造出整棵状态空间树，再进行搜索，而是在搜索过程，逐步构造出状态空间树，即边搜索,边构造。四.答TclassGraph()def_init_(self,vertices):self.V=verticesself,graph=Oforcolumninrange(vertices)forrowinrange(ve
27、rtices)defisSafe(self,v,colour,c):foriinrange(self.V):ifself,graphvi=1andcolouri=c:returnFalsereturnTruedefgraphColourUtil(self,m,colour,v):ifv=self.V:returnTrueforcinranged,m+l):ifself.isSafe(v,colour,c)=True:colourv=cifself.graphColourUtil(m,colour,v+l)=TruereturnTruecolourv=0defgraphColouring(self,m):colour=0*sclf.Vifself.graphColourUtil(m,colour,0)=None:returnFalseprint(usolution:,)forcincolour:print(c)returnTrueg=Graph(4)ggraph=0,1,1.11,l,0,l,0j1j1j0j1,1j0,1,0m=3
