一.单选题(每题2分，共30分)

1. 下⾯关于链表和数组的描述， 错误的是

{{ select(1) }}

• 数组⼤⼩固定， 链表⼤⼩可动态调整。
• 数组⽀持随机访问， 链表只能顺序访问。
• 存储相同数⽬ 的整数， 数组⽐链表所需的内存多。
• 数组插⼊和删除元素效率低， 链表插⼊和删除元素效率⾼。

2. 通过（ ） 操作， 能完成在双向循环链表结点 p 之后插⼊结点 s 的功能（其中 next 域为结点的直接后继， prev 域为结点的直接前驱） 。

{{ select(2) }}

• p->next->prev = s; s->prev = p; p->next = s; s->next = p->next;
• p->next->prev = s; p->next = s; s->prev = p; s->next = p->next;
• s->prev = p; s->next = p->next; p->next = s; p->next->prev = s;
• s->next = p->next; p->next->prev = s; s->prev = p; p->next = s;

3. 对下⾯两个函数， 说法错误的是 （ ）。

   int sumA(int n) {
   	int res = 0;
   	for (int i = 1; i <= n; i++) {
   		res += i;
   	}
   	return res;
   }
   
   int sumB(int n) {
   	if (n == 1)
   		return 1;
   	int res = n + sumB(n - 1);
   	return res;
   }
   

{{ select(3) }}

• sumA体现了迭代的思想。
• SumB采⽤的是递归⽅式。
• SumB函数⽐SumA的时间效率更⾼。
• 两个函数的实现的功能相同。

4. 有如下函数 fun ， 则 fun(20, 12) 的返回值为

   int fun(int a, int b) {
   	if (a % b == 0)
   		return b;
   	else
   		return fun(b, a % b);
   }
   
   

{{ select(4) }}

• $20$
• $12$
• $4$
• $2$

5. 下述代码实现素数表的埃拉托斯特尼筛法， 筛选出所有⼩于等于 n 的素数， 则横线上应填的最佳代码是 （ ）。

   void sieve_Eratosthenes(int n) {
   	vector<bool> is_prime(n + 1, true);
   	vector<int> primes;
       
   	for (int i = 2; i * i <= n; i++) {
   		if (is_prime[i]) {
   			primes.push_back(i);
   			________________________________ { // 在此处填入代码
   				is_prime[j] = false;
   			}
   		}
   	}
       
   	for (int i = sqrt(n) + 1; i <= n; i++) {
   		if (is_prime[i]) {
   			primes.push_back(i);
   		}
   	} 
       
   	return primes;
   }
   
   

{{ select(5) }}

• for (int j = i; j <= n; j++)
• for (int j = i * i; j <= n; j++)
• for (int j = i * i; j <= n; j += i)
• for (int j = i; j <= n; j += i)

6. 下述代码实现素数表的线性筛法， 筛选出所有⼩于等于 n 的素数， 则横线上应填的代码是 （ ）。

vector<int> sieve_linear(int n) {
	vector<bool> is_prime(n + 1, true);
    vector<int> primes;
    
    for (int i = 2; i <= n / 2; i++) {
		if (is_prime[i])
			primes.push_back(i);
		________________________________ { // 在此处填入代码
			is_prime[i * primes[j]] = 0;
			if (i % primes[j] == 0)
				break;
		}
	}
    
	for (int i = n / 2 + 1; i <= n; i++) {
		if (is_prime[i])
			primes.push_back(i);
	} 
	return primes;
}

下面有关说法，错误的是

{{ select(6) }}

• for (int j = 0; j < primes.size() && i * primes[j] <= n; j++)
• for (int j = 1; j < primes.size() && i * j <= n; j++)
• for (int j = 2; j < primes.size() && i * primes[j] <= n; j++)
• 以上都不对

7. 下⾯函数可以将 n 的所有质因数找出来， 其时间复杂度是 （ ）。

   #include <iostream>
   #include <vector>
   
   vector<int> get_prime_factors(int n) {
   	vector<int> factors;
       
   	while (n % 2 == 0) {
   		factors.push_back(2);
   		n /= 2;
   	}
       
      for (int i = 3; i * i <= n; i += 2) {
   		while (n % i == 0) {
   			factors.push_back(i);
   			n /= i;
   		}
   	}
       
       if (n > 2) {
   		factors.push_back(n);
   	}
       
   	return factors;
   }
   
   
   

{{ select(7) }}

• $O(n^2)$

• $O(nlogn)$

• $O(\sqrt{n}logn)$

• $O(n)$

8. 现在⽤如下代码来计算 $x^n$（ n个x相乘） ， 其时间复杂度为（ ） （ ）。

{{ select(8) }}

double quick_power(double x, unsigned n) {
	if (n == 0) return 1;
	if (n == 1) return x;
	return quick_power(x, n / 2) * quick_power(x, n / 2) * ((n & 1) ? x : 1);
}

• $O(n)$
• $O(n^2)$
• $O(logn)$
• $O(nlogn)$

9. 假设快速排序算法的输⼊是⼀个长度为 的已排序数组， 且该快速排序算法在分治过程总是选择第⼀个元素 作为基准元素。 下⾯选项（ ） 描述的是在这种情况下的快速排序⾏为。

{{ select(9) }}

• 快速排序对于此类输⼊的表现最好， 因为数组已经排序。
• 快速排序对于此类输⼊的时间复杂度是$O(nlogn)$ 。
• 快速排序对于此类输⼊的时间复杂度是$O(n^2)$ 。
• 快速排序⽆法对此类数组进⾏排序， 因为数组已经排序。

