算法设计期中试卷

1选择题：(每题2分，共30分)1.衡量一个算法好坏的标准是（C）。A.运行速度快B.占用空间少C.时间复杂度低D.代码短2.当输入规模为n时，算法增长率最快的是（C）。A.12nB.100log2nC.2n2D.3nlog3n3.渐进算法分析是指（B）。A.算法在最好情况、最坏情况和平均情况下的代价B.当规模逐步往极限方向增大时，对算法资源开销“增长率”上的简化分析C.数据结构所占用的空间D.在最小输入规模下算法的资源代价4.当上下限表达式相等时，我们使用下列（C）来描述算法代价？A.大O表示法B.大Ω表示法C.θ表示法D.小o表示法5.二分搜索算法是利用（A）实现的算法。A.分治策略B.动态规划法C.贪心法D.回溯法6.下列不是动态规划算法基本步骤的是（A）。A.找出最优解的性质B.构造最优解C.算出最优解D.定义最优解7.动态规划算法的基本要素为（C）。A.最优子结构性质与贪心选择性质B．重叠子问题性质与贪心选择性质C．最优子结构性质与重叠子问题性质D.预排序与递归调用8.能采用贪心算法求最优解的问题，一般具有的重要性质为（A）。A.最优子结构性质与贪心选择性质B．重叠子问题性质与贪心选择性质C．最优子结构性质与重叠子问题性质D.预排序与递归调用29.备忘录方法是那种算法的变形。（B）。A．分治法B.动态规划法C.贪心法D.回溯法10.实现大整数乘法利用的算法是（A）。A.分治策略B.动态规划法C.贪心法D.回溯法11.使用分治法求解不需要满足的条件是（A）。A.子问题必须是一样的B.子问题不能够重复C.子问题的解可以合并D.原问题和子问题使用相同的方法解12.贪心算法与动态规划算法的主要区别是（B）。A.最优子结构B.贪心选择性质C.构造最优解D.定义最优解13.实现最长公共子序列利用的算法是（B）。A.分治策略B.动态规划法C.贪心法D.回溯法14.使用二分搜索算法在1000个有序元素表中搜索一个特定元素，在最坏情况下，搜索总共需要比较的次数是（A）。A.10B.11C.500D.100015.关于0-1背包问题以下描述正确的是（D）。A.可以使用贪心算法找到最优解B.能找到多项式时间的有效算法C.使用动态规划算法可求解任意0-1背包问题D.对于同一背包与相同的物品，做背包问题取得的总价值一定大于等于做0-1背包问题二、填空题：(每空1分，共10分)1.一个算法复杂性的高低体现在计算机运行该算法所需的时间和存储器资源上，因此算法的复杂性有时间复杂性和空间复杂性之分。2.一个直接或间接调用自身的算法称为递归算法。3.出自于“平衡子问题”的思想，通常分治法在分割原问题，形成若干子问题时，这些子问题的规模都大致相等。4.大整数乘积算法是用分治法来设计的。5.快速排序算法的性能取决于划分的对称性。36.已知一个分治算法耗费的计算时间T(n)，T(n)满足如下递归方程：解此递归方程可得T(n)=O（nlogn）。7.递归通常用栈来实现。8.最优二叉搜索树即是最小平均路长二叉搜索树。9.任何可用计算机求解的问题所需的时间都与其规模有关。三、简答题：（每小题10分，共30分）1.简述归动态规划算法的基本步骤，以及动态规划算法与分治法的异同。设计动态规划算法的主要步骤为：（4分）（1）找出最优解的性质，并刻划其结构特征。（2）递归地定义最优值。（3）以自底向上的方式计算出最优值。（4）根据计算最优值时得到的信息，构造最优解。分治法与动态规划法的相同点是：将待求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。（3分）两者的不同点是：适合于用动态规划法求解的问题，经分解得到的子问题往往不是互相独立的。而用分治法求解的问题，经分解得到的子问题往往是互相独立的。（3分）2.与顺序查找算法相比，二分查找算法的时间复杂性有多大程度的降低？它是如何提高算法的效率的？有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当使用二分查找值为82的结点时，经过多少次比较后查找成功？答：顺序查找的时间是O(n)，折半查找O(logn)降低了一个数量级。采用分治策略，每一次比较可以排除一半的数据。共需要比较4次才能找到82.3.简述归并排序算法和快速排序算法的分治方法。并对下列实例数据A=(38,27,55,50,13,49,65)排序，写出采用快速排序算法，数组A第一次被分割的过程。答：归并排序的分治是将数组从中间分开，分别对前后来那个部分进行排序，将排序后的两个数组合并成整个数组的排序。这样分治为递归过程，直到一个元素时返回。快速排序的分治是选取分割元素，以分割元素为界，将数组分成两部分，一部分小于分割元素，一部分大于分割元素，分别对两部分排序。数组A第一次被分割的过程如下：382755501349654132755503849651373850554965四、算法分析题：（每题10分，共30分）1.有16个选手参加循环赛，循环赛一共进行15天，每个选手必须与其他的15个选手各赛一场，每个选手一天只比赛一次；设计一个满足上述要求的比赛日程表，并简述采用的算法基本思路。2.对于矩阵连乘所需最少数乘次数问题，其递归关系式为：其中m[i,j]为计算矩阵连乘Ai…Aj所需的最少数乘次数，pi-1为矩阵Ai的行，pi为矩阵的列。现有四个矩阵，其中各矩阵位数分别为：A1A2A3A4501010404030305p0p1p1p2P2p3p3p4(1)在这个四矩阵连乘积问题中，请问不同子问题的个数总共有多少个？并请把所有的子问题列出来。(2)请根据以上的递归关系，计算出矩阵连乘积A1A2A3A4所需要的最少数乘次数。要求写出求解过程，并将结果填入m[4][4]。3.请用动态规划解下列0-1背包问题，写出递归式及求解过程。共有4个物品，背包重量C=5，下表中列出每个物品的重量和价值。物品重量（公斤）价值（美元）1212521103321421562013-2014学年第1学期算法分析期中参考答案一、选择题：(每题2分，共30分)1C2C3B4C5A6A7C8A9B10A11A12B13B14A15D二、填空题：(每空1分，共10分)1时间2空间3递归4相等5分治法6划分的对称性7nlogn8栈9最小平均路长（或最小搜索代价）10规模三、简答题：（每题10分，共30分）1.答：设计动态规划算法的主要步骤为：（4分）（1）找出最优解的性质，并刻划其结构特征。（2）递归地定义最优值。（3）以自底向上的方式计算出最优值。（4）根据计算最优值时得到的信息，构造最优解。分治法与动态规划法的相同点是：将待求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。（3分）两者的不同点是：适合于用动态规划法求解的问题，经分解得到的子问题往往不是互相独立的。而用分治法求解的问题，经分解得到的子问题往往是互相独立的。（3分）2.答：顺序查找的时间是O(n)，折半查找O(logn)降低了一个数量级。采用分治策略，每一次比较可以排除一半的数据。共需要比较4次才能找到82.3.答：归并排序的分治是将数组从中间分开，分别对前后来那个部分进行排序，将排序后的两个数组合并成整个数组的排序。这样分治为递归过程，直到一个元素时返回。快速排序的分治是选取分割元素，以分割元素为界，将数组分成两部分，一部分小于分割元素，一部分大于分割元素，分别对两部分排序。数组A第一次被分割的过程如下：738275550134965132755503849651373850554965四、算法分析题：（每题10分，共30分）1.答：可采用分治策略，将所有的选手分为两半，n个选手的比赛日程表就可以通过为n/2个选手设计的比赛日程表来决定。递归地用一分为二的策略对选手进行分割，直到只剩下2个选手时，比赛日程表的制定就变得很简单。这时只要让这2个选手进行比赛就可以了。设计的比赛日程表如下所示：天数1234567891011121314152.答：（1）共有10个子问题。n+C(n,2)个A1,A2,A3,A44个A1A2,A2A3,A3A4A1A2A3，A2A3A4A1A2A3A4A5（2）最少数乘次数即m[1,4]=105001234020000270001050001200080000600003.答：由0-1背包问题的最优子结构性质，可以建立计算m(i，j)的递归式如下。12345678910111213141516214365871091211141316153412785611129101516131443218765121110916151413567812341314151691011126587214314131615109121178563412151613141112910876543211615141312111099101112131415161234567810912111413161521436587111291015161314341278561211109161514134321876513141516910111256781234141316151091211658721431516131411129107856341216151413121110987654321iiiiwjwjjimvwjimjimjim0),1(}),1(),,1(max{),(12348根据动态规划解0-1背包的递归式，得到下面的动态规划表：i01234500000001010152531372010152531363001521213640015151515由上表可知，背包最大价值为m[1][5]=37，最优解为（1，1,0,1）nnnwjwjvjnm00),(