算法基础设计 5

《XXXXXXXXXXX》试题A卷 第4页共4页试卷1选择题（共15小题，每小题3分，共45分）在已经排序好的n个元素中，二分搜索的复杂度是多少：A.Θ(logn)B.O(nlogn)C.Θ(n)D.O(log2n)T(n)的递归表达式如下：则T(n)可化简为：cn2B.cnlognC.cnD.clogn有如下循环代码，则其复杂度为：O(n3)B.O(nlogn2)C.O(nlog2n)D.O(n2logn)假如有一序列：-2，11，-4，13，-5，-2，在用动态规划求解此序列的最大子数组时，针对每个子问题的b值分别为多少（注：b值为每个子问题包含最右边元素的最大子数组和）：b(1)=-2,b(2)=11,b(3)=-4,b(4)=13,b(5)=-5,b(6)=-2b(1)=-2,b(2)=11,b(3)=7,b(4)=20,b(5)=15,b(6)=13b(1)=-2,b(2)=11,b(3)=5,b(4)=18,b(5)=15,b(6)=13b(1)=-2,b(2)=11,b(3)=5,b(4)=20,b(5)=15,b(6)=13将递归式TnA：A针对n后问题中的回朔树，总共有多少叶子节点A.2nB.n2C.2nD.nn三矩阵连乘（M1=5*6，M2=6*7，M3=7*2）如下表格所示，则C[1,3]和最优加括弧的方式为：C[1,1]=0,M1C[1,2]=210,M1M2C[1,3]C[2,2]=0,M2C[2,3]=84,M2M3C[3,3]=0,M3A.C[1,3]=280M1(M2M3)B.C[1,3]=144,M1(M2M3)C.C[1,3]=280(M1M2)M3D.C[1,3]=144,(M1M2)M3某图的邻接矩阵如下，在所有点对最短距离中，通过动态规划第一步后，矩阵变为：A.B.C.D.下面对NP问题描述错误的是：如果一个问题是P问题，则一定是NP问题任何一个NP问题都可以归约为一个NPC问题A问题可以归约为B问题，则如果A问题是NPC问题，则B问题一定也是NPC问题如果一个问题是NP问题，则一定是P问题在有向图应用DFS算法，可通过节点之间先序号和后序号的关系，来确定图中的边是属于何种边，假设有节点i和节点j，i的先序号大于j的先序号，但i的后序号小于j的后序号，则边i-j（边不在树中）是何种边？树边B.回边C.前向边D.横跨边以下排序不能在线性时间内完成的是：计数排序B.基数排序C.桶排序D.堆排序哪两个算法需要最优子结构性质A.分治和动态规划B.分治和贪心C.动态规划和贪心D.动态规划和回溯Prim算法和Dijkstra算法分别用于什么计算?A.都用于最小生成树B.最小生成树和最短路径C.都用于最短路径D.最短路径和最小生成树设序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最长公共子序列为Z={z1,z2,…,zk}，则下列说法错误的是：若xm=yn，则zk=xm=yn，且Zk-1是Xm-1和Yn-1的最长公共子序列若xm≠yn且zk≠xm，则Z是Xm-1和Y的最长公共子序列若xm≠yn且zk≠yn，则Z是X和Yn-1的最长公共子序列若xm=yn，则zk=xm=yn，且Zk是Xm-1和Yn-1的最长公共子序列如下图所示，Prim算法生成以节点3为根的最小生成树，和Kruskal生成的最小生成树，两个算法选择的第一条边的权重分别为（前面为Prim后面为Kruskal）：A.10,10B.15,10C.15,15D.10,15二、简答计算题(共4小题，共30分)1.有数组A=⟨29,18,10,15,20,9,5,13,2,4,15⟩，问1）这是最大堆吗？如果不是请交换两个数据，使之成为堆；2）将根元素删除后，写出使数组重新成为一个堆的步骤（即写出数组的每一次交换）(6)2.使用动态规划求解0-1背包问题：如有编号分别为1，2，3，4的4件物品，它们的重量分别是2,3,4,5，它们的价值分别是3,4,5，6，现在给你个承重为8的背包，如何让背包里装入的物品具有最大的价值总和?1）写出自底向上的计算m值（最大价值）的矩阵，得出最大价值总和（5分）2）根据m值矩阵得出最优装物品的方案（简要说明如何得到最优装物品方案）（3分）3.钱币兑换问题：有一个货币系统，假设它有n中硬币，v1,v2…vn,现要求用这些硬币兑换面值为Y的纸币，且硬币数量最少，请用动态规划求解此问题。要求：1）列出递归式（M代表最少的硬币数量值，即用递归的方式表示MY）；现假设有3种面值分别为v1=1,v2=2，v3=5的硬币.我们需要兑换价值为17的钱币，要让硬币的数目最少，求2）自底向上的计算1到17的每个M值,并且需要指出每个M是由之前的哪个M值得出的。（6）4.用分支限界法解决如下图所示的旅行商问题。要求：1）给出边界（上界和下界）；2）画出搜索树，对树中的每个节点给出编号（访问顺序）、下界、以及节点是否舍弃（按照上界条件）。（10分）三、综合分析题(2小题，共25分)给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。如区间集合[[1,2],[2,3],[3,4],[1,3]]，移除[1,3]即可使得剩余区间不重叠（[1,2]和[2,3]不重叠）。要求：1.设计一个贪心算法解决以上问题，2.并说明算法的计算复杂度（区间个数为n），3.说明算法是最优算法，并证明之。（12分）子集和问题：给出某个集合W={w1,w2…wi…wn-1,wn}和M值，请找出W的子集其和为M。如n＝4,W=(wl，w2，w3，w4)＝(11，13，24，7)，M＝31，则子集(11，13，7)和子集(24，7)