数据结构摘星题库800题笔记 第1章绪论

第1章绪论

§1.1 数据结构的概念

考点 1 数据结构基础概念

题组闯关

1.在设计存储结构时，通常不仅要存储各数据元素的值，而且还要存储 ( )。
A. 数据的处理方法
B. 数据元素的类型
C. 数据元素之间的关系
D. 数据的存储方法

1.参考答案：C
解析：数据结构是带有结构特性的数据元素的集合，它研究的是数据的逻辑结构和数据的物理结构以及它们之间的相互关系，并对这种结构定义相适应的运算设计出相应的算法，即不仅要存储各数据元素的值，还要存储数据元素之间的关系。

2.数据结构是具有 ( ) 的数据元素的集合。
A. 性质相同
B. 特定关系
C. 相同运算
D. 数据项

2.参考答案：B
解析：数据结构是相互之间存在一种或多种特定关系的数据元素的集合，选 B。

3.在数据结构中，按存储结构可把数据结构分为 ( )。
A. 静态结构和动态结构
B. 线性结构和非线性结构
C. 顺序结构和链式结构
D. 内部结构和外部结构

3.参考答案：C
解析：数据结构按存储结构分为顺序结构和链式结构，按逻辑结构分为线性结构和非线性结构。

4.数据结构是研究数据的 ( ) 以及它们之间的相互关系。
A. 理想结构，物理结构
B. 理想结构，抽象结构
C. 物理结构，逻辑结构
D. 抽象结构，逻辑结构

4.参考答案：C
解析：本题是概念题。数据结构包含三个方面的内容：逻辑结构、存储结构和数据的运算。

5.( ) 是数据的最小单位。
A. 数据元素
B. 数据项
C. 数据对象
D. 数据结构

5.参考答案：B
解析：数据项：一个数据可以由若干个数据项组成。数据项是数据不可分割的最小单位。

6.在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 ( )。
A. 数据的处理方法
B. 数据元素的类型
C. 数据元素间的关系
D. 数据的存储方法

6.参考答案：C
解析：数据结构的实质就是相互存在各种特定关系的数据元素的集合。存储数据时，通常不仅要存储数据元素的值，还要存储元素之间的关系。

真题实战

1.下列关于数据结构的说法中错误的是 ( )。 【北京工业大学 2016 年】
A. 数据结构相同，对应的存储结构也相同
B. 数据结构涉及数据的逻辑结构、存储结构和施加在其上的操作
C. 数据结构操作的实现与存储结构有关
D. 定义逻辑结构时可以不考虑存储结构

1.参考答案：A
解析：相同的逻辑结构可以用不同的存储结构实现。一般来说，在不同的存储结构下基本操作的实现是不同的，例如线性表可以顺序存储，也可以链式存储，在顺序存储和链接存储结构下插入操作的实现截然不同。

2.与数据元素本身的形式、相对位置和个数无关的是 ( )。 【广东工业大学 2019 年】
A. 数据存储结构
B. 数据逻辑结构
C. 算法
D. 操作

2.参考答案：B
解析：所谓数据的逻辑结构，是指反映数据元素之间逻辑关系的数据结构；所谓数据的存储结构，是指数据的逻辑结构在计算机存储空间中的存放形式，与数据元素全身的形式、内容、相对位置、个数有关，逻辑结构与物理存储无关，所以答案选 B。

3.以下数据结构中元素之间为非线性关系的是 ( )。 【武汉大学 2015 年】
A. 栈
B. 队列
C. 线性表
D. 以上都不是

3.参考答案：D
解析：栈和队列是受限的线性表，也是线性关系。

4.下列说法中，不正确的是 ( )。 【扬州大学 2017 年】
A. 数据元素是数据的基本单位
B. 数据项是数据元素中不可分割的最小可标识单位
C. 数据可由若干个数据元素构成
D. 数据项可由若干个数据元素构成

4.参考答案：D
解析：数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行处理。一个数据元素可以由若干个数据项组成。数据项是数据的不可分割的最小单位。数据元素也称节点、定点、元素、记录。

5.数据结构的定义为（D,S），其中 D 是 ( ) 的集合。 【中国石油大学 2015 年】
A. 算法
B. 数据元素
C. 数据操作
D. 逻辑结构

5.参考答案：B
解析：D 是数据元素的有限集，S 是 D 上关系的有限集。

