单选题（每题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<int>)pivot
• (vector<int>)pivot + (qSort(less) + qSort(greater))
• (qSort(less) + (vector<int>)pivot + qSort(greater))
• qSort(less) + pivot + qSort(greater)

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

   

• isPrimeA( ) 的最坏时间复杂度是$O({N\over2})$，isPrimeB( ) 的最坏时间复杂度是$O(logN)$，isPrimeA( ) 优于isPrimeB( )
• isPrimeA( ) 的最坏时间复杂度是 $O({N\over2})$，isPrimeB( ) 的最坏时间复杂度是$O(N{1\over2})$，isPrimeB( ) 绝⼤多数情况下优于isPrimeA( )
• isPrimeA( ) 的最坏时间复杂度是 $O(N{1\over2})$ ，isPrimeB( ) 的最坏时间复杂度是$O(N)$，isPrimeA( ) 优于isPrimeB( )
• isPrimeA( ) 的最坏时间复杂度是 $O(logN)$ ，isPrimeB( ) 的最坏时间复杂度是 $O(N)$，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) }}

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