作业详情

第4章分治法

题量: 34 满分: 100

作答时间:04-03 14:46至04-15 08:00

智能分析

77.9分

一. 单选题（共22题，64分）

1. (单选题)“大事化小，小事化了”概括了（）算法设计策略。

A. 分治法
B. 动态规划
C. 回溯法
D. 贪心法

我的答案: A :分治法; 正确答案: A :分治法;

2.9分

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

A. 子问题必须是一样的
B. 子问题不能够重复
C. 子问题的解可以合并
D. 原问题和子问题使用相同的方法解

我的答案: A :子问题必须是一样的; 正确答案: A :子问题必须是一样的;

2.9分

3. (单选题)应用分治法的两个前提是（）

A. 问题的可分性和解的存在性
B. 问题的可分性和解的可归并性
C. 问题的复杂性和解的可归并性
D. 问题的可分性和解的复杂性

我的答案: B :问题的可分性和解的可归并性; 正确答案: B :问题的可分性和解的可归并性;

2.9分

4. (单选题)分治法所能解决的问题应具有的关键特征是（）

A. 该问题的规模缩小到一定的程度就可以容易地解决
B. 该问题可以分解为若干个规模较小的相同问题
C. 利用该问题分解出的子问题的解可以合并为该问题的解
D. 该问题所分解出的各个子问题是相互独立的

我的答案: C :利用该问题分解出的子问题的解可以合并为该问题的解; 正确答案: C :利用该问题分解出的子问题的解可以合并为该问题的解;

2.9分

5. (单选题)以下不可以采用分治法求解的问题是（）

A. 求一个序列中最小元素
B. 求一条迷宫路径
C. 求二叉树的高度
D. 求一个序列中最大连续子序列和

我的答案: B :求一条迷宫路径; 正确答案: B :求一条迷宫路径;

2.9分

6. (单选题)分治法所能解决的问题具有的特征，下述不正确的是

A. 问题的规模小到一定的程度就可以容易地解决
B. 最优子结构性质
C. 无重复子问题性质
D. 该问题可以分解为若干个规模较小的问题，小问题可能和原问题性质不同

我的答案: C :无重复子问题性质; 正确答案: D :该问题可以分解为若干个规模较小的问题，小问题可能和原问题性质不同;

0分

7. (单选题)用T(n)表示分治法求解规模为n的问题所需的计算时间，则有T(n)=aT(n/b)+f(n)，关于递归方程T(n)，下列描述正确的是？

A. a表示常系数，无实际含义，b表示子问题的数量，n/b表示子问题规模，T(n/b)表示解决规模为n/b的子问题所需要的时间，f(n)表示合并子问题所需要的时间
B. a表示分解的子问题数量，n/b表示子问题规模，T(n/b)表示解决规模为n/b的子问题所需要的时间，f(n)表示分解子问题、合并子问题等逻辑处理所需要的时间
C. a表示常系数，无实际含义，b表示子问题的数量，n/b表示子问题规模，T(n/b)表示解决规模为n/b的子问题所需要的时间，f(n)表示分解子问题、合并子问题等逻辑处理所需要的时间
D. a表示分解的子问题数量，n/b表示子问题规模，T(n/b)表示解决规模为n/b的子问题所需要的时间，f(n)表示合并子问题所需要的时间

我的答案: B :a表示分解的子问题数量，n/b表示子问题规模，T(n/b)表示解决规模为n/b的子问题所需要的时间，f(n)表示分解子问题、合并子问题等逻辑处理所需要的时间; 正确答案: B :a表示分解的子问题数量，n/b表示子问题规模，T(n/b)表示解决规模为n/b的子问题所需要的时间，f(n)表示分解子问题、合并子问题等逻辑处理所需要的时间;

2.9分

8. (单选题)快速排序算法的性能取决于（）

A. 划分的对称性
B. 数据的原始序列
C. 随机选择策略
D. 以上都不正确

我的答案: A :划分的对称性; 正确答案: A :划分的对称性;

