江苏大学 程序设计与算法算法设计与分析数据结构与算法程序设计与数据结构 期末考研复试复习

江苏大学 程序设计与算法/算法设计与分析/数据结构与算法/程序设计与数据结构 期末/考研复试复习

目录

考试范围一、问答题二、时间复杂度计算：

1.动态规划、贪心：2.排序：3.堆/优先队列4.回溯法、分支限界法解背包问题5.递归 三、证明：

活动安排问题最长公共子序列问题 四、动态规划填表：

最长公共子序列：0-1背包：矩阵连乘： 五、实践题

1.棋盘覆盖2.循环赛安排3.矩阵连乘4.添加括号数目问题5.找新数6.0-1背包问题（回溯法）7.0-1背包问题（分支限界法）

考试范围

1.问答题
2.根据代码写时间复杂度
3.0-1背包问题的分支限界法/回溯法计算实例
4.正确性证明（lcs，不相交区间）
5.动态规划填表（lcs，背包，矩阵）
6.算法设计实践题

一、问答题

  1．什么是最坏情况时间复杂性？什么是平均情况时间复杂性？
最坏情况的时间复杂性是规模为n的所有输入中，基本运算执行次数为最多的时间复杂性。平均时间复杂性是规模为n的所有输入的算法时间复杂性的平均值（假设每种输入情况等概率出现）。
  2．什么是递归算法？什么是递归函数？
  递归：若一个对象部分地包含它自己，或用它自己给自己定义，则称这个对象是递归的。
  递归算法:直接或间接地调用自身的算法。
  递归函数:用函数自身给出定义的函数。
   3．递归函数的二要素是什么？
  边界条件、递归方程。
   4．分治法的设计思想是什么？
  将要求解的较大规模的问题分割成若干个更小规模的子问题。
  对这若干子问题分别求解。如果子问题的规模仍然不够小，则再划分为若干个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。
  5．什么叫问题的最优子结构性质？
  最优子结构性质：问题的最优解包含着其子问题的最优解。
  6．动态规划基本步骤是什么？【第三章PPT P26】
  分解。将原问题可以分解为若干个规模较小的相同问题。
  递归地定义最优值。（相当于分治法中的合并 *** 作）
  以自底向上的方式计算出最优值。
  根据计算最优值时得到的信息，构造最优解。
  7．动态规划算法的基本要素是什么？举例说明一些可以用动态规划算法解决的问题。
  动态规划算法的基本要素是：最优子结构：问题的最优解包含子问题  的最优解、重叠子问题：每次产生的子问题不是新问题，被反复计算多次。
  矩阵连乘、最长公共子序列、0-1背包问题
  8．说明分治法与动态规划法的相同点和不同之处？
  与分治法类似，动态规划法也是把问题一层一层地分解为规模逐渐减小的同类型的子问题。动态规划法与分治法的一个重要的不同点在于，用分治法分解后得到的子问题通常都是相互独立的，而用动态规划法分解后得到的子问题很多都是重复的。因此，对重复出现的子问题，只是在第一次遇到时才进行计算，然后把计算所得的结果保存起来；当再次遇到该子问题时，就直接引用已保存的结果，而不再重新求解。
  9．贪心算法的两个重要要素是什么？举例说明一些可以用贪心算法解决的问题。
  两个重要要素：贪心选择性质：所求的问题的整体最优解可以通过一系列局部最优的选择达到、最优子结构性质：问题最优解包含子问题最优解。
  活动安排问题、最优装载问题、单源最短路径问题
  10．什么叫贪心选择性质？
  所求问题的整体最优解可以通过一系列的局部最优选择来得到，即贪心选择来达到。
  11．贪心算法与动态规划算法的的相同点和不同之处？
  相同点：都具有最优子结构性质，都用来求解最优化问题。
  不同点：贪心算法具有贪心选择性质，局部最优解能得到整体最优解。动态规划具有重叠子问题性质。
   12．背包问题与0－1背包问题有何区别？
  0-1背包问题物品有两种选择，要么放进去要么不放进去，而背包问题可以放部分，重量的选择可以是非整数
  13．回溯法与分支限界法之间的相同点是什么？不同之处在哪些方面？
  回溯法和分支限界法都需要隐式地构造解空间树并对其进行搜索。回溯法以深度优先的顺序进行搜索，避免不必要的搜索。分支限界法则以广度优先或最小耗费（最大效益优先）的方式搜索解空间树。
   14．分支限界法基本思想是什么？
  分支限界法以广度优先或以最小耗费（最大效益）优先的方式搜索解空间树。扩展子结点时，一次性生成它的所有孩子结点，舍弃不可能导致可行解或最优解的子结点，其余节点进入队列。
  15．常用的剪枝函数有哪两类？
  约束函数剪枝和限界函数剪枝。
   16．约束函数的功能是什么？
  在扩展节点处剪去不满足约束的子树，保留可行解点。
  17．限界函数的功能是什么？
  剪去可行但得不到最优解的子树。
   18.．常见的两种分支限界法是什么？
  （1）队列式(FIFO)分支限界法
按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。
   （2）优先队列式分支限界法
