目录

第1讲算法引论

作业1-1

1. (单选题, 5分)算法研究领域包括的三个主要方面为( A  )

2. (单选题, 5分)下面说法关于算法与问题的说法错误的是（B）。

3. (单选题, 5分)下面关于程序和算法的说法不正确的是（B）。

4. (单选题, 5分)对于以下给出的解决问题的基本步骤，正确的基本过程为（D ）。

5. (单选题, 5分)算法与程序的区别是（A）

6. (判断题, 5分)证明算法不正确，只需给出一个反例，算法不能正确处理即可。

7. (判断题, 5分)算法是一个语句集合，按照顺序执行语句，处理实例，得到正确答案。

8. (判断题, 5分)计算机每次求解是针对问题的每个实例求解。

9. (判断题, 5分)问题的两个要素是输入和实例。

作业1-2

1. (单选题, 5分)

2. (单选题, 5分)

3. (单选题, 5分)

4. (单选题, 5分)

5. (单选题, 5分)若函数间的关系有：f1(n) = O( g(n) )，f2(n) = Θ( g(n) )，则以下正确的是（     ）。

6. (单选题, 5分)

7. (单选题, 5分)

8. (单选题, 5分)设 f 和g是定义域为自然数集N上的函数，若有f(n) = Ω( g(n) )，则表示f(n)的阶（       ）g(n)的阶。

9. (单选题, 5分)若有函数f(n) = 1.3n / 2 - 5，g(n) = n4 + 2n2 + n/2，则以下正确的是（     ）。

10. (单选题, 5分)

11. (判断题, 5分)若有f(n) = W ( g(n) )，则f(n)2 = W ( g(n) 2)  

12. (判断题, 5分)f(n) = Θ( g(n) )  当且仅当g(n) = Θ( f(n) )

13. (判断题, 5分) f(n) = O( g(n) )  当且仅当log(f(n)) = O( log(g(n)) )

14. (判断题, 5分)f(n) = O( g(n) )  当且仅当g(n) = Ω( f(n) )

作业1-3

1. (单选题, 5分)

2. (单选题, 5分)在算法的时间复杂度分析中，其中比较容易分析和计算且最有实际价值的是（    ）

3. (单选题, 5分)常用的指数时间算法的时间复杂度可能为：O(nn)，O(2n)，O(n!)，则给定的这三种指数时间算法的时间复杂度的大小关系为          。

4. (单选题, 5分)

5. (单选题, 5分)

6. (单选题, 5分)

7. (单选题, 5分)

8. (单选题, 5分)算法必须满足定义中的5个特征，而程序不需要满足5个特征中的（   ）

9. (单选题, 5分)

10. (单选题, 5分)

作业1-4

1.简答题

2. (简答题)

3. (简答题)

4. (简答题)

5. (简答题)

6. (简答题)

7. (简答题)

8. (简答题)

9. (简答题)

10. (填空题)

第2讲枚举算法

作业2-1

1. (填空题, 15分)

2. (填空题, 10分)

3. (填空题, 5分)

4. (填空题, 10分)

作业2-2

1. (单选题, 5分)通常可用枚举算法求解的问题是（      )。

2. (单选题, 5分)下列问题中不适合使用枚举算法解决的是（    ）。

3. (填空题, 20分)

4. (填空题, 5分)

5. (填空题, 15分)

6. (填空题, 10分)

作业2-3

1. (多选题, 5分)

2. (填空题, 15分)

3. (填空题, 10分)

4. (填空题, 10分)

5. (填空题, 20分)

作业2-4

1. (填空题, 5分)

2. (填空题, 15分)

3. (填空题, 15分)

4. (填空题, 15分)

第3讲 分治算法

作业3-1

1. (填空题, 35分)分治法解题步骤：

2. (填空题, 25分)

3. (单选题, 5分)

4. (单选题, 5分)使用分治法求解不需要满足的条件是（  ）。

5. (单选题, 5分)如下哪一个不是改进分治算法的方法（  ）。

6. (单选题, 5分)减少子问题个数，就是减少时间复杂度函数T(n)=aT(n/b)+f(n) 中的（   ）值。

作业3-2

1. (填空题, 30分)

2. (填空题, 25分)

3. (填空题, 25分)

作业3-3

1. (单选题, 5分)二路归并排序与快速排序都是典型的分治算法，以下说法不正确的是（   ）。

2. (填空题, 5分)将待排序的数组分解成左右两个规模大致相同的子数组，然后对这两个子数组分别进行排序，再将排好序的两个有序子数组合并成一个有序的数组，这是     排序的基本思想。

3. (填空题, 40分)

4. (填空题, 5分)以待排序数组的某个元素x为主元，将主元x放置到最终的排序位置，并将待排序数组划分成小于等于x和大于等于x的两部分，并分别再对这两部分递归排序。这种排序方法是      排序的基本思想。

作业3-4

1. (填空题, 35分)

2. (填空题, 15分)

作业3-5

1. (填空题, 30分)

作业3-6

1. (填空题, 20分)

2. (填空题, 30分)

作业3-7

1. (填空题, 25分)

第4讲 贪心算法

作业4-1

1. (填空题, 10分)

2. (填空题, 5分)

3. (单选题, 5分)

4. (填空题, 25分)

5. (单选题, 5分)上题（4题）

作业4-2

1. (单选题, 5分)使目标函数最大（小）的解是问题的（      ）。

2. (单选题, 5分)满足问题约束条件的解，称为（           ）。

3. (单选题, 5分)证明贪心算法时，把任意一个最优解逐渐变为贪心算法的解，不会影响其最优性，这种证明方法是(  )。

4. (填空题, 5分)问题的最优子结构性质是指一个问题的最优解包含其（            ）。（填写5字或6字）

5. (判断题, 5分)贪心算法的思想是寻求局部最优解，逐步达到全局最优解。

6. (判断题, 5分)贪心算法总能找到可行解，并且是最优解。

7. (判断题, 5分)贪心法处理问题的核心是贪心准则的选取。

作业4-3

1. (单选题, 5分)部分背包问题的贪心准则是按照各个物品的        来考察每个物品。

2. (填空题, 10分)

3. (填空题, 30分)

4. (单选题, 5分)上题（题3）的算法中的排序算法，采用的是          排序方法。

作业4-4

1. (填空题, 10分)

2. (单选题, 5分)

3. (填空题, 15分)

第5讲 动态规划算法

作业5-1

1. (单选题, 5分)一个问题能用动态规划方法求解，通常具有两个重要的性质。这两个性质为（    ）。

2. (填空题, 5分)最优子结构性质是指当一个问题的最优解包含了其（    ）。（填6字或7字）

3. (填空题, 40分)

作业5-2

1. (填空题, 10分)

2. (填空题, 25分)

3. (填空题, 25分)

作业5-3

1. (填空题, 5分)

2. (填空题, 30分)

3. (填空题, 60分)

作业5-4

1.(填空题, 30分)

2. (填空题, 55分)

---

第1讲算法引论

作业1-1

1. (单选题, 5分)算法研究领域包括的三个主要方面为( A  )

• A. 算法设计、算法证明和算法分析
• B. 算法实现、算法测试和算法改进
• C. 算法实现、算法证明和算法分析
• D. 算法设计、算法实现和算法分析

2. (单选题, 5分)下面说法关于算法与问题的说法错误的是（B）。

• A. 算法是一种计算方法，对问题的每个实例计算都能得到正确答案。
• B. 证明算法不正确，需要证明对任意实例算法都不能正确处理。 
• C. 同一问题可能有几种不同的算法，解题思路和解题速度也会显著不同。
• D. 如果一个算法能应用于问题的任意实例，并保证得到正确解答，称这个算法解答了该问题。

3. (单选题, 5分)下面关于程序和算法的说法不正确的是（B）。

• A. 算法是一个过程，计算机每次求解是针对问题的一个实例求解。
• B. 程序总是在有穷步的运算后终止。
• C. 算法的每一步骤必须要有确切的含义，必须是清楚的、无二义的。
• D. 程序是算法用某种程序设计语言的具体实现。

4. (单选题, 5分)对于以下给出的解决问题的基本步骤，正确的基本过程为（D ）。

（1）算法设计（2）算法实现（3）数学建模（4）算法分析（5）正确性证明

• A. (3)(1)(4)(5)(2) 
• B. (3)(4)(1)(5)(2) 
• C. (1)(2)(3)(4)(5)
• D. (3)(1)(5)(4)(2)

5. (单选题, 5分)算法与程序的区别是（A）

• A. 有穷性
• B. 输入
• C. 确定性
• D. 输出 

6. (判断题, 5分)证明算法不正确，只需给出一个反例，算法不能正确处理即可。

• A. 对   √
• B. 错

7. (判断题, 5分)算法是一个语句集合，按照顺序执行语句，处理实例，得到正确答案。

• A. 对   √
• B. 错

8. (判断题, 5分)计算机每次求解是针对问题的每个实例求解。

• A. 对
• B. 错   ×

