一、基本概念与算法复杂度（第 1-8 题）｜数据结构 · 笔试 100+7 题

一、基本概念与算法复杂度（第 1-8 题）

1. 数据结构是相互之间存在特定关系的数据元素的集合。数据结构的三要素不包括以下哪一项？

标签：【互联网/国企笔试高频】

A. 数据的逻辑结构 B. 数据的存储结构（物理结构） C. 数据的传输结构 D. 数据的操作（运算）

答案：C

【结论】 数据结构三要素 = 逻辑结构 + 存储结构 + 数据运算；“传输结构”是杜撰的干扰项，选 C。

【逐项辨析】

A 逻辑结构：三要素之一。指数据元素之间的抽象关系，与计算机无关，分四类 —— 线性结构（线性表、栈、队列、串）、树形结构（二叉树、一般树）、图状结构（图）、集合。
B 存储结构：三要素之一，又称物理结构。指数据在计算机中的表示方式，分四类 —— 顺序存储（数组）、链式存储（指针）、索引存储（索引表）、散列存储（哈希表）。
C 传输结构：正确项（本题选它）。 数据结构教材中不存在“传输结构”这一概念，是四个选项中唯一没有定义的杜撰词。“传输”属于计算机网络领域（如传输层、传输介质），被借来设置跨学科干扰。
D 数据运算：三要素之一。指施加于数据上的操作，包括增、删、改、查、排序等。

【知识点】 三要素的层次关系

要素	分类	举例	面向
逻辑结构	线性 / 树形 / 图状 / 集合	线性表、二叉树、图	问题（与机器无关）
存储结构	顺序 / 链式 / 索引 / 散列	数组、指针、索引表、哈希表	机器
数据运算	增删改查 + 排序等	Insert / Delete / Search	操作

两条关键关系：1. 同一逻辑结构可有多种存储结构 —— 线性表既能顺序存储（数组），也能链式存储（链表）。 2. 运算定义在逻辑结构上，实现依赖存储结构 —— 同样是“插入”，顺序表要移动元素，链表只改指针。

【记忆锚点】 “逻辑看关系，存储看摆放，运算看操作”——三要素就是“关系、摆放、操作”三件事。

【易混对比】 常见进阶考法是把“抽象数据类型(ADT)”与“数据结构”混考。ADT = 逻辑结构 + 运算,不含存储结构；它只描述“是什么、能做什么”，不规定“怎么存、怎么做”。本科期末与 408 均考过。

【自测】 抽象数据类型(ADT)的定义包含以下哪一项？ A. 存储结构 B. 逻辑结构与运算 C. 程序代码 D. 内存布局

答：B。ADT 只描述逻辑结构与运算，不含存储结构。与第 8 题（逻辑结构 vs 存储结构）连考。

【知识关联】

同库连考：与第 8 题（逻辑结构 vs 存储结构）构成「概述」双子星 —— 本题考三要素的名称，第 8 题考三要素之间的关系；与第 9、13 题（顺序表/链表/ArrayList）连成「概念 → 存储 → 工程实现」三层链路。
工程实现:Java 中 List 接口对应「逻辑结构 = 线性表」；ArrayList/LinkedList 对应两种「存储结构」；add/remove/get 对应「运算」。三要素在 JDK 集合框架里可逐一对上号。
408 / 国企真题:408 统考「数据结构概述」必考三要素与 ADT；国网计算机类考纲第一章原样收录。
面试追问:①「ADT 和数据结构差在哪一层？」（差在存储结构）；②「为什么说运算定义在逻辑上、实现在存储上？」（举顺序表插入 vs 链表插入）。

【拓展延伸】

变式问法:①「ADT 包含哪两要素？」（逻辑结构+运算，不含存储）；②「下列哪个不是逻辑结构？」（顺序存储/链式存储都是存储结构）；③「数据的逻辑结构与问题本身有关还是与机器有关？」（与问题有关，与机器无关）。

工程映射:Java 集合框架三层对应 —— List/Set/Map 接口≈逻辑结构与运算约定；ArrayList/HashSet/HashMap≈存储结构；add/remove/contains≈运算。理解三要素才能看懂「接口与实现分离」的设计。

408 延伸：常考「数据结构=逻辑结构+存储结构+运算」与「ADT=逻辑结构+运算」的差集，差的正是存储结构一层。