按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。
   19．什么是P问题和NP问题？
  如果一个问题可以找到一个能在多项式时间里解决它的算法，那么这个问题就属于P问题。
  NP问题不是非P类问题，是多项式复杂程度的非确定性问题。 是指可以在多项式的时间里验证一个解的问题。
  20．回溯法中剪枝函数有哪几类？各有何用途？
  约束函数：用约束函数在扩展结点处剪去不满足约束的子树,保留可行节点；
  限界函数：用限界函数剪去得不到最优解的子树。
  21．什么是NP完全问题？
   NP完全问题又叫NPC问题。同时满足下面两个条件的问题就是NPC问题。
  第一条，它是一个NP问题；
  第二条，所有的NP问题都可以约化到它。
   22.子集树和排列树。
  都是回溯法的状态空间树。
  子集树：从n个元素组成的集合S中找出S满足某种性质的子集时，相应的解空间树。
  排列树：当所给问题是确定n个元素满足某种性质的排列时，相应解空间树为排列数。

二、时间复杂度计算： 1.动态规划、贪心：

最内层循环次数。

2.排序：

T ( n ) = O ( n log ⁡ n ) T(n)=O(nlog n) T(n)=O(nlogn)

3.堆/优先队列

每次 *** 作都需要 T ( n ) = O ( log ⁡ n ) T(n)=O(log n) T(n)=O(logn)

4.回溯法、分支限界法解背包问题

T ( n ) = O ( n 2 n ) T(n)=O(n2^n) T(n)=O(n2n)

5.递归

解得 T ( n ) = n l o g m k + ∑ j = 0 l o g m n − 1 k j f ( n / m j ) T(n)=n^{log_mk}+sum_{j=0}^{log_mn-1}k^jf(n/m^j) T(n)=nlogm​k+∑j=0logm​n−1​kjf(n/mj)
（主定理）
典型情况： T ( k ) = m T ( k − 1 ) + O ( 1 ) , T ( k ) = O ( m k ) T(k)=mT(k-1)+O(1),T(k)=O(m^k) T(k)=mT(k−1)+O(1),T(k)=O(mk)

三、证明： 活动安排问题

