二、判断题（每题 2 分，共 20 分）
1、归并排序的时间复杂度是 O（N logN) 。( )
【答案】正确
【考纲知识点】排序算法知识
【解析】本题考察排序算法知识。归并排序算法的时间复杂度的描述正确。

2、⼩杨在⽣⽇聚会时拿⼀块 H*W 的巧克⼒招待来的 K 个⼩朋友，保证每位⼩朋友⾄少能获得⼀块相同⼤⼩的巧克⼒ 。那么⼩杨想分出来最⼤边长的巧克⼒可以使⽤二分法。 ( )
【答案】错误
【考纲知识点】算法知识
【解析】因为考纲中对二分法同时列出了“二分查找”和“二分答案（或二分枚举）”。

3、以下 C++代码能以递归⽅式实现斐波那契数列 ，该数列第1 、2 项为1，以后各项均是前两项之和 。( )

int Fibo(int N){
	if (N==1 || N==2){
		return 1;
	}
	else{
		int m = fiboA(N-1);
		int n = fiboB(N-2);
		return m+n;
	}
}

【答案】错误
【考纲知识点】算法知识
【解析】本题考察递归算法知识。递归函数要调用自己。

4、贪⼼算法可以达到局部最优 ，但可能不是全局最优解。( )
【答案】正确
【考纲知识点】算法知识
【解析】本题考察贪心算法知识。贪心是局部达到最优。

5、⼩杨设计了⼀个拆数程序，它能够将任意的⾮质数⾃然数N 转换成若⼲个质数的乘积，这个程序是可以设计出来的。 ( )
【答案】正确
【考纲知识点】数学知识
【解析】本题考察数学知识。素数分解定理规定:任何一个整数都可以被分解为一系列因子的乘积,乘积中所有的因子都是质数(即素数)。（更严谨一点：大于1的整数）

6、插⼊排序有时⽐快速排序时间复杂度更低 。 ( )
【答案】正确
【考纲知识点】排序知识
【解析】本题考察排序算法知识。当数据初始有序时，插入排序的最快时间复杂度是 O(n)，快排最坏时间复杂度是 O(N2)。

7、下⾯的 C++代码能实现⼗进制正整数 N 转换为⼋进制并输出。( )

char s[10];
int main(){
	int N;
	cin>>N;
	string rst = "";
	while (N != 0){
		s[0] = N % 8 + '0';
		rst += string(s);
		N /= 8;
	}
	cout<< rst << endl;
	return 0;
}

【答案】错误
【考纲知识点】计算机基础知识
【解析】本题考察进制转换知识。转换后的内容要倒序输出并以0 开头。

8、对数组 int arr[]={2, 6, 3, 5, 4, 8, 1, 0, 9, 10}执⾏ sort(arr, arr+10),则执⾏后arr 中的数据调整为 {0, 1, 2, 3, 4, 5, 6, 8,9, 10}( )
【答案】正确
【考纲知识点】排序知识
【解析】本题考察排序算法知识。sort 默认是从小到大排序。

9、⼩杨想写⼀个程序来算出正整数 N 有多少个因数,经过思考他写出了⼀个重复没有超过 N/2 次的循环就能够算 出来了( )
【答案】正确
【考纲知识点】数学知识
【解析】本题考察数学知识。可以循环 N 的一半找到所有因数。

10、同样的整数序列分别保存在单链表和双向链中 ，这两种链表上的简单冒泡排序的复杂度相同。 ( )
【答案】正确
【考纲知识点】排序算法知识
【解析】本题考察排序算法知识。冒泡排序，相邻的数据交换，而且修改节点链的操作不会改变复杂度。