2. 算法的时间复杂度取决于( )

标签：【互联网/国企笔试超高频】

A. 问题的规模 B. 待处理数据的初态 C. A和B D. 与A和B无关

答案：C

【结论】 时间复杂度同时取决于问题规模与待处理数据的初态，选 C（A 和 B）。

【逐项辨析】

A 问题的规模：只答对一半。规模 n 是影响复杂度的第一要素，但同一算法在不同数据初态下复杂度可以不同。
B 待处理数据的初态：也只答对一半。初态决定“同一规模下落在哪一种情况”，但规模本身不可忽略。
C A 和 B：正确。 规模决定数量级的基数，初态决定落在最好 / 平均 / 最坏哪一种。
D 与 A 和 B 无关：显然错误，时间复杂度就是关于规模 n 的函数 T(n)。

【知识点】 时间复杂度 T(n) 由两个因素共同决定：1. 问题规模 n —— 如数组长度、矩阵阶数、图的顶点数；2. 待处理数据的初始状态 —— 即数据的排列情况。

同一算法在不同初态下的三种情况

算法	最好	平均	最坏	初态对应
冒泡排序	O(n)	O(n²)	O(n²)	有序 / 逆序
快速排序	O(n log n)	O(n log n)	O(n²)	均匀 / 已有序
直接插入排序	O(n)	O(n²)	O(n²)	有序 / 逆序

“数据已有序”对冒泡、插入是最好情形，对快排（取首元素为基准）却是最坏情形。

【记忆锚点】 “规模定量级，初态定最好最坏”——先看 n 有多大，再看数据长什么样。

【易混对比】 注意与“空间复杂度”区分：本题所举的冒泡、选择、直接插入这类原地非递归算法，辅助空间恒为 O(1)，确实与数据初态无关——这是「空间复杂度不受初态影响」成立的唯一场景。但别把它当普遍结论：一旦递归栈深度参与计费，空间复杂度同样随初态变化，例如快速排序的递归栈平均 O(log n)，而数据已有序（取首元素为基准）时退化成 O(n)（见第 86 题「快排最坏递归深度 O(n)，栈空间 O(n)」）；归并排序恒为 O(n)，与初态无关。准确说法是「原地非递归算法的空间复杂度与初态无关」，而不是「空间复杂度与初态无关」。

【自测】 同一个快速排序算法，分别对已有序数组和随机数组执行，时间复杂度各是多少？

答：已有序为 O(n²)（最坏），随机为 O(n log n)（平均）。同一算法、同一规模，仅因初态不同就相差一个数量级。与第 81 题连考。

【知识关联】

同库连考：与第 3 题（复杂度量级排序）、第 4~7 题（循环复杂度计算）、第 81 题（快排最坏）构成「复杂度」专题。本题是总纲，后几题是具体演算。
工程实现:JDK Arrays.sort 对基本类型用双轴快排（平均 O(n log n)，最坏 O(n²))，对对象类型用 TimSort（归并+插入，最坏 O(n log n))—— 选 TimSort 正是为了规避「初态导致最坏」这一风险，呼应本题「初态影响复杂度」。
408 / 国企真题:408 选择题原题高频；国网「算法基础」模块必考。
面试追问:①「为什么快排平均比归并快，工程上对象排序却用 TimSort？」；②「空间复杂度受数据初态影响吗？」（分算法：冒泡、插入等原地算法不受，恒 O(1)；快排的递归栈随初态在 O(log n)~O(n) 之间变，所以「一概不受」是错的）。

【拓展延伸】

变式问法:①「时间复杂度与空间复杂度哪个受初态影响？」（时间一定受；空间只在「递归栈深度参与计费」时才受——快排由 O(log n) 变到 O(n)，冒泡/插入这类原地算法不受）；②「同一算法对随机数据与最坏数据，应报告哪个复杂度？」（工程报平均，实时系统报最坏）；③「规模 n 还没变但数据分布变了，复杂度会变吗？」（会，落入不同情况）。

完整对照：冒泡/插入「有序=最好 O(n)」；快排（首元 pivot）「有序=最坏 O(n²)」；归并/堆排「三种情况都是 n log n」。「数据已有序」不能笼统说更好或更坏，必须看算法。

