1. 以下哪种情况使用链表比数组更合适?

   {{ select(1) }}

• 数据量固定且读多写少
• 需要频繁在中间或开头插入、删除元素
• 需要高效随机访问元素
• 存储空间必须连续

2. 函数 removeElements 删除单链表中所有结点值等于 $val$ 的结点，并返回新的头结点，其中链表头结点为 $head$ ，则横线处填写( )。

//结点结构体 
struct Node{    
    int val;    
    Node* next;    
    Node(): val(0), next(nullptr){}    
    Node(int x): val(x), next(nullptr){}    
    Node(int x, Node*next): val(x), next(next){} 
};

Node* removeElements(Node* head, int val){    
    Node dummy(0, head);        //哑结点，统一处理头结点    
    Node* cur=&dummy;    
    while(cur->next){        
        if(cur->next->val== val){            
            _______________________        //在此填入代码
        }        
        else{            
            cur= cur->next;        
        }    
    }    
    return dummy.next; 
}

{{ select(2) }}

• Node* del = cur; cur = del->next; delete del;
• Node* del = cur->next; cur->next = del; delete del;
• Node* del = cur->next; cur->next = del->next; delete del;
• Node* del = cur->next; delete del; cur->next = del->next;

3. 函数 hasCycle 采用Floyd快慢指针法判断一个单链表中是否存在环，链表的头节点为 $head$ ，即用两个指针在链表上前进: $slow$ 每次走 1 步， $fast$ 每次走 2 步，若存在环， $fast$ 终会追上 $slow$ (相遇);若无环， $fast$ 会先到达 nullptr，则横线上应填写( )。

struct Node{    
    int val;    
    Node*next;    
    Node(int x): val(x), next(nullptr){} 
};

bool hasCycle(Node*head){    
    if(!head || !head->next)        
        return false;    
    Node* slow= head;    
    Node* fast= head->next;    
    while(fast&& fast->next){        
        if(slow== fast) return true;        
        _______________________        //在此填入代码    
    }    
    return false; 
}

{{ select(3) }}

• slow = slow->next; fast = fast->next->next;
• slow = fast->next; fast = slow->next->next;
• slow = slow->next; fast = slow->next->next;
• slow = fast->next; fast = fast->next->next;

4. 函数 isPerfectNumber 判断一个正整数是否为完全数(该数是否即等于它的真因子之和)，则横线上应填写( )。一个正整数 $n$ 的真因子包括所有小于 $n$ 的正因子，如28的真因子为1， 2， 4， 7， 14。

bool isPerfectNumber(int n){    
    if(n<= 1) return false;    
    int sum= 1;    
    for(int i= 2;______; i++){        
        if(n% i== 0){            
            sum+= i;            
            if(i!= n/i) sum+= n/i;        
        }    
    }    
    return sum== n; 
}

{{ select(4) }}

• i <= n
• i*i <= n
• i <= n/2
• i < n

5. 以下代码计算两个正整数的最大公约数(GCD)，横线上应填写( )。

int gcd0(int a, int b){    
    if(a< b){        
        swap(a, b);    
    }    
    while(b!= 0){        
        int temp= a% b;        
        a= b;        
        b= temp;    
    }    
    return______; 
}

{{ select(5) }}

• b
• a
• temp
• a * b

6. 函数 sieve 实现埃拉托斯特尼筛法(埃氏筛)，横线处应填入( )。

vector<bool> sieve(int n){    
    vector<bool> is_prime(n+1, true);    
    is_prime[0]= is_prime[1]= false;    
    for(int i= 2; i<= n; i++){        
        if(is_prime[i]){            
            for(int j=______; j<= n; j+= i){                
                is_prime[j]= false;            
            }        
        }    
    }    
    return is_prime; 
}

{{ select(6) }}

• i
• i+1
• i*2
• i*i

7. 函数 linearSieve 实现线性筛法(欧拉筛)，横线处应填入( )。

