选择题（每题3分，共10题，总分30分）

1. 下面关于链表和数组的描述，错误的是（ ）。

• A. 数组大小固定，链表大小可动态调整。
• B. 数组支持随机访问，链表只能顺序访问。
• C. 存储相同数目的整数，数组比链表所需的内存多。
• D. 数组插入和删除元素效率低，链表插入和删除元素效率高。

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

• A. p->next->prev = s; s->prev = p; p->next = s; s->next = p->next;
• B. p->next->prev = s; p->next = s; s->prev = p; s->next = p->next;
• C. s->prev = p; s->next = p->next; p->next = s; p->next->prev = s;
• D. 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;
}

• A. sumA体现了迭代的思想。
• B. SumB采用的是递归方式。
• C. SumB函数比SumA的时间效率更高。
• D. 两个函数的实现的功能相同。

5. 有如下函数 fun ，则 fun(20, 12) 的返回值为（ ）。

int fun(int a, int b) {
        if (a % b == 0)
return b;
else
return fun(b, a % b);
}
A. 20
B. 12
C. 4
D. 2

7. 下述代码实现素数表的埃拉托斯特尼筛法，筛选出所有小于等于 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;
}
A. for (int j = i; j <= n; j++)
B. for (int j = i * i; j <= n; j++)
C. for (int j = i * i; j <= n; j += i)
D. for (int j = i; j <= n; j += i)
 

8. 在循环单链表中，节点的 next 指针指向下一个节点，最后一个节点的 next 指针指向（ ）。 A. 当前节点 B. nullptr C. 第一个节点 D. 上一个节点

9. 对下面两个函数，说法错误的是？ ( )

int fibA(int n) {
  if (n <= 1) return n;
  int f1 = 0, f2 = 1;
  for (int i = 2; i <= n; ++i) {
    int temp = f2;
    f2 = f1 + f2;
    f1 = temp;
  }
  return f2;
}
int fibB(int n) {
  if (n <= 1) return n;
  return fibB(n - 1) + fibB(n - 2);
}

A. 两个函数的实现的功能相同。 B. fibA采用递推方式。 C. fibB采用的是递归方式。 D. fibA时间复杂度为 O(n)，fibB的时间复杂度为O($n^2$)

10. 下述代码实现素数表的线性筛法，筛选出所有小于等于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);
  for (int j = 0; j < primes.size() && i * primes[j] <= n; j++) {
    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;

A. 线性筛的时间复杂度是O(n)。 B. 每个合数会被其所有的质因子标记一次。 C. 线性筛和埃拉托色尼筛的实现思路完全相同。 D. 以上都不对