工程应用：基准测试要区分 random/sorted/reverse 三种数据；JDK 排序实现会检测「已部分有序」以走 TimSort 快路径 —— 这正是「初态影响复杂度」的工程化。

3. 以下哪种复杂度表示的算法效率最高？

标签：【互联网/国企笔试常考】

A. O(2ⁿ) B. O(n²) C. O(n log n) D. O(log n)

答案：D

【结论】 复杂度越低效率越高，四个选项中 O(log n) 最优，选 D。

【逐项辨析】

A O(2ⁿ)：指数级，增长最快、效率最低。典型如未优化的斐波那契递归、穷举所有子集。n = 30 时运算量已超过 10 亿。
B O(n²)：平方级，效率低。典型如冒泡 / 选择 / 插入排序、双层循环。
C O(n log n)：线性对数级，是基于比较的排序算法的理论下界，如快排、归并、堆排序。
D O(log n)：对数级，四者中最优。 典型如二分查找、平衡树查找 —— 数据量翻倍，运算量只多 1 次。

【知识点】 常见复杂度的增长顺序（从优到劣）：

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)

复杂度	名称	典型算法	n = 1024 时的量级
O(1)	常数级	数组按下标访问	1
O(log n)	对数级	二分查找	10
O(n)	线性级	顺序查找	1,024
O(n log n)	线性对数级	归并 / 快排 / 堆排序	≈ 10,240
O(n²)	平方级	冒泡排序	≈ 1,048,576
O(2ⁿ)	指数级	穷举子集	天文数字

对比可见：同样是 n = 1024,O(log n) 与 O(n²) 相差约 10 万倍。

【记忆锚点】 “指数最慢，对数最快”——看到 2ⁿ、n! 直接判最差，看到 log n 直接判最优。

【易混对比】 注意 O(n log n) 与 O(n²) 都含 n，但前者只多一个对数因子、后者多一个线性因子。判断技巧：只看最高阶项，忽略常数与低阶项 —— 如 3n² + 100n + 5 记作 O(n²)。

【自测】 把下列复杂度按效率从高到低排列，正确的是？ ①O(n²) ②O(log n) ③O(n log n) ④O(2ⁿ)

答：② < ③ < ① < ④（② 最优、④ 最差）。与第 4~7 题的循环复杂度连考。

【知识关联】

同库连考：与第 2 题（复杂度两因素）、第 4~7 题（循环计算）、第 65~68 题（二分/顺序查找复杂度）同一知识面。
工程实现：二分查找 O(log n) 对应 Arrays.binarySearch、TreeMap.get（红黑树 O(log n))；哈希查找 O(1) 对应 HashMap.get。面试常说「哈希 O(1) 是均摊，红黑树 O(log n) 是最坏」。
408 / 国企真题:408 常考「下列哪个效率最高/最低」；国网真题库把量级排序与算法举例绑在一起考。
面试追问:①「O(n log n) 为什么是基于比较排序的下界？」（决策树高度，叶子 ≥ n!）；②「O(1) 一定比 O(log n) 快吗？」（渐进意义上是，小 n 时看常数）。

【拓展延伸】

变式问法：把 O(1)、O(√n)、O(n)、O(n log n)、O(n²)、O(2ⁿ) 混排；或给两个算法「n=1000 时谁更快」（需考虑常数，如 O(1000n) 与 O(n log n))。

数量级直觉(n=10⁶):

O(log n)≈20,O(n)=10⁶,O(n log n)≈2×10⁷,O(n²)=10¹²(不可行)

工程应用：算法选型先看阶再看常数；缓存友好、SIMD、并行能改变常数但改不了阶。面试常问「为什么不用 O(n²) 的冒泡」——大数据下不可接受。

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

标签：【互联网/国企笔试高频】

for (i = 1; i <= n; i++)
    for (j = 1; j <= n; j++)
        x++;

A. O(n²) B. O(n) C. O(log n) D. O(n log n)

答案：A

【结论】 基本操作 x++ 共执行 n × n = n² 次，时间复杂度 O(n²)，选 A。

【推导过程】 数清每层循环各跑多少次

外层 i = 1..n       → 执行 n 次
内层 j = 1..n       → 每轮执行 n 次
x++ 总次数 = n × n  = n²

大 O 只保留最高阶项：O(n²)。

【逐项辨析】