考点 2 数据结构的逻辑结构

题组闯关

1.在数据结构中，与所使用的计算机无关的是 ( )。
A. 逻辑结构
B. 存储结构
C. 逻辑结构和存储结构
D. 物理结构

1.参考答案：A
解析：数据的逻辑结构只抽象地反映数据元素之间的逻辑关系，而不管它在计算机中的存储表示形式。

2.数据的逻辑结构是 ( ) 关系的整体。
A. 数据元素之间逻辑
B. 数据项之间逻辑
C. 数据类型之间
D. 存储结构之间

2.参考答案：A
解析：一个数据结构应包含两方面的信息：一是表示数据元素的信息，二是表示各数据元素之间的前后关系。其中数据元素之间的前后关系是指数据元素的逻辑关系，而与它们在计算机中的存储位置无关。

3.下列术语中，( ) 与数据的存储结构无关。
A. 循环队列
B. 堆栈
C. 散列表
D. 单链表

3.参考答案：B
解析：数据的存储结构有顺序存储、链式存储、索引存储和散列存储。栈是一种抽象数据类型，可采用顺序存储或链式存储，是一种逻辑结构。循环队列是用顺序表表示的队列，是一种数据结构。散列表和单链表表示一种数据结构，既描述逻辑结构，又描述存储结构。

4.( ) 不属于数据的线性逻辑结构。
A. 串
B. 栈
C. 二叉树
D. 队列

4.参考答案：C
解析：线性结构的定义：如果一个非空的数据结构满足下列两个条件：(1) 有且只有一个根节点；(2) 每一个节点最多有一个前驱，也最多有一个后继。那就可以说这个数据结构是线性结构。
线性表：线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其他数据元素都是首尾相接的（注意，这句话只适用于大部分线性表，而不是全部。比如，循环链表逻辑层次上也是一种线性表，它在存储层次上属于链式存储，但是把最后一个数据元素的尾指针指向了首位节点。
队列：就和排队一样，晚来的站后面，所以前面最多一个，后面最多一个。
二叉树：分为根节点、左子树、右子树，所以后继可能有两个。
栈：栈是一种特殊的线性结构，里面的方法也是上面最多一个，下面最多一个。
综上所述：根据线性结构和二叉树的定义可以知道：二叉树不是线性结构。

5.数组的逻辑结构不同于 ( ) 的逻辑结构。
A. 线性表
B. 栈
C. 队列
D. 树

5.参考答案：D
解析：数组属于线性结构，A、B、C 各项也都属于线性结构，而 D 项的树属于非线性结构。

6.下列属于线性结构的是 ( )。
A. 线性表
B. 树
C. 查找
D. 图

6.参考答案：A
解析：树具有以下的特点：(1) 每个节点有零个或多个子节点；(2) 没有父节点的节点称为根节点；(3) 每一个非根节点有且只有一个父节点；(4) 除了根节点外，每个子节点可以分为多个不相交的子树。
查找表分为：(1) 静态查找表。①以顺序表或线性链表表示静态查找表，则查找可用顺序查找来实现；②以有序表（排好顺序的顺序表）表示静态查找表，则查找可用折半查找（二分查找）来实现。(2) 动态查找表。(3) 哈希表。每种查找表有不同的特点。
图：图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成的，通常表示为：G (V, E)，其中，G 表示一个图，V 是图 G 中顶点的集合，E 是图 G 中边的集合。
线性结构有：顺序表、单链表、栈、队列、串、广义数组、循环链表和双向链表。非线性结构有：树、二叉树、图、Set、Map、字典、散列表。

真题实战

以下属于逻辑结构的是 ( )。 【南京邮电大学 2016 年】
A. 顺序表
B. 哈希表
C. 有序表
D. 单链表

参考答案：C
解析：A、B、D 三项属于物理结构，题目问的是逻辑结构，逻辑结构包括线性和非线性两种，有序表中的 “有序” 是逻辑意义上的有序，指表中的元素按某种规则已经排好了位置。故选 C。

考点 3 数据结构的物理结构

题组闯关

1.以下关于链式存储结构的叙述中，( ) 是不正确的。
A. 节点除自身信息外还包括指针域，因此存储密度小于顺序存储结构
B. 逻辑上相邻的节点物理上不必相邻
C. 可以通过计算直接确定第 i 个节点的存储地址
D. 插入、删除运算操作方便，不必移动节点