9. (判断题, 5分)问题的两个要素是输入和实例。

• A. 对
• B. 错   ×

---

作业1-2

1. (单选题, 5分)

对于某规模为n的问题，其求解算法的时间效率递推方程为：

T(n) = 2T(n/2) + nlogn

T(1) = 0

则该算的时间复杂度为（    ）。

• A. Θ(nlogn) 
• B. Θ(n) 
• C. Θ(nlog2n) 
• D. Θ(n2)

我的答案: C:Θ(nlog2n) ;正确答案: C:Θ(nlog2n) ;

5分

答案解析：

本题不满足主定理情况3，所以不能用主定理求解，可用递推树求解。

2. (单选题, 5分)

若有函数f(n) = 3nlog2n + 2n，g(n) = n1.2+3，则以下正确的是（     ）。

• A. f(n) = Ω( g(n) )
• B. f(n) = Θ( g(n) )
• C. g(n) = ω( f(n) )
• D. g(n) = O( f(n) )

正确答案: C:g(n) = ω( f(n) );

3. (单选题, 5分)

• A. f(n) = Ω( g(n) )
• B. f(n) = Θ( h(n) )
• C. g(n) = ω( h(n) )
• D. f(n) = O( g(n) )

正确答案: A:f(n) = Ω( g(n) );

答案解析：

4. (单选题, 5分)

• A. f(n) = ω( g(n) )
• B. f(n) = o( g(n) )
• C. g(n) = o( f(n) )
• D. f(n) = Θ( g(n) )

正确答案: D:f(n) = Θ( g(n) );

5. (单选题, 5分)若函数间的关系有：f1(n) = O( g(n) )，f2(n) = Θ( g(n) )，则以下正确的是（     ）。

• A. f1(n) = Θ( f2(n) )
• B. f2(n) = O( f1(n) )
• C. f1(n) = o( f2(n) )
• D. f2(n) = Ω( f1(n) )

正确答案: D:f2(n) = Ω( f1(n) );

6. (单选题, 5分)

以下描述中正确的个数为（     ）。

（1）若有f(n) = O(g(n))，则表明函数f(n)的阶不高于函数g(n)的阶；

（2）若有f(n) = Ω(g(n))，则表明函数f(n)的阶高于函数g(n)的阶；

（3）若有f(n) = Θ(g(n))，则表明函数f(n)的阶等于函数g(n)的阶；

（4）若有f(n) = ω(g(n))，则表明函数f(n)的阶不低于函数g(n)的阶；

• A. 2
• B. 3
• C. 4
• D. 1

正确答案: A:2;

7. (单选题, 5分)

以下关于渐近记号的性质，正确的是（ ）

• A.

  O(g(n))+O(h(n))  =>  O( min{f(n), g(n)} )

• B.

  f(n)=O(g(n)), g(n)=O(h(n)) => f(n)=O(h(n))

• C.

  f(n)=O(g(n))  <=>  g(n) = O(f(n))

• D.

  f(n)=O(g(n)), g(n)=O(h(n))  =>  h(n)=O(f(n))

正确答案: B:f(n)=O(g(n)), g(n)=O(h(n)) => f(n)=O(h(n));

8. (单选题, 5分)设 f 和g是定义域为自然数集N上的函数，若有f(n) = Ω( g(n) )，则表示f(n)的阶（       ）g(n)的阶。

• A. 不高于
• B. 逼近
• C. 不低于
• D. 等价于

正确答案: C:不低于;

9. (单选题, 5分)若有函数f(n) = 1.3n / 2 - 5，g(n) = n4 + 2n2 + n/2，则以下正确的是（     ）。

• A. g(n) = o( f(n) )
• B. f(n) = O( g(n) )
• C. g(n) = ω( f(n) )
• D. f(n) = o( g(n) )

正确答案: A:g(n) = o( f(n) );

10. (单选题, 5分)

算法时间复杂度的表示中，以下符号中用于表示算法运行时间的上界的是（     ）。

• A.Θ 
• B.Ω 
• C.ω
• D.O

正确答案: D:O;

11. (判断题, 5分)若有f(n) = W ( g(n) )，则f(n)2 = W ( g(n) 2)  

• A. 对
• B. 错

正确答案: 对

12. (判断题, 5分)f(n) = Θ( g(n) )  当且仅当g(n) = Θ( f(n) )

• A. 对
• B. 错

正确答案: 对

13. (判断题, 5分) f(n) = O( g(n) )  当且仅当log(f(n)) = O( log(g(n)) )

• A. 对
• B. 错

正确答案: 对

14. (判断题, 5分)f(n) = O( g(n) )  当且仅当g(n) = Ω( f(n) )

• A. 对
• B. 错

正确答案: 对

---

作业1-3

1. (单选题, 5分)

下面算法的时间复杂度是

i=n; sum=0;

while(i>0)

{   sum=sum+a[i];  i=i/2;  }

• A. Θ(1) 
• B. Θ(logn)
• C. Θ(n1/2) 
• D. Θ(n) 

正确答案: B:Θ(logn);

2. (单选题, 5分)在算法的时间复杂度分析中，其中比较容易分析和计算且最有实际价值的是（    ）

• A. 最坏时间复杂度 
• B. 最好时间复杂度
• C. 平均时间复杂度 
• D. 最好时间复杂度和最坏时间复杂度

正确答案: A:最坏时间复杂度 ;

3. (单选题, 5分)常用的指数时间算法的时间复杂度可能为：O(nn)，O(2n)，O(n!)，则给定的这三种指数时间算法的时间复杂度的大小关系为          。

• A. O(2n)< O(n!)< O(nn)
• B. O(nn) <O(2n)< O(n!)
• C. O(n!) <O(2n)< O(nn)
• D. O(n!) < O(nn)< O(2n)

正确答案: A:O(2n)< O(n!)< O(nn);

4. (单选题, 5分)

下面算法的时间复杂度是

int Sum3(int a[][MAX], int n) {

    int i, j, total = 0;

    for( i = 0; i < n; i ++)

        for( j = 0; j <= i; j ++)  total += a[i][j];

    return  total;

}

• A. Θ(n3/2) 
• B. Θ(n2) 
• C. Θ(n) 
• D. Θ(nlogn)  

正确答案: B:Θ(n2) ;

5. (单选题, 5分)

下面算法的时间复杂度是（    ）

int Sum(int n){

int i=0, s=0;

while(s<n){  i++;  s+=i;  }

return s;

}

• A.  Θ(n2)
• B.  Θ(n1/2)
• C. Θ(logn) 
• D. Θ(n)

正确答案: B: Θ(n1/2);

6. (单选题, 5分)

下面算法的时间复杂度是（      ）

int Sum(int n){

   int total, i;

   total=0; i=1;

   while(i<=n) { total=total+i; i=i+2; }

   return total;

}

• A. Θ(n1/2)
• B. Θ(n)
• C. Θ(logn) 
• D. Θ(n2) 

正确答案: B:Θ(n);

7. (单选题, 5分)

下面算法的时间复杂度是

count=0;

for(i=0; i<n; i++)

      for(j=1; j<=n; j=j*2)  count++;

• A. Θ(nlogn)
• B. Θ(n2) 
• C. Θ(n3/2) 
• D. Θ(n) 

正确答案: A:Θ(nlogn);

8. (单选题, 5分)算法必须满足定义中的5个特征，而程序不需要满足5个特征中的（   ）

• A. 确定性
• B. 能行性
• C. 有限性
• D. 输入

正确答案: C:有限性;

9. (单选题, 5分)

下面算法的时间复杂度是（      ）

int Sum(int n){

   int i=1, total=0;

   while(i<=n) { total=total+i; i=i*2; }

   return total;

}

• A. Θ(n1/2)
• B. Θ(n2)
• C. Θ(logn) 
• D.  Θ(n)  

正确答案: C:Θ(logn) ;

10. (单选题, 5分)

下面算法的时间复杂度是

count=0;

for(i=n; i>0; i=i/2)

     for(j=0; j<n; j++)  count++;

• A. Θ(nlogn)  
• B. Θ(n) 
• C. Θ(n3/2) 
• D. Θ(n2) 

正确答案: A:Θ(nlogn) ;

---

作业1-4

1.简答题

采用直接迭代法求解如下递推方程，即给出通项公式，并给出大Θ表示。

    T(n) = 2T(n-1) + 1

    T(1) = 1

答题说明：笔答，拍照上传，上传图片要清晰，且上传图片方向正确（文字方向向上）。

正确答案：

解： T(n) = 2T(n-1) + 1

         = 2[ 2T(n-2)+1] + 1 = 22T(n-2) + 2 + 1

         = 22[2T(n-3)+1] + 2 + 1 = 23T(n-3) + 22 + 2 + 1

         = ……

         = 2n-1T(1) + 2n-2 + …… + 2 + 1

         = 2n-1 + 2n-2 + …… + 2 + 1

         = 2n - 1

         = Θ(2n)

2. (简答题)