B O(n)：只数了单层循环，漏乘内层。
A O(n²)：正确。 外层 n 次 × 内层每轮 n 次 = n² 次。
C O(log n)：对数级来自“循环变量倍增 / 减半”，本题循环变量是 i++、j++，没有。
D O(n log n)：需要“一层 n 级 + 一层 log 级”的组合，本题两层都是 n 级。

【知识点】 循环嵌套复杂度的通用分析法 —— 把每层循环的次数相乘。内层写法与复杂度的对照（第 4~7 题核心）：

内层写法	总执行次数	复杂度
`for (j=1; j<=n; j++)`	n²	O(n²)
`for (j=1; j<=i; j++)`	n(n+1)/2	O(n²)
`for (j=1; j<=n; j+=2)`	n²/2	O(n²)
`for (j=1; j<=n; j*=2)`	n·log₂n	O(n log n)

关键结论：决定复杂度的不是“有几层循环”，而是“每层循环跑多少次”。

【记忆锚点】 “嵌套看乘积，只留最高次”——先把各层次数相乘，再丢掉常数系数与低阶项。

【易混对比】 与第 5 题（内层 j<=i）、第 7 题（内层 j*=2）构成一组连考。三者差异只在两处：内层上界和步长方式。看到 j<=n 就答 n²，看到 j*=2 才想到 log。

【自测】 把内层改成 for (j = 1; j <= n; j *= 2)，时间复杂度是多少？

答：O(n log n)。外层 n 次、内层 log₂n 次，相乘。与第 7 题同型，国网真题库与 408 均考过。

【知识关联】

同库连考：第 4、5、6、7 题是「循环复杂度」四连：本题 n×n → n²；第 5 题 j≤i → n²；第 6 题 i*=2 → log n；第 7 题外 n 内 log → n log n。四题一起背，考场直接对照。
工程实现：嵌套遍历矩阵、暴力两两比较都是 O(n²);JDK 中禁止对大数据做双重全表扫描，改用哈希（把一层循环换成 O(1) 查找）降为 O(n)。
408 / 国企真题：国网、银行科技岗「复杂度计算」几乎每套都有同型循环题。
面试追问:①「把内层改成 j<=i 复杂度变吗？」（不变，仍是 O(n²)，系数从 1 变 1/2);②「三层 n 循环是几？」(O(n³))。

【拓展延伸】

变式问法:

内层 for (j = 1; j <= n; j++) 改为 for (j = 1; j <= n; j += 2) → 总次数 n·⌈n/2⌉，仍是 O(n²)（步长常数只影响系数）。
改为 for (j = i; j <= n; j++) → Σ(n−i+1) = n(n+1)/2,O(n²)。
三层 for i,j,k = 1..n → O(n³)。

完整验算(n=4):

外层 i=1..4,内层 j=1..4
x++ 总次数 = 4×4 = 16 = n²
n=8 → 64;n=16 → 256;倍增 n 时次数变 4 倍 → 平方级特征 ✓

工程应用：图像处理中对 n×n 像素做邻域滤波是 O(n²)；若邻域大小固定(3×3)，总代价仍是 O(n²) 而不是 O(n⁴) —— 内层次数是常数。

5. 以下程序段的时间复杂度为( )

标签：【互联网/国企笔试常考】

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

A. O(n) B. O(n log n) C. O(log n) D. O(n²)

答案：D

【结论】 总次数 = 1 + 2 + … + n = n(n+1)/2，数量级仍是 n²，选 D。

【推导过程】 逐层数次数

i = 1 → 内层跑 1 次
i = 2 → 内层跑 2 次
i = 3 → 内层跑 3 次
...
i = n → 内层跑 n 次
总计 = 1 + 2 + 3 + ... + n = n(n+1)/2 = n²/2 + n/2

大 O 只保留最高次项、去掉系数：O(n²)。

【逐项辨析】

A O(n)：只看到外层是 n，漏掉了内层次数随 i 递增。
D O(n²)：正确。 n(n+1)/2 ≈ n²/2，系数 1/2 在大 O 中忽略。
C O(log n)：与本题无关，内层没有倍增 / 减半。
B O(n log n)：与本题无关。

【知识点 · 关键判断】 内层上界是 i（变量）还是 n（常量），只影响常数系数，不影响数量级:

