一、单选题（每题 2分，共 30分）

第 1 题 下⾯ C++代码⽤于求斐波那契数列，该数列第 1 、 2 项为 1 ，以后各项均是前两项之和。下⾯有关说法错误的是( )。

{{ select(1) }}

• fiboA( )⽤递归⽅式，fiboB()循环⽅式
• fiboA( )更加符合斐波那契数列的数学定义，直观易于理解，⽽fiboB()需要将数学定义转换为计算机程序实现
• fiboA( )不仅仅更加符合数学定义，直观易于理解，且因代码量较少执⾏效率更⾼
• fiboB( )虽然代码量有所增加，但其执⾏效率更⾼

第 2 题 下⾯ C++代码以递归⽅式实现合并排序，并假设merge (int T[], int R[], int s, int m, int t)函数将有序（同样排序规则）的 T[s..m] 和 T[m+1..t] 归并到 R[s..t] 中。横线处应填上代码是 ( )。

{{ select(2) }}

• mergeSort(SList, T2, s, m,len), mergeSort(SList, T2, m,t,len)
• mergeSort(SList, T2, s, m-1,len), mergeSort(SList, T2, m+1,t,len)
• mergeSort(SList, T2, s, m,len), mergeSort(SList, T2, m+1,t,len)
• mergeSort(SList, T2, s, m-1,len), mergeSort(SList, T2, m-1,t,len)

第 3 题 阅读下⾯的 C++代码，执⾏后其输出是 ( )。

{{ select(3) }}

• 1->120<===>2->120
• 1->120<===>1->120
• 1->120<===>1->2->3->4->5->120
• 1->120<===>2->3->4->5->6->120

第 4 题 下⾯的 C++⽤于对lstA排序，使得偶数在前奇数在后，横线处应填⼊ ( )。

{{ select(4) }}

• isEven(lstA[j]) && !isEven(lstA[j+1])
• !isEven(lstA[j]) && isEven(lstA[j+1])
• lstA[j] > lstA[j+1]
• lstA[j] < lstA[j+1]

第 5 题 下⾯的 C++代码⽤于将字符串保存到带头节点的双向链表中，并对重复的串计数，然后将最新访问的串的节点放在链头便于查找。横线处应填⼊代码是（ ）。

{{ select(5) }}

• if(pHead) {p->next = pHead->next, pHead->next->prev = p;}
• if(pHead->next) {p->next = pHead->next, pHead->next->prev = p;}
• p->next = pHead->next, pHead->next->prev = p;
• 触发异常，不能对空指针进⾏操作。

第 6 题 有关下⾯ C++代码说法正确的是（ ）。

{{ select(6) }}

• 如果x⼩于 10，rc值也不会超过 20
• foo可能⽆限递归
• foo可以求出 x 和 y 的最⼤公共质因⼦
• foo能够求出 x 和 y 的最⼩公倍数

第 7 题 下⾯的 C++代码实现对 list 的快速排序，有关说法，错误的是（ ）。

{{ select(7) }}

• qSort(less) + qSort(greater) + (vector)pivot
• (vector)pivot + (qSort(less) + qSort(greater))
• (qSort(less) + (vector)pivot + qSort(greater))
• qSort(less) + pivot + qSort(greater)

第 8 题 下⾯ C++代码中的 isPrimeA() 和 isPrimeB() 都⽤于判断参数 N 是否素数，有关其时间复杂度的正确说法是（ ）。

{{ select(8) }}

• isPrimeA( )的最坏时间复杂度是，isPrimeB( )的最坏时间复杂度是，isPrimeA()优于isPrimeB()
• isPrimeA()的最坏时间复杂度是，isPrimeB( )的最坏时间复杂度是，isPrimeB()绝⼤多数情况下优于isPrimeA()
• isPrimeA()的最坏时间复杂度是，isPrimeB( )的最坏时间复杂度是，isPrimeA( )优于isPrimeB( )
• isPrimeA()的最坏时间复杂度是，isPrimeB( )的最坏时间复杂度是，isPrimeA()优于isPrimeB( )

第 9 题 下⾯ C++代码⽤于有序list的⼆分查找，有关说法错误的是（ ）。

{{ select(9) }}

• 代码采⽤⼆分法实现有序list的查找
• 代码采⽤分治算法实现有序list的查找
• 代码采⽤递归⽅式实现有序list的查找
• 代码采⽤动态规划算法实现有序list的查找

第 10 题 在上题的_binarySearch算法中，如果lst中有N个元素，其时间复杂度是（ ）。 {{ select(10) }}

• O(N)
• O(logN)
• O(NlogN)
• $O(N^2)$

第 11 题 下⾯的 C++代码使⽤数组模拟整数加法，可以处理超出⼤整数范围的加法运算。横线处应填⼊代码是（ ）。

{{ select(11) }}

• c.push_back(t % 10), t = t % 10;
• c.push_back(t / 10), t = t % 10;
• c.push_back(t / 10), t = t / 10;
• c.push_back(t % 10), t = t / 10;

第 12 题 有关下⾯ C++代码的说法正确的是（ ）。

{{ select(12) }}

• 上述代码构成单向链表
• 上述代码构成双向链表
• 上述代码构成循环链表
• 上述代码构成指针链表

第 13 题 通讯卫星在通信⽹络系统中主要起到（）的作⽤。 {{ select(13) }}

• 信息过滤
• 信号中继
• 避免攻击
• 数据加密

第 14 题 ⼩杨想编写⼀个判断任意输⼊的整数 N 是否为素数的程序，下⾯哪个⽅法不合适？（ ） {{ select(14) }}

• 埃⽒筛法
• 线性筛法
• ⼆分答案
• 枚举法

第 15 题 下⾯的排序算法都要处理多趟数据，哪种排序算法不能保证在下⼀趟处理时从待处理数据中选出最⼤或最⼩的数据？（ ） {{ select(15) }}

• 选择排序
• 快速排序
• 堆排序
• 冒泡排序

二、判断题（每题 2分，共 20分）

16、1 题 归并排序的时间复杂度是。( ) {{ select(16) }}

• 对
• 错

17、2 题 ⼩杨在⽣⽇聚会时拿⼀块 H*W 的巧克⼒招待来的 K 个⼩朋友，保证每位⼩朋友⾄少能获得⼀块相同⼤⼩的巧克⼒。那么⼩杨想分出来最⼤边长的巧克⼒可以使⽤⼆分法。（ ） {{ select(17) }}

• 对
• 错

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

{{ select(18) }}

• 对
• 错

19、4 题 贪⼼算法可以达到局部最优，但可能不是全局最优解。 ( ) {{ select(19) }}

• 对
• 错

20、5 题 ⼩杨设计了⼀个拆数程序，它能够将任意的⾮质数⾃然数 N 转换成若⼲个质数的乘积，这个程序是可以设计出来的。（ ） {{ select(20) }}

• 对
• 错

21、6 题 插⼊排序有时⽐快速排序时间复杂度更低。（ ） {{ select(21) }}

• 对
• 错

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

{{ select(22) }}

• 对
• 错

23、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}。（ ） {{ select(23) }}

• 对
• 错

24、9 题 ⼩杨想写⼀个程序来算出正整数 N 有多少个因数，经过思考他写出了⼀个重复没有超过 N/2 次的循环就能够算出来了。（ ） {{ select(24) }}

• 对
• 错

25、10 题 同样的整数序列分别保存在单链表和双向链中，这两种链表上的简单冒泡排序的复杂度相同。（ ） {{ select(25) }}

• 对
• 错