采用直接迭代法求解如下递推方程，即给出通项公式，并给出大Θ表示。

   T(n) = T(n-1) + n

   T(2) = 2

答题说明：笔答，拍照上传，上传图片要清晰，且图片方向正确（文字方向向上）。

正确答案：

解：T(n) = T(n-1) + n

              = T(n-2) + n-1 + n

              = ……

              = T(2) + 3 + 4 + ……+ n-1 + n

              = 2 + 3 + 4 + ……+ n-1 + n

              = (2 + n)(n - 1) / 2

              = Θ(n2)

3. (简答题)

用主定理求解递推方程：

     T(n)= 9T(n/3) + n

答题说明：笔答，拍照上传，上传图片要清晰，且图片方向正确（文字方向向上）。

正确答案：

答案解析：

4. (简答题)

用主定理求解递推方程：

     T(n)= T(2n/3) + 1

答题说明：笔答，拍照上传，上传图片要清晰，且图片方向正确（文字方向向上）。。

正确答案：

5. (简答题)

用主定理求解二路归并排序的递推方程：

     T(n) = 2T(n/2) + n - 1

答题说明：笔答，拍照上传，上传图片要清晰，且图片方向正确（文字方向向上）。

正确答案：

6. (简答题)

用主定理求解递推方程：

T(n)=3T(n/4) + nlogn

答题说明：笔答，拍照上传，上传图片要清晰，且图片方向正确（文字方向向上）。

正确答案：

7. (简答题)

算法A：将原问题划分规模减半的5个子问题，递归求解每个子问题。然后在线性时间将子问题的解合并得到原问题的解。

（1）给出该算法的递推方程。

（2）直接给出此算法的时间复杂度。（不需要给出求解过程）

答题说明：笔答，拍照上传，上传图片要清晰，且图片方向正确（文字方向向上）。

正确答案：

（1）递推方程 ：T(n)=5T(n/2)+Θ(n)

（2） 时间复杂度 ：T(n)=Θ(nlog25)

8. (简答题)

算法B：先递归求解两个规模为n-1的子问题，然后在常量时间内将子问题的解合并。

（1）给出该算法的递推方程。

（2）直接给出此算法的时间复杂度。（不需要给出求解过程）

答题说明：笔答，拍照上传，上传图片要清晰，且图片方向正确（文字方向向上）。。

正确答案：

（1）递推方程：T(n)=2T(n-1)+Θ(1)

（2）时间复杂度：T(n)=Θ(2n)

9. (简答题)

算法C：将原问题划分规模为n/3的9个子问题。递归求解每个子问题，然后在Θ(n3)时间将子问题的解合并得到原问题的解。

（1）给出该算法的递推方程。

（2）直接给出此算法的时间复杂度。（不需要给出求解过程）

正确答案：

（1）递推方程： T(n)=9T(n/3)+Θ(n3)

（2） 时间复杂度 ：T(n)=Θ(n3)

10. (填空题)

以上三题所给的算法A、算法B、算法C中，在最坏情况下，时间复杂度最低的是算法（  ），时间复杂度最高的是算法（  ）。

我的答案：

10分

(1) A 

(2) B 

正确答案：

(1) A; a; 算法A

(2) B; b; 算法B

---

---

---

第2讲枚举算法

作业2-1

1. (填空题, 15分)

