南邮算法分析与设计综合练习册期末复习题.docx

《南邮算法分析与设计综合练习册期末复习题.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.顺序、选择、循环11.需求分析阶段的任务是确定OA.软件开发方法B.软件开发工具C.软件开发费用D.软件系统功能12.软件开发的结构化生命周期方法将软件生命周期划分成()A.定义、开发、运行维护B.设计阶段、编程阶段、测试阶段C总体设计、详细设