2.9分

9. (单选题)
在寻找n个元素中第k小元素问题中，如果运用快速排序算法思想对n个元素进行划分，如何选择划分基准（基元）

A. 随机选择一个元素作为划分基准
B. 取子序列的第一个元素作为划分基准
C. 用选取中位数元素作为划分基准
D. 以上皆可行。但不同方法算法复杂度上界可能不同

我的答案: D :以上皆可行。但不同方法算法复杂度上界可能不同; 正确答案: D :以上皆可行。但不同方法算法复杂度上界可能不同;

2.9分

10. (单选题)使用二分查找算法在n个有序表中查找一个特定元素，在最好情况和最坏情况下的时间复杂性分别为（）

A. O(1)，O(log2n)
B. O(n)，O(log2n)
C. O(1)，O(nlog2n)
D. O(n)，O(nlog2n)

我的答案: A :O(1)，O(log2n) ; 正确答案: A :O(1)，O(log2n) ;

2.9分

11. (单选题)二分查找算法的时间复杂度函数，下述正确的是

A. T(n)=O(1)（当n=0），T(n)=2T(n/2)+O(1)（当n>1）
B. T(n)=O(1)（当n=0），T(n)=2T(n/2)+O(n)（当n>1）
C. T(n)=O(1)（当n=0），T(n)=T(n/2)+O(1)（当n>1）
D. T(n)=O(1)（当n=0），T(n)=T(n/2)+O(n)（当n>1）

我的答案: B :T(n)=O(1)（当n=0），T(n)=2T(n/2)+O(n)（当n>1）; 正确答案: C :T(n)=O(1)（当n=0），T(n)=T(n/2)+O(1)（当n>1）;

0分

12. (单选题)在递归二路归并排序算法中，若分解的策略为每次一分为四，即分解出来的4个子问题规模为n/4，则算法的复杂度为（）

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

我的答案: B :O(nlog2n); 正确答案: B :O(nlog2n);

2.9分

13. (单选题)递归二路归并排序算法是基于（）的一种排序算法。

A. 分治策略
B. 动态规划法
C. 贪心法
D. 回溯法

我的答案: A :分治策略; 正确答案: A :分治策略;

2.9分

14. (单选题)在用分治法解决逆序对计数问题中，分治策略的关键是（）

A. 设计分解的算法
B. 设计合并的算法
C. 子问题求解
D. 以上都不正确

我的答案: A :设计分解的算法; 正确答案: B :设计合并的算法;

0分

15. (单选题)在最大子数组问题的分治算法中，若可以用 O(1)的时间求得跨越中点的最大子数组，则该算法的时间复杂度为（）

A. Ο(log2n)
B. Ο(n)
C. Ο(nlog2n)
D. Ο(1)

我的答案: B :Ο(n); 正确答案: B :Ο(n);

2.9分

16. (单选题)二分查找算法采用的是（）

A. 回溯法
B. 穷举法
C. 贪心法
D. 分治策略

我的答案: D :分治策略; 正确答案: D :分治策略;

2.9分

17. (单选题)快速排序方法在（）情况下最不利于发挥其长处。

A. 要排序的数据量太大
B. 要排序的数据中含有多个相同值
C. 要排序的数据个数为奇数
D. 要排序的数据已基本有序

我的答案: D :要排序的数据已基本有序; 正确答案: D :要排序的数据已基本有序;

2.9分

18. (单选题)快速排序中对n个元素做一次划分，元素比较的最少次数是（）

A. 2n
B. n
C. n-1
D. n/2

我的答案: C :n-1; 正确答案: C :n-1;

2.9分

19. (单选题)若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）

A. 快速排序
B. 堆排序
C. 二路归并排序
D. 直接插入排序

我的答案: C :二路归并排序; 正确答案: C :二路归并排序;

2.9分

20. (单选题)某个规模为n的问题采用分治法求解，每次划分为两个规模为n/2的子问题，合并的时间为O(n2)，则该分治算法的时间复杂度为（）

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

