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

1 int fibo(int n) {
2  if (n <= 0)
3   return 0;
4  if (n == 1 || n == 2)
5   return 1;
6
7  int a = 1，b = 1, next;
8  for (int i = 3; i <= n; i++) {
9   next = a + b;
10   a = b;
11   b = next;
12  }
13  return next;
14 }

下面C++代码用于将输入金额换成最少币种组合方案，其实现算法是( )。

1 #include <iostream>
2 using namespace std;
3
4 #define N_COINS 7
5 int coins[N_COINS] = {100, 50, 20, 10, 5, 2, 1}; //货币面值，单位相同
6 int coins_used[N_COINS];
7
8 void find_coins(int money) {
9  for (int i = 0; i < N_COINS; i++) {
10   coins_used[i] = money / coins[i];
11   money = money % coins[i];
12  }
13  return;
14 }
15 int main() {
16  int money;
17  cin >> money; //输入要换算的金额
18
19  find_coins(money);
20  for (int i = 0; i < N_COINS; i++)
21   cout << coins_used[i] << endl;
22
23  return 0;
24 }

小杨采用如下双链表结构保存他喜欢的歌曲列表：

1 struct dl_node {
2  string song;
3  dl_node* next;
4  dl_node* prev;
5 }

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

1 dl_node* search(dl_node* head, string my_song) {
2  dl_node* temp = head;
3  while (temp != nullptr) {
4   if (temp->song == my_song)
5    return temp;
6   temp = temp->next;
7  }
8  return nullptr;
9 }

小杨想在如上题所述的双向链表中加入一首新歌曲。为了能快速找到该歌曲，他将其作为链表的第一首歌 曲，则下面横线上应填入的代码为（ ）。

1 void insert(dl_node *head, string my_song) {
2  p = new dl_node;
3  p->song = my_song;
4  p->prev = nullptr;
5  p->next = head;
6
7  if (head != nullptr) {
8   ________________________________ // 在此处填入代码
9  }
10  head = p;
11 }

下面是根据欧几里得算法编写的函数，它计算的是 与 的（ ）。

1 int gcd(int a, int b) {
2  while (b != 0) {
3   int temp = b;
4   b = a % b;
5   a = temp;
6  }
7  return a;
8 }

欧几里得算法还可以写成如下形式

