算法基础设计 1

《算法设计与分析》试题A卷 第4页共4页试卷5选择题（共15小题，每小题3分，共45分）对于表达式n2logn+nlog2n，下述复杂度表示错误的是：A.Θ(nlog2n)B．O(n2logn)C．Ω(nlog2n)D．O(n3logn)T(n)表示当输入规模为n时的算法效率，以下算法效率最优的是：A.T(n)=T(n-1)+1，T(1)=1B.T(n)=2nC.T(n)=T(n2)+1，T(D.T(n)=3nlog下面这段代码的时间复杂度是多少？：MyTest(intn){if(n<=1)return1;else{intm=n/2;returnMyTest(m)+MyTest(m);}}A.Θ(n1/2)B.Θ(n)在最小堆中，初始时堆是[4,5,8,7,6]，执行一次删除操作（删除堆顶元素）后，堆的状态是什么：A.[5,7,8,6]B.[6,5,8,7]C.[5,6,8,7]D.[7,5,8,6]以下排序不能在线性时间内完成的是：计数排序B.基数排序C.桶排序D.堆排序迪杰斯特拉（Dijkstra）算法用于求解图上的单源点最短路径。该算法按路径长度递增次序产生最短路径，本质上说，该算法是一种基于（）策略的算法：A.分治B.动态规划C.贪心D.回溯假如有一序列:[-2,-3,4,-1,-2,1,5]，在用动态规划求解此序列的最大子数组时，针对每个子问题的b值分别为多少（注：b值为每个子问题包含最右边元素的最大子数组和）：A.b(1)=-2,b(2)=-5,b(3)=1,b(4)=0,b(5)=-2,b(6)=1,b(7)=5B.b(1)=-2,b(2)=-3,b(3)=4,b(4)=3,b(5)=1,b(6)=1,b(7)=6C.b(1)=-2,b(2)=-3,b(3)=1,b(4)=3,b(5)=-2,b(6)=1,b(7)=6D.b(1)=-2,b(2)=-3,b(3)=4,b(4)=3,b(5)=1,b(6)=2,b(7)=7在有6个字符组成的字符集S中，各个字符出现的频次分别为3,4,5,6,8,10，为S构造的哈夫曼编码树的加权平均长度为:A．2.4B.2.5C.2.67D.2.75下面对最优子结构性质描述有误的是：A.问题最优解包含了子问题的最优解B.最优子结构性质是针对问题，而不是针对算法C.只要问题具有最优子结构性质，贪心算法就可以得出最优解D.最短路径具有最优子结构性质设序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最长公共子序列为Z={z1,z2,…,zk}，则下列说法错误的是：A.若xm=yn，则zk=xm=yn，且Zk-1是Xm-1和Yn-1的最长公共子序列B.若xm≠yn且zk≠xm，则Zk是Xm-1和Y的最长公共子序列C.若xm≠yn且zk≠yn，则Zk是X和Yn-1的最长公共子序列D.若xm=yn，则zk=xm=yn，且Zk是Xm-1和Yn-1的最长公共子序列0-1背包问题：背包承重为9，现有3个物品，其重量和价值分别为分别为1:(3,4)；2：（4,5）；3：（5,6），则按照性价比的贪心算法得出的物品为：A．2和3B.1和2C.1和3D.1，2，3对有向图进行深度优先搜索时，可依据深度优先搜索树，对图中各边进行判断，下面描述错误的是：A.在树中，边的终点是边起点的祖先，则为回边B.在树中，边的终点是起点的子孙，则为前向边C.图中的边如对应树中的边，则为树边D.只要不是在树中的边，都为横跨边给定如下有向图，该图的拓扑有序序列的个数是:1B.2C.3D.4下面对回溯和分支限界说法错误的：分支限界采用深度优先遍历回溯法可用于可行解问题和最优解问题的求解分支限界只能用于最优解问题的求解回溯和分支限界都不需要存储整个搜索树在Dijkstra算法中，设源节点为a，X用于存放已经加入到树中的节点，Y用于存放还未加入到树中的节点，假设算法当前要将v加入到树中，且通过树中节点u加入。以下说法有误的是：a到任一x∈X的距离小于等于到任一y∈Y的距离v是所有Y中节点，算法得出的离树的距离最小的（和树相连边的权重最小）u必然是a到v一条最短路径上的点对于任一y∈Y（y≠v），a到v的距离必然小于等于到y的距离二、简答计算题(共4小题，共30分)1.证明logn!=Θ(n2.对下图所示的一个无向连通带权图，分别画出用Kruskal算法和Prim算法构造它的一棵最小代价生成树的过程（从结点1出发）。提示：需要有过程，不能仅有结果（6）对于边数相对较多的无向连通带权图，比较适合于用哪种方法求解？对于边数较少的无向连通带权图有较高效率的又是哪种算法？（2）3.在寻找第k小元素时，将原来的数组分为5个一组，可否分成3个一组？为什么？（7分）提示：从复杂度的角度分析，也就是计算分成3个一组的复杂度可否达到线性复杂度。4.用分支限界法解决如下图（无向图）所示共有5个城市{a,b,c,d,e}的旅行商问题（从a出发）。要求：1）给出边界（上界和下界）；2）画出搜索树，对树中的每个节点给出编号（访问顺序）、对应图中哪个城市、下界、以及节点是否舍弃（按照上界条件）；3）给出最优解和最优值。（9分）三、综合分析题(2小题，共25分)1.给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。如区间集合{(2,3),(1,2),(3,4),(1,3)}，移除{(1,2),(2,3)}和移除(1,3)都可使得剩余区间不重叠，但最少得方案是移除(1,3)。要求：1）设计一个贪心算法解决以上问题，使得解为最优；（5分）2）算法的复杂度（问题规模为n）；（2分）3）证明这个贪心算法是最优（提示：可用替换法）。（5分）2.现有一项工作，该工作每日报酬不同且每日单独结算。由于工作强度较大，最多每连续工作两天就需要休息一天才可继续参与工作。在给定一段时间内每日报酬的前提下，要求最大化此时间段内的总收益。例如，在一个连续4天的时间段上，每日报酬分别为100，400，200和350