我的答案: D :O(n3); 正确答案: C :O(n2);

0分

21. (单选题)现要对n个实数（仅包含正实数和负实数）组成的数组A进行重新排列，使得其中所有的负实数位于正实数之前。求解该问题的算法的伪代码如下所示，则该算法的时间和空间复杂度为（）。 i=0;j=n-1; while i<j do while A[i]<0 do i=i+1; while A[j]>0 do j=j-1; if i<j do 交换A[i]和A[j];

A. (n)和(n)
B. (1)和(n)
C. (n)和(1)
D. (1)和(1)

我的答案: C :(n)和(1); 正确答案: C :(n)和(1);

3分

22. (单选题)
给定n个整数构成的数组A={a1，a2，…，an}和整数x。判断A中是否存在两个元素ai和aj，使得ai+aj=x。为了求解该问题，首先用归并排序算法对数组A进行从小到大排序，然后判断是否存在ai+aj=x，具体如下列伪代码所示，则求解该问题时排序算法应用了①算法设计策略，整个算法的时间复杂度为②。

i=1;j=n;

while i<j do

if ai+aj=x return true;

else if ai+aj>x

j--;

else

i++;

return false;

A. ①分治法 ②O(n)
B. ①分治法 ② O(nlog2n)
C. ①回溯法 ②O(n2)
D. ①分治法 ② O(n(log2n)2)

我的答案: B :①分治法 ② O(nlog2n); 正确答案: B :①分治法 ② O(nlog2n);

3分

二. 判断题（共8题，24分）

23. (判断题)分治算法只能采用递归实现。

A. 对
B. 错

我的答案: 错 正确答案: 错

3分

24. (判断题)适用于分治法求解的问题，经分解得到的子问题往往是相互独立的。

A. 对
B. 错

我的答案: 对 正确答案: 对

3分

25. (判断题)从分治法的一般设计模式可以看出，用它设计出的程序一般是递归算法。

A. 对
B. 错

我的答案: 对 正确答案: 对

3分

26. (判断题)二分查找、二路归并排序和二叉树遍历等算法中均采用了分治策略。

A. 对
B. 错

我的答案: 对 正确答案: 对

3分

27. (判断题)快速排序基准元素的选取可以是待排序元素中的任何一个元素。

A. 对
B. 错

我的答案: 错 正确答案: 对

0分

28. (判断题)在最坏的情况下快速排序退化为冒泡排序

A. 对
B. 错

我的答案: 错 正确答案: 对

0分

29. (判断题)
以下二分查找算法是正确的。 int binarySearch(int a[], int n, int x) { int low=0, high=n-1; while(low<=high) { int mid=(low+high)/2; if(x==a[mid]) return mid; if(x>a[mid]) low=mid; else high=mid; } return –1; }

A. 对
B. 错

我的答案: 对 正确答案: 错

0分

30. (判断题)
某个规模为n的问题采用分治法求解，每次划分为4个规模为n/2的子问题，合并的时间为O(n)，则该分治算法的时间复杂度为 O(n^2) 。n

A. 对
B. 错

我的答案: 对 正确答案: 对

3分

三. 填空题（共4题，12分）

31. (填空题)
假设不带头结点的整数单链表L的结点类型为（val，next），以下算法求L中所有结点值之和，请填空。

nt sums(ListNode *L) { if(L==NULL) return 0; else return ①+sums( ② ); }

我的答案： 3分: (1) L.val; (2) L.next

正确答案：: (1) L->val;L->val;; (2) L->next;L->val;