写法	总次数	与 n² 的关系	复杂度
`j <= n`	n²	系数 1	O(n²)
`j <= i`	n(n+1)/2	系数 1/2	O(n²)
`j <= i`，且 `i *= 2`	1+2+4+…+n ≈ 2n	系数 2	O(n)

只有出现“倍增 / 减半”时，数量级才会真正下降。

【记忆锚点】 “上界随外层变，只降系数、不降数量级；唯有倍增减半，才降数量级。”

【易混对比】 第 4、5、7 题三连对照 —— 都是“双层循环”，答案却是 n² / n² / n log n。判据只有一条：看循环变量怎么变，而不是看有几层循环。

【自测】 for (i = 1; i <= n; i *= 2) for (j = 1; j <= i; j++) x++; 的时间复杂度是多少？

答：O(n)。外层执行 ⌊log₂n⌋+1 次，内层总次数 = 1+2+4+…+n ≈ 2n，总计 O(n)。与第 4、7 题连考。

【知识关联】

同库连考：与第 4、6、7 题同属循环复杂度组；与第 87 题（快排一趟划分）有结构相似 —— 快排平均递归深度 log n、每层划分 O(n)，总 O(n log n)，与「外 n 内 log」同构。
工程实现：插入排序内层 while 是「在已排序前缀中找位置」，最坏每轮扫 i 个，总 O(n²) —— 正是本题的代码形态。
408 / 国企真题:408 考过「j<=i 与 j<=n 是否同阶」；国网真题库把本题与第 4 题并列设问。
面试追问:①「n(n+1)/2 为什么还是 O(n²)？」（大 O 忽略系数与低阶项）；②「什么写法能把这个双重循环降到 O(n log n)？」（内层倍增或外层倍增）。

【拓展延伸】

变式：外层改 i *= 2、内层 j <= i → 总次数 1+2+4+…+n ≈ 2n,O(n)。这是「系数变、阶不变」与「阶也变」的分水岭。

完整验算(n=5):

i=1 → 1 次
i=2 → 2 次
i=3 → 3 次
i=4 → 4 次
i=5 → 5 次
总计 15 = 5×6/2 = n(n+1)/2 ✓
n=100 → 5050 ≈ n²/2 → O(n²) ✓

工程应用：两层「外层枚举、内层扫前缀」的写法出现在朴素最近对、冒泡、插入中；竞赛里见到要立刻想「能否用树状数组/线段树把内层降到 log」。

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

标签：【互联网/国企笔试高频】

x = 0;
for (i = 1; i <= n; i *= 2)
    x++;

A. O(log n) B. O(n) C. O(n log n) D. O(n²)

答案：A

【结论】 循环变量每轮翻倍，执行 ⌊log₂n⌋+1 次，时间复杂度 O(log n)，选 A。

【推导过程】 列出 i 的取值序列

i = 1, 2, 4, 8, 16, ... , 2^k    (2^k ≤ n)
循环次数 = 满足 2^k ≤ n 的最大 k 再加 1 = ⌊log₂n⌋ + 1

n = 1024 时，i 取 1、2、4、…、1024 共 11 个值，只跑 11 次，而 n 本身是 1024 —— 这就是对数级。

【逐项辨析】

B O(n)：误以为“从 1 到 n 要跑 n 次”，忽略了 i 是翻倍增长。
A O(log n)：正确。 每轮翻倍，次数为 log₂n 量级。
C O(n log n)：需要两层循环相乘，本题只有一层。
D O(n²)：本题只有一层循环，不可能到平方级。

【知识点】 单层循环的复杂度由循环变量的变化方式决定

循环写法	执行次数	复杂度
`i = 1; i <= n; i++`	n	O(n)
`i = 1; i <= n; i += 2`	n/2	O(n)（常数因子忽略）
`i = 1; i <= n; i *= 2`	log₂n	O(log n)
`i = n; i >= 1; i /= 2`	log₂n	O(log n)

判据：变量按“加”变化 → 线性；按“乘 / 除”变化 → 对数。

【记忆锚点】 “加法线性，乘法对数”——i++ 走 n 步，i*=2 只走 log n 步。

【易错提醒】 不要看到“循环”就答 O(n)。判断复杂度的关键是循环变量每轮的变化方式，而非循环层数。本题与第 4、5、7 题构成“循环复杂度分析”的完整考法。

