上一届(2019 春季学期)期末考试题

  1. （简答）解 0−10-1 背包问题，其中 n=6n=6 ，物品重量数组为 w=[4,4,12,10,9,5]w=[4, 4, 12, 10, 9, 5]，价值数组 p=[12,6,10,8,12,10]p=[12, 6, 10, 8, 12, 10]，背包容积 c=20c=20 。

    • 使用回溯法
    • 使用队列式分支限界法

    分别给出约束条件和上界函数，画出展开部分解空间树，并标明节点的对应重量及价值，剪枝时说明理由，最后给出该问题的最优值和最优解。

  2. （判断）贪心算法是不求最优，只求满意的算法。

  3. （判断）分支限界方法和回溯法的搜索方式不同，回溯法为深度优先搜索。

  4. （简答）简述分治、动态规划及贪心算法的基本思想，三者的区别和联系。

  5. （简答）有 nn 个作业和 mm 台机器，每个作业有需要加工的时间长度 tt ，每台机器房钱可空闲时间长度 ll ，当机器空闲时间长度 ll 大于等于某个作业的处理时长 tt 时，代表该机器可以分配给改作业；求使用这些机器，最多能安排多少作业？（注意，某个作业最多只能用1个机器加工）

    例如，作业处理时长 t[]=[5,10,2,9,15,9]t[]=[5,10,2,9,15,9] ；机器空闲时长 l=[6,1,20,3,8]l=[6,1,20,3,8] ；最多可以安排三个作业。

    使用贪心算法解该问题，写出你的贪心标准，并证该贪心标准是否可以得到最优解，最后写出响应的算法，并分析算法的复杂度。

  6. （单选）某设备需要4种配件，每种1件，有3个供应商提供这些配件，下面表格给出相关的价格和每种配件的重量。从中选择4种配件，使得总价值不超过120，总重量最轻。如果用回溯法解，则解空间树是

    A. 三叉树
    B. 二叉树
    C. 排列树
    D. 四叉树

  7. （简答）现有一笔经费可以报销一定额度的发票，共有 nn 张发票，发票等面值存于数组 w[]w[] 中，w[i]w[i] 为第 ii 张发票等面值。允许报销的发票面值不超过 vv 。现请你编写程序，在给出的一堆发票中找出可以报销的、不超过给定额度的最大报销额。利用动态规划算法给出递归式并进行简要说明。

  8. （填空）Arrange the following functions in increasing order of growth rate (with g(n)g(n) following f(n)f(n) in your list if and only if f(n)=O(g(n))f(n)=O(g(n)) )

    a. 2log⁡(n)2^{\log(n)}

    b. 22log⁡(n)2^{2^{\log(n)}}

    c. n5/2n^{5/2}

    d. 2n22^{n^2}

    e. n2log⁡(n)n^2\log(n)

    Write your 5-letter answer, i.e., the sequence in lower case letters in the space provided. For example, if you feel that the answer is a->b->c->d->e (from smallest to largest), then type abcde in the space provided without any spaces in between the string.

    You can assume that all logarithms are base 2 (though it actually doesn't matter). _____

  9. （单选）Suppose we implement QuickSort so that ChoosePivot always selects the first element of the array.

    What is the running time of this algorithm on an input array that is already sorted?

    A. Θ(nlog⁡n)\Theta(n\log n)
    B. Θ(n)\Theta(n)
    C. Not enough information to answer this question.
    D. Θ(n2)\Theta(n^2)

  10. （简答）使用代入法证明如下递归式的时间复杂度（先用主定理对复杂度猜测，然后证明其正确）。

    T(n)=4T(n/2)+n2T(n)=4T(n/2)+n^2

  11. （填空）假设一个序列 (7,2,10,6,8,5)(7, 2, 10, 6, 8, 5) ，用线性时间选择算法，选择第三小的元素，选择方法采用课上讲授的方法，多少个 pivot 产生 _____，他们分别是 _____，例如，被比较的数据为 4 和 9 ，则敲 49 ，不要加任何空格等。最后一个空为备注，如果你没用使用课上的基准选择方案，可以备注在此 _____。