一个三位数的每个数位上的立方和等于该数，则此三位数称为水仙花数。现欲枚举所有的三位数，并将每个数位上的数设为枚举变量，若百位数变量为a，十位数变量为b，个位数变量为c，则这些枚举变量的取值范围分别为         ①       (a的范围），         ②      (b的范围），0<=c<=9，且a,b,c为非负整数（空①和②用题中所给c的取值范围形式给出）。该问题求解的约束条件应为a3+b3+c3=          ③             （用含有枚举量a,b,c的算数表达式表示）。

正确答案：

(1) 1<=a<=9

(2) 0<=b<=9

(3) a*100+b*10+c；100a+10b+c ;  a×100+b×10+c; 100×a+10×b+c ; 100*a+10*b+c  

2. (填空题, 10分)

设计枚举算法时，通常要根据问题的具体情况确定枚举变量，并由枚举变量的        来设置枚举循环，而枚举循环的重数则与          的个数有关。

正确答案：

(1) 数值范围; 值域; 取值范围

(2) 枚举变量;枚举对象; 枚举量

3. (填空题, 5分)

一一列举问题所涉及的所有情况，并根据问题的条件来判断哪些是问题的解，哪些不是，这种算法设计策略的算法统称为      算法。（填2字）

正确答案：

(1) 枚举;穷举;蛮力;暴力

4. (填空题, 10分)

改进枚举算法时间效率的方法通常有减少枚举变量的                 、缩小枚举变量的                    及优化数学模型等方式。

正确答案：

(1) 个数

(2) 值域;取值范围

---

作业2-2

1. (单选题, 5分)通常可用枚举算法求解的问题是（      )。

• A. 一切问题
• B. 解的个数非常多的问题
• C. 解的个数无限的问题
• D. 解的个数有限且能逐一列举的问题

正确答案: D:解的个数有限且能逐一列举的问题;

2. (单选题, 5分)下列问题中不适合使用枚举算法解决的是（    ）。

• A. 判断自然数n (n>1）是否为素数
• B. 计算某个自然数的因子之和
• C. 查找100以内所有能被6整除且不能被10整除的数
• D. 计算一元二次方程的实数解

正确答案: D:计算一元二次方程的实数解;

3. (填空题, 20分)

百钱买百鸡问题：鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一；百钱买百鸡，则翁、母、雏各几何？求解该问题的枚举算法如下。

1  int x, y, z;   //x为公鸡数，y变母鸡数，z为小鸡数

2  for( x = 0; x <20; x++ )

3  {        for( y = 0; y <34; y++ )

4           {      for( z = 0; z < 100;  z++ )

5                          if( z%3==0 &&          ①        && 5*x+3*y+z/3==100 )

6                                    printf("Cock:%d, Hen:%d, Chick:%d\n", x, y, z);

7           }

8  }

（1）填写空①处所缺代码。

（2）算法中最内层的循环体（即if语句）的执行次数为          （给出准确数值）

（3）若采用除去“行5”的if语句中的条件“z%3 == 0”以减少枚举变量的取值范围来提高算法效率，可将行4中的代码“z++”改为：                    

（4）现采用减少枚举变量个数的方式来提高算法效率，即利用行5的空①处的条件，来消除行4的循环。删除行4的for循环语句，还需在此行位置添加的代码行：

                            ;    //语句末不需再填入语句结束符“；”

正确答案：

(1) x+y+z == 100; 100==x+y+z ; x+z+y == 100;  z+y+x == 100; 

(2) 68000

(3) z=z+3; z+=3; z=3+z

(4) z=100-x-y; z=100-(x+y) 

4. (填空题, 5分)

逆序数问题：如果对于数组a[1:n]中的任意两个下标i和j（1≤i≤n，1≤j≤n），当i<j时，有a[i]>a[j]，则数偶（a[i]，a[j]）就称为数组a的一个逆序。给定一个数组a，求解a中包含的逆序个数。

数组a[1:6]={ 4，7，3，6，8，2 }共有             个逆序数。

正确答案：

(1) 8

5. (填空题, 15分)

求逆序数的枚举算法算法如下，将算法的空缺填写完整。

int inverNum(int a[], int n)  //函数返回数组a[1:n]中逆序数,

{         int i, j, count = 0;

          for( i = 1; i<=               ; i++)   //i是数偶中第一个数的可能下标

          {      for( j =               ; j<=n; j++)  //j是数偶中第二个数的可能下标

                   {      if(                          )  count++;      }   //累计逆序数偶个数

          }

          return count;

}

正确答案：

(1) n-1

(2) i+1;  1+i

(3) a[i]>a[j]; a[j]<a[i]

答案解析：

6. (填空题, 10分)

生日蜡烛问题：某君从某年开始每年都举办一次生日party，并且每次都要吹熄与年龄相同根数的蜡烛。现在算起来，他一共吹熄了n根蜡烛。请问，他从多少岁开始过生日party的？求解该问题的算法如下，填写算法中的空缺。

void birthday(int n )  //参数n为共吹熄的蜡烛数

{      int s, total, i;   //s为开始生日party的年龄

        for( s=1;                    ; s++)  //枚举所有可能的s

        {        total=0;

                 for( i = s;                       ; i++ )  total += i;

                 if( total == n )

                 {      printf("开始：%d岁,现在%d岁\n",s, i-1);  } //

        }    

}

正确答案：

(1) s<=n;  n>=s

(2) total<n; n>total

---

作业2-3

1. (多选题, 5分)

任何一个自然数都能被1和它本身所整除，而所有小于它本身的因子称为这个自然数的真因子，如果一个自然数的所有真因子之和等于这个自然数本身，则称这个自然数为完美数。下面给出的数中是完美数的有（        ）（多选题）。

• A. 5
• B. 6
• C. 7
• D. 8
• E. 16
• F.  28

正确答案: BF:6; 28;

2. (填空题, 15分)

判断自然数n是否为完美数的枚举算法如下，将算法的空缺填写完整。

int perfect(int n)    //若n是完美数函数返回1，否则返回0

{   int i,sum=0;

    for(i=1; i<=              ; i++)      //穷举出n的所有可能的真因子

           if(                           ) sum=sum+i;         //若i为n的真因子

    if(                               )  return 1;

    else  return 0;   

}

正确答案：

(1) n/2;  n-1

(2) n%i==0;  （n%i)==0;  !(n%i)  

(3) sum==n; n==sum

3. (填空题, 10分)

判断自然数n是否为完美数的枚举算法如下，将算法的空缺填写完整。

int perfect2( int n )  

{      int i, s = 1, t = sqrt(n) ;

       for( i = 2;  i <= t ;  i++ )

       {       if( n%i == 0 )   s +=                      ;  

       } 

       if(  n%t == 0 &&                    )  s=s-t      

       if( s == n )  return 1;

       else  return 0; 

}

正确答案：

(1)  i+n/i ; n/i+i

(2)  t==n/t；n/t==t

4. (填空题, 10分)

欧几里得完美数定理为：如果整数p和2p-1均为素数，则2p-1(2p-1)是完美数。则素数3所对应的完美数是         ，素数5所对应的完美数为          。

正确答案：

(1) 28

(2) 496

5. (填空题, 20分)

利用欧几里得完美数定理求完美数的程序如下。

int prime(long long n)    //素数的判定算法，若n是素数返回1，否则返回0

{      int k=(int)sqrt(n);

        for(int i=2; i<=k; i++)

                 if(                  )  return 0; 

        return 1;

}

int main()

{      long long t, x, y;    //变量t表示2p，x表示2p-1，y表示2p-1

        for( int p=2; p<=31; p++ )    //利用2到31之间的素数求相应的完美数

        {      if(                   )       //调用prime算法判断p是否为素数

                 {      t=1;

                         for(int k=1; k<=p; k++)  t=               ;   //求t=2p

                         x=                 ;  

                         y=t-1;       

                         if( prime(y) )  printf("%I64d*%I64d=%I64d\n", x, y, x*y);   

                 }

        }

        return 0; 

}

正确答案：

(1) n%i==0; (n%i)==0; 0==n%i; 0==(n%i);  !(n%i)

(2) prime(p)==1; 1==prime(p); prime(p)

(3) t*2; 2*t

(4) t/2

---

作业2-4

1. (填空题, 5分)

最简真分数问题：对于一个分数而言，如果它的分子小于分母，则我们称这样的分数为真分数，如果一个真分数的分子与分母无大于1的公因子，即不存在大于等于2的公因子，则称这样的真分数为最简真分数。则分母在2到5之间的最简真分数共有         个。

正确答案：

(1) 9

答案解析：

2. (填空题, 15分)

函数fraction的作用是：采用枚举算法策略，分母在区间[a,b]内的最简真分数个数；函c[i]与d[i]分别存放所求得的第i个最简真分数的分子与分母数；函数最终返回所求得的最简真分数个数。将算法中空缺代码补充完整。

int fraction(int a, int b, int c[], int d[] ) // 求解最简真分数

{      int x, y, k, i=0;

        for( x = a; x<=b; x++)  //枚举分母x的可能取值

        {      for( y = 1;  y <=             ;  y++)  //枚举分子y的可能取值

                 {      for( k = 2; k <= y; k++ )   //枚举x和y所有可能大于1的公因子

                                  if(                                  ) break;  

                         if(                       )  //若分子x和分母y无大于1的公因子

                        {  i++;  c[i]=y; d[i]=x; }

                 } 

        }

        return i;    

}

我的答案：

15分

(1) x-1 

(2) x%k==0&&y%k==0 

(3) k>y 

正确答案：

(1) x-1

(2)

x%k==0 && y%k==0;   (x%k)==0 && (y%k)==0;   0==x%k && 0==y%k;   0==(x%k) && 0==(y%k); 

y%k==0 && x%k==0;   (y%k)==0 && (x%k)==0;   0==y%k && 0==x%k;   0==(y%k) && 0==(x%k); 

(x%k==0)&& (y%k==0) ;   ((x%k)==0) && ((y%k)==0);   (0==x%k) && (0==y%k);   (0==(x%k)) && (0==(y%k));

(y%k==0)&& (x%k==0) ;   ((y%k)==0) && ((x%k)==0);   (0==y%k) && (0==x%k);   (0==(y%k)) && (0==(x%k));

!(x%k)&&!(y%k); !(y%k)&&!(x%k) 

(3) k>y; y<k

3. (填空题, 15分)

数组c和d所表示的n个（下标1~n）最简真分数，c[i]与d[i]分别存放所求得的第i个最简真分数的分子与分母。现对这n个最简真分数采用冒泡排序方法进行递增排序。给定算法如下，将算法中空缺代码补充完整。

void swap(int a[], int i, int j)  //交换数组元素a[i]与a[j]的值

{      int temp;

        temp=a[i]; a[i]=a[j]; a[j]= temp;

}

int fracSort(int c[], int d[], int n )

{      //对用数组c和d所表示的n个（下标1~n）最简真分数进行冒泡排序(递增)

        for( int i = 1; i < n; i++)

        {      for( int j = 1; j <=                ; j++) 

                 {      if( c[j]*d[j+1] >                               )

                         {      swap(c, j, j+1);       

                                                              ;

                         }     

                 } 

        }              

}

正确答案：

(1) n-i

(2) c[j+1]*d[j]; d[j]*c[j+1]

(3) swap(d, j, j+1)

答案解析：

4. (填空题, 15分)

最大子段和问题：给定由 n 个整数（可能为负整数）组成的序列 L = (a1, a2, …，an )，若序列S = ( ai, ai+1, …，aj-1,aj) (1 ≤ i ≤ j ≤n)，则将 S 称为序列 L 的一个子段，子段 S中所有元素的和称为该子段的和。现要求出序列 L 的各个子段的和的最大值，当序列中所有整数均为负整数时定义其最大子段和为0。

求解最大子段和问题的枚举算法如下，将算法中空缺代码补充完整。

int  maxSum(int a[ ], int n, int &posi, int &posj)

{      //求a[1:n]所表示序列的最大子段和并将其由函数返回

       //参数posi、posj返回该最大子段的起止下标位置

       int max = 0, i, j;

       for( i = 1; i <= n; i++ )         //枚举变量i为子段的起始位置（下标）

       {     int  s = 0;

              for( j =              ;  j<=n;  j++)  //枚举变量j为子段的结束位置（下标）

              {      s =                ;                   //计算子段(a[i]~a[j])的和

                     if(                )

                     {   max = s;  posi = i;  posj=j;   }

              }

       }

       return max;

}

正确答案：

(1) i

(2) s+a[j]; a[j]+s

(3) s > max ; max<s

---

---

---

第3讲 分治算法

作业3-1

1. (填空题, 35分)分治法解题步骤：

第一步是将待求解的问题分解成若干  【空1】  较小、相互  【空2】  ，且与原问题类型相同的  【空3】  ；（分别填2字、2字、3字）

第二步是  【空4】  地求解这些子问题的解；（填2字）

第三步是将各个子问题的解  【空5】  成  【空6】  的解。（分别填2字、3字）

用三个字来概括每一步就是：“  【空7】  ”。（三个字间用逗号“,”分隔）

正确答案：

(1) 规模

(2) 独立

(3) 子问题

(4) 递归

(5) 合并; 组合

(6) 原问题

(7) 分,治,合;  分，治，合

答案解析：

2. (填空题, 25分)

可用分治法求解的问题的基本要素：

第一，问题规模足够 【空1】时可以直接求解；（填1字）

第二，当问题规模较大时，问题能够按照某种方式  【空2】  成若干个规模  【空3】  、相互独立且与 【空4】  类型相同的子问题；（分别填2字、2字、3字）

第三，能够将  【空5】  的解组合成原问题的解；（填3字）

正确答案：

(1) 小

(2) 分解

(3) 较小

(4) 原问题

(5) 子问题

3. (单选题, 5分)

分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题，分别解决子问题，最后将子问题的解组合起来形成原问题的解。这要求原问题和子问题（    ）。

• A. 问题规模相同，问题性质不同
• B. 问题规模不同，问题性质相同
• C. 问题规模相同，问题性质相同
• D. 问题规模不同，问题性质不同

正确答案: B:问题规模不同，问题性质相同;

4. (单选题, 5分)使用分治法求解不需要满足的条件是（  ）。

• A. 子问题不能够重复
• B. 子问题的解可以合并
• C. 子问题必须具有相同的性质
• D. 原问题和子问题使用相同的方法求解

正确答案: A:子问题不能够重复;

5. (单选题, 5分)如下哪一个不是改进分治算法的方法（  ）。

• A. 减少子问题的个数
• B. 改进分治的均衡度
• C. 减少合并的时间
• D. 减少问题的规模

正确答案: D:减少问题的规模;

6. (单选题, 5分)减少子问题个数，就是减少时间复杂度函数T(n)=aT(n/b)+f(n) 中的（   ）值。

• A. f(n)
• B. b
• C. a
• D. n

正确答案: C:a;

---

作业3-2

1. (填空题, 30分)

快速排序

（1）基于分治策略的快速排序（递增）算法如下，填写算法空白。

//一趟快速排序：对数组a[low:high]的一种划分

int partition( int a[ ], int low, int high)

{     a[0] = a[low];  //a[low]作为枢轴，a[0]作为临时变量

       while( low<high )

       {     while(low<high && a[high]>=a[0]) high--;  //从后向前找小的

              a[low] = a[high]; //将小于枢轴的数放到前面

              while(low<high &&       【空1】    ) low++;  //从前向后找大的

                     【空2】       ;   //将大于枢轴的数放到后面

       }

              【空3】      ; //枢轴到位

       return low;

}

//对数组a[low:high]进行快速排序（递增）

void quickSort(int a[],int low,int high) 

{     if(low<high)

       {      int loc=         【空4】         ;

              quickSort(a, low, loc-1);

                          【空5】            ;

       }

} 

（2）设有9个元素的数组a[1:9]=( 65, 26, 70, 88, 42, 80, 75, 65, 60 )，则该序列的第一趟快速排序后的结果为（              【空6】              ）。（注：给出数组a[1:9]的值，数值间用英文逗号分隔）

我的答案：

(1) a[low]<=a[0] 

(2) a[high]=a[low] 

(3) a[low]=a[0] 

(4) partition(a,low,high) 

(5) quickSort(a,loc+1,high)

(6) 60,26,42,65,88,80,75,65,70 

正确答案：

(1) a[low] <= a[0] ；a[0] >= a[low] 

(2) a[high] = a[low]

(3) a[low] = a[0]

(4) partition(a,low,high) 

(5)  quickSort(a, loc+1, high);

(6) 60, 26, 42, 65, 88, 80, 75, 65, 70 ；（60, 26, 42, 65, 88, 80, 75, 65, 70）

2. (填空题, 25分)

一趟快速排序

（1）基于分治策略的快速排序（递增）的一趟排序的另一种划分算法如下，填写算法空白。

//一趟快速排序：以a[low]作为枢轴对数组a[low:high]的划分

int partition(int a[], int low, int high)

{      int i=low, j=high+1, t; 

       while(i<j)

       {      j--;

              while(i<j &&       【空1】    ) j--; //从后向前找不大的 

              i++;

              while(i<j &&      【空2】       ) i++; //从前向后找大的        

              if(i<j) { t=a[i]; a[i]=a[j];  a[j]=t;  }

       }

       t=a[low];  a[low]=a[j];  a[j]=t;   

       return     【空3】   ; 

} 

（2）设有9个元素的数组a[1:9]=( 65, 26, 75, 88, 42, 80, 55, 65, 60 )，则该序列的第一趟快速排序后的结果为（          【空4】        ），此时枢轴元素到达的位置（下标）为   【空5】   。（注：空【4】给出数组a[1:9]的值，数值间用英文逗号分隔）

我的答案：

(1) a[j]>a[low] 

(2) a[i]<=a[low] 

(3) j

(4) 55,26,60,65,42,65,80,88,75

(5) 6
 

正确答案：

(1) a[j]>a[low] ;  a[low]<a[j]

(2) a[i]<=a[low] ;  a[low]>=a[i]

(3) j

(4) 55, 26, 60, 65, 42, 65, 80, 88, 75 ;  (55, 26, 60, 65, 42, 65, 80, 88, 75)

(5) 6

3. (填空题, 25分)

一趟快速排序

（1）基于分治策略的快速排序（递增）的一趟排序的算法如下，填写算法空白。

//一趟快速排序：以a[low]作为枢轴对数组a[low:high]进行分划操作

int partition(int a[ ],int low,int high) 

{     //以high+1处元素做为向后查找时的右端哨兵

       //初始：i指向枢轴位置，j指向右端哨兵位置, t用于交换

       int i=low, j=high+1,t;    

       while(i<j)

       {      i++;

              while(a[i]<a[low]) i++;  //向后找，直到找到不小于枢轴的

              j--;

              while(    【空1】   ) j--; //向前找，直到找到不大于枢轴的

              if(      【空2】   ) { t=a[i]; a[i]=a[j]; a[j]=t; }

       }

       t=a[low]; a[low]=a[j]; a[j]=t;

       return    【空3】  ;

}

（2）设有9个元素的数组a[1:9]=( 65, 70, 75, 80, 85, 60, 55, 50, 45 )，则该序列的第一趟快速排序后的结果为             【空4】        。（注：给出数组a[1:9]的值，数值间用英文逗号分隔）

（3）设有9个元素的数组a[1:9]=(70, 26, 57, 88, 42, 80, 72, 48, 60)，则该序列的第一趟快速排序后的结果为               【空5】        。（注：给出数组a[1:9]的值，数值间用英文逗号分隔）

我的答案：

(1) a[j]>a[low] 

(2) i<j 

(3) j 

(4) 60,45,50,55,65,85,80,75,70

(5) 48,26,57,60,42,70,72,80,88 

正确答案：

(1) a[j]>a[low]; a[low]<a[j]

(2) i<j;  j>i

(3) j

(4) 60,45,50,55,65,85,80,75,70 ;  (60,45,50,55,65,85,80,75,70)

(5) 48,26,57,60,42,70,72,80,88 ;  (48,26,57,60,42,70,72,80,88)

---

作业3-3

1. (单选题, 5分)二路归并排序与快速排序都是典型的分治算法，以下说法不正确的是（   ）。

• A. 二路归并排序与快速排序都采用的都是二分法思想。
• B. 二路归并排序与快速排序子题的划分都采用均分方法。
• C. 二路归并排序算法中两个子问题的划分工作量为常数C，合并工作量Θ(n)。
• D. 快速排序算法中两个子问题的划分工作量为Θ(n)常数C，且不需要合并。

正确答案: B:二路归并排序与快速排序子题的划分都采用均分方法。;

2. (填空题, 5分)将待排序的数组分解成左右两个规模大致相同的子数组，然后对这两个子数组分别进行排序，再将排好序的两个有序子数组合并成一个有序的数组，这是     排序的基本思想。

正确答案：

(1) 归并; 二路归并

3. (填空题, 40分)

如下为基于分治思想的归并排序算法，填写算法空白。

说明：（1）merge算法为相邻两个有序表的合并算法。已知左子数组a[low:mid]递增有序，右子数组a[mid+1:high]递增有序，merge算法将其归并后使得a[low:high]递增有序。（2）mergeSort算法则将a[low:high]进行归并排序（递增）。

 int b[100];  //b用作辅助数组

void merge(int a[], int low,int mid,int high)

{      int i=low, j=mid+1, k=low;

        while(          【空1】        ) //运算符仅限用<, <=, &&, ||

        {      if(a[i]<=a[j]) {    【空2】  ; i++; k++; }

                 else b[k++]=    【空3】   ;

        }

        while(i<=mid) b[k++]=a[i++];

        while(j<=high)     【空4】     ;

        for(i=low;i<=high;i++)     【空5】   ;

                //把辅助数组b中的元素依次放回原数组a

}

void mergeSort(int a[], int low, int high)

{      if(low==high)  return;

        int mid=     【空6】     ;

                   【空7】         ;    //递归对左子数组归并排序

        mergeSort(a, mid+1,high);  //递归对右子数组归并排序

                【空8】          ;

}

我的答案：

(1) i<=mid&&j<=high 

(2) b[k]=a[i] 

(3) a[j++] 

(4) b[k++]=a[j++] 

(5) a[i]=b[i] 

(6) (low+high)/2 

(7) mergeSort(a,low,mid) 

(8) merge(a,low,mid,high) 

正确答案：

(1)

 i<=mid && j<=high; j<=high && i<=mid ;

(i<=mid) && (j<=high); (j<=high) && (i<=mid)

(2) b[k]=a[i]

(3) a[j++]

(4)  b[k++]=a[j++]

(5) a[i]=b[i]

(6) (low+high)/2;  (high+low)/2

(7) mergeSort(a, low, mid)

(8) merge(a, low, mid, high)

4. (填空题, 5分)以待排序数组的某个元素x为主元，将主元x放置到最终的排序位置，并将待排序数组划分成小于等于x和大于等于x的两部分，并分别再对这两部分递归排序。这种排序方法是      排序的基本思想。

正确答案：

(1) 快速

---

作业3-4

1. (填空题, 35分)

分治法求解最大最小元素问题算法，填写算法空白。

//求数组a[i:j]的最大值和最小值

//max返回最大值，min返回最小值

void MaxMin( int a[], int i, int j, int &max, int &min ) 

{       if( i == j ) {  max=min=   【空1】  ;  return;  }

        if(   i==  【空2】  )   //只有两个元素时

        {      if(      【空3】     ) {  max = a[i];  min = a[j];  }

               else {  max = a[j];  min = a[i];  }

               return;

        }

        int max1, min1, mid;

        mid=       【空4】      ;

           //递归求解左子数组最大最小值分别存于max和min

                        【空5】                 ; 

           //递归求解右子数组的最大最小值分别存于max1和min1

                        【空6】                 ;

          if(max<max1) max=max1;

        if(      【空7】      ) min=min1;

}

我的答案：

(1) a[i] 

(2) j-1 

(3) a[i]>a[j] 

(4) (i+j)/2 

(5) MaxMin(a,i,mid,max,min) 

(6) MaxMin(a,mid+1,j,max1,min1) 

(7) min>min1 

正确答案：

(1) a[i]; a[j]

(2)  j-1

(3) a[i]>=a[j];   a[j]<=a[i];    a[i]>a[j];   a[j]<a[i]

(4) (i + j) / 2;  (j+ i) / 2

(5) MaxMin(a,  i,  mid,  max,  min) 

(6) MaxMin(a, mid+1, j, max1, min1)

(7) min>min1; min1<min

2. (填空题, 15分)

针对上题所给求解最大最小元素问题的分治法算法，回答如下问题。

（1）若用T(n)表示该算法的运行时的进行的比较次数，则其递推式为：

                     T(1) = 0，T(2) = 1

                     T(n) =       【空1】      （n>2）

（2）当n>2时，则T(n)=  【空2】  。（填写选项）

         A. 2n+2                    B. 2n+3                  C.3n/2-2                D. 2n-2

（3）该算法的时间复杂度为  【空3】  。（填写选项）

         A. Θ(logn)         B. Θ(n1/2)        C. Θ(n)           D. Θ(n2)

我的答案：

(1) 2T(n/2)+2 

(2) C 

(3) C 

正确答案：

(1) 2T(n/2)+2 

(2) C;c

(3) C;c

---

作业3-5

1. (填空题, 30分)

棋盘覆盖问题：有一个 n×n 的方格棋盘（n = 2k, k≥1 ），其中恰有一个方格残缺，此棋盘称为残缺棋盘。现要求用L形骨牌（三格板）覆盖除了特殊方格以外的其他全部方格，骨牌可以任意旋转，并且任何两个骨牌不能重不能重叠。给出一种覆盖方法。

现采用分治算法求解，设求解递归函数为solve(n,si,sj,pi,pj)，其中：n为棋盘大小，(si,sj)棋盘左上角坐标(行号,列号)，(pi,pj)为残缺方格坐标(行号,列号)。

对于一个8×8棋盘覆盖问题实例，采用数组board[0..7][0..7]表示该棋盘，求解函数solve(8,0,0,1,6)的过程如下：

（1）先将此8×8棋盘覆盖问题，分解成4×4的4个子棋盘块。

（2）再用一个三格板来覆盖棋盘中的3个棋盘格，则覆盖的3个棋盘格的坐标分别为：

          (3,3)、  【空1】  、（4,4)。

