408 真题做题本·数据结构部分

第 1 章绪论

1.1 绪论

【2011】设 $n$ 是描述问题规模的非负整数，下面程序片段的时间复杂度是（）。

C
x = 2;
while (x < n / 2)
    x = 2 * x;

A. $O (lo g_{2} n)$
B. $O (n)$
C. $O (n lo g_{2} n)$
D. $O (n^{2})$

答案： A

解析： 设循环执行了 $t$ 次。初始时 $x = 2$ ，每执行一次循环， $x$ 扩大为原来的 $2$ 倍，因此执行 $t$ 次后

x = 2 \cdot 2^{t} = 2^{t + 1} .

循环结束时应有 $2^{t + 1} \geq \frac{n}{2}$ ，所以

t = Θ (lo g_{2} n) .

循环体内只有常数次基本操作，故程序的时间复杂度为 $O (lo g_{2} n)$ 。

【2012】求整数 $n (n \geq 0)$ 阶乘的算法如下，其时间复杂度是（）。

C
int fact(int n) {
    if (n <= 1) return 1;
    return n * fact(n - 1);
}

A. $O (lo g_{2} n)$
B. $O (n)$
C. $O (n lo g_{2} n)$
D. $O (n^{2})$

答案： B

解析： 当 $n > 1$ 时，函数每次递归都将参数减 $1$ ，直至参数变为 $1$ 。递归调用序列为

n, n - 1, n - 2, \dots, 1,

共进行 $n$ 级左右的调用。每一层除递归调用外只进行常数次判断和乘法，因此递推式可写为

T (n) = T (n - 1) + O (1) .

解得 $T (n) = O (n)$ ，故选 B。该算法的递归栈空间复杂度也为 $O (n)$ ，但本题只问时间复杂度。

【2013】已知两个长度分别为 $m$ 和 $n$ 的升序链表，若将它们合并为一个长度为 $m + n$ 的降序链表，则最坏情况下的时间复杂度是（）。

A. $O (n)$
B. $O (m \times n)$
C. $O (min (m, n))$
D. $O (max (m, n))$

答案： D

解析： 合并时可同时扫描两个升序链表，每次取当前较小的结点，并采用头插法插入新链表。由于取出的元素按升序排列，而头插后顺序恰好反转，因此最终得到降序链表。

在最坏情况下，两个链表中的所有结点都需要被访问和链接一次，时间复杂度为

O (m + n) .

又因为

max (m, n) \leq m + n \leq 2 max (m, n),

所以 $O (m + n) = O (max (m, n))$ 。四个选项中应选 D。

【2014】下列程序段的时间复杂度是（）。

C
count = 0;
for (k = 1; k <= n; k *= 2)
    for (j = 1; j <= n; j++)
        count++;

A. $O (lo g_{2} n)$
B. $O (n)$
C. $O (n lo g_{2} n)$
D. $O (n^{2})$

答案： C

解析： 外层循环中 $k$ 依次取

1, 2, 4, \dots, 2^{t},

当 $2^{t} \leq n < 2^{t + 1}$ 时停止，因此外层循环执行次数为 $⌊ lo g_{2} n ⌋ + 1 = Θ (lo g_{2} n)$ 。

每次外层循环中，内层循环均执行 $n$ 次，所以总基本操作次数为

n (⌊ lo g_{2} n ⌋ + 1) = Θ (n lo g_{2} n) .

故时间复杂度为 $O (n lo g_{2} n)$ 。

【2017】下列函数的时间复杂度是（）。

C
int func(int n) {
    int i = 0, sum = 0;
    while (sum < n) sum += ++i;
    return i;
}

A. $O (lo g_{2} n)$
B. $O (n^{1/2})$
C. $O (n)$
D. $O (n lo g_{2} n)$

答案： B

解析： 循环第 $i$ 次执行后，变量 $s u m$ 的值为

1 + 2 + \dots + i = \frac{i ( i + 1 )}{2} .

循环终止时， $s u m \geq n$ ，即

\frac{i ( i + 1 )}{2} \geq n .

由此可得 $i = Θ (n)$ 。循环体每次只执行常数次操作，所以函数的时间复杂度为

O (n) = O (n^{1/2}) .

【2019】设 $n$ 是描述问题规模的非负整数，下列程序段的时间复杂度是（）。

C
x = 0;
while (n >= (x + 1) * (x + 1))
    x = x + 1;

A. $O (lo g_{2} n)$
B. $O (n^{1/2})$
C. $O (n)$
D. $O (n^{2})$

答案： B

解析： 循环条件等价于

(x + 1)^{2} \leq n .

变量 $x$ 从 $0$ 开始，每次增加 $1$ 。循环执行次数约为 $⌊ n ⌋$ ，因此基本操作次数与 $n$ 同阶，即

T (n) = Θ (n) .

故时间复杂度为 $O (n^{1/2})$ 。

【2022】下列程序段的时间复杂度是（）。

C
int sum = 0;
for (int i = 1; i < n; i *= 2)
    for (int j = 0; j < i; j++)
        sum++;

A. $O (lo g_{2} n)$
B. $O (n)$
C. $O (n lo g_{2} n)$
D. $O (n^{2})$

答案： B

解析： 外层循环中， $i$ 依次取 $1, 2, 4, \dots, 2^{k}$ ，其中 $2^{k} < n \leq 2^{k + 1}$ 。第 $r$ 次外层循环中，内层循环执行 $2^{r}$ 次，因此总执行次数为等比数列之和

1 + 2 + 4 + \dots + 2^{k} = 2^{k + 1} - 1.

由 $2^{k} < n \leq 2^{k + 1}$ 可知，该和为 $Θ (n)$ 。因此程序的时间复杂度为 $O (n)$ ，而不是把“外层 $O (lo g n)$ ”与“最大内层 $O (n)$ ”直接相乘得到 $O (n lo g n)$ 。

【2023】下列对顺序存储的有序表（长度为 $n$ ）实现给定操作的算法中，平均时间复杂度为 $O (1)$ 的是（）。

A. 查找包含指定值元素的算法
B. 插入包含指定值元素的算法
C. 删除第 $i (1 \leq i \leq n)$ 个元素的算法
D. 获取第 $i (1 \leq i \leq n)$ 个元素的算法

答案： D

解析： 顺序表中的元素存放在一段连续的存储空间中。若首元素地址为 $L O C (a_{1})$ ，每个元素占用 $L$ 个存储单元，则第 $i$ 个元素的地址为

L O C (a_{i}) = L O C (a_{1}) + (i - 1) L .

因此，只要给出合法下标 $i$ ，便可通过地址计算直接访问第 $i$ 个元素，时间复杂度为 $O (1)$ 。

其余选项中：有序顺序表按值查找即使采用折半查找也需 $O (lo g_{2} n)$ ；插入元素通常需要移动后续元素，平均为 $O (n)$ ；删除第 $i$ 个元素也通常需要前移其后的元素，平均为 $O (n)$ 。故选 D。

第 1 章 绪论​

1.1 绪论​

第 1 章绪论

1.1 绪论