算法基础设计 4

《算法设计与分析》试题A卷 第4页共4页试卷2选择题（共15小题，每小题3分，共45分）关于渐进记号以下说法正确的是：如果f(n)=Θ(g(n))，则f(n)=O(g(n))如果f(n)=O(g(n))，则f(n)=Ω(g(n))如果f(n)=Ω(g(n))，则f(n)=Θ(g(n))如果f(n)=Ω(g(n))，则f(n)=O(g(n))对于以下数组，插入排序算法总共执行了多少次比较？17，27，12，5，12，9，15，25A.19B.18C.17D.16下面正确的是：fff如果limn→∞f有如下递归代码，则其复杂度为：MyTest(intn){if(n<=1)return1;else{intm=n/4;returnMyTest(m)+MyTest(m);}}A.Θ(n)B.Θ(nlog快速排序的最好和最坏时间复杂度分别为：A.Θnlogn,Θ(nlogn)B.Θn2,Θ(n下列数组中，哪一个不是堆A.9，7，4，3，2，2B.8，5，7，6，3，2C.10，4，8，3，2，6D.11，9，5，6，7，30-1背包问题，有4个重量为3，2，4，6，价值为5，3，7，8的物品，背包的总承重为10，按照动态规划算法，已知m值矩阵的0-2行如下，则第3行为： 0 1 2 3 4 5 6 7 8 9 100 0 0 0 0 0 0 0 0 0 0 01 0 0 0 5 5 5 5 5 5 5 52 0 0 3 5 5 8 8 8 8 8 80 0 3 5 7 8 10 12 12 15 150 0 3 3 5 8 10 12 12 12 150 0 5 5 7 8 10 12 12 15 150 0 3 7 7 8 10 12 12 12 15Dijkstra算法作用于以下图结束时（A为源点），已经计算过的节点按计算顺序排列的集合为?A.{A,B,C,D,E}B.{A,C,E,B,D}C.{A,C,B,D,E}D.{A,B,C,E,D}在有向图应用DFS算法，可通过节点之间先序号和后序号的关系，来确定图中的边是属于何种边，假设有节点i和节点j，i的先序号大于j的先序号，但i的后序号也大于j的后序号，则边i-j是何种边？树边B.回边C.前向边D.横跨边以下哪个问题不具有最优子结构性质A.最长路径问题B.0-1背包问题C.小数背包问题D.最长公共子序列问题下面对Prim算法和Dijkstra算法描述错误的是?A.Prim算法用于最小生成树B.Dijkstra算法用于最短路径C.两者都生成以源节点为根的一棵树D.如果将加入到树的点看出一个集合，剩余的点看出一个集合，Dijkstra算法每次添加到树中的边都是连接这两个集合的最小边下面对回溯描述错误的是：回溯是通过深度优先遍历解空间树解空间树中的节点只遍历一次对解空间树的左减枝通常是通过约束函数，如n后问题，放置的皇后不能同列、同斜线3着色问题回溯最坏的时间复杂度为O(n3n)针对有n个顶点的图的3着色问题中的解空间树，总共有多少叶子节点：A.3nB.n3C.3nD.nn下面对NP问题描述错误的是：如果一个问题是P问题，则一定是NP问题任何一个NPC问题都可以归约为一个NP问题A问题可以归约为B问题，B问题可以归约为C问题，则A问题可以归约为C问题NPC问题一定是NP问题以下问题不属于NPC（NP完全）问题的是：小数背包问题3着色问题旅行商问题哈密顿回路问题二、简答计算题(共4小题，共30分)1.使用快速排序对数组5，7，6，4，2，1进行升序排序，要求写出每轮排序（每次递归调用）后数组序列。（5分） 2.请将下面的有向图按照深度优先搜索生成搜索树，并指出各个边的类型（树边，回边，前向边，横跨边），以及指出每个节点的先序号和后序号（7分）。3.钱币兑换问题：有一个货币系统，假设它有n种硬币，面值从小到大分别为v1,v2…vn,其中v1=1。要求用这些硬币兑换面值为Y的纸币，要求兑换硬币数量最少。如有面值为10的纸币，以及3种面值分别为v1=1,v2=2，v3=5的硬币，则最少的兑换为2个面值为5的硬币。请用回溯法求解此问题。（共8分）描述回溯法的解空间和树结构，并简单画出此树（4分）描述你的搜索策略：也就是通过什么方式进行搜索，搜索到哪些节点的时候表示已经得到一个可行解，以及搜索到哪些节点的时候停止搜索而进行回溯（剪枝函数）（4分）4.给定一个无向图G=V,E和两个顶点u,v,让distu,v为u到v的最短路径的长度。对于两个非空的顶点集合Vdist给出一个在时间O(V+|E|)内计算出distV三、综合分析题(2小题，共25分)1.轮船装载问题：轮船载重为C，n个集装箱的重量分别为wi,1<=i<=n;在装载体积不受限的情况下，尽可能多的装集装箱。请设计一个贪心算法能够获得最大装载数（4分）；并证明贪心算法得出的解是最优解（6分）。（共10分）2.假设有一个n×n的棋盘，每一个棋格x,yϵ{1,…,n}×{1,…,n}上有一个价值为c(x,y)的硬币。你可以从棋盘的底端往上移动你的棋子，并收集对应棋格里的硬币。假设在每一步，你只能这样移动棋子：往正上方移动一格往左上方移动一格（如果棋子不在棋盘的最左边）往右上方移动一格（如果棋子不在棋盘的最右边）你可以选择在在最底部一排的任意格子开始，在最顶部一排的任意格子结束。设计一个动态规划算法输出最大可以收集到的硬币的总价值。（共15分）描述算法思路（6分）。用OPT(x,y)表示从第x列，y排出发能收集到的最大硬币总价值。写出OPT(x,y)的递推式（4分）。写出算法伪代码（3分