23年12月五级判断题

1.归并排序的时间复杂度是 $O(N logN)$ 。( )

【答案】正确

【考纲知识点】排序算法知识

【解析】本题考察排序算法知识。归并排序算法的时间复杂度的描述正确。

2. 小杨在生日聚会时拿⼀块 $H*W$ 的巧克力招待来的 K 个小朋友，保证每位小朋友至少能获得⼀块相同大小的巧克力 。那么小杨想分出来最大边长的巧克力可以使用二分法。 ( )

【答案】错误

【考纲知识点】算法知识

【解析】因为考纲中对二分法同时列出了“二分查找”和“二分答案（或二分枚举）”。

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

【答案】错误

【考纲知识点】算法知识

【解析】本题考察递归算法知识。递归函数要调用自己。

4. 贪心算法可以达到局部最优 ，但可能不是全局最优解 。( )

【答案】正确

【考纲知识点】算法知识

【解析】本题考察贪心算法知识。贪心是局部达到最优。

5. 小杨设计了一个拆数程序，它能够将任意的非质数自然数 N 转换成若干个质数的乘积，这个程序是可以设计出来的。( )

【答案】正确

【考纲知识点】数学知识

【解析】本题考察数学知识。素数分解定理规定:任何一个整数都可以被分解为一系列因子的乘积,乘积中所有的因子都是质数(即素数)。（更严谨一点：大于 1的整数）

6. 插⼊排序有时比快速排序时间复杂度更低 。（ ）

【答案】正确

【考纲知识点】排序知识

【解析】本题考察排序算法知识。当数据初始有序时，插入排序的最快时间复杂度是 O(n)，快排最坏时间复杂度是 O(N2)。

7. 下面的 C++代码能实现十进制正整数 N 转换为八进制并输出 。（ ）

【答案】错误

【考纲知识点】计算机基础知识

【解析】本题考察进制转换知识。转换后的内容要倒序输出并以 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. 同样的整数序列分别保存在单链表和双向链中 ，这两种链表上的简单冒泡排序的复杂度相同。( )

【答案】正确

【考纲知识点】排序算法知识

【解析】本题考察排序算法知识。冒泡排序，相邻的数据交换，而且修改节点链的操作不会改变复杂度。