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

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

   int fiboA(int N) {
   	if (N == 1 || N == 2)
   		return 1;
   
   	return fiboA(N - 1) + fiboA(N - 2);
   }
   
   int fiboB(int N) {
   	if (N == 1 || N == 2)
   		return 1;
   
   	int last2 = 1, last1 = 1;
   	int nowVal = 0;
   	for (int i = 2; i < N; i++) {
   		nowVal = last1 + last2;
   		last2 = last1;
   		last1 = nowVal;
   	}
   
   	return nowVal;
   }
   

{{ select(1) }}

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

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

   void mergeSort(int SList[], int TList[], int s, int t, int len) {
   	if (s == t) {
   		TList[s] = SList[s];
   		return ;
   	}
   
   	int *T2 = new int[len]; // 保存中间结果
   	int m = (s + t) / 2;
   	___________________;
   	merge(T2, SList, s, m, t);
   
   	delete T2;
   	return ;
   }
   

{{ 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. 阅读下面的 $\tt C$++ 代码，执行后其输出是（ ）。

   int stepCount = 0;
   int fracA(int N) {
   	stepCount += 1;
   	cout << stepCount << "->";
   
   	int rtn = 1;
   	for (int i = 1; i <= N; i++)
   		rtn *= i;
   
   	return rtn;
   }
   
   int fracB(int N) {
   	stepCount += 1;
   	cout << stepCount << "->";
   
   	if (N == 1)
   		return 1;
   
   	return N * fracB(N - 1);
   }
   
   int main() {
   	cout << fracA(5);
   	cout << "<===>";
   	cout << fracB(5);
   
   	return 0;
   }
   

{{ 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. 下面的 $\tt C$++ 代码用于对 $\tt lstA$ 排序，使得偶数在前奇数在后，横线处应填入（ ）。

   bool isEven(int N) {
   	return N % 2 == 0;
   }
   
   void swap(int &a, int &b) {
   	int t;
   	t = a, a = b, b = t;
   
   	return ;
   }
   
   void sortA(int lstA[], int n) {
   	int i, j, t;
   	for (i = n - 1; i > 0; i--)
   		for (j = 0; j < i; j++)
   			if (______________)
   				swap(lstA[j], lstA[j + 1]);
   
   	return ;
   }
   

{{ 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. 下面的 $\tt C$++ 代码用于将字符串保存到带头节点的双向链表中，并对重复的串计数，然后将最新访问的串的节点放在链头便于查找。横线处应填入代码是（ ）。

   typedef struct Node {
   	string str;
   	int ref;
   	struct Node *next, *prev;
   }Node;
   
   Node * Insert(Node *pHead, string s) {
   	Node *p = pHead->next;
   	Node *q;
   	while (p) {
   		if (p->str == s) {
   			p->ref++;
   			p->next->prev = p->prev;
   			p->prev->next = p->next;
   			break;
   		}
   		p = p->next;
   	}
   
   	if (!p) {
   		p = new Node;
   		p->str = s;
   		p->ref = 0;
   		p->next = p->prev = NULL;
   	}
   
   	__________________
   	pHead->next = p, p->prev = pHead;
   
   	return pHead;
   }
   

{{ 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. 有关下面 $\tt C$++ 代码说法正确的是（ ）。

   int rc;
   int foo(int x, int y) {
   	int r;
   	if (y == 0)
   		r = x;
   	else {
   		r = foo(y, x % y);
   		rc++;
   	}
   
   	return r;
   }
   

{{ select(6) }}

• 如果 $x$ 小于 $10$，$rc$ 值也不会超过 $20$
• $\tt foo$ 可能无限递归
• $\tt foo$ 可以求出 $x$ 和 $y$ 的最大公共质因子
• $\tt foo$ 能够求出 $x$ 和 $y$ 的最小公倍数

7. 下面的 $\tt C$++ 代码实现对 $\tt list$ 的快速排序，横线处应该填入的是（ ）。

   注：原题为错题，此处进行了修正。

   vector<int> operator +(vector<int> lA, vector<int> lB) {
       vector<int> lst;
       for (int i = 0; i < lA.size(); i++)
           lst.push_back(lA[i]);
       for (int i = 0; i < lB.size(); i++)
           lst.push_back(lB[i]);
   
       return lst;
   }
   
   vector<int> qSort(vector<int> lst) {
       if (lst.size() < 2)
           return lst;
       
       int pivot = lst[0];
       vector<int> less, greater, tmp{pivot};
       for (int i = 1; i < lst.size(); i++)
           if (lst[i] <= pivot) less.push_back(lst[i]);
           else greater.push_back(lst[i]);
   
       return ________________;
   }
   

{{ select(7) }}

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

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

   bool isPrimeA(int N) {
   	if (N < 2)
   		return false;
   	
   	for (int i = 2; i <= N / 2; i++)
   		if (N % i == 0)
   			return false;
   
   	return true;
   }
   
   bool isPrimeB(int N) {
   	if (N < 2)
   		return false;
   
   	for (int i = 2; i <= sqrt(N); i++)
   		if (N % i == 0)
   			return false;
   
   	return true;
   }
   

{{ select(8) }}

• $\tt isPrimeA()$ 的最坏时间复杂度是 $O(\frac{N}{2})$，$\tt isPrimeB()$ 的最坏时间复杂度是 $O(\log N)$，$\tt isPrimeA()$ 优于 $\tt isPrimeB()$
• $\tt isPrimeA()$ 的最坏时间复杂度是 $O(\frac{N}{2})$，$\tt isPrimeB()$ 的最坏时间复杂度是 $O(N^{\frac{1}{2}})$，$\tt isPrimeB()$ 绝大多数情况下优于 $\tt isPrimeA()$
• $\tt isPrimeA()$ 的最坏时间复杂度是 $O(N^{\frac{1}{2}})$，$\tt isPrimeB()$ 的最坏时间复杂度是 $O(N)$，$\tt isPrimeA()$ 优于 $\tt isPrimeB()$
• $\tt isPrimeA()$ 的最坏时间复杂度是 $O(\log N)$，$\tt isPrimeB()$ 的最坏时间复杂度是 $O(N)$，$\tt isPrimeA()$ 优于 $\tt isPrimeB()$

9. 下面 $\tt C$++ 代码用于有序 $\tt list$ 的二分查找，有关说法错误的是（ ）。

   int _binarySearch(vector<int> lst, int Low, int High, int Target) {
   	if (Low > High)
   		return -1;
   
   	int Mid = (Low + High) / 2;
   	if (Target == lst[Mid])
   		return Mid;
   	else if (Target < lst[Mid])
   		return _binarySearch(lst, Low, Mid - 1, Target);
   	else 
   		return _binarySearch(lst, Mid + 1, High, Target);
   }
   
   int bSearch(vector<int> lst, int Val) {
   	return _binarySearch(lst, 0, lst.size(), Val);
   }
   

{{ select(9) }}

• 代码采用二分法实现有序 $\tt list$ 的查找
• 代码采用分治算法实现有序 $\tt list$ 的查找
• 代码采用递归方式实现有序 $\tt list$ 的查找
• 代码采用动态规划算法实现有序 $\tt list$ 的查找

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

{{ select(10) }}

• $O(N)$
• $O(\log N)$
• $O(N \log N)$
• $O(N^2)$

11. 下面的 $\tt C$++ 代码使用数组模拟整数加法，可以处理超出大整数范围的加法运算。横线处应填入代码是（ ）。

    vector<int> operator +(vector<int> a, vector<int> b) {
    	vector<int> c;
    	int t = 0;
    
    	for (int i = 0; i < a.size() || i < b.size(); i++) {
    		if (i < a.size()) t = t + a[i];
    		if (i < b.size()) t = t + b[i];
    		______________________________;
    	}
    
    	if (t) c.push_back(t);
    
    	return 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. 有关下面 $\tt C$++ 代码的说法正确的是（ ）。

    class Node {
    public:
    	int Value;
    	Node* Prev;
    	Node* Next;
    	Node(int val, Node* Prv = NULL, Node* Nxt = NULL);
    };
    
    Node::Node(int Val, Node* Prv, Node* Nxt) {
    	this->Value = Val;
    	this->Prev = Prv;
    	this->Next = Nxt;
    }
    
    int main() {
    	Node firstNode = Node(10);
    	firstNode.Next = new Node(100, &firstNode);
    	firstNode.Next->Next = new Node(111, firstNode.Next);
    }
    

{{ select(12) }}

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

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

{{ select(13) }}

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

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

{{ select(14) }}

• 埃氏筛法
• 线性筛法
• 二分答案
• 枚举法

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

{{ select(15) }}

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

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

1. 归并排序的时间复杂度是 $O(N \log N)$。（ ）

{{ select(16) }}

• 正确
• 错误

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

   注：根据题意，分出来的巧克力应为正方形。

{{ select(17) }}

• 正确
• 错误

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

   int Fibo(int N) {
   	if (N == 1 || N == 2)
   		return 1;
   	else {
   		int m = fiboA(N - 1);
   		int n = fiboB(N - 2);
   
   		return m + n;
   	}
   }
   

{{ select(18) }}

• 正确
• 错误

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

{{ select(19) }}

• 正确
• 错误

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

{{ select(20) }}

• 正确
• 错误

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

{{ select(21) }}

• 正确
• 错误

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

   char s[10];
   int main() {
   	int N;
   	cin >> N;
   	string rst = "";
   	while (N != 0) {
   		s[0] = N % 8 + '0';
   		rst += string(s);
   		N /= 8;
   	}
   
   	cout << rst << endl;
   
   	return 0;
   }
   

{{ select(22) }}

• 正确
• 错误

8. 对数组 int arr[] = {2, 6, 3, 5, 4, 8, 1, 0, 9, 10} 执行 sort(arr, arr+10)，则执行后 $\tt arr$ 中的数据调整为 $\{0, 1, 2, 3, 4, 5, 6, 8, 9, 10\}$。（ ）

{{ select(23) }}

• 正确
• 错误

9. 小杨想写一个程序来算出正整数 $N$ 有多少个因数，经过思考他写出了一个重复没有超过 $N/2$ 次的循环就能够算出来了。（ ）

{{ select(24) }}

• 正确
• 错误

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

{{ select(25) }}

• 正确
• 错误