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

第 1 题 有一个存储了 $n$ 个整数的线性表，分别用数组和单链表两种方式实现。在已知下标（或结点指针）的前提下，数组的随机访问是 $O(1)$，而在链表中已知某结点的指针时，在该结点之后插入一个新结点的操作也是 $O(1)$。

{{ select(1) }}

• 正确
• 错误

---

第 2 题 若数组 a 已按升序排列，则下面代码可以正确实现 "在 a 中查找第一个大于等于 x 的元素的位置"。

int lowerBound(vector<int>& a,int x){
    int l=0, r=a.size();
    while(l < r) {
        int mid = (l + r) / 2;
        if( a[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return l;
}

{{ select(2) }}

• 正确
• 错误

---

第 3 题 快速排序只要每次都选取中间元素作为枢轴，就一定是稳定排序。

{{ select(3) }}

• 正确
• 错误

---

第 4 题 若某算法满足递推式：$T(n) = 2T(n/2) + O(n)$，则其时间复杂度为 $O(n \log n)$。

{{ select(4) }}

• 正确
• 错误

---

第 5 题 在一个数组中，如果两个元素 a[i] 和 a[j] 满足 i < j 且 a[i] > a[j]，则 a[i] 和 a[j] 是一个逆序对。

下面代码可以正确统计数组 a 区间 [l,r] 内的逆序对总数。

long long cnt=0;
void merge_count(vector<int>& a, int l, int m, int r){
    int i = l, j = m + 1;
    while(i <= m && j <= r) {
        if(a[i] <= a[j]) i++;
        else {
            cnt += (m - i+ 1);
            j++;
        }
    }
}

{{ select(5) }}

• 正确
• 错误

---

第 6 题 唯一分解定理保证：若一个数未被任何不超过其平方根的质数筛去，则它一定是质数。

{{ select(6) }}

• 正确
• 错误

---

第 7 题 假设数组 $a$ 的值域范围是 $D$，以下程序的时间复杂度是 $O(n \log n + n \log D)$。

bool check(int n, int a[], int k, int dist) {
    int cnt = 1;
    int last = a[0];
    
    for (int i = 1; i < n; i++) {
        if (a[i] - last >= dist) {
            cnt++;
            last = a[i];
        }
    }
    
    return cnt >= k;
}

int solve(int n, int a[], int k) {
    std::sort(a, a + n);
    
    int l = 0;
    int r = a[n - 1] - a[0];
    
    while (l < r) {
        int mid = (l + r + 1) / 2;
        
        if (check(n, a, k, mid))
            l = mid;
        else
            r = mid - 1;
    }
    
    return l;
}

int main() {
    int a[] = {1, 2, 8, 4, 9};
    int n = 5;
    int k = 3;
    
    std::cout << solve(n, a, k) << std::endl;
    
    return 0;
}

{{ select(7) }}

• 正确
• 错误

---

第 8 题 若一个问题满足最优子结构性质，则一定可以用贪心算法得到最优解。

{{ select(8) }}

• 正确
• 错误

---

第 9 题 线性筛相比埃氏筛的核心改进在于：埃氏筛中一个合数可能被多个质数重复标记，线性筛通过"每个合数只被其最大质因子筛去"的策略，保证每个合数恰好被标记一次，从而实现 $O(n)$ 的时间复杂度。

{{ select(9) }}

• 正确
• 错误

---

第 10 题 任何递归程序都可以改写为等价的非递归程序，但改写后的非递归程序一定需要显式地使用栈来模拟递归调用过程。

{{ select(10) }}

• 正确
• 错误

---