试卷-算法分析与设计

《试卷-算法分析与设计》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、南京理工大学课程考试试卷精品快线之计算机课程名称：算法设计与分析学分：2教学大纲编号：试卷编号：A考试方式：闭卷满分分值：100考试时间：120分钟组卷日期：2010年10月18日组卷教师(签字)：审定人(签字)：2.算法的复杂性与以下哪些因索有关？()A.编程技巧B.问题的规模C.输入实例D.算法本身E.计算机的性能F.所使用的程序设计语言3.关于分治算法与动态规划算法，以下说法成立的是()A.它们的解都是递归定义并递归求解的B.适合于分治算法求解的问题也适合于动态规划算法，反之亦然C.它们都遵循将原问题分解为许多子问题的思想D

2、.以上说法均不正确4.关于分支限界法在搜索时的节点扩展，卞列描述正确的是：()A.深度优先B.广度优先C.最小耗费/最人收益优先D.活结点优先5.关于贪心策略，以下说法成立的是()A.贪心策略并非总是能找到问题的最优解B.贪心策略的计算效率往往很低C.贪心策略总是能找到理论上最优解D.以上说法均不正确三、计算题(每题10分，共20分)'3/(n-l)+4/(n-2),n>=2(1)已知/(〃)=

3、(每空格1分，共25分)1.算法的复杂性是指算法运行所需姿的计算机资源的量，需要的称为时间复杂性，需要的称为空间复杂性。一个算法的复杂性的高低体现在运行该算法所需要的计算机资源的多少上，所需诳源越多，我们就说该算法的复杂性：反之，所需俗源越少，我们就说该算法的复杂性。2.算法的复杂性与、和有关。3.常用的算法设计策略包括：、、、、等。4.冋溯法在进行搜索时以优先方式搜索解空间，并在搜索过程屮用函数避免无效搜索。5.分治算法一般分为三个步骤，即、、。6.分治算法与动杰规划算怯不同之处在于，适合于分治法得到的子问题之间是，而适合于动态

4、规划法求解的子问题之间是。7.排序算法和排序算法是两种比较典型的分治策略篦法。&堆是一•种队列。有n个节点的堆T,可以用一个数组H[l...n俅存储，T的根节点存储在H111屮。假设T的节点x存储在H[i]中，那么，它的左右子节点分别存放在及中(如果有的话)。Hli]的父节点如果不是根节点，则存储在中。二、不定项选择题(每题2分，共10分)1.下列选项成立的有：()A./(W)=O(g(N))=>.f(N)=o(g(/V))B.gV)=o(g(N))n/(N)=O(g(N))C./(N)=o(g(W))=>g(N)=Q(/(N))

5、D./(W)=0(g(W))=>f(N)=O(g(N))课程名称:[法设计与分析四、解答题1.(9分)给定不相交集如下图所示:学分：_—试卷编号：A问：1.最少执行多少次元素的赋值操作？何时最少?2.最多执行多少次元索的赋值操作？何时最多?画图表示以下操作完毕示的不札I交集的状态。(1)执行FIND⑸得到的结果是？(2)继续执行UNI0N(4,8)后的结果是?⑶继续执行FIND(l)后的结來是？2.(10分)给定如下算法:4.(10分)给定n=4的0-1背包问题：背包承重量为C=10,各物站的相关信息如下表所示。物品重量(w)价值

6、(v)价值/車呆144010274263525543124现考虑使用优先队列式分支限界法求解该问题。搜索结点的上界ub设置如下：把已经选择的物品总价值(v)，加上背包剩余承重虽(C-w)与剩下可选择的物品的最高“价值/重虽比”的乘积，即”=v+(C-w)(十)1皿。试画出搜索生成树。1.count—0elsej—j/25.(10分)给出一个求解二项式系数Cnk的高效算法，并分析其时间复杂度。2.fori—1ton3.j-Ln/2」4.whilej>=15.count—count+16.ifj为奇数thenj-07.endwhile

7、8.endfor问：(1)当n为2的幕吋，第5步执行的最大次数是多少次?(2)当n为3的幕时，笫5步执行的最大次数是多少次?3.（6分）输入：n个元素的数组A[l...n]输岀：按照非降序排列的数组A[l...nJ1.foriTton-12.forj—i+lton3.ifA[jJ