算法设计期中试卷

1、南京信息工程大学滨江学院2013 2014 学年第 1 学期 算法设计与分析 课程试卷试卷类型 期中 考试类型 开卷 注意：1、本课程为 必修 ，学时为 51 ，学分为 3 2、本试卷共 5 页；考试时间 120 分钟； 出卷时间： 2013年 11 月3、姓名、学号等必须写在指定地方；考试时间：2013年11月 11 日4、本考卷适用专业年级： 计科11，软工11 任课教师： 宣文霞 题号一二三四五六七八九十十一十二总分得分阅卷人（以上内容为教师填写）专业 年级 班级 请仔细阅读以下内容：1、 考生必须遵守考试纪律，详细内容见南京信息工程大学滨江学院考试纪律规定。2、 所有考试材料不得带离考

2、场。3、 考生进入考场后，须将学生证或身份证放在座位的左上角。4、 考场内不许抽烟、吃食物、喝饮料。5、 考生不得将书籍、作业、笔记、草稿纸袋入考场，主考教师允许带入的除外。6、 考试过程中，不允许考生使用通讯工具。7、 开考15分钟后不允许考生进入考场，考试进行30分钟后方可离场。8、 考生之间不得进行任何形式的信息交流。9、 除非被允许，否则考生交卷后才能离开座位。10、 考试违纪或作弊的同学将被请出考场，其违纪或作弊行为将上报学院。本人郑重承诺：我已阅读上述10项规定，如果考试是违反了上述10项规定，本人将自愿接受学校按照有关规定所进行的处理。上面姓名栏所填姓名即表示本人已阅读本框的内容

3、并签名。学号 姓名 一、 选择题：(每题2分，共30分)1. 衡量一个算法好坏的标准是（ ）。A.运行速度快 B.占用空间少 C.时间复杂度低 D.代码短2. 当输入规模为n时，算法增长率最快的是（ ）。 A.12n B. 100log2n C.2n2 D.3nlog3n3. 渐进算法分析是指（ ）。A. 算法在最好情况、最坏情况和平均情况下的代价B. 当规模逐步往极限方向增大时，对算法资源开销“增长率”上的简化分析C. 数据结构所占用的空间 D. 在最小输入规模下算法的资源代价4. 当上下限表达式相等时，我们使用下列（ ）来描述算法代价？ A.大O 表示法 B.大 表示法C.表示法 D.小o

4、表示法5. 二分搜索算法是利用（ ）实现的算法。A.分治策略 B.动态规划法 C.贪心法 D.回溯法6. 下列不是动态规划算法基本步骤的是（ ）。A.找出最优解的性质 B.构造最优解 C.算出最优解 D.定义最优解7. 动态规划算法的基本要素为（ ）。A. 最优子结构性质与贪心选择性质B重叠子问题性质与贪心选择性质C最优子结构性质与重叠子问题性质D. 预排序与递归调用8. 能采用贪心算法求最优解的问题，一般具有的重要性质为（ ）。A. 最优子结构性质与贪心选择性质B重叠子问题性质与贪心选择性质C最优子结构性质与重叠子问题性质D. 预排序与递归调用9. 备忘录方法是那种算法的变形。（ ）。A分治

5、法 B.动态规划法 C.贪心法 D.回溯法 10. 实现大整数乘法利用的算法是（）。A.分治策略 B.动态规划法C.贪心法 D.回溯法11. 使用分治法求解不需要满足的条件是（ ）。A. 子问题必须是一样的B. 子问题不能够重复C. 子问题的解可以合并D. 原问题和子问题使用相同的方法解12. 贪心算法与动态规划算法的主要区别是（ ）。A.最优子结构 B.贪心选择性质 C.构造最优解 D.定义最优解13. 实现最长公共子序列利用的算法是（ ）。A.分治策略B.动态规划法 C.贪心法 D.回溯法14. 使用二分搜索算法在1000个有序元素表中搜索一个特定元素，在最坏情况下，搜索总共需要比较的次数

6、是（ ）。A.10 B.11 C.500 D.100015. 关于0-1背包问题以下描述正确的是（ ）。A. 可以使用贪心算法找到最优解B. 能找到多项式时间的有效算法C. 使用动态规划算法可求解任意0-1背包问题D. 对于同一背包与相同的物品，做背包问题取得的总价值一定大于等于做 0-1背包问题二、 填空题：(每空1分，共10分)1. 一个算法复杂性的高低体现在计算机运行该算法所需的时间和存储器资源上，因此算法的复杂性有 【1】 复杂性和 【2】 复杂性之分。2. 一个直接或间接调用自身的算法称为 【3】 算法。3. 出自于“平衡子问题”的思想，通常分治法在分割原问题，形成若干子问题时，这些