vector<int> linearSieve(int n){    
    vector<bool> is_prime(n+1, true);    
    vector<int> primes;    
    for(int i= 2; i<= n; i++){        
        if(is_prime[i]) primes.push_back(i);        
        for(int p: primes){            
            if(p* i> n) break;            
            is_prime[p* i]= false;            
            if(________) break;        
        }    
    }    
    return primes; 
}

{{ select(7) }}

• i % p == 0
• p % i == 0
• i == p
• i * p == n

8. 关于 埃氏筛 和 线性筛 的比较，下列说法错误的是( )。

   {{ select(8) }}

• 埃氏筛可能会对同一个合数进行多次标记
• 线性筛的理论时间复杂度更优，所以线性筛的速度往往优于埃氏筛
• 线性筛保证每个合数只被其最小质因子筛到一次
• 对于常见范围( $10^7$ )，埃氏筛因实现简单，常数较小，其速度往往优于线性筛

9. 唯一分解定理描述的是( )。

   {{ select(9) }}

• 每个整数都能表示为任意素数的乘积
• 每个大于 1 的整数能唯一分解为素数幂乘积(忽略顺序)
• 合数不能分解为素数乘积
• 素数只有两个因子:1 和自身

10. 给定一个 $n \times n$ 的矩阵 $matrix$ ，矩阵的每一行和每一列都按升序排列。函数 countLE 返回矩阵中第 $k$ 小的元素，则两处横线上应分别填写( )。

//统计矩阵中<= x的元素个数：从左下角开始
int countLE(const vector<vector<int>>& matrix, int x){    
    int n=(int)matrix.size();    
    int i= n- 1, j= 0, cnt= 0;    
    while(i>= 0&& j< n){        
        if(matrix[i][j]<= x){            
            cnt+= i+ 1;            
            ++j;        
        }        
        else{            
            --i;        
        }    
    }    
    return cnt; 
}

int kthSmallest(vector<vector<int>>& matrix, int k){    
    int n=(int)matrix.size();    
    int lo= matrix[0][0];    
    int hi= matrix[n- 1][n- 1];
    while(lo< hi){        
        int mid= lo+(hi- lo)/ 2;        
        if(countLE(matrix, mid)>= k){
            ________________    //在此处填入代码
        } else{
            ________________    //在此处填入代码
        }    
    }    
    return lo; 
}

{{ select(10) }}

• hi = mid - 1; 和 lo = mid + 1;
• hi = mid; 和 lo = mid;
• hi = mid; 和 lo = mid + 1;
• hi = mid + 1; 和 lo = mid;

11. 下述C++代码实现了快速排序算法，下面说法错误的是( )。

int partition(vector<int>& arr, int low, int high){    
    int i= low, j= high;    
    int pivot= arr[low];                //以首元素为基准    
    while(i< j){
        while(i< j&& arr[j]>= pivot) j--;  //从右往左查找        
        while(i< j&& arr[i]<= pivot) i++;  //从左往右查找
        if(i< j) swap(arr[i], arr[j]);    
    }    
    swap(arr[i], arr[low]);                
    return i;                             
}

void quickSort(vector<int>& arr, int low, int high){    
    if(low>= high) return;    
    int p= partition(arr, low, high);    
    quickSort(arr, low, p- 1);    
    quickSort(arr, p+ 1, high); 
}

{{ select(11) }}

• 快速排序之所以叫"快速"，是因为它在平均情况下运行速度较快，常数小、就地排序，实践中通常比归并排序更高效。
• 在平均情况下，划分的递归层数为 $O(\log n)$ ，每层中的总循环数为 $O(n)$ ，总时间为 $O(n \log n)$ 。
• 在最差情况下，每轮划分操作都将长度为 $n$ 的数组划分为长度为 0 和 $n-1$ 的两个子数组，此时递归层数达到 $O(n)$ ，每层中的循环数为 $O(n)$ ，总时间为 $O(n^2)$ 。
• 划分函数 partition 中"从右往左查找"与"从左往右查找"的顺序可以交换。

12. 下述C++代码实现了归并排序算法，则横线上应填写( )。