1 int gcd(int a, int b) { 
2  return b == 0 ? a : gcd(b, a % b); 
3

下述代码实现素数表的线性筛法，筛选出所有小于等于 的素数，则横线上应填的代码是( )

1 vector<int> linear_sieve(int n) {
2  vector<bool> is_prime(n + 1, true);
3  vector<int> primes;
4  is_prime[0] = is_prime[1] = 0; //0和1两个数特殊处理
5  for (int i = 2; i <= n; ++i) {
6   if (is_prime[i]) {
7    primes.push_back(i);
8   }
9   ________________________________ { // 在此处填入代码
10    is_prime[i * primes[j]] = 0;
11    if (i % primes[j] == 0)
12     break;
13   }
14  }
15  return primes;
16 }

上题代码的时间复杂度是（ ）

为了正确实现快速排序，下面横线上的代码应为（ ）。

1 void qsort(vector<int>& arr, int left, int right) {
2  int i, j, mid;
3  int pivot;
4
5  i = left;
6  j = right;
7  mid = (left + right) / 2; // 计算中间元素的索引
8  pivot = arr[mid]; // 选择中间元素作为基准值
9
10  do {
11   while (arr[i] < pivot) i++;
12   while (arr[j] > pivot) j--;
13   if (i <= j) {
14    swap(arr[i], arr[j]); // 交换两个元素
15    i++; j--;
16   }
17  } ________________________________; // 在此处填入代码
18  if (left < j) qsort(arr, left, j); // 对左子数组进行快速排序
19  if (i < right) qsort(arr, i, right); // 对右子数组进行快速排序
20 }

根据下述二分查找法，在排好序的数组 1，3，6，9，17，31，39，52，61，79，81，90，96 中查找数值 82，和82比较的数组元素分别是（ ）。

1 int binary_search(vector<int>& nums, int target) {
2  int left = 0;
3  int right = nums.size() - 1;
4  while (left <= right) {
5   int mid = (left + right) / 2;
6   if (nums[mid] == target) {
7    return mid;
8   } else if (nums[mid] < target) {
9    left = mid + 1;
10   } else {
11    right = mid - 1;
12   }
13  }
14  return -1; // 如果找不到目标元素，返回-1
15 }

要实现一个高精度减法函数，则下面代码中加划线应该填写的代码为（ ）。

1 //假设a和b均为正数，且a表示的数比b大
2 vector<int> minus(vector<int> a, vector<int> b) {
3  vector<int> c；
4  int len1 = a.size();
5  int len2 = b.size();
6  int i, t;
7
8  for (i = 0; i < len2; i++) {
9   if (a[i] < b[i]) { //借位
10    _____________ // 在此处填入代码
11    a[i] += 10;
12   }
13   t = a[i] - b[i];
14   c.push_back(t);
15  }
16  for (; i < len1; i++)
17   c.push_back(a[i]);
18
19  len3 = c.size();
20  while (c[len3 - 1] == 0) {//去除前导0
21   c.pop_back();
22   len3--;
23  }
24  return c;
25 }

给定如下函数：

1 int fun(int n) {
2  if (n == 1) return 1;
3  if (n == 2) return 2;
4  return fun(n - 2) - fun(n - 1);
5 }

给定如下函数（函数功能同上题，增加输出打印）：

1 int fun(int n) {
2  cout << n << " ";
3  if (n == 1) return 1;
4  if (n == 2) return 2;
5  return fun(n - 2) - fun(n - 1);
6 }

如果将双向链表的最后一个结点的下一项指针指向第一个结点，第一个结点的前一项指针指向最后一个结点，则该双向链表构成循环链表。

归并排序和快速排序都采用递归实现，也都是不稳定排序。

在下面C++代码中，由于删除了变量 ptr ，因此 ptr 所对应的数据也随之删除，故执行下述代码时，将报错。

1 int* ptr = new int(10);
2 cout << *ptr << endl;
3 delete ptr;
4 cout << ptr << endl;

3.1 编程题 1 

试题名称：黑白格 

时间限制：1.0 s 

内存限制：512.0 MB 

3.1.1 题面描述 

小杨有一个n行m列的网格图，其中每个格子要么是白色，要么是黑色。 

小杨想知道至少包含k个黑色格子的最小子矩形包含了多少个格子。 

3.1.2 输入格式 

第一行包含三个正整数n，m，k，含义如题面所示。 

之后n行，每行一个长度为m的01串，代表网格图第i行格子的颜色，如果为0，则对应格子为白色，否则为黑色。 

3.1.3 输出格式 

输出一个整数，代表至少包含k个黑色格子的最小子矩形包含格子的数量，如果不存在则输出0。 

3.1.4 样例1 

3.1.5 样例解释 

对于样例1，假设 (i，j) 代表第i行第j列，至少包含5个黑色格子的最小子矩形的四个顶点为 (2，4)，(2，5)，(,4，4)，(4，5)，共包含6个格子。 

3.1.6 数据范围 

对于全部数据，保证有1≤n，m≤100，1≤k≤n×m。

3.2 编程题 2 

试题名称：小杨的幸运数字 

时间限制：1.0 s 

内存限制：512.0 MB

3.2.1 题面描述 

小杨认为他的幸运数字应该恰好有两种不同的质因子，例如，12=2×2×3的质因子有2，3，恰好为两种不同的质因子，因此12是幸运数字，而30=2×3×5的质因子有2,3,5，不符合要求，不为幸运数字。 

小杨现在有n个正整数，他想知道每个正整数是否是他的幸运数字。 

3.2.2 输入格式 

第一行包含一个正整数n，代表正整数个数。 

之后n行，每行一个正整数。 

3.2.3 输出格式 

输出n行，对于每个正整数，如果是幸运数字，输出1，否则输出0。 

3.2.4 样例1 

3.2.5 样例解释 

7的质因子有7，只有一种。 

12的质因子有2,3，恰好有两种。 ， 

30的质因子有2,3,5，有三种。  

3.2.6 数据范围 

对于全部数据，保证有1≤n≤10⁴，每个正整数a_i满足2≤a_i≤10⁶。