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

1、以下关于链表和数组的描述错误的是（ ）。 {{ select(1) }}

• 数组支持随机访问，链表只能顺序访问
• 链表插入和删除元素效率高于数组
• 数组的大小在声明时固定，链表的大小可动态调整
• 链表可以通过指针直接访问任意节点

2、在双向循环链表中，若要在结点 p 之后插入结点 s，正确的操作是（ ）。 {{ select(2) }}

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

3、下面代码中 factorial 函数的时间复杂度是（ ）。

int factorial(int n) {
    if (n == 1) return 1;
    return n * factorial(n - 1);
}

{{ select(3) }}

• O(1)
• O(n)
• O(n²)
• O(log n)

4、使用埃拉托斯特尼筛法筛选小于等于 n 的素数，时间复杂度为（ ）。 {{ select(4) }}

• O(n log log n)
• O(n)
• O(n²)
• O(n√n)

5、以下关于递归和迭代的说法正确的是（ ）。 {{ select(5) }}

• 递归一定比迭代效率高
• 迭代无法实现递归的功能
• 递归可能导致栈溢出
• 迭代需要更多的内存空间

6、归并排序算法的时间复杂度是（ ）。 {{ select(6) }}

• O(n)
• O(n log n)
• O(n²)
• O(log n)

7、以下代码实现素数筛法，横线处应填入（ ）。

void sieve(int n) {
    bool isPrime[n + 1];
    memset(isPrime, true, sizeof(isPrime));
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i * i <= n; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }
}

{{ select(7) }}

• 埃氏筛法
• 线性筛法
• 欧拉筛法
• 以上都不对

8、以下关于贪心算法的描述错误的是（ ）。 {{ select(8) }}

• 贪心算法总能得到全局最优解
• 贪心算法通常用于求解最优子结构问题
• 贪心算法的核心是局部最优选择
• 贪心算法的时间复杂度通常较低

9、以下代码实现的排序算法是（ ）。

void sort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
            }
        }
    }
}

{{ select(9) }}

• 冒泡排序
• 插入排序
• 选择排序
• 快速排序

10、以下关于高精度运算的说法正确的是（ ）。 {{ select(10) }}

• 高精度加法需要处理进位
• 高精度乘法只能用递归实现
• 高精度除法无法处理余数
• 高精度运算的时间复杂度与普通运算相同

11、以下关于递归函数调用的说法正确的是（ ）。 {{ select(11) }}

• 递归深度过大会导致栈溢出
• 递归函数必须有返回值
• 递归函数的参数必须是整数
• 递归函数无法转换为迭代实现

12、以下代码实现的算法是（ ）。

int binarySearch(int arr[], int left, int right, int target) {
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

{{ select(12) }}

• 二分查找
• 线性查找
• 插值查找
• 斐波那契查找

13、以下关于分治算法的描述错误的是（ ）。 {{ select(13) }}

• 分治算法将问题分解为子问题递归求解
• 归并排序是分治算法的典型应用
• 分治算法的时间复杂度一定优于其他算法
• 分治算法需要合并子问题的解

14、以下关于链表的说法正确的是（ ）。 {{ select(14) }}

• 单链表可以直接访问尾节点
• 循环链表的头节点和尾节点相连
• 双向链表只能顺序遍历
• 链表的存储空间是连续的

15、以下关于算法复杂度的说法正确的是（ ）。 {{ select(15) }}

• 时间复杂度和空间复杂度成正比
• 算法的最优时间复杂度是最坏情况下的表现
• 大O表示法描述的是算法的渐进复杂度
• 空间复杂度为O(1)的算法一定比O(n)的算法优

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

1、递归函数的时间复杂度一定高于迭代实现。 {{ select(16) }}

• 对
• 错

2、埃氏筛法的时间复杂度低于线性筛法。 {{ select(17) }}

• 对
• 错

3、快速排序是一种稳定的排序算法。 {{ select(18) }}

• 对
• 错

4、链表的插入和删除操作不需要移动元素。 {{ select(19) }}

• 对
• 错

5、贪心算法在某些情况下可能无法得到最优解。 {{ select(20) }}

• 对
• 错

6、归并排序的空间复杂度为O(n)。 {{ select(21) }}

• 对
• 错

7、二分查找只能在有序数组中使用。 {{ select(22) }}

• 对
• 错

8、高精度加法需要处理进位，而减法不需要。 {{ select(23) }}

• 对
• 错

9、递归函数的调用深度受系统栈空间限制。 {{ select(24) }}

• 对
• 错

10、分治算法的时间复杂度通常为O(n log n)。 {{ select(25) }}

• 对
• 错