（3）然后递归调用solve函数求解4个子问题，对应调用函数分别为：

      solve(4,0,0,3,3);         //求左上角子棋盘覆盖问题

                【空2】        ;   //求右上角子棋盘覆盖问题

                【空3】        ;   //求左下角子棋盘覆盖问题

                【空4】        ;   //求右下角子棋盘覆盖问题

（4）当递归求解到1×1的棋盘问题时，什么也不需要做。

该问题时间效率的递推方程为：T(n)=   【空5】   + Θ(1); T(1) = 0

由此得出其时间复杂度为：       【空6】       。（填写选项）

         A） T(n)= Θ(n)   B）T(n)= Θ(n2)   C）T(n)= Θ(nlogn)   D）T(n)= Θ(n3)

我的答案：

(1) (4,3) 

(2) solve(4,0,4,1,6) 

(3) solve(4,4,0,4,3) 

(4) solve(4,4,4,4,4) 

(5) 4T(n/2) 

(6) B 

正确答案：

(1)  (4,3)

(2) solve(4,0,4,1,6)

(3) solve(4,4,0,4,3)

(4) solve(4,4,4,4,4)

(5) 4T(n/2) 

(6) B;b

---

作业3-6

1. (填空题, 20分)

三分法找假币问题：一个装有n枚硬币的袋子，这些硬币中有一枚是伪造的，且那枚假硬币比真硬币要轻一些。你的任务是找出这个伪造的硬币。为了帮助你完成这一任务，将提供一台仅可用来比较两组硬币重量是否相同的仪器（天平）。现用三分法寻找这枚假币，算法如下：