1.参考答案：C
解析：选项 C 错误的原因是链式存储结构的地址不一定是连续的，所以不能通过计算直接确定第 i 个节点的存储地址。

2.数据采用链式存储结构存储，要求 ( )。
A. 每个节点占用一片连续的存储区域
B. 所有节点占用一片连续的存储区域
C. 节点的最后一个数据域是指针类型
D. 每个节点有多少个后继，就设多少个指针域

2.参考答案：A
解析：链式存储结构不需要所有节点占用一片连续的存储区域，节点之间用指针相链接。顺序存储才是需要所有节点都有一片连续的存储区域的。但是无论是顺序存储还是链式存储，每个节点都要占用一片连续的存储区域。

3.在计算机的存储器中表示数据时，物理地址和逻辑地址的相对位置相同并且是连续的，称之为 ( )。
A. 逻辑结构
B. 顺序存储结构
C. 链式存储结构
D. 以上都对

3.参考答案：B
解析：顺序存储结构是存储结构类型中的一种，该结构是把逻辑上相邻的节点存储在物理位置上相邻的存储单元中，节点之间的逻辑关系由存储单元的邻接关系来体现；同时所有的节点元素存放在一块连续的存储区域中。

4.在数据结构中，用计算关键字来确定其存储位置的数据结构是 ( )。
A. Hash 表
B. 二叉搜索树
C. 链式结构
D. 顺序结构

4.参考答案：A
解析：散列存储方式又称 hash 存储。散列存储方式是根据节点的关键字直接计算出该节点的存储地址的一种存储方式。

5.若节点的存储地址是其关键字的某个函数，则称这种存储结构为 ( )。
A. 顺序存储结构
B. 链式存储结构
C. 索引存储结构
D. 散列存储结构

5.参考答案：D
解析：若节点的存储地址与其关键字存在某种映射关系，即为函数关系，则称这种存储结构为散列存储结构。

6.以下哪一组都是物理结构 ( )。
A. 线性表、二叉树
B. 集合、图
C. 单链表、散列表
D. 线性表、散列表

6.参考答案：C
解析：数据的存储结构有：顺序存储、链式存储、索引存储、散列存储。单链表是链式存储，散列表是散列存储。

7.链式存储结构中，每个数据的存储节点里 ( ) 指向邻接存储节点的指针，用以反映数据间的逻辑关系。
A. 只能有 1 个
B. 只能有 2 个
C. 只能有 3 个
D. 可以有多个

7.参考答案：D
解析：本题考查数据结构中常用的物理存储方法 —— 链式存储方法。在链式存储中，节点间的逻辑关系是由附加的指针表示。而数据的逻辑关系包括线性和非线性，线性指数据间存在一对一的关系，非线性指数据间存在一对多的关系，所以本题选 D。

真题实战

1.在线性表的存储结构中，() 查找（按关键字查找）、插入、删除速度慢，但顺序存取和随机存取第 i 个元素速度快；() 查找和存取速度快，但插入、删除速度慢；( ) 查找、插入和删除速度快，但不能进行顺序存取；( ) 插入、删除和顺序存取速度快，但查找速度慢。 【昆明理工大学 2016 年】
A. 散列表，顺序有序表，顺序表，链接表
B. 顺序表，顺序有序表，散列表，链接表
C. 链接表，顺序有序表，散列表，顺序表
D. 顺序有序表，顺序表，链接表，散列表

1.参考答案：B
解析：顺序表按照下标查找速度快，但是按照关键词查找需要依次访问，所以速度慢，插入和删除元素需要移动元素，所以速度慢。链接表查找需要从头到尾依次查找，速度比较慢，但是插入和删除元素时，只需要改变指针的指向，不需要移动元素，所以速度比较快。散列表是根据关键字而直接进行访问的数据结构，散列表建立了关键字和存储地址之间的一种直接映射关系，查找、插入和删除速度快。

2.数据的四种基本存储结构是指 ( )。 【昆明理工大学 2018 年】
A. 顺序存储结构、索引存储结构、直接存储结构、倒排存储结构
B. 顺序存储结构、索引存储结构、链式存储结构、散列存储结构
C. 顺序存储结构、非顺序存储结构、指针存储结构、树型存储结构
D. 顺序存储结构、链式存储结构、树型存储结构、圆形存储结构

