A. 分治算法的核心思想是分而治之，即把问题转化为多个规模更小的子问题求解。
B. 分治算法可以不使用递归实现。
C. 分治算法的时间复杂度是O(log N)，其中N表示问题的规模。
D. 分治算法通常较容易在多核处理器上实现加速。
4、有关下面 C++代码说法错误的是（ ）。
#include<iostream>usingnamespace std;intfactA(int n){if(n <=1)return1;int ret =1;for(int i =2; i <= n;++i)
ret *= i;return ret;}intfactB(int n){return n ==1?1: n *factB(n -1);}intmain(){int n ;
cin >> n;
cout <<factA(n)<<' '<<factB(n)<< endl;return0;}
A.factA()采用循环方式求 n 的阶乘，factB()采用递归方式求 n 的阶乘
B. 程序执行时如果输入 5，能实现求其阶乘，程序输出结果为 120120
C. 任何递归程序都可以使用循环改写
D. 程序执行时如果输入 100，不能正确求出 100 的阶乘
A. 上面代码实现的二分查找，最少只需查找一次即可得到结果
B. 如果调用该函数在列表{2,3,4,10,12}中查找元素 0，则它实际被调用 3次
C. 如果调用该函数在列表{2,3,4,10,12}中查找元素 3，则它实际被调用 3次
D. 如果调用该函数在列表{2,3,4,10,12}中查找元素 10，则它实际被调用3 次
A. 该程序不能正常运行，因为 f1 函数被重复定义。
B. 该程序可以正常运行，输出结果共 3 行，依次为 f1()、f1()、f1()
C. 该程序可以正常运行，输出结果共 3 行，依次为 f1()、f1(0)、f1(0)
D. 该程序可以正常运行，输出结果共 3 行，依次为 f1()、f1(0)、f1(48)
9、关于 C++程序的异常处理，以下选项中描述错误的是（ ）。
A. 编程语言中的异常和错误是不同的概念
B. 异常一旦发生，程序便一定不能继续执行
C. 通过 try、catch 等保留字提供异常处理功能
D. 程序使用 throw 在任何地方抛出各种异常
10、下面代码执行后的输出是（ ）。
#include<iostream>usingnamespace std;intfibonacci(int N){
cout << N <<",";if(N ==1|| N ==2){return1;}else{returnfibonacci(N -1)+fibonacci(N -2);}}intmain(){
cout <<fibonacci(5)<< endl;return0;}
A. 两种排序算法的时间复杂度不同。
B. 两种排序算法的空间复杂度一致。
C. sortA 的时间复杂度在最好和最坏情况下都是
O
(
N
2
)
O(N^2)
O
(
N
2
)
。
D. sortB 的平均时间复杂度、最好情况的时间复杂度都是
O
(
l
o
g
N
)
O(log N)
O
(
l
o
g
N
)
，最坏情况的时间复杂度是
O
(
N
2
)
O(N2)
O
(
N
2
)
。
13、上一题中的sortB函数，明显体现出的算法思想和编程方法包括（ ）。
A. 递归
B. 分治
C. A、B 都正确
D. A、B 都不正确
14、下列哪个算法并没有体现分治思想？（ ）。
A. 二分查找
B. 埃氏筛法。
C. 归并排序。
D. 快速排序。
15、下列关于链表说法，正确的是（ ）。
A. 不能用数组来实现链表。
B. 在链表头部插入元素的时间复杂度是 $O(1)$。
C. 循环链表使得任意一个结点都可以很方便地访问其前驱与后继。
D. 从双向链表的任意一个节点出发，并不一定能够访问到所有其他节点。
判断题（每题 2 分，共 20 分）
1、计算机硬件主要包括运算器、控制器、存储器、输入设备和输出设备。
2、唯一分解定理指的是分解质因数只有唯一的一种算法。
3、埃氏筛法用于找出自然数 N 以内的所有质数，其时间复杂度为
O
(
N
N
)
O(N\sqrt{N})
O
(
N
N
)
，因为判定一个数是否为质数的时间复杂度为
O
(
N
)
O(N)
O
(
N
)
。