（1）如果n=1，则此枚为假币;

（2）如果n=2, 天平一边放入1枚，轻的为假币

（3）如果n>=3, 则：

         m=[n/3] （“[]”表示向下取整）

         硬币分三组：a组m枚, b组m枚，c组  【空1】  枚

         将a、b两组放入天平

          ① 情况1：若a、b两组重量  【空2】  ，则假币在c组，继续求解c组。

          ② 情况2：若a组轻，则假币在a组，继续求解a组。

          ③ 情况3：若b组轻，则假币在b组，继续求解b组。

回答如下问题：

（1）如果将每放上天平称1次作为一个基本操作，则该三分法寻找假币算法称重次数的递推方程式可表示为：

              T(1) = 0，T(2) = 1

              T(n) =      【空3】     （n>2）

（2）该算法的时间复杂度为  【空4】  。（填写选项）

         A. O(log3n)      B. O(nlog3n)      C. O(n1/3)      D. O(n)

我的答案：

(1) n-2m

(2) 相同 

(3) T(n/3)+1

(4) A 

正确答案：

(1) n-2m; n-2*m; n-m-m

(2) 相同; 相等; 一样

(3) T(n/3)+1； 1+T(n/3)

(4) A

2. (填空题, 30分)

分治法求解最大子段和问题的算法如下。

（1）填写算法空白

int maxSumDac(int a[ ], int left, int right)

{       if(left==right)  return(a[left]>0 ? a[left] : 0);

        int mid=    【空1】    ;  //二等分求分割点

        int leftsum=maxSumDac(a,left,mid);

        int rightsum=      【空2】      ;

        int s1=0,s2=0; sum1=0, sum2=0;

        for(int i=mid; i>=left; i--)

        {        sum1+=a[i];

                 if(sum1>s1)     【空3】    ;

        }

        for(int i=mid+1;i<=right;i++)

        {             【空4】     ;

                 if(sum2>s2) s2=sum2;

        }

        int sum=     【空5】     ;

        if(sum<leftsum) sum=leftsum;

        if(sum<rightsum) sum=rightsum;

        return sum;

}

（2）maxSumDac算法的运行时间满足如下递归方程式：

        T(1) = O(1)

            T(n) = 2T(n/2)+O(n)  （n>1）

则该算法的时间复杂度为  【空6】  。（填写选项）

A. O(log2n)    B. O(nlog2n)    C. O(n)    D. O(n2)

我的答案：

(1) (left+right)/2

(2) maxSumDac(a,mid+1,right) 

(3) s1=sum1

(4) sum2+=a[i] 

(5) s1+s2 

(6) B 

正确答案：

(1) (left+right)/2; (right+ left)/2

(2) maxSumDac(a,mid+1,right)

(3) s1=sum1

(4) sum2+=a[i]; sum2= sum2+a[i]; sum2= a[i]+sum2;

(5) s1+s2; s2+s1

(6) B

---

作业3-7

1. (填空题, 25分)

采用分治算法求解xn，其计算公式如下：

当n=1时：xn = x

当n>1时：

（1）xn = xn/2 ×xn/2                       （n 为偶数）

（2）xn = x(n–1)/2×x(n–1)/2×x     （n 为奇数）

其递归算法如下，填写空缺及回答问题：

double fac(double x, int n)

{     if( n == 1 ) return x;

       double y = fac(     【空1】       );

       if( n%2 )  return        【空2】        ;

       else  return        【空3】         ;

}

问题：

该算法时间效率的递推方程为：

         T(1) = 0

         T(n)=   【空4】   + Θ(1)   （n>1）

由此得出其时间复杂度为：      【空5】     。（填写选项）

  A） T(n)= Θ(n)   B）T(n)= Θ(n2)   C）T(n)= Θ(nlogn)   D）T(n)= Θ(logn)

填写算法及问题中的空缺。

我的答案：

(1) x,n/2

(2) y*y*x 

(3) y*y 

(4) T(n/2) 

(5) D 

正确答案：

(1) x, n/2

(2) y * y * x;  x* y * y 

(3)  y * y

(4) T(n/2)

(5) D;d

---

---

---

第4讲 贪心算法

作业4-1

1. (填空题, 10分)

适合于用贪心法求解的问题通常具有两个重要的性质，即        性质和        性质。这两个重要的性质是一个问题可用贪心法求解的基本要素。（分别填4字、5字）