2.参考答案：B
解析：顺序存储方式。顺序存储方式就是在一块连续的存储区域一个接着一个地存放数据。顺序存储方式把逻辑上相邻的节点存储在物理位置相邻的存储单元里，节点间的逻辑关系由存储单元的邻接关系来体现。顺序存储方式也称为顺序存储结构，一般采用数组或结构数组来描述。
(2) 链接存储方式。链接存储方式比较灵活，不要求逻辑上相邻的节点在物理位置上相邻，节点间的逻辑关系由附加的引用字段来表示。一个节点的引用字段往往指向下一个节点的存放位置。链接存储方式也称为链式存储结构。
(3) 索引存储方式。索引存储方式是采用附加的索引表的方式来存储节点信息的一种存储方式。索引表由若干索引项组成。索引存储方式中索引项的一般形式为（关键字，地址）。其中，关键字是能够唯一标识一个节点的数据项。索引存储方式还可以细分为：①稠密索引：这种方式中每个节点在索引表中都有一个索引项，其中索引项的地址指示节点所在的存储位置。②稀疏索引：这种方式中一组节点在索引表中只对应一个索引项。其中，索引项的地址指示一组节点的起始存储位置。
(4) 散列存储方式。散列存储方式是根据节点的关键字直接计算出该节点的存储地址的一种存储方式。
在实际应用中，往往需要根据具体的数据结构来决定采用哪种存储方式。同一逻辑结构采用不同的存储方法可以得到不同的存储结构。而且这 4 种基本存储方法，既可以单独使用，也可以组合起来对数据结构进行存储描述。

§1.2 算法分析

考点 1 算法的基本概念

题组闯关

1.下面关于算法的说法正确的是 ( )。
A. 算法最终必须由计算机程序实现
B. 一个算法所花时间等于该算法中每条语句的执行时间之和
C. 算法的可行性是指指令不能有二义性
D. 以上说法都是错误的

1.参考答案：B
解析：算法是对特定问题求解步骤的一种描述，所以 A 是错的；算法的可行性，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的，所以 C 是错的。

2.算法的有穷性是指 ( )。
A. 算法程序的运行时间是有限的
B. 算法程序所处理的数据量是有限的
C. 算法程序的长度是有限的
D. 算法只能被有限的用户使用

2.参考答案：A
解析：算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。算法的有穷性是指算法程序的运行时间是有限的，因此本题答案为 A。

3.算法分析的两个主要方面是 ( )。
A. 算法的正确性和可行性
B. 算法的时间复杂度和空间复杂度
C. 算法的有穷性
D. 算法的稳定性和安全性

3.参考答案：B
解析：时间复杂度和空间复杂度是衡量算法好与差的重要指标，正确性和简洁性、可读性和可运行性是从软件工程角度要求系统实现的目标。

4.一个算法具有以下 5 个重要特性 ( )。
A. 有穷性、确定性、可行性、输入、输出
B. 可行性、可移植性、可扩充性、输入、输出
C. 确定性、有穷性、稳定性、输入、输出
D. 易读性、稳定性、安全性、输入、输出

4.参考答案：A
解析：算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作，一个算法具有下列 5 个重要特性：
(1) 有穷性。一个算法必须总是在执行有穷步之后结束，且每一步都可在有穷时间内完成。
(2) 确定性。算法中每一条指令必须有确切的含义，读者理解时不会产生二义性。
(3) 可行性。一个算法是可行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。
(4) 输入。一个算法有零个或者多个的输入，这些输入取自某个特定的对象的集合。
(5) 输出。一个算法有一个或多个的输出，这些输出是同输入有着某种特定关系的量。

5.下面说法中，错误的是 ( )。
①算法原地工作的含义是指不需要任何额外的辅助空间
②在相同规模 n 下，复杂度为 O(n) 的算法在时间上总是优于复杂度为 O(n^2) 的算法
③所谓时间复杂度，是指最坏情况下估算算法执行时间的一个上界
④同一个算法，实现语言的级别越低，执行效率越低
A. ①
B. ①②
C. ①④
D. ③

5.参考答案：C
解析：①若算法执行时所需要的辅助空间相对于输入数据量而言是一个常数，则称这个算法为原地工作，辅助空间为 O (1)。不是指不需要任何额外的空间。④同一个算法，实现语言的级别越低，执行效率越高。原命题说反了。故①和④错误，本题选 C。

