单选题

1.下面 C++ 代码用于求斐波那契数列，该数列第 1、2 项为 1，以后各项均是前两项之和。函数 fibo() 属于 ( )。

{{ select(1) }}

• 枚举算法
• 贪心算法
• 迭代算法
• 递归算法

2.下面 C++ 代码用于将输入金额换成最少币种组合方案，其实现算法是 ( )。

{{ select(2) }}

• 枚举算法
• 贪心算法
• 迭代算法
• 递归算法

3.小杨想在头指针为 head 的双链表中查找他喜欢的某首歌曲，采用如下查询函数，该操作的时间复杂度为（ ）。

{{ select(3) }}

• 

• 

• 

• 

4.小杨想在如上题所述的双向链表中加入一首新歌曲。为了能快速找到该歌曲，他将其作为链表的第一首歌曲，则下面横线上应填入的代码为（ ）。

{{ select(4) }}

• head->next->prev = p;
• head->next = p;
• head->prev = p;
• 触发异常，不能对空指针进行操作。

5.下面是根据欧几里得算法编写的函数，它计算的是a与b的（ ）。

{{ select(5) }}

• 最小公倍数
• 最大公共因子
• 最大公约数
• 最小公共因子

6.欧几里得算法还可以写成如下形式：

int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }

下面有关说法，错误的是（ ）。

{{ select(6) }}

• 本题的gcd()实现为递归方式。
• 本题的gcd()代码最少，更容易理解其模特相除的思想。
• 当a较大时，本题的gcd()实现会多次调用自身，需要较多额外的辅助空间。
• 当a较大时，相比上题中的gcd()的实现，本题的gcd()执行效率更高。

7.下述代码实现素数的线性筛选法，筛选出所有小于等于n的素数，则横线上应填的代码是（ ）。

{{ select(7) }}

• for (int j = 0; j < primes.size() && i * primes[j] <= n; j++)
• for (int j = 0; j <= sqrt(n) && i * primes[j] <= n; j++)
• for (int j = 0; j <= n; j++)
• for (int j = 1; j <= sqrt(n); j++)

8.上题代码的时间复杂度是（ ）。

{{ select(8) }}

• ( O(n^2) )
• ( O(n\log n) )
• ( O(n\log\log n) )
• ( O(n) )

9.为了正确实现快速排序，下面横线上 的代码应为（ ）。

{{ select(9) }}

• while (i <= mid)
• while (i < mid)
• while (i < j)
• while (i <= j)

10.关于分治算法，以下哪个说法正确？

{{ select(10) }}

• 分治算法将问题分成子问题，然后分别解决子问题，最后合并结果。
• 归并排序不是分治算法的应用。
• 分治算法通常用于解决小规模问题。
• 分治算法的时间复杂度总是优于 (O(n\log(n)))。

11.根据下述二分查找法，在排序序的数组1, 3, 6, 9, 17, 31, 39, 52, 61, 79, 81, 90, 96中查找数值82，和82比较的数组元素分别是（ ）。

{{ select(11) }}

• 52, 61, 81, 90
• 52, 79, 90, 81
• 39, 79, 90, 81
• 39, 79, 90

12.要实现一个高精度减法函数，则下面代码中加划线应该填写的代码为（ ）。

{{ select(12) }}

• a[i + 1]--;
• a[i]--;
• b[i + 1]--;
• b[i]--;

13.设A和B是两个长度为n的有序数组，现将A和B合并成一个有序数组，归并排序算法在最坏情况下至少要做（ ）次比较。

{{ select(13) }}

• n²
• n log n
• 2n - 1
• n

14.给定如下函数：

int fun(int n) { if (n == 1) return 1; if (n == 2) return 2; return fun(n - 2) - fun(n - 1); }

则当n = 7时，函数返回值为（ ）。

{{ select(14) }}

• 0
• 1
• 21
• -11

15.给定如下函数（函数功能同上题，增加输出打印）：

int fun(int n) { cout << n << " "; if (n == 1) return 1; if (n == 2) return 2; return fun(n - 2) - fun(n - 1); }

则当 ( n = 4 ) 时，屏幕上输出序列为（ ）。

{{ select(15) }}

• 4 3 2 1
• 1 2 3 4
• 4 2 3 1 2
• 4 2 3 2 1

判断题

1.如果将双向链表的最后一个结点的下一项指针指向第一个结点，第一个结点的前一项指针指向最后一个结点，则该双向链表构成循环链表。

{{ select(16) }}

• 对
• 错

2.数组和链表都是线性表，链表的优点是插入删除不需要移动元素，并且能随机查找。

{{ select(17) }}

• 对
• 错

3.链表的存储空间物理上可以连续，也可以不连续。

{{ select(18) }}

• 对
• 错

4.找出自然数以内的所有质数，常用算法有埃拉托斯特尼（埃氏）筛法和线性筛法，其中埃氏筛法效率更高。

{{ select(19) }}

• 对
• 错

5.唯一分解定理表明任何一个大于1的整数都可以唯一地表示为一系列质数的乘积，即质因数分解是唯一的。

{{ select(20) }}

• 对
• 错

6.贪心算法通过每一步选择局部最优解来获得全局最优解，但并不一定能找到最优解。

{{ select(21) }}

• 对
• 错

7.归并排序和快速排序都采用递归实现，也都是不稳定排序。（ ）

{{ select(22) }}

• 对
• 错

8.插入排序有时比快速排序时间复杂度更低。

{{ select(23) }}

• 对
• 错

9.在进行全国人口普查时，将其分解为对每个省市县乡来进行普查和统计。这是典型的分治策略。

{{ select(24) }}

• 对
• 错

10.在下面C++代码中，由于删除了变量ptr，因此ptr所对应的数据也随之删除，故执行下述代码时，将报错。

{{ select(25) }}

• 对
• 错