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

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

A、fiboA( ) 用递归方式，fiboB( ) 循环方式

B、fiboA( ) 更加符合斐波那契数列的数学定义，直观易于理解，而fiboB() 需要将数学定义转换为计算机程序实现

C、 fiboA( ) 不仅仅更加符合数学定义，直观易于理解，且因代码量较少执行效率更高

D、fiboB( ) 虽然代码量有所增加，但其执行效率更高

【答案】：C

【考纲知识点】：算法知识点

【解析】：fiboA()是很好理解的，但是执行效率不高，有的计算是重复的，导致效率低。

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

A、mergeSort(SList, T2, s, m,len), mergeSort(SList, T2, m,t,len)

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

C、 mergeSort(SList, T2, s, m,len), mergeSort(SList, T2, m+1,t,len)

D、mergeSort(SList, T2, s, m-1,len), mergeSort(SList, T2, m-1,t,len)

【答案】：C

【考纲知识点】：算法知识点

【解析】：本题考察归并排序。归并排序需要先将排序序列一分为二，左边的元素的区间是[s,m],右边元素区间是[m+1,t]，然后递归排序两个子序列后，将有序的子序列合并。

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

A、1->120<===>2->120

B、 1->120<===>1->120

C、1->120<===>1->2->3->4->5->120

D、1->120<===>2->3->4->5->6->120

【答案】：D

【考纲知识点】：算法知识点

【解析】：本题考察递归算法。输出 fracA 函数，是先输出 1，再输出 5 的阶乘，120；2行代码，执行fracB函数，此时stepCount从2开始计数，依次输出2/3/4/5/6，再输出 5 的阶乘 120。

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

A、!isEven(lstA[j]) && isEven(lstA[j+1])

B、 isEven(lstA[j]) && !isEven(lstA[j+1])

C、 lstA[j] > lstA[j+1]

D、 lstA[j] < lstA[j+1]

【答案】：A

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

【解析】：本题考察排序算法。前一个数字，下标是 j 的数字是偶数，后面的数字下标是 j+1 的是奇数，按照要求，偶数在奇数的后面，要交换。A 符合题意条件。

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

A、if(pHead) {p->next = pHead->next, pHead->next->prev = p;}

B、 if(pHead->next) {p->next = pHead->next, pHead->next->prev = p;}

C、p->next = pHead->next, pHead->next->prev = p;

D、 触发异常 ，不能对空指针进行操作。

【答案】：B

【考纲知识点】：指针知识点

【解析】：本题考察双链表知识点。每个节点需要 2 个指针，指向前驱节点和后继节点。按照要求，新的节点要求插入到链表头部。头节点和新插入的节点都需要修改。B 选项能够完成新节点的插入。

6. 有关下面C++代码说法正确的是（ ）。

A、 如果 x 小于 10， rc 值也不会超过 20

B、 foo 可能无限递归

C、foo 可以求出 x 和 y 的最大公共质因子

D、foo 能够求出 x 和 y 的最小公倍数

【答案】：A

【考纲知识点】：数学知识点

【解析】：本题考察数学算法，求最大公约数。这是典型的最大公约数写法的变形。排除法选 A。

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

A、 qSort(less) + qSort(greater) + (vector<int>)pivot

B、 (vector<int>)pivot + (qSort(less) + qSort(greater))

C、 (qSort(less) + (vector<int>)pivot + qSort(greater))

D、qSort(less) + pivot + qSort(greater)

【答案】：C

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

【解析】：本题考察快速排序。Less 数组保存的是小于等于 pivot，然后加上 pivot元素，再加上大于等于 pivot 的数组。

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

A、 isPrimeA( ) 的最坏时间复杂度是$O({N\over2})$，isPrimeB( ) 的最坏时间复杂度是$O(logN)$，isPrimeA( ) 优于isPrimeB( )

B、 isPrimeA( ) 的最坏时间复杂度是 $O({N\over2})$，isPrimeB( ) 的最坏时间复杂度是$O(N{1\over2})$，isPrimeB( ) 绝⼤多数情况下优于isPrimeA( )

C、isPrimeA( ) 的最坏时间复杂度是 $O(N{1\over2})$ ，isPrimeB( ) 的最坏时间复杂度是$O(N)$，isPrimeA( ) 优于isPrimeB( )

D、 isPrimeA( ) 的最坏时间复杂度是 $O(logN)$ ，isPrimeB( ) 的最坏时间复杂度是 $O(N)$，isPrimeA( ) 优于isPrimeB( )

【答案】：B

【考纲知识点】：数学知识点

【解析】：本题考察数学知识，判断质数。A 函数时间复杂度是 O(n/2)，B 函数算法是 O(sqrt(n))

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

A、 代码采用二分法实现有序 list 的查找

B、 代码采用分治算法实现有序 list 的查找

C、 代码采用递归⽅式实现有序 list 的查找

D、代码采用动态规划算法实现有序 list 的查找

【答案】：D

【考纲知识点】：算法知识点

【解析】：本题考察算法知识点。二分法每次规模减半，查找平均时间复杂度是 B。

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

A、 $O(N)$

B、 $O(logN)$

C、$O(NlogN)$

D、 $O({N^2})$

【答案】：B

【考纲知识点】：算法知识点

【解析】：本题考察算法知识点。二分法每次规模减半，单词查找平均时间复杂度是 B。

11. 下⾯的 C++代码使⽤数组模拟整数加法，可以处理超出⼤整数范围的加法运算。横线处应填入代码是 ( ) 。

A、 c.push_back(t % 10), t = t % 10;

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

C、 c.push_back(t / 10), t = t / 10;

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

【答案】：D

【考纲知识点】：算法知识点

【解析】：本题考察高精度知识点。每次保存对应位和的最低位数字，去掉最低位数字后，保持进位，循环执行。

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

A、 上述代码构成单向链表

B、 上述代码构成双向链表

C、上述代码构成循环链表

D、 上述代码构成指针链表

【答案】：B

【考纲知识点】：链表知识点

【解析】：本题考察链表知识点。每个节点指向自己前一个节点和后一个节点，因此是双向链表。

13. 通讯卫星在通信网络系统中主要起到（ ）的作⽤ 。

A、 信息过滤

B、 信号中继

C、避免攻击

D、数据加密

【答案】：B

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

【解析】：本题考察计算机基础知识。通信卫星可以转发无线电信号，实现通信地球站间或地球站与航天器间的无线电通信，因此具有信号中继作用。选 B。

14. 小杨想编写⼀个判断任意输入的整数 N 是否为素数的程序 ，下面哪个方法不合适？ ( )

A、 埃氏筛法

B、 线性筛法

C、二分答案

D、枚举法

【答案】：C

【考纲知识点】：数学知识

【解析】：本题考察数学知识。线筛和埃筛都可以判断素数，枚举也可以，二分规模减半，不能合理判断。

15. 下面的排序算法都要处理多趟数据 ，哪种排序算法不能保证在下一趟处理时从待处理数据中选出最大或最小的数据？ ( )

A、选择排序

B、快速排序

C、堆排序

D、冒泡排序

【答案】：B

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

【解析】：本题考察排序算法知识。需要了解每种排序算法的特点。快速排序是选定一个数字，每次把比它小的放在左边，比元素大的放在右边，不能确定最值。