真题实战

1.下面关于 “算法” 的描述，错误的是 ( )。 【四川大学 2018 年】
A. 算法必须是正确的
B. 算法必须要能够结束
C. 一个问题可以有多种算法解决
D. 算法的某些步骤可以有二义性

1.参考答案：D
解析：一个算法应该具有以下 5 个重要的特征：
(1) 有穷性。算法的有穷性是指算法必须能在执行有限个步骤之后终止。
(2) 确切性。算法的每一个步骤必须有确切的定义；故 D 选项说法错误。
(3) 输入项。一个算法有 0 个或多个输入，以刻画运算对象的初始情况，所谓 0 个输入是指算法本身定出了初始条件。
(4) 输出项。一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的。
(5) 可行性。算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步，即每个计算步都可以在有限时间内完成（也称为有效性）。

2.算法是指为解决某一问题的有限指令序列，它必须具有输入、输出以及 ( ) 等特性。 【武汉大学 2015 年】
A. 易读性、稳定性、确定性
B. 易读性、稳定性、可移植性
C. 有穷性、可行性、确定性
D. 有穷性、可行性、可扩充性

2.参考答案：C
解析：算法是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

3.计算机算法指的是 ( )。 【上海海事大学 2017 年】
A. 计算方法
B. 排序方法
C. 调度方法
D. 解决问题的步骤序列

3.参考答案：D
解析：本题考查算法的定义。算法是对特定问题求解步骤的一种描述，所以选择 D。

考点 2 时间复杂度

题组闯关

1.以比较为基础的排序算法，在最坏的情况下的计算时间复杂度的下界为 ( )。
A. O(n^2)
B. O(log2​(n))
C. O(n)
D. O(nlog2​(n))

1.参考答案：D
解析：此问题考查以比较为基础的排序算法的时间复杂度分析，利用二叉树可以证明对任何以关键字比较为基础的排序算法，最坏情况的计算时间下界都为 O(nlog2​(n))，如归并排序算法。

2.下面函数的时间复杂度是 ( )。

void func(int n) {
    int sum = 0, i, j;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j *= 3)
            sum++;
}

A. O(log3​(n))
B. O(n^2)
C. O(nlog3​(n))
D. O(n)

2.参考答案：C
解析：外循环执行 n 次，内循环执行了 log3​(n) 次，所以答案是 O(nlog3​(n))。

3.参考答案：C
解析：O 的含义是表示程序的执行时间或占用空间随数据规模的增长趋势。

A 选项，算法的时间复杂度与问题规模没有任何关系。故 A 选项错误。

B 选项，任何算法的执行时间都几乎不可能完全等于n^2。故 B 选项错误。

C 选项，如果一个算法的时间复杂度为O(n^2)，n的值增加，n2的值也会随之增加，那么执行时间肯定就是与n^2成正比的。故 C 选项正确。

D 选项，一个算法的时间复杂度与这个问题的数据规模没有关系，故 D 选项也错误。

4.下面程序段的时间复杂度为 ( )。

i = 1;
while (i <= n) i *= 3;

A. O(3n)
B. O(n)
C. O(n^3)
D. O(log3​n)

4.【参考答案】D
【解析】i<=n时，i=i∗3，那么循环的次数即为i一直乘 3 到n的次数，即为log3​n。所以时间复杂度为O(log3​n)。

5.下面算法的时间复杂度是 ( )。

int f(unsigned int n)
{
    if (n == 0 || n == 1) return(1);
    else return n * f(n - 1);
}

A. O(1)
B. O(n)
C. O(n^2)
D. O(n!)

5.【参考答案】B
【解析】这个算法实质上是在求n的阶乘，也就是说运算过程是：n×(n−1)×…×2×1，中间经过了n次运算，也就是说时间复杂度是O(n)。

6.下面程序段的时间复杂度为 ( )。

for(int i = 0; i < m; i++)
    for(int j = 0; j < n; j++)
        A[i][j] = i * j;

A. O(m^2)
B. O(n^2)
C. O(m×n)
D. O(m+n)

6.【参考答案】C
【解析】该程序为嵌套循环，外层循环的时间复杂度T(n1)=O(m)，内层循环的时间复杂度T(n2)=O(n)，则此程序的时间复杂度T(n)=m×n，即为O(m×n)。

