第 1 题

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

{{ select(1) }}

• 正确
• 错误

---

第 2 题

若数组a已按升序排列，则下面代码可以正确实现“在a中查找第一个大于等于x的元素的位置”。 [cite: 2140]

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 题

快速排序只要每次都选取中间元素作为枢轴，就一定是稳定排序。 [cite: 2152]

{{ select(3) }}

• 正确
• 错误

---

第 4 题

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

{{ select(4) }}

• 正确
• 错误

---

第 5 题

在一个数组中，如果两个元素 a[i]和a[j]满足 $i<j$ 且 $a[i]>a[j]$，则a[i]和a[j]是一个逆序对。下面代码可以正确统计数组a区间 [l,r] 内的逆序对总数。 [cite: 2154, 2156]

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 题

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

{{ select(6) }}

• 正确
• 错误

---

第 7 题

假设数组的值域范围是D，以下程序的时间复杂度是 $O(n \log n + n \log D)$。 [cite: 2175]

// std::sort(a, a + n);
// l = 0, r = a[n-1] - a[0];
// while(l < r) { ... check() ... }

{{ select(7) }}

• 正确
• 错误

---

第 8 题

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

{{ select(8) }}

• 正确
• 错误

---

第 9 题

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

{{ select(9) }}

• 正确
• 错误

---

第 10 题

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

{{ select(10) }}

• 正确
• 错误

---