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

第1题. 唯⼀分解定理描述的内容是（ ）。

{{ select(1) }}

• 任意整数都可以分解为素数的乘积
• 每个合数都可以唯⼀分解为⼀系列素数的乘积
• 两个不同的整数可以分解为相同的素数乘积
• 以上都不对

第2题. 贪⼼算法的核⼼思想是（ ）。

{{ select(2) }}

• 在每⼀步选择中都做当前状态下的最优选择。
• 在每⼀步选择中都选择局部最优解。
• 在每⼀步选择中都选择全局最优解。
• 以上都对。

第3题. 下⾯的 C++ 代码⽚段⽤于计算阶乘。请在横线处填⼊（ ），实现正确的阶乘计算（ ）。

int factorial(int n){
	if(n==0 || n==1){
		return 1;
	}else{
		________
	}		
}

{{ select(3) }}

• return n * factorial(n - 1);
• return factorial(n - 1) / n;
• return n * factorial(n);
• return factorial(n / 2) * factorial(n / 2);

第4题. 下⾯的代码⽚段⽤于在双向链表中删除⼀个节点。请在横线处填⼊（ ），使其能正确实现相应功能（ ）。

void deleteNode(DoublyListNode*& head, int value){
	DoublyListNode* currrent = head;
	while(current != nullptr && current->val != value){
		current = current->next;
	}
	if(current != nullptr){
		if(current->prev != nullptr){
			________ //在此处填写代码
		}else{
			head = current->next;
		}
		if(current->next != nullptr){
			current->next->prev = current->prev;
		}
		delete current;
	}
}

{{ select(4) }}

• if (current->next != nullptr) current->next->prev = current->prev;
  

• current->prev->next = current->next;
  

• delete current->next;
  

• current->prev = current->next;
  

第5题. 辗转相除法也被称为（ ）。

{{ select(5) }}

• ⾼斯消元法
• 费马定理
• 欧⼏⾥德算法
• ⽜顿迭代法

第6题. 下⾯的代码⽚段⽤于计算斐波那契数列。该代码的时间复杂度是（ ）。

int fibonacci(int n){
	if(n<=1){
		return n;
	}else{
		return fibonacci(n-1)+fibonacci(n-2);
	}
}

{{ select(6) }}

• $O(1)$
• $O(n)$
• $O(2^n)$
• $O(log n)$

第7题. 下⾯的代码⽚段⽤于将两个⾼精度整数进⾏相加。请在横线处填⼊（ ），使其能正确实现相应功能。

string add(string num1, string num2){
	string result;
	int carry=0;
	int i=num1.size()-1, j=num2.size()-1;
	while(i>=0 || j>=0 || carry){
		int x = (i>=0)?num1[i--] - '0':0;
		int y = (j>=0)?num2[j--] - '0':0;
		int sum = x+y+carry;
		carry = sum / 10;
		________ //此处填入代码 
	}
	return result; 
}

{{ select(7) }}

• result = to_string(sum % 10) + result;
• result = to_string(carry % 10) + result;
• result = to_string(sum / 10) + result;
• result = to_string(sum % 10 + carry) + result;

第8题. 给定序列：1，3，6，9，17，31，39，52，61，79，81，90，96。使⽤以下代码进⾏⼆分查找查找元素 82 时，需要循环多少次，即最后输出的 times 值为（ ）。

int binarySearch(const std::vector<int> &arr, int target){
	int left = 0;
	int right = arr.size()-1;
	int times = 0;
	while(left <= right){
		times++;
		int mid = left+(right-left)/2;
		if(arr[mid] == target){
			cout<<times<<endl;
			return mid;
		}else if(arr[mid] < target){
			left = mid+1;
		}else{
			right = mid-1;
		}
	}
	cout<<times<<endl;
	return -1;
}

{{ select(8) }}

• 2
• 5
• 3
• 4

第9题. 下⾯的代码⽚段⽤于判断⼀个正整数是否为素数。请对以下代码进⾏修改，使其能正确实现相应功能（ ）。