7.程序段

for(i = n - 1; i > = 1; i--)
    for(j = 1; j < = i; j++)
        if (A[j] > A[j + 1]) A[j]与A[j + 1]对换;

其中 n 为正整数，则该程序段在最坏情况下的时间复杂度是 ( )。

A. O(n)
B. O(nlog(n))
C. O(n^3)
D. O(n^2)

8.下面是有关算法时间复杂度的论述，其中正确的说法是 ( )。

A. 算法的时间复杂度与数据规模无关
B. 算法的时间复杂度与算法的语句频度无关
C. 算法的时间复杂度与算法采用的解决问题的策略无关
D. 算法的时间复杂度与选择的程序设计语言无关

8.【参考答案】D
【解析】程序执行的效率与数据的存储结构、数据的逻辑结构、程序的控制结构、所处理的数据量等有关。除O(1)外，时间复杂度随问题的规模增大而增大；语句频度越高，高到多出一个量级，复杂度就变了；不同的策略，复杂度有可能是不同的。

9.下列程序的时间复杂度为 ( )。

for (i = 0; i < m; i++)
    for(j = 0; j < t; j++)
        c[i][j] = 0;
for(i = 0; i < m; i++)
    for(j = 0; j < t; j++)
        for(k = 0; k < m; k++)
            c[i][j] = c[i][j] + a[i][k] * b[k][j];

A. O(m+n×t)
B. O(m+n+t)
C. O(m×n×t)
D. O(m×t+n)

9.【参考答案】C
【解析】计算程序的时间复杂度时，对于一个多层循环，假设循环体的时间复杂度为O(n)，各层循环的循环次数分别是、、，则这个循环的时间复杂度为O(n×a×b×c×……)。分析的时候应该由里向外分析这些循环。而对于顺序执行的语句或者算法，总的时间复杂度等于其中最大的时间复杂度。结合上述信息可以看出题目给出的两个循环是顺序执行的。其中第二个循环的时间复杂度更高，为m×n×t，所以答案为 C。

10.Fibonacci 数列的递归计算方法如下：F(0)=0,F(1)=1,F(n)=F(n−1)+F(n−2)，该递归函数的时间复杂度是 ( )。

A. O(n)
B. O(n^2)
C. O(2^n)
D. O(nlog2​(n))

10.【参考答案】C
【解析】每次n减小 1，一共需要进行n次。因此时间复杂度为O(2^n)，速度慢是因为其系数在指数变大。

11.在一个元素个数为 n 的数组里，找到升序排在 n/5 位置的元素的最优算法时间复杂度是 ( )。

A. O(n)
B. O(nlogn)
C. O(n(logn)^3)
D. O(n^3/2)

11.【参考答案】A
【解析】BFPRT 算法解决的问题十分经典，即从某n个元素的序列中选出第k大（第k小）的元素，通过巧妙的分析，BFPRT 可以保证在最坏情况下仍为线性时间复杂度。该算法的思想与快速排序思想相似。当然，目的是使得算法在最坏情况下，依然能达到O(n)的时间复杂度。

真题实战

1.下面程序段的时间复杂度是 ( )。 【广东工业大学 2017 年】

x = 0;
for(i = 0; i < n; i++)
    for(j = i; j < m; j++)
        x++;

A. O(log2​n)
B. O(n)
C. O(nlog2​n)
D. O(n^2)

2.时间复杂度 O(1) 的含义是 ( )。 【广东工业大学 2016 年】

A. 问题规模为 1
B. 执行时间为 1 秒
C. 问题规模为 1 的常数倍
D. 执行时间与问题规模无关

3.下列程序段的时间复杂度是 ( )。 【全国统考 2022 年】

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

A. O(logn)
B. O(n)
C. O(nlogn)
D. O(n^2)

4.下面程序段的时间复杂度是 ( )。 【昆明理工大学 2016 年】

j = 0;
s = 0;
while(s < n)
{
    j++;
    s = s + j;
}

考点 3 空间复杂度

题组闯关

真题实战

某算法的空间复杂度为 O(1)，则 ( )。 【四川大学 2015 年】

A. 该算法执行不需要任何辅助空间
B. 该算法执行所需辅助空间大小与问题规模 n 无关
C. 该算法执行不需要任何空间
D. 该算法执行所需空间大小与问题规模 n 无关