void merge(vector<int>&nums, int left, int mid, int right){
    //左子数组区间为[left, mid],右子数组区间为[mid+1, right]    
    vector<int> tmp(right- left+ 1);    
    int i= left, j= mid+ 1, k= 0;    
    while(i<= mid&& j<= right){        
        if(nums[i]<= nums[j])            
            tmp[k++]= nums[i++];        
        else            
            tmp[k++]= nums[j++];    
    }    
    while(i<= mid){        
        tmp[k++]= nums[i++];    
    }
    while(________){    //在此处填入代码		
        tmp[k++]= nums[j++];    
    }    
    for(k= 0; k< tmp.size(); k++){        
        nums[left+ k]= tmp[k];    
    } 
}

void mergeSort(vector<int>&nums, int left, int right){    
    if(left>= right)        
        return;	
    int mid=(left+ right)/ 2;    
    mergeSort(nums, left, mid);    
    mergeSort(nums, mid+ 1, right);    
    merge(nums, left, mid, right); 
}

{{ select(12) }}

• i < mid
• j < right
• i <= mid
• j <= right

13. 假设你是一家电影院的排片经理，只有一个放映厅。你有一个电影列表 $movies$ ，其中 movies[i] = [start_i， end_i] 表示第 $i$ 部电影的开始和结束时间。请你找出最多能安排多少部不重叠的电影，则横线上应分别填写的代码为( )。

int maxMovies(vector<vector<int>>& movies){    
    if(movies.empty()) return 0;
    sort(movies.begin(), movies.end(),[](const vector<int>& a, const vector<int>& b){
        return______;//在此处填入代码
    });
    int count= 1;    
    int lastEnd= movies[0][1];
    for(int i= 1; i< movies.size(); i++){        
        if(movies[i][0]>= lastEnd){            
            count++;
            ______= movies[i][1];//在此处填入代码
        }    
    }
    return count; 
}

{{ select(13) }}

• a[0] < b[0] 和 lastEnd
• a[1] < b[1] 和 lastEnd
• a[0] < b[0] 和 movies[i][0]
• a[1] < b[1] 和 movies[i][0]

14. 给定一个整数数组 $nums$ ，下面代码找到一个具有最大和的连续子数组，并返回该最大和。则下面说法错误的是( )。

int crossSum(vector<int>& nums, int left, int mid, int right){    
    int leftSum= INT_MIN, rightSum= INT_MIN;    
    int sum= 0;    
    for(int i= mid; i>= left; i--){        
        sum+= nums[i];        
        leftSum= max(leftSum, sum);    
    }    
    sum= 0;    
    for(int i= mid+ 1; i<= right; i++){        
        sum+= nums[i];        
        rightSum= max(rightSum, sum);    
    }    
    return leftSum+ rightSum; 
}

int helper(vector<int>& nums, int left, int right){    
    if(left== right)        
        return nums[left];    
    int mid= left+(right- left)/ 2;    
    int leftMax= helper(nums, left, mid);    
    int rightMax= helper(nums, mid+ 1, right);    
    int crossMax= crossSum(nums, left, mid, right);    
    return max({leftMax, rightMax, crossMax}); 
}

int maxSubArray(vector<int>& nums){    
    return helper(nums, 0, nums.size()- 1); 
}

{{ select(14) }}

• 上述代码采用分治算法实现
• 上述代码采用贪心算法
• 上述代码时间复杂度为 $O(n \log n)$
• 上述代码采用递归方式实现

15. 给定一个由非负整数组成的数组 $digits$ ，表示一个非负整数的各位数字，其中最高位在数组首位，且 $digits$ 不含前导0(除非是0本身)。下面代码对该整数执行 +1 操作，并返回结果数组，则横线上应填写( )。

vector<int> plusOne(vector<int>& digits){    
    for(int i=(int)digits.size()- 1; i>= 0;--i){        
        if(digits[i]< 9){            
            digits[i]+= 1;            
            return digits;        
        }
        ________________    //在此处填入代码
    }    
    digits.insert(digits.begin(), 1);    
    return digits; 
}

{{ select(15) }}

• digits[i] = 0;
• digits[i] = 9;
• digits[i] = 1;
• digits[i] = 10;