【自测】 循环 for (i = n; i >= 1; i /= 2) x++; 的时间复杂度是多少？

答：O(log n)。i 依次取 n、n/2、n/4、…、1，共 ⌊log₂n⌋+1 次。与本题对照记忆。

【知识关联】

同库连考：与第 4、5、7 题四连；与第 67 题（二分比较次数）、第 74 题（折半查找）同一「log 从哪来」的知识面 —— 都是「每轮砍半」。
工程实现：二分查找、红黑树查找、while (lo < hi) 边界写法、数据库 B+ 树层高、Java HashMap 扩容时 rehash 的「容量翻倍」都是 log 型。
408 / 国企真题：国网「算法基础」模块高频；408 复杂度题必含倍增循环。
面试追问:①「i += 2 是 O(n) 还是 O(n/2)？」(O(n)，常数忽略）;②「三重循环外 i*=2 中 j*=2 内 k=1..n 是几？」(O(n log² n))。

【拓展延伸】

变式:for (i = n; i > 0; i /= 3) → O(log₃ n)，渐进仍记 O(log n)（底数是常数因子）。

完整验算(n=1024):

i = 1,2,4,8,...,1024
次数 = log₂1024 + 1 = 11
n 翻倍到 2048 → 次数 12,只多 1 → 对数特征 ✓

工程应用：线段树建树 O(n)、单次更新 O(log n)；跳表平均 O(log n)。凡「每次范围减半」的算法都归此阶。

7. 以下程序段的时间复杂度为( )

标签：【互联网/国企笔试高频】

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

A. O(n) B. O(log n) C. O(n log n) D. O(n²)

答案：C

【结论】 外层 n 次、内层 log₂n 次，总次数 n·log₂n，时间复杂度 O(n log n)，选 C。

【推导过程】 两层分别数，再相乘

外层 i = 1..n              → 执行 n 次
内层 j = 1,2,4,...; j *= 2 → 每轮执行 ⌊log₂n⌋+1 ≈ log₂n 次
x++ 总次数 = n × log₂n

【逐项辨析】

A O(n)：只算了外层，漏掉内层的对数因子。
B O(log n)：只算了内层，漏掉外层。
C O(n log n)：正确。 n × log₂n。
D O(n²)：内层是倍增而非线性，达不到 n²。

【知识点】 双层循环的复杂度 = 外层次数 × 内层次数，四种组合一次记全

外层	内层	复杂度	对应题号
n 级(i++)	n 级(j++)	O(n²)	第 4 题
n 级(i++)	累加(j<=i)	O(n²)	第 5 题
log 级(i*=2)	—	O(log n)	第 6 题
n 级(i++)	log 级(j*=2)	O(n log n)	本题

O(n log n) 是基于比较的排序算法的理论下界，归并排序、堆排序、快速排序的平均情况都是这个量级。

【记忆锚点】 “外层线性、内层对数，乘起来就是 n log n”——这正是归并排序“分 n 份、每份 log 层”的复杂度来源。

【易混对比】 本题与第 4、5、6 题四题一组，把“循环嵌套复杂度”的四种典型一次考全。区分要点：外层看怎么变、内层看怎么变，两者相乘。

【自测】 for (i = 1; i <= n; i *= 2) for (j = 1; j <= n; j++) x++; 的时间复杂度是多少？

答：O(n log n)。外层 log₂n 次、内层 n 次，相乘。与本题同型，国网真题库同型题。

【知识关联】

同库连考：第 4~7 题终点；与第 80、83 题（归并/堆排序 O(n log n))对照 —— 归并「log 层 × 每层 O(n)」正是本题代码的算法化身。
工程实现：归并排序、堆排序、快排平均情况都是 n log n;Java Arrays.sort（对象） 的 TimSort 最坏也是 n log n。
408 / 国企真题:408 与国网均考过「外层线性内层对数」的识别。
面试追问:①「归并为什么是 n log n 而不是 n²？」（每层合并 O(n)，共 log n 层）;②「若外层 i*=2、内层 j=1..n？」（仍是 O(n log n)，乘法交换）。

【拓展延伸】

变式:

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

→ O(n · log n · n) = O(n² log n)。三层时「相乘」规则不变。

完整验算(n=8):