正确答案：

(1) 贪心选择

(2) 最优子结构

答案解析：

2. (填空题, 5分)

           性质是指一个问题的整体最优解可以通过一系列的局部最优选择来得到。（填4字）

我的答案：

(1) 贪心选择

3. (单选题, 5分)

活动安排问题的贪心准则是按照活动的             的次序考察每个活动。

• A. 结束时间递增
• B. 开始时间递增
• C. 结束时间递减
• D. 活动时长递增

正确答案: A:结束时间递增;

4. (填空题, 25分)

活动安排问题的贪心算法如下，填写算法空白。

struct active  //活动类型

{    int num;  //活动编号    

     int s, f;     //s为开始时间,f为结束时间

};

struct active a[100];   //a[1:n]存储给定的活动

int x[100];    //x[i]=1活动i被安排, x[i]=0活动i未被安排

void sortByFinished(int n)  //将a[1:n]中活动排序

{       int i, j;

        for(i=2; i<=n; i++ )

        {        if( a[i].f<a[i-1].f )

                 {       a[0]=a[i];  //a[0]为哨兵

                         for(j=i-1;   【空1】   ;j--)  a[j+1]=a[j];

                              【空2】      ;

                 }

        }

}

void active(int n)

{       sortByFinished(n); 

        for( int i=1; i<=n; i++)  x[i]=0;

        x[a[1].num]=1;  //安排a[1]中的活动

        int k=1;  //当前最后被安排活动下标

        for(int i=2; i<=n; i++)

        {        if(      【空3】      )

                 {        【空4】    =1;  k= 【空5】 ;  }

        }

}

我的答案：

(1) a[0].f<a[j].f 

(2) a[j+1]=a[0] 

(3) a[i].s>=a[k].f 

(4) x[a[i].num] 

(5) i 

正确答案：

(1) a[0].f<a[j].f;  a[j].f > a[0].f

(2) a[j+1]=a[0]

(3) a[i].s>=a[k].f; a[k].f<=a[i].s

(4) x[a[i].num]

(5) i 

5. (单选题, 5分)上题（4题）

算法中函数sortByFinished采用的是          排序方法。

• A. 快速
• B. 直接插入
• C. 简单选择
• D. 冒泡

正确答案: B:直接插入;

---

作业4-2

1. (单选题, 5分)使目标函数最大（小）的解是问题的（      ）。

• A. 可行解
• B. 最优解 
• C. 最小解
• D. 最大解

正确答案: B:最优解 ;

2. (单选题, 5分)满足问题约束条件的解，称为（           ）。

• A. 解空间
• B. 最优解
• C. 可行解
• D. 贪心解

正确答案: C:可行解;

3. (单选题, 5分)证明贪心算法时，把任意一个最优解逐渐变为贪心算法的解，不会影响其最优性，这种证明方法是(  )。

• A. 领先法
• B. 反证法
• C. 交换论证法
• D. 归纳法

正确答案: C:交换论证法;

4. (填空题, 5分)问题的最优子结构性质是指一个问题的最优解包含其（            ）。（填写5字或6字）

我的答案：

(1) 子问题最优解 

正确答案：

(1) 子问题的最优解; 子问题最优解

5. (判断题, 5分)贪心算法的思想是寻求局部最优解，逐步达到全局最优解。

• A. 对
• B. 错

正确答案: 对

6. (判断题, 5分)贪心算法总能找到可行解，并且是最优解。

• A. 对
• B. 错

正确答案: 错

7. (判断题, 5分)贪心法处理问题的核心是贪心准则的选取。

• A. 对
• B. 错

正确答案: 对

---

作业4-3

1. (单选题, 5分)部分背包问题的贪心准则是按照各个物品的        来考察每个物品。

• A. 单位重量价值递减次序
• B. 价值递减次序
• C. 重量递增次序
• D. 重量递减次序

正确答案: A:单位重量价值递减次序;

2. (填空题, 10分)

部分背包问题：现有7个物品，背包载重量为15，各个物品的重量为(w1, w2, w3, w4, w5, w6, w7)=(2, 3, 5, 7, 1, 4, 1),各个物品的价值为(p1, p2, p3, p4, p5, p6, p7)=(10, 5, 20, 7, 6, 18, 3)。则：

（1）此问题实例的最优值（最大价值）是          （保留1位小数）；

（2）此问题的最优解(x1, x2, x3, x4, x5, x6, x7)=(                         )  。(xi为初始给定的第i个物品装入背包的比例，可用分式表示) （注：数值间用逗号分隔）

我的答案：

(1) 60.3 

(2) 1,2/3,1,0,1,1,1 

正确答案：

(1) 60.3 

(2) 1,2/3,1,0,1,1,1； (1,2/3,1,0,1,1,1)

3. (填空题, 30分)

下面给出的是求解部分背包问题的贪心算法，填写该算法空白。

struct object //表示物品的结构体

{      float p;             //价值

        float w;            //重量

        float v;             //单位重量价值

};

struct object a[100], t;    //a[1:n]用于保存各个物品

float x[100];    //存储解向量

float Knapsack_Greedy(float M, int n)

{      //n种物品，背包载重量为M

        float m=M, opt=0;  //opt存储最优值

        for(int i=1;i<=n;i++)  //求各物品单位重量价值，初始化解向量x

        {  a[i].v=   【空1】   ;  x[i]=0;  }    

        for(int j=1;j<n;j++)     //将a[1:n]中物品按单位重量价值排序

        {      for(int i=1;i<=n-j;i++)

                 {      if(     【空2】     )

                         {   t=a[i];  a[i]=a[i+1];  a[i+1]=t;  }

                 }

        }

        for(int i=1;i<=n;i++)  

        {      if(   【空3】   )  

                 {    x[i]=1;     m=    【空4】   ;     opt=    【空5】    ;  }

                 else

                 {    x[i]=   【空6】   ; opt=opt+x[i]*a[i].p; break; }

        }

        return opt;

}

我的答案：

(1) a[i].p/a[i].w 

(2) a[i].v<a[i+1].v 

(3) a[i].w<=m

(4) m-a[i].w 

(5) opt+a[i].p 

(6) m/a[i].w 

正确答案：

(1) a[i].p/a[i].w 

(2) a[i].v<a[i+1].v; a[i+1].v> a[i].v

(3) a[i].w<=m; m>=a[i].w  

(4) m-a[i].w

(5) opt+a[i].p; a[i].p+opt

(6) m/a[i].w

4. (单选题, 5分)上题（题3）的算法中的排序算法，采用的是          排序方法。

• A. 简单选择
• B. 冒泡
• C. 快速
• D. 归并

正确答案: B:冒泡;

---

作业4-4

1. (填空题, 10分)

活动安排问题：有 n 个活动申请使用同一个会场，从这n个申请使用同一个会场的活动中选出一些活动来安排，使得被安排的活动的数目达到最多。

用贪心算法求解如下活动安排问题的具体实例：

（1）应采用的正确贪心准则为（       ）。（填写选项）

       A.开始时间早的优先         B. 时长短的优先

       C.结束时间早的优先         D. 结束时间晚的优先

（2）按此贪心准则所求得此实例的贪心解（活动选取的先后顺序）为（              ）（填写活动编号序列，活动号间用英文逗号分隔）

我的答案：

(1) C 

(2) 2,6,9,11 

正确答案：

(1) C; c

(2) 2,6,9,11 ;   (2,6,9,11)

2. (单选题, 5分)

区间划分问题：给定n个活动，以及每个活动的开始时间和结束时间，现使用最少房间安排下所有活动。现采用贪心算法求解该问题，其贪心准则应为（        ）。

• A. 开始时间早的活动优先
• B. 时长短的活动优先
• C. 结束时间早的活动优先 
• D. 结束时间晚的活动优先

正确答案: A: 开始时间早的活动优先;

3. (填空题, 15分)

某理发店中只有一位发型师，每种服务的用时不同，具体见表1。若发型师只能为某顾客服务完成后才能为另一个顾客服务。每个顾客花费时间是从0时刻到该顾客所接受的服务完成时的总时间。现有6位客户等待接受相应的服务，具体见表2。如何按排这6位客户的服务顺序使得所有顾客的总花费时间最小。

（1）现采用贪心算法求解此问题，应采用的正确贪心准则为（  ）。（填写选项）

       A.接受服务用时长的顾客优先

       B.接受服务用时短的顾客优先

       C.接受服务项目少且用时短的顾客优先

       D.接受服务项目多且用时长的顾客优先

（2）按此贪心准则所求得此实例的贪心解（顾客的服务先后顺序）为（      ）（填写顾客编号序列，编号间用英文逗号分隔）

（3）若按所求得的贪心解按排顾客的服务顺序，此时顾客的总花费时间为（  ）分钟。

我的答案：

(1) B 

(2) 3,2,6,1,5,4 

(3) 223 

正确答案：

(1) B;  b