32. (填空题)假设不带头结点的整数单链表L的结点类型为（val，next），以下算法求L中结点值为偶数的结点个数，请填空。int evencnt(ListNode *L) { if(L==NULL) return 0; else { if(L->val%2==0)//偶数结点 return ①; else return ②; } }

我的答案： 3分: (1) 1 + evencnt(L->next); (2) evencnt(L->next)

正确答案：: (1) 1+evencnt(L->next);evencnt(L->next)+1;; (2) evencnt(L->next)

33. (填空题)假设不带头结点的整数单链表L的结点类型为（val，next），以下算法求L中值为x的结点个数，请填空。int cntx(ListNode *L,int x) { if(L==NULL) return 0; else { if( ① )//x结点 return 1+cntx(L->next,x); else return ②; } }

我的答案： 1.5分: (1) 1 + cntx(L->next, x); (2) cntx(L->next, x)

正确答案：: (1) L->val==x; x==L->val;; (2) cntx(L->next,x)

34. (填空题)假设采用二叉链存储的整数二叉树t的结点类型为（left，val，right），以下算法求t中值为x的结点个数，请填空。int cntx(TreeNode*t,int x) { if(t==NULL) return 0; else if(t->val==x) return ①; else return ②; }

我的答案： 3分: (1) 1 + cntx(t->left, x) + cntx(t->right, x); (2) cntx(t->left, x) + cntx(t->right, x)

正确答案：

(1)

1+cntx(t->left,x)+cntx(t->right,x);

cntx(t->left,x)+1+cntx(t->right,x);

cntx(t->left,x)+cntx(t->right,x)+1;

cntx(t->right,x)+1+cntx(t->left,x);

cntx(t->right,x)+cntx(t->left,x)+1;

1+cntx(t->right,x)+cntx(t->left,x);

(2)

cntx(t->left,x)+cntx(t->right,x);

cntx(t->right,x)+cntx(t->left,x);

一. 单选题（64分）

二. 判断题（24分）

三. 填空题（12分）

第4章 分治法

一. 单选题（共22题，64分）

1. (单选题)“大事化小，小事化了”概括了（ ）算法设计策略。

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

3. (单选题)应用分治法的两个前提是（ ）

4. (单选题)分治法所能解决的问题应具有的关键特征是（ ）

5. (单选题)以下不可以采用分治法求解的问题是（ ）

6. (单选题)分治法所能解决的问题具有的特征，下述不正确的是

7. (单选题)用T(n)表示分治法求解规模为n的问题所需的计算时间，则有T(n)=aT(n/b)+f(n)，关于递归方程T(n)，下列描述正确的是？

8. (单选题)快速排序算法的性能取决于（ ）

9. (单选题)在寻找n个元素中第k小元素问题中，如果运用快速排序算法思想对n个元素进行划分，如何选择划分基准（基元）

10. (单选题)使用二分查找算法在n个有序表中查找一个特定元素，在最好情况和最坏情况下的时间复杂性分别为（ ）

11. (单选题)二分查找算法的时间复杂度函数，下述正确的是

12. (单选题)在递归二路归并排序算法中，若分解的策略为每次一分为四，即分解出来的4个子问题规模为n/4，则算法的复杂度为（ ）

13. (单选题)递归二路归并排序算法是基于（ ）的一种排序算法。

14. (单选题)在用分治法解决逆序对计数问题中，分治策略的关键是（ ）

15. (单选题)在最大子数组问题的分治算法中，若可以用 O(1)的时间求得跨越中点的最大子数组，则该算法的时间复杂度为（ ）

16. (单选题)二分查找算法采用的是（ ）

17. (单选题)快速排序方法在（ ）情况下最不利于发挥其长处。

18. (单选题)快速排序中对n个元素做一次划分，元素比较的最少次数是（ ）

19. (单选题)若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（ ）

20. (单选题)某个规模为n的问题采用分治法求解，每次划分为两个规模为n/2的子问题，合并的时间为O(n2)，则该分治算法的时间复杂度为（ ）

二. 判断题（共8题，24分）

23. (判断题)分治算法只能采用递归实现。

24. (判断题)适用于分治法求解的问题，经分解得到的子问题往往是相互独立的。

25. (判断题)从分治法的一般设计模式可以看出，用它设计出的程序一般是递归算法。

26. (判断题)二分查找、二路归并排序和二叉树遍历等算法中均采用了分治策略。

27. (判断题)快速排序基准元素的选取可以是待排序元素中的任何一个元素。

28. (判断题)在最坏的情况下快速排序退化为冒泡排序

29. (判断题)以下二分查找算法是正确的。 int binarySearch(int a[], int n, int x) { int low=0, high=n-1; while(low<=high) { int mid=(low+high)/2; if(x==a[mid]) return mid; if(x>a[mid]) low=mid; else high=mid; } return –1; }

30. (判断题)某个规模为n的问题采用分治法求解，每次划分为4个规模为n/2的子问题，合并的时间为O(n)，则该分治算法的时间复杂度为 O(n^2) 。n

三. 填空题（共4题，12分）

31. (填空题)假设不带头结点的整数单链表L的结点类型为（val，next），以下算法求L中所有结点值之和，请填空。 nt sums(ListNode *L) { if(L==NULL) return 0; else return ①+sums( ② ); }

32. (填空题)假设不带头结点的整数单链表L的结点类型为（val，next），以下算法求L中结点值为偶数的结点个数，请填空。int evencnt(ListNode *L) { if(L==NULL) return 0; else { if(L->val%2==0)//偶数结点 return ①; else return ②; } }

33. (填空题)假设不带头结点的整数单链表L的结点类型为（val，next），以下算法求L中值为x的结点个数，请填空。int cntx(ListNode *L,int x) { if(L==NULL) return 0; else { if( ① )//x结点 return 1+cntx(L->next,x); else return ②; } }

34. (填空题)假设采用二叉链存储的整数二叉树t的结点类型为（left，val，right），以下算法求t中值为x的结点个数，请填空。int cntx(TreeNode*t,int x) { if(t==NULL) return 0; else if(t->val==x) return ①; else return ②; }

第4章分治法

1. (单选题)“大事化小，小事化了”概括了（）算法设计策略。

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

3. (单选题)应用分治法的两个前提是（）

4. (单选题)分治法所能解决的问题应具有的关键特征是（）

5. (单选题)以下不可以采用分治法求解的问题是（）

8. (单选题)快速排序算法的性能取决于（）

9. (单选题)
在寻找n个元素中第k小元素问题中，如果运用快速排序算法思想对n个元素进行划分，如何选择划分基准（基元）

10. (单选题)使用二分查找算法在n个有序表中查找一个特定元素，在最好情况和最坏情况下的时间复杂性分别为（）

12. (单选题)在递归二路归并排序算法中，若分解的策略为每次一分为四，即分解出来的4个子问题规模为n/4，则算法的复杂度为（）

13. (单选题)递归二路归并排序算法是基于（）的一种排序算法。

14. (单选题)在用分治法解决逆序对计数问题中，分治策略的关键是（）

15. (单选题)在最大子数组问题的分治算法中，若可以用 O(1)的时间求得跨越中点的最大子数组，则该算法的时间复杂度为（）

16. (单选题)二分查找算法采用的是（）

17. (单选题)快速排序方法在（）情况下最不利于发挥其长处。

18. (单选题)快速排序中对n个元素做一次划分，元素比较的最少次数是（）

19. (单选题)若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）

20. (单选题)某个规模为n的问题采用分治法求解，每次划分为两个规模为n/2的子问题，合并的时间为O(n2)，则该分治算法的时间复杂度为（）

29. (判断题)
以下二分查找算法是正确的。 int binarySearch(int a[], int n, int x) { int low=0, high=n-1; while(low<=high) { int mid=(low+high)/2; if(x==a[mid]) return mid; if(x>a[mid]) low=mid; else high=mid; } return –1; }

30. (判断题)
某个规模为n的问题采用分治法求解，每次划分为4个规模为n/2的子问题，合并的时间为O(n)，则该分治算法的时间复杂度为 O(n^2) 。n

31. (填空题)
假设不带头结点的整数单链表L的结点类型为（val，next），以下算法求L中所有结点值之和，请填空。

nt sums(ListNode *L) { if(L==NULL) return 0; else return ①+sums( ② ); }