10. 考虑以下C++代码实现的归并排序算法

    void merge(int arr[], int left, int mid, int right) {
    	int n1 = mid - left + 1;
    	int n2 = right - mid;
    	int L[n1], R[n2];
    	for (int i = 0; i < n1; i++)
    		L[i] = arr[left + i];
    	for (int j = 0; j < n2; j++)
    		R[j] = arr[mid + 1 + j];
    	int i = 0, j = 0, k = left;
    	while (i < n1 && j < n2) {
    		if (L[i] <= R[j]) {
    			arr[k] = L[i];
    			i++;
    		}
    		else {
    			arr[k] = R[j];
    			j++;
    		} 
    		k++;
        }
           
    	while (i < n1) {
    		arr[k] = L[i];
    		i++;
    		k++;
    	}
        
     	while (j < n2) {
    		arr[k] = R[j];
    		j++;
    		k++;
    	}
    }
    

对长度为 n 的数组 arr ， 挑⽤函数 merge_sort(a, 0, n-1) ， 在排序过程中 merge 函数的递归调⽤次数⼤约是

{{ select(10) }}

• $O(1)$
• $O(n)$
• $O(logn)$
• $O(nlogn)$

11. 现在有 n 个⼈要过河， 每只船最多载2⼈， 船的承重为100kg。 下列代码中， 数组 weight 中保存有 n 个⼈ 的体重（单位为kg） ， 已经按从⼩到⼤排好序， 代码输出过河所需要的船的数⽬ ， 采⽤的思想为（ ）

    int i, j;
    int count = 0;
    for (i = 0, j = n - 1; i < j; j--) {
    	if (weight[i] + weight[j] <= 100) {
    	i++;
    }
    	count++;
    } 
    printf("过河的船数： %d\n", count);
    
    

{{ select(11) }}

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

12. 关于分治算法， 以下哪个说法正确？

{{ select(12) }}

• 分治算法将问题分成⼦问题， 然后分别解决⼦问题， 最后合并结果。
• 归并排序不是分治算法的应⽤。
• 分治算法通常⽤于解决⼩规模问题。
• 分治算法的时间复杂度总是优于$O(nlog(n))$。

13. 根据下述⼆分查找法， 在排好序的数组 1， 3， 6， 9， 17， 31， 39， 52， 61， 79 中查找数值 31 ， 循环 while (left <= right) 执⾏的次数为 ( )。

    int binary_search(vector<int>& nums, int target) {
    	int left = 0;
    	int right = nums.size() - 1;
    	while (left <= right) {
    		int mid = left + (right - left) / 2;
    		if (nums[mid] == target) {
    			return mid;
    		}
    		else if (nums[mid] < target) {
    			left = mid + 1;
    		}
    		else {
                right = mid - 1;
    		}
    	} 
    	return -1; // 如果找不到目标元素， 返回-1
    }
    

{{ select(13) }}

• $1$
• $2$
• $3$
• $4$

14. 以下关于⾼精度运算的说法错误的是

{{ select(14) }}

• ⾼精度计算主要是⽤来处理⼤整数或需要保留多位⼩数的运算。
• ⼤整数除以⼩整数的处理的步骤可以是， 将被除数和除数对齐， 从左到右逐位尝试将除数乘以某个数， 通过 减法得到新的被除数， 并累加商。
• ⾼精度乘法的运算时间只与参与运算的两个整数中长度较长者的位数有关。
• ⾼精度加法运算的关键在于逐位相加并处理进位。

15. 当$n=7$时， 下⾯函数的返回值为

```cpp
int fun(int n) {
	if (n == 1) return 1;
	else if (n >= 5) return n * fun(n - 2);
	else return n * fun(n - 1);
}
```

{{ select(15) }}

• $105$
• $804$
• $210$
• $420$

二.判断题(每题2分，共20分)

16. 在操作系统中， 需要对⼀组进程进⾏循环。 每个进程被赋予⼀个时间⽚， 当时间⽚⽤完时， CPU将切换到下⼀个进程。 这种循环操作可以通过环形链表来实现。

{{ select(16) }}

• 正确
• 错误

17. 找出⾃ 然数 n 以内的所有质数， 常⽤算法有埃拉托斯特尼（埃⽒） 筛法和线性筛法， 其中线性筛法效率更 ⾼。

{{ select(17) }}

• 正确
• 错误

18. 唯⼀分解定理表明任何⼀个⼤于 1 的整数都可以唯⼀地分解为素数之和。

    {{ select(18) }}

• 正确
• 错误

19. 贪⼼算法通过每⼀步选择局部最优解， 从⽽⼀定能获得最优解。

{{ select(19) }}

• 正确
• 错误

20. 快速排序和归并排序的平均时间复杂度均为$O(nlogn)$，且都是稳定排序。

    {{ select(20) }}

• 正确

• 错误

21. 插⼊排序的时间复杂度总是⽐快速排序低。

    {{ select(21) }}

• 正确
• 错误

22. 引⼊分治策略往往可以提升算法效率。 ⼀⽅⾯， 分治策略减少了操作数量； 另⼀⽅⾯， 分治后有利于系统的并⾏优化。

{{ select(22) }}

• 正确
• 错误

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

    {{ select(23) }}

• 正确
• 错误

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

{{ select(24) }}

• 正确
• 错误

25. 对于已经定义好的标准数学函数 sin(x) ， 应⽤程序中的语句 y=sin(sin(x)); 是⼀种递归调⽤。

    {{ select(25) }}

• 正确

• 错误