bool isPrime(int num){
	if(num < 2){
		return false;
	}
	for(int i=2; i*i<num; i++){
		if(num%i==0){
			return false;
		}
	}
	return true;
}

{{ select(9) }}

• num < 2 应该改为 num <= 2
• 循环条件 i $*$ i < num 应该改为 i $*$ i <= num
• 循环条件应该是 i <= num
• 循环体中应该是 if (num % i != 0)

第10题. 在埃拉托斯特尼筛法中，要筛选出不⼤于 n 的所有素数，最外层循环应该遍历什么范围（ ）。

vector<int> sieveOfEratosthenes(int n){
	std::vector<bool> isPrime(n + 1, true);
	std::vector<int> primes;
	if(){
		if (isPrime[i]){
			primes.push_back(i);
			for (int j = i * i; j <= n; j += i){
				isPrime[j] = false;
			}
		}
	}
	for (int i = sqrt(n) + 1; i <= n; ++i){
		if(isPrime[i]){
			primes.push_back(i);
		}
	}
	return primes;
}

{{ select(10) }}

• for (int i = 2; i <= n; ++i)
• for (int i = 1; i < n; ++i)
• for (int i = 2; i <= sqrt(n); ++i)
• for (int i = 1; i <= sqrt(n); ++i)

第11题. 素数的线性筛法时间复杂度为（ ）。

{{ select(11) }}

• $O(n)$
• $O(n log log n)$
• $O(n log n)$
• $O(n^2)$

第12题. 归并排序的基本思想是（ ）。

{{ select(12) }}

• 动态规划
• 分治
• 贪⼼算法
• 回溯算法

第13题. 在快速排序中，选择的主元素（pivot）会影响算法的（）。

{{ select(13) }}

• 不影响
• 时间复杂度
• 空间复杂度
• 时间复杂度和空间复杂度

第14题. 递归函数在调⽤⾃⾝时，必须满⾜（ ），以避免⽆限递归？

{{ select(14) }}

• 有终⽌条件
• 函数参数递减（或递增）
• 函数返回值固定
• 以上都对

第15题. 假设给定链表为: 1->3->5->7->nullptr，若调⽤ searchValue(head, 5) ，函数返回值为（ ）。

int searchValue(ListNode*head, int target){
	while(head != nullptr){
		if(head->val == target){
			return 1;
		}
		head = head->next;
	}
	return 0;
}

{{ select(15) }}

• 返回 1
• 返回 0
• 死循环，⽆法返回
• 返回 -1

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

第16题. 辗转相除法⽤于求两个整数的最⼤公约数。（） {{ select(16) }}

• √
• ×

第17题. 插⼊排序的时间复杂度是$O(N log N)$。（ ） {{ select(17) }}

• √
• ×

第18题. ⼆分查找要求被搜索的序列是有序的，否则⽆法保证正确性。（ ）

{{ select(18) }}

• √
• ×

第19题. 使⽤贪⼼算法解决问题时，每⼀步的局部最优解⼀定会导致全局最优解。（ ）

{{ select(19) }}

• √
• ×

第20题. 分治算法的核⼼思想是将⼀个⼤问题分解成多个相同或相似的⼦问题进⾏解决，最后合并得到原问题的解。（ ）

{{ select(20) }}

• √
• ×

第21题. 分治算法的典型应⽤之⼀是归并排序，其时间复杂度为$O(N log N)$。（ ）

{{ select(21) }}

• √
• ×

第22题. 素数表的埃⽒筛法和线性筛法的时间复杂度都是$O(N log log N)$。（ ）

{{ select(22) }}

• √
• ×

第23题. 贪⼼算法是⼀种可以应⽤于所有问题的通⽤解决⽅案。（ ）

{{ select(23) }}

• √
• ×

第24题. 单链表和双链表都可以在常数时间内实现在链表头部插⼊或删除节点的操作。（ ）

{{ select(24) }}

• √
• ×

第25题. 在C语⾔中，递归的实现⽅式通常会占⽤更多的栈空间，可能导致栈溢出。（ ）

{{ select(25) }}

• √
• ×