外层 8 次,内层 j=1,2,4,8 → 4 次/轮
总计 8×4 = 32 = n·(log₂n + 1) ✓
注意精确计数是 n·(⌊log₂n⌋+1)（j 取 1,2,…,n 共 log₂n+1 个值），不是 n·log₂n（n=8 时只有 24）；量级仍是 O(n log n)
n=16 → 16×5=80;比值 80/32=2.5,介于 2 倍(n 翻倍)与 2 倍多一点(log 也+1)之间

工程应用：分治算法总代价 = 子问题数 × 每子问题代价 × 层数；掌握本题就能现场推归并、快排平均、堆排序复杂度。

8. 以下关于数据的逻辑结构与存储结构的说法，正确的是( )

标签：【互联网/国企笔试高频】

A. 线性表的链式存储属于逻辑结构 B. 同一逻辑结构可以采用不同的存储结构实现 C. 顺序存储只能表示线性结构 D. 数据的运算与所采用的存储结构无关

答案：B

【结论】 同一逻辑结构可采用不同存储结构实现，选 B。

【逐项辨析】

A 错：链式存储属于存储结构（物理结构），不是逻辑结构。逻辑结构只有四类 —— 集合、线性、树形、图状。
B 对：同一逻辑结构可有多种存储实现 —— 线性表既可用顺序表（数组），也可用链表（指针）。
C 错：顺序存储同样能表示非线性结构，如用数组顺序存储完全二叉树（堆）、用邻接矩阵存储图。
D 错：运算的实现效率直接依赖存储结构 —— 按序号查找在顺序表是 O(1)、在链表是 O(n)；插入在顺序表要移动元素、在链表只改指针。

【知识点】 逻辑结构与存储结构是“抽象关系”与“具体实现”的关系

	逻辑结构	存储结构
描述对象	数据元素之间的逻辑关系	数据在计算机中的表示方式
分类	集合、线性、树形、图状	顺序、链式、索引、散列
是否依赖机器	不依赖（与语言无关）	依赖（与内存布局有关）
与运算的关系	运算定义在逻辑结构上	运算实现依赖存储结构

一句话：逻辑结构回答“数据之间是什么关系”，存储结构回答“这些关系在内存里怎么摆”。

【记忆锚点】 “逻辑管关系，存储管实现；逻辑不依赖机器，存储依赖机器”。

【易混对比】 常与“三要素”（第 1 题）连考。要点：三要素 = 逻辑结构 + 存储结构 + 数据运算，而 ADT 只含逻辑结构 + 运算。这一组辨析是“数据结构概述”模块的必考起点。

【自测】 下列说法正确的是？ A. 顺序存储只能存储线性结构 B. 链式存储属于逻辑结构 C. 同一逻辑结构可有多种存储实现 D. 运算与存储结构无关

答：C。A 错（数组可存完全二叉树）、B 错（链式是存储结构）、D 错（运算实现依赖存储结构）。与第 1 题连考。

【知识关联】

同库连考：与第 1 题（三要素）、第 9~15 题（顺序表/链表）、第 51~55 题（图的邻接矩阵 vs 邻接表）构成「抽象 → 实现」完整链路。邻接矩阵/邻接表就是「同一逻辑结构（图）的两种存储结构」。
工程实现:Java List 逻辑上都是线性表，ArrayList（顺序）与 LinkedList（链式）是同一 ADT 的两种存储；Map 逻辑上是映射，HashMap（散列）与 TreeMap（树形）也是。
408 / 国企真题:408「数据结构概述」原题；国网考纲第一章。
面试追问:①「为什么 JDK 要同时提供 ArrayList 和 LinkedList？」（操作频率不同）；②「运算与存储无关这句话错在哪？」（定义无关，实现强相关）。

【拓展延伸】

变式问法:①「完全二叉树用数组存，属于逻辑结构还是存储结构？」（存储结构）；②「图用邻接矩阵还是邻接表，逻辑结构变了吗？」（没变，仍是图）；③「运算定义在逻辑上，为何实现要依赖存储？」（同一 Insert，顺序表搬元素、链表改指针）。

工程应用：接口编程(List list = new ArrayList<>())就是「逻辑约定 + 可替换存储实现」；换 new LinkedList<>() 不改业务代码，却改变性能特征 —— 选错实现是线上事故常见原因。

408 延伸：常与第 1 题连考；答题时先分清「关系/实现/操作」三层再选。