二、判断题

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

• 对
• 错

第 2 题 若数组 a 已按升序排列,则下面代码可以正确实现 “在 a 中查找第一个大于等于 x 的元素的位置”｡（ ） {{ select(2) }}

• 对
• 错

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;
}

第 3 题 快速排序只要每次都选取中间元素作为枢轴,就一定是稳定排序｡（ ） {{ select(3) }}

• 对
• 错

第 4 题 若某算法满足递推式: $T(n)=2 T(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] 内的逆序对总数｡（ ） {{ select(5) }}

• 对
• 错

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++;
        }
    }
}

第 6 题 根据唯一分解定理,如果大于1的整数不能被任何不超其平方根的质数整除,那么n 必定是质数｡（ ） {{ select(6) }}

• 对
• 错

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

• 对
• 错

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;
}

第 8 题 若一个问题满足最优子结构性质,则一定可以用贪心算法得到最优解。（ ） {{ select(8) }}

• 对
• 错

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

• 对
• 错

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

• 对
• 错