设有n个活动的集合 E ＝ { 1 ， 2 ， … ， n } E＝{1，2，…，n} E＝{1，2，…，n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。
每个活动 i i i都有一个要求使用该资源的起始时间 s i s_i si​和一个结束时间 f i f_i fi​，且 s i ＜ f i s_i＜f_i si​＜fi​。
如果选择了活动 i i i，则它在半开时间区间 [ s i ， f i ) [s_i ，f_i ) [si​，fi​)内占用资源。若区间 [ s i ， f i ) [s_i ，f_i ) [si​，fi​)与区间 [ s j ， f j ) [s_j，f_j ) [sj​，fj​)不相交，则称活动 i i i与活动 j j j是相容的，即当 s i ≥ f j s_i ge f_j si​≥fj​ 或 s j ≥ f i s_j ge f_i sj​≥fi​时，活动 i i i与活动 j j j相容。
活动安排问题就是在所给的活动集合中选出最大的相容活动子集合。
每次总是选择具有最早完成时间的相容活动得到的活动数最多，这就是贪心选择。
证明：设由此方法得到的活动安排为： a 1 , a 2 , . . . , a p {a_1,a_2,...,a_p} a1​,a2​,...,ap​
反证法：
假设不是最大个数的相容集，即存在这么一个活动安排： b 1 , b 2 , . . . , b p , b p + 1 , . . . , b q , q > p b_1,b_2,...,b_p,b_{p+1},...,b_q,q>p b1​,b2​,...,bp​,bp+1​,...,bq​,q>p
显然活动 b 1 b_1 b1​的结束时间大于等于活动 a 1 a_1 a1​的结束时间。
用数学归纳法说明：当 i ≤ p i le p i≤p
活动 b i b_i bi​的结束时间大于等于活动 a i a_i ai​的结束时间。
从而：活动 b p b_p bp​的结束时间大于等于活动 a p a_p ap​的结束时间。
从而活动 a p a_p ap​与活动 b p + 1 , . . . , b q b_{p+1},...,b_q bp+1​,...,bq​是相容的
此与此方法停止的条件矛盾。
因此，前面的假设错误。因此，由原方法得到的活动安排是最优解。

最长公共子序列问题

设序列 X m = { x 1 , x 2 , … , x m − 1 , x m } X_m={x_1,x_2,…,x_{m-1},x_m} Xm​={x1​,x2​,…,xm−1​,xm​}和 Y n = { y 1 , y 2 , … , y n − 1 , y n } Y_n={y_1,y_2,…,y_{n-1},y_n} Yn​={y1​,y2​,…,yn−1​,yn​}的最长公共子序列为 Z = { z 1 , z 2 , … , z k − 1 , z k } Z={z_1,z_2,…,z_{k-1},z_k} Z={z1​,z2​,…,zk−1​,zk​} ，则：
(1) 若 x m = y n x_m=y_n xm​=yn​，则 z k = x m = y n z_k=x_m=y_n zk​=xm​=yn​，且 Z k − 1 Z_{k-1} Zk−1​是 X m − 1 X_{m-1} Xm−1​和 Y n − 1 Y_{n-1} Yn−1​的最长公共子序列。
(2) 若 x m ≠ y n x_m≠y_n xm​​=yn​且 z k ≠ x m z_k≠x_m zk​​=xm​，则 Z Z Z是 X m − 1 X_{m-1} Xm−1​和 Y Y Y的最长公共子序列。
(3) 若 x m ≠ y n x_m≠y_n xm​​=yn​且 z k ≠ y n z_k≠y_n zk​​=yn​，则 Z Z Z是 X X X和 Y n − 1 Y_{n-1} Yn−1​的最长公共子序列。
由此可见，Xm和Yn序列的最长公共子序列可以分解为2个前缀序列Xm-1和Yn、Xm和Yn-1的最长公共子序列。
因此，最长公共子序列问题具有最优子结构性质。
即可以将原问题分解成若干个规模较小的相同子问题。
证明：序列 X m = { x 1 , x 2 , … , x m − 1 , x m } X_m={x_1,x_2,…,x_{m-1},x_m} Xm​={x1​,x2​,…,xm−1​,xm​}和 Y n = { y 1 , y 2 , … , y n − 1 , y n } Y_n={y_1,y_2,…,y_{n-1},y_n} Yn​={y1​,y2​,…,yn−1​,yn​}， Z = { z 1 , z 2 , … , z k − 1 , z k } Z={z_1,z_2,…,z_{k-1},z_k} Z={z1​,z2​,…,zk−1​,zk​} 。
(1) 当 x m = y n x_m=y_n xm​=yn​时：原问题可以转换成一个子问题，即 X m − 1 X_{m-1} Xm−1​和 Y n − 1 Y_{n-1} Yn−1​的最长公共子序列。显然成立。
(2) x m ≠ y n x_m≠y_n xm​​=yn​时：
反证法。设序列 X m − 1 X_{m-1} Xm−1​和 Y n Y_n Yn​、 X m X_m Xm​和 Y n − 1 Y_{n-1} Yn−1​的最长公共子序列的长度为 k k k.
假设存在长度大于 k k k的 X m X_m Xm​和 Y n Y_n Yn​公共子序列 A p = { a 1 , a 2 , … , a k , a k + 1 , . . . . . . , a p } A_p={a_1,a_2,…,a_k,a_{k+1},......,a_p} Ap​={a1​,a2​,…,ak​,ak+1​,......,ap​}，至少 k + 1 k+1 k+1
有三种情况： a p = x m a_p=x_m ap​=xm​， a p ≠ y n a_p≠y_n ap​​=yn​则 A p A_p Ap​是 X m X_m Xm​和 Y n − 1 Y_{n-1} Yn−1​的一个公共子序列。矛盾。
a p = y n a_p=y_n ap​=yn​， a p ≠ x m a_p≠x_m ap​​=xm​则 A p A_p Ap​是 X m − 1 X_{m-1} Xm−1​和 Y n Y_n Yn​的一个公共子序列。矛盾。
a p ≠ x m a_p≠x_m ap​​=xm​， a p ≠ y n a_p≠y_n ap​​=yn​则 A p A_p Ap​是 X m − 1 X_{m-1} Xm−1​和 Y n − 1 Y_{n-1} Yn−1​的一个公共子序列。矛盾。

四、动态规划填表： 最长公共子序列：

从左至右、从上往下更新。

0-1背包：

从左至右、从下往上更新。 w w w为重量/体积， v v v为价值。


(注：从下往上！！！)
(注：不要擅自使用 d p i , j = m a x ( d p i − 1 , j , d p i − 1 , j − w i + v i ) dp_{i,j}=max(dp_{i-1,j},dp_{i-1,j-w_i}+v_i) dpi,j​=max(dpi−1,j​,dpi−1,j−wi​​+vi​)或 d p j = m a x ( d p j , d p j − w i + v i ) dp_j=max(dp_j,dp_{j-w_i}+v_i) dpj​=max(dpj​,dpj−wi​​+vi​)等其他形式的公式！！！

矩阵连乘：

用 p 0.. n p_{0..n} p0..n​存放矩阵 A 1.. n A_{1..n} A1..n​的维数。 A i A_i Ai​的维数为 p i − 1 ∗ p i p_{i-1}*p_i pi−1​∗pi​

五、实践题 1.棋盘覆盖

算法设计与分析/数据结构与算法实验1：棋盘覆盖问题

2.循环赛安排

算法设计与分析/数据结构与算法实验2：循环赛安排问题

3.矩阵连乘

算法设计与分析/数据结构与算法实验3：矩阵连乘问题

4.添加括号数目问题

算法设计与分析/数据结构与算法实验4：添加括号数目问题

5.找新数

算法设计与分析/数据结构与算法实验5：找新数最小的删除方案

6.0-1背包问题（回溯法）

算法设计与分析/数据结构与算法实验6：0-1背包问题（回溯法）

7.0-1背包问题（分支限界法）

算法设计与分析/数据结构与算法实验7：0-1背包问题（分支限界法）