(2) 3,2,6,1,5,4 ;   (3,2,6,1,5,4)

(3) 223

---

---

---

第5讲 动态规划算法

作业5-1

1. (单选题, 5分)一个问题能用动态规划方法求解，通常具有两个重要的性质。这两个性质为（    ）。

• A. 最优子结构性质和子问题的重叠性质
• B. 最优子结构性质和贪心选择性质
• C. 贪心选择性质和子问题的重叠性质
• D. 以上均不对

正确答案: A:最优子结构性质和子问题的重叠性质;

2. (填空题, 5分)最优子结构性质是指当一个问题的最优解包含了其（    ）。（填6字或7字）

正确答案：

(1) 子问题的最优解; 子问题最优解

3. (填空题, 40分)

动态规划方法求解最大子段和问题。

给定数组a[1:n]，用数组b的元素b[i]来表示以数组元素a[i]为尾的最大子段和。

（1）求解最大子段和的动态规划算法如下，填写算法空白。

int maxSumDP(int a[], int b[], int n)

{      int i, sum=0;

        b[0]=0;

        for(i=1 ;i<=n; i++)

        {       if( b[i-1]>0 ) b[i]=    【空1】    ;

                 else      【空2】     ;

                 if(    【空3】    ) sum=b[i];

        }

        return sum;

}

（2）求解一个具体实例如下,填写空缺处。

我的答案：

(1) b[i-1]+a[i] 

(2) b[i]=a[i] 

(3) b[i]>sum 

(4) -2 

(5) 11 

(6) 7 

(7) 20 

(8) 15 

正确答案：

(1) b[i-1]+a[i]; a[i]+b[i-1]

(2) b[i]=a[i]

(3) b[i]>sum; sum<b[i]

(4) -2

(5) 11

(6) 7

(7) 20

(8) 15

---

作业5-2

1. (填空题, 10分)

动态规划算法适用于求解多阶段决策过程最优化问题，动态规划算法的解题步骤的正确顺序为（     ）（填写以下给定选项的正确顺序，选项间无需其他符号分隔）

        A. 建立最优值的递推关系；

        B.分析最优解的性质，并刻画其结构特征；

        C.根据计算最优值时保存的信息，构造最优解；

        D.以自底向上的方式计算出最优值；

在只需要求出最优值时的情形，步骤（    ）可以省略。若需要求出问题的最优解，则该步骤必须执行。（填写选项）

正确答案：

(1) BADC; badc

(2) C; c

2. (填空题, 25分)

动态规划方法求解最长递减子序列问题。

给定数组a[1:n]，用数组b的元素b[j]来表示以数组元素a[j]为尾元素的最长递减子序列的长度，b[j]满足的如下递推关系。

        b[j]=max{ b[k]+1| k<j且a[k]>a[j]}

数组flag用来标记最长递减子序列上的元素，flag[i]=1表示a[i]是最长递减子序列上的元素，flag[i]=0则表示a[i]不是最长递减子序列上的元素。

求解最长递减子序列长度的动态规划算法如下，填写算法空白。

int a[100], b[100], flag[100];

int LDS(int n)

{      int max=0, j, k;

        for(j=1; j<=n; j++) { flag[j]=0; b[j]=1; } //初始化

        for(j=2; j<=n ;j++)

        {      for(k=1; k<= 【空1】 ; k++)

                         if(a[k]>a[j]&&   【空2】   ) b[j]=b[k]+1;

                 if(b[j]>max)     【空3】    ;

        }

        //构造最优解

        int temp=max;

        for(k=n; k>=1; k--)

                 if(   【空4】   ){ flag[k]=1;    【空5】   ; }

        return max;  

}

正确答案：

(1)  j-1

(2) b[k]+1>b[j]; b[j]<b[k]+1

(3) max=b[j]

(4) b[k]==temp; temp==b[k]

(5) temp--; temp=temp-1

3. (填空题, 25分)

利用上题算法求解如下具体实例a[1:6]的最长递减子序列。

（1）求解结果如下表，填写表中空白。

（2）根据算法构造最优解的方法得到的数组a[1:6]的最长递减子序列为(    【空5】    )（填写数值序列，用逗号分隔）。

正确答案：

(1) 2

(2) 3

(3) 2

(4) 4

(5) 11,8,7,6

---

作业5-3

1. (填空题, 5分)

动态规划方法求解投资问题。

正确答案：

(1) B[k-1][x-j]

2. (填空题, 30分)

根据上题（题1）给定的递推关系，求解投资问题动态规划算法。其中：

（1）用数组t的元素t[k][x]值表示：存储对应B[k][x]的取值时，分配给第k个项目的钱数；

（2）用数组y[1:n]存放的最终的所求问题的最优解向量，y[i]存储第i个项目的投资额；

求解投资问题的最优值和最优解的动态规划算法如下，填写算法空白。

float B[100][100],  t[100][100];

void tzPDP(float f[][100], int n, int m)

{     //求解投资问题的最优值

       for(int x=1; x<=m; x++) {  B[1][x] = f[1][x];  t[1][x] = x; }

       for(int k=1; k<=n; k++)  {  B[k][0] = 0;  t[k][0] = 0;  }

       for(int k=2; k<=n; k++)

       {     for(int x=1; x<=m; x++)

              {     float max = -1;

                     int tx;

                     for(int j=0; j<=【空1】; j++)

                     {     float value =      【空2】      ;

                            if(value > max) {  max = value; tx =【空3】;  }

                     }

                     B[k][x] =  【空4】 ;   t[k][x] = tx;

              }

       }

}

void tzOpt( int n, int m, int y[])

{     //求解最优解；利用求最优值时数组t记录的信息

       int x = m;

       for( int i=n; i>=1; i-- )

       {     y[i] =   【空5】  ;

                   【空6】        ;

       }           

}

正确答案：

(1) x

(2) f[k][j]+B[k-1][x-j];  B[k-1][x-j]+f[k][j]

(3) j

(4) max

(5)  t[i][x]

(6) x=x-y[i]; x-=y[i]; x=x-t[i][x]; x-=t[i][x]

3. (填空题, 60分)

按上题（题2）给定的投资问题求解算法求解如下实例。

n=4，m=5，效益函数 fi(x) 如下：

正确答案：

(1) 0.21, 3 

(2) 0.26, 4

(3) 0.13, 1

(4) 0.30, 3;  0.3, 3

(5) 0.41, 3

(6) 0.43, 4

(7) 0.31, 1

(8) 0.33, 1 

(9) 0.50, 1;  0.5, 1

(10) 0.61, 1

(11) 0.61

(12) 1, 0, 3, 1 ;   (1, 0, 3, 1)

---

作业5-4

1.(填空题, 30分)

动态规划方法求解0-1背包问题

给定n个物品，背包载重为M的0-1整数背包问题，数组w[1:n]存放n个物品的重量，数组p[1:n]存放n个物品的价值。现有数组m的数组元素m[i][j]存储前i种物品、载重量为j背包时所取得的最优值（最大价值），其最优值所满足的递推关系式如下：

用数组x[1:n]存放的最终的所求问题的最优解向量（n元的0-1向量）

（1）求解0-1背包问题的最优值和最优解的动态规划算法如下，填写算法空白。

int w[100],p[100],x[100],m[100][100];

void KnapSack_dynamic(int n,int M)

{      int i,j; 

        for(i=0;i<=n;i++) {  m[i][0]=0; x[i]=0; }

        for(j=0;j<=M;j++) m[0][j]=0;

        for(i=1;i<=n;i++)

        {      for(j=1;j<=M;j++)

                 {      if(    【空2】   ) m[i][j]=m[i-1][j];

                         else if(p[i]+m[i-1][j-w[i]]>m[i-1][j])

                                m[i][j]=       【空3】       ; 

                         else m[i][j]=   【空4】   ;

                 }

        }

        j=M;

        for(i=n;i>=1;i--)

        {      if(     【空5】    )

               {   x[i]=1;       【空6】   ;  }

        }

}

正确答案：

(1) p[i]+m[i-1][j-w[i]]

(2) j<w[i]

(3) p[i]+m[i-1][j-w[i]]

(4) m[i-1][j]

(5) m[i][j]>m[i-1][j]

(6) j-=w[i]

2. (填空题, 55分)

按上题0-1整数背包问题求解算法求解如下实例：

设有5个物品，重量分别为(w1,w2,w3,w4,w5)=(2,2,6,5,4)，各物品的价值分别为(p1,p2,p3,p4,p5)=(6,3,5,4,6)，给定背包的载重量为M=10。

（1）如下给出面给出了数组m的计算结果，填写空白处的值。

（2）依据算法，此实例的所求得的最优值为   (10)  ，最终构造最优解（0-1向量）为（      (11)      ） (数值间用逗号分隔)。

正确答案：

(1) 6

(2) 9

(3) 9

(4) 11

(5) 14

(6) 10

(7) 13

(8) 12

(9) 15

(10) 15

(11) 1,1,0,0,1

---

我写完了，你看完了吗