2025.06 DC5月测 - 题目详情 - 信创计划

ID: 1817

客观题

难度: 7

上传者:

管理员 (admin)

冒泡排序在最好情况（数组已升序）的时间复杂度是：
{{ select(1) }}

$\boldsymbol{O(n^2)}$
$\boldsymbol{O(n)}$
$\boldsymbol{O(n\log n)}$
$\boldsymbol{O(\log n)}$

以下排序算法中，不稳定的是：
{{ select(2) }}

冒泡排序
选择排序
插入排序
计数排序

插入排序效率最优的场景是：
{{ select(3) }}

数组完全逆序
数组基本有序
数组元素随机
数组元素全相同

选择排序的第 $i$ 轮（从0开始）操作是：
{{ select(4) }}

第 $i$ 个元素与后面所有元素比较并交换
找到 $i\sim n-1$ 中最小元素，与第 $i$ 个交换
第 $i$ 个元素插入到前面已排序部分
相邻元素交换

以下排序算法中，时间复杂度不可能达到 $\boldsymbol{O(n)}$ 的是： {{ select(5) }}

插入排序（最好情况）
冒泡排序（最好情况）
选择排序（始终 $\boldsymbol{O(n^2)}$ ）
计数排序（ $\boldsymbol{O(n+k)}$ ）

已知一维前缀和数组 $\text{sum}$ （ $\text{sum}[0]=0$ ， $\text{sum}[i] = a[1]+\dots+a[i]$ ），区间 $\{[L, R]}$ 的和为：
{{ select(6) }}

${\text{sum}[R] - \text{sum}[L-1]}$
$\text{sum}[R+1] - \text{sum}[L]$
$\text{sum}[R] - \text{sum}[L]$
$\text{sum}[R+1] - \text{sum}[L-1]$

对一维数组做 区间 $\boldsymbol{[L, R]}$ 加 $v$ 操作，差分数组 $\text{diff}$ 的正确修改是：
{{ select(7) }}

$\text{diff}[L] += v$ ； $\text{diff}[R] -= v$
${\text{diff}[L] += v}$ ； ${\text{diff}[R+1] -= v}$
$\text{diff}[L-1] += v$ ； $\text{diff}[R] -= v$
$\text{diff}[L-1] += v$ ； $\text{diff}[R+1] -= v$

二维前缀和 $\text{sum}[i][j]$ 表示 $(1,1)\sim(i,j)$ 的矩形和，子矩阵 ${(L1,R1)\sim(L2,R2)}$ 的和为：
{{ select(8) }}

${\text{sum}[L2][R2] - \text{sum}[L1-1][R2] - \text{sum}[L2][R1-1] + \text{sum}[L1-1][R1-1]}$
$\text{sum}[L2][R2] - \text{sum}[L1][R2] - \text{sum}[L2][R1] + \text{sum}[L1][R1]$
$\text{sum}[L2+1][R2+1] - \text{sum}[L1][R2+1] - \text{sum}[L2+1][R1] + \text{sum}[L1][R1]$
直接遍历求和

二维数组做 子矩阵 $\boldsymbol{(L1,R1)\sim(L2,R2)}$ 加 $v$ 操作，差分数组 $\text{diff}$ 的正确修改是：
{{ select(9) }}

$\boldsymbol{\text{diff}[L1][R1] += v}$ ； $\boldsymbol{\text{diff}[L1][R2+1] -= v}$ ； $\boldsymbol{\text{diff}[L2+1][R1] -= v}$ ； $\boldsymbol{\text{diff}[L2+1][R2+1] += v}$
$\text{diff}[L1][R1] += v$ ； $\text{diff}[L2][R2] -= v$
$\text{diff}[L1-1][R1-1] += v$ ； $\text{diff}[L2+1][R2+1] -= v$
遍历子矩阵修改

一维差分数组 $\text{diff}$ 与原数组 $a$ 的关系是：
{{ select(10) }}

${\text{diff的前缀和是原数组}}$ （ $\text{a}[i] = \text{diff}[1]+\dots+\text{diff}[i]$ ）
原数组的前缀和是差分数组
两者无关
差分是前缀和的逆操作

在下列比赛中:

DC5级班 2025.06 月测