第一章绪论¶

答案速对¶

序号	题号	答案
1	2011-01	A
2	2012-01	B
3	2013-01	D
4	2014-01	C
5	2017-01	B
6	2019-01	B
7	2022-01	B
8	2023-01	D

(一) 数据结构的基本概念¶

(二) 算法的基本概念¶

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

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

A.\( O(log⁡n) \)\( B. \)\( O(n) \)\( C. \)\( O(nlog⁡n) \)\( D. \)\( O(n^2) \)

解析

答案：A

这段程序的基本操作是循环体中的 x = 2 * x。变量 x 的初值为 2，每执行一次循环，x 都扩大为原来的 2 倍。

执行过程为：

循环结束时，x 第一次不再满足，因此可近似写成

两边取以 2 为底的对数：

所以循环次数与同阶，因此时间复杂度为。

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

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

A.\( O(log⁡n) \)\( B. \)\( O(n) \)\( C. \)\( O(nlog⁡n) \)\( D. \)\( O(n^2) \)

解析

答案：B

当时，函数每次递归都把问题规模从减少为：

从递减到 1，一共需要大约次递归调用。每层递归只进行一次条件判断、一次乘法以及一次函数调用，这些操作都按常数时间计算。设运行时间为，可列递推式：

逐层展开：

因此时间复杂度为。此外，递归调用栈的深度也是级，所以该算法的辅助空间复杂度为

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

A. O(n)

B. O(mn)

C. O(min(m,n))

D. O(max(m,n))

解析

案：D

可以同时设置两个指针，分别指向两个升序链表当前尚未处理的首结点。每次比较这两个结点：

取出关键字较小的结点；
将该结点用头插法插入结果链表；
对应链表的指针向后移动一次；
某一链表处理完后，再把另一链表的剩余结点依次头插到结果链表中。

被取出的结点按升序出现，而头插法会把次序反转，因此最终结果是降序链表。

在整个合并过程中，每个结点最多被访问和移动一次。两个链表共有个结点，所以最坏情况下

选项中没有直接给出。注意：

由于常数 2 在渐进复杂度中可以忽略，因此

故应选择。不能选，因为即使较短的链表已经处理完，较长链表中的剩余结点仍然需要接入结果链表。

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

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

A.\( O(log⁡n) \)\( B. \)\( O(n) \)\( C. \)\( O(nlog⁡n) \)\( D. \)\( O(n^2) \)

解析

答案：C

先看外层循环。k 依次取值

外层循环继续执行需满足，所以

因此，外层循环共执行次，时间规模为。

每执行一次外层循环，内层循环中的 j 都从 1 递增到，所以内层循环固定执行次，时间规模为。

总执行次数为

故

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

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

A.\( O(log⁡n) \)\( B. \)\( O(n^{1/2}) \)\( C. \)\( O(n) \)\( D. \)\( O(nlogn) \)

解析

答案：B

循环体 sum += ++i 会先把 i 增加 1，再把新的 i 加入 sum。各轮结束后的状态如下：

循环停止时，sum 第一次达到或超过，因此满足

解对应的一元二次方程：

得到正根

取满足条件的最小整数时需要向上取整，但向上取整不影响数量级。由于

所以循环次数为，时间复杂度为。

易错点是把 sum 每次增加看成固定值。实际上，sum 每轮增加的数依次为，增长速度越来越快，因此不需要执行次循环。

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

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

A.\( O(log⁡_{10}n) \)\( B. \)\( O(n^{1/2}) \)\( C. \)\( O(n) \)\( D. \)\( O(n^2) \)

解析

答案：B

x 从 0 开始，每轮只增加 1。循环能够执行的条件是

当循环执行第次时，执行前有，此时条件变为

因此可以执行的最大轮数为

也就是说，循环体大约执行次。循环中的加法、乘法、比较和赋值均按常数时间计算，所以

虽然判断条件中出现了平方，但这不意味着复杂度是；应该根据循环变量达到退出条件所需的执行次数来判断。

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

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

A.\( O(log⁡n) \)\( B. \)\( O(n) \)\( C. \)\( O(nlogn) \)\( D. \)\( O(n^2) \)

解析

答案：B

外层循环中，i 依次取

其中最后一个值。表面上看，外层循环执行次，但内层循环的执行次数不是固定的，而是当前的 i。

因此各轮内层循环的执行次数依次为

总执行次数是一个等比数列之和：

由于，可知这个和与同阶。更具体地说，对整数，有

于是程序的时间复杂度为。

本题不能直接把“外层 ”与“内层最大 ”相乘得到，因为只有最后几轮的内层循环接近次；正确方法是把每轮的实际执行次数相加。

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

A. 查找包含指定值的元素的位置

B. 插入包含指定值元素的算法

C. 删除第 i (1≤i≤n) 个元素的算法

D. 获取第 i (1≤i≤n) 个元素的算法

解析

答案：D

顺序存储结构使用一段连续的存储空间。若首元素地址为，每个元素占用个存储单元，则第个元素的地址可直接计算：

这个地址计算只需要固定次数的算术运算，因此无论是多少，获取第个元素都只需常数时间，即。

逐项分析如下：

A. 有序表可使用二分查找，每次把查找区间缩小一半,平均时间复杂度

B.即使先用二分查找确定位置，插入时仍需平均移动约一半元素,平均时间复杂度

C.删除第个元素后，需要把其后的元素依次前移，平均移动约一半元素,平均时间复杂度

D.根据首地址、下标和元素长度直接计算目标地址,根据首地址、下标和元素长度直接计算目标地址

因此，平均时间复杂度为的操作是“获取第个元素”。这也是顺序表具有随机存取特性的体现。