No testdata at current.

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

第1题. 下⾯C++代码⽤于求斐波那契数列，该数列第1、2项为1，以后各项均是前两项之和。函数fibo()属于( )。

{{ select(1) }}

int fibo(int n){
	if(n<=0)
		return 0;
	if(n==1 || n==2)
		return 1;
	int a=1,b=1,next;
	for(int i=3;i<=n;i++){
		next=a+b;
		a=b;
		b=next;
	}
	return next;
}

• 枚举算法
• 贪心算法
• 迭代算法
• 递归算法

第2题. 下⾯C++代码⽤于将输⼊⾦额换成最少币种组合⽅案，其实现算法是（ ）。

{{ select(2) }}

#include<iostream>
using namespace std;

#define N_COINS 7
int coins[N_COINS]={100,50,20,10,5,2,1};
int coins_used[N_COINS];

void find_coins(int money){
	for(int i=0;i<N_COINS;i++){
		coins_used[i]=money / coins[i];
		money = money % coins[i];
	}
	return;
}
int main(){
	int money;
	cin>>money;//输入要换算的金额
	find_coins(money);
	for(int i=0;i<N_COINS;i++)
		cout<<coins_used[i]<<endl;
	return 0; 
}

• 枚举算法
• 贪心算法
• 迭代算法
• 递归算法

第3题. ⼩杨采⽤如下双链表结构保存他喜欢的歌曲列表：

struct dl_node{
	string song;
	dl_node* next;
	dl_node* prev;
};

⼩杨想在头指针为 head 的双链表中查找他喜欢的某⾸歌曲，采⽤如下查询函数，该操作的时间复杂度为（ ）。

dl_node* search(dl_node* head, string my_song){
	dl_node* temp = head;
	while(temp != nullptr){
		if(temp->song == my_song)
			return temp;
		temp = temp->next;
	}
	return nullptr;
}

{{ select(3) }}

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

第4题. ⼩杨想在如上题所述的双向链表中加⼊⼀⾸新歌曲。为了能快速找到该歌曲，他将其作为链表的第⼀⾸歌曲，则下⾯横线上应填⼊的代码为（ ）。

void insert(dl_node *head, string my_song){
	p=new dl_node;
	p->song = my_song;
	p->prev = nullptr;
	p->next = head;
	
	if(head != nullptr){
		________//在此处填入代码 
	}
	head = p;
}

{{ select(4) }}

• head->next->prev = p;
• head->next = p;
• head->prev = p;
• 触发异常，不能对空指针进⾏操作

第5题. 下⾯是根据欧⼏⾥得算法编写的函数，它计算的是 a与b 的（ ）。

int gcd(int a,int b){
	while(b != 0){
		int temp=b;
		b=a%b;
		a=temp;
	}
	return a;
}

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

• √
• ×