7、子问题的规模都大致 【4】 。4. 大整数乘积算法是用 【5】 来设计的。5. 快速排序算法的性能取决于 【6】 。6. 已知一个分治算法耗费的计算时间T(n)，T(n)满足如下递归方程：Tn=O1 n22Tn2+On n2解此递归方程可得T(n)=O（ 【7】 ）。7. 递归通常用 【8】 来实现。8. 最优二叉搜索树即是 【9】 二叉搜索树。9. 任何可用计算机求解的问题所需的时间都与其 【10】 有关。三、 简答题：（每小题10分，共30分）1. 简述归动态规划算法的基本步骤，以及动态规划算法与分治法的异同。2. 与顺序查找算法相比，二分查找算法的时间复杂性有多大程度的降低？它是如何提高

8、算法的效率的？有一个有序表为1，3，9，12，32，41，45，62，75，77，82，95，100，当使用二分查找值为82的结点时，经过多少次比较后查找成功？3. 简述归并排序算法和快速排序算法的分治方法。并对下列实例数据A=(38,27,55,50,13,49,65)排序，写出采用快速排序算法，数组A第一次被分割的过程。四、 算法分析题：（每题10分，共30分）1. 有16个选手参加循环赛，循环赛一共进行15天，每个选手必须与其他的 15个选手各赛一场，每个选手一天只比赛一次；设计一个满足上述要求的比赛日程表，并简述采用的算法基本思路。2. 对于矩阵连乘所需最少数乘次数问题，其递归关系式为

9、：mi,j=o i=jminikjmi,k+mk+1,j+pi-1pipj ij其中mi,j为计算矩阵连乘AiAj所需的最少数乘次数，pi-1为矩阵Ai的行，pi为矩阵的列。现有四个矩阵，其中各矩阵位数分别为：A1A2A3A4501010404030305p0p1p1p2P2p3p3p4(1) 在这个四矩阵连乘积问题中，请问不同子问题的个数总共有多少个？并请把所有的子问题列出来。(2) 请根据以上的递归关系，计算出矩阵连乘积A1A2A3A4所需要的最少数乘次数。要求写出求解过程，并将结果填入m44。3. 请用动态规划解下列0-1背包问题，写出递归式及求解过程。共有4个物品，背包重量C=5，下表

10、中列出每个物品的重量和价值。物品重量（公斤）价值（美元）1212211033214215南京信息工程大学滨江学院 算法分析 试卷答题纸班级 学号 姓名 成绩 一、选择题：(每题2分，共30分)123456789101112131415二、填空题：(每空1分，共10分)12345678910三、简答题：（每题10分，共30分）2013-2014学年第1学期算法分析期中参考答案一、选择题：(每题2分，共30分)1 C2 C3 B4 C5 A6 A7 C8 A9 B10 A11 A12 B13 B14 A15 D二、填空题：(每空1分，共10分)1 时间2 空间3 递归4 相等5 分治法6 划分的对

11、称性7 nlogn8 栈9 最小平均路长（或最小搜索代价）10 规模三、简答题：（每题10分，共30分）1. 答：设计动态规划算法的主要步骤为：（4分）（1）找出最优解的性质，并刻划其结构特征。（2）递归地定义最优值。（3）以自底向上的方式计算出最优值。（4）根据计算最优值时得到的信息，构造最优解。分治法与动态规划法的相同点是：将待求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。（3分）两者的不同点是：适合于用动态规划法求解的问题，经分解得到的子问题往往不是互相独立的。而用分治法求解的问题，经分解得到的子问题往往是互相独立的。（3分）2. 答：顺序查找的时间是O

12、(n)，折半查找O(log n) 降低了一个数量级。采用分治策略，每一次比较可以排除一半的数据。共需要比较4次才能找到82.3. 答：归并排序的分治是将数组从中间分开，分别对前后来那个部分进行排序，将排序后的两个数组合并成整个数组的排序。这样分治为递归过程，直到一个元素时返回。快速排序的分治是选取分割元素，以分割元素为界，将数组分成两部分，一部分小于分割元素，一部分大于分割元素，分别对两部分排序。数组A第一次被分割的过程如下：38 27 55 50 13 49 6513 27 55 50 38 49 6513 7 38 50 55 49 65四、算法分析题：（每题10分，共30分）1. 答：可

13、采用分治策略，将所有的选手分为两半，n个选手的比赛日程表就可以通过为n/2个选手设计的比赛日程表来决定。递归地用一分为二的策略对选手进行分割，直到只剩下2个选手时，比赛日程表的制定就变得很简单。这时只要让这2个选手进行比赛就可以了。设计的比赛日程表如下所示：天数 1 2 3 4 5 6 7 8 9 10 11 12 13 14 151234567891011121314151621436587109121114131615341278561112910151613144321876512111091615141356781234131415169101112658721431413161510

14、91211785634121516131411129108765432116151413121110991011121314151612345678109121114131615214365871112910151613143412785612111091615141343218765131415169101112567812341413161510912116587214315161314111291078563412161514131211109876543212. 答：（1）共有10个子问题。 n+C(n,2)个A1,A2,A3,A4 4个A1A2, A2A3, A3A4 A1A2A3，A2A3A4A1A2A3A4A5（2）最少