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

$1、$​​ 下面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) }}

• 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]中。横线处应填上代码是( )。

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、$阅读下面的C++代码，执行后其输出是( )。

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);
}

{{ 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 排序，使得偶数在前奇数在后，横线处应填入( )

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

#include<iostream>
using namespace std;

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;
		}
	}
	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、$有关下面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
• foo 可能无限递归
• foo 可以求出 x 和 y 的最大公共质因子
• foo 能够求出 x 和 y 的最小公倍数

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

vector<int> operator + v(vector<int>lA, vector<int>lB) {
	vector<int>lst;
	for (int i = 1; i < lA.size(); i++)
		lst.push_back(lA[i]);

	for (int i = 1; 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;
	for (int i = 1; i < lst.size(); i++)
		if (lst[i] <= pivot) less.push_back(lst[i]);
		else greater.push_back(lst[i]);
	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) + (vector)pivot
• (vector)pivot + (qSort(less) + qSort(greater))
• (qSort(less) + (vector)pivot + qSort(greater))
• qSort(less) + pivot + qSort(greater)

$8、$下面C++代码中的 isPrimeA() 和 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 isPrime(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) }}

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

$9、$下面C++代码用于有序 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) }}

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

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

{{ select(10) }}

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

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

class Node {
public:
	int Value;
	Node* Prev;
	Node* Next;
	Node(int Val, Node* Pre = 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$ 分）

$16、$归并排序的时间复杂度是$O(NlogN)$ 。( )

{{ select(16) }}

• 正确
• 错误

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

{{ select(17) }}

• 正确
• 错误

$18、$以下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) }}

• 正确
• 错误

$19、$贪心算法可以达到局部最优，但可能不是全局最优解。()

{{ select(19) }}

• 正确
• 错误

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

{{ select(20) }}

• 正确
• 错误

$21、$插入排序有时比快速排序时间复杂度更低。（ ）

{{ select(21) }}

• 正确
• 错误

$22、$下面的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) }}

• 正确
• 错误

$23、$对数组 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、$小杨想写一个程序来算出正整数N有多少个因数，经过思考他写出了一个重复没有超过N/2次的循环就能够算出来了。（ ）

{{ select(24) }}

• 正确
• 错误

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

{{ select(25) }}

• 正确
• 错误