一、2025真题

关于栈的特性，以下描述正确的是（）。

A.先进先出（FIFO)

B.支持随机访问

C.只能从中间插入元素

D.后进先出（LIFO)

三、按知识点分类的往年题

1.关于查找运算及查找表的说法，错误的是（）。

A哈希表可以动态创建

B二叉排序树属于动态查找表 二叉排序树（BST）的典型特征就是可以在查找的过程中执行插入和删除节点操作，且不破坏其排序性质

C二分查找要求查找表采用顺序存储结构或循环链表结构 ，二分查找要求的是顺序存储结构（数组），不能是链表。因为它只能一头一尾找，不能直接"跳到中间"

D顺序查找方法既适用于顺序存储结构，也适用于链表结构 顺序查找就是逐个元素进行比较，既不要求随机存取，也不依赖数据物理上的连续存放，所以在数组（顺序存储）和链表上都可以实现。

2.关于二叉排序树的说法，错误的是（）。

A 对二叉排序树进行中序遍历，必定得到结点关键字的有序序列

中序（左-根-右）遍历，因为左子树 < 根结点 < 右子树，所以必然按升序输出关键字。

B 依据关键字无序的序列建立二叉排序树，也可能构造出单支树

如果输入序列本身有序（如依次插入 1,2,3,4,5），构建出的就是退化成链表的单支树

C 若构造二叉排序树时进行平衡化处理，则根结点的左子树结点数与右子树结点数的差值一定不超过1

错误。 平衡化处理（构建平衡二叉树，AVL）只保证左右子树高度差 ≤ 1，不保证结点数差 ≤ 1。反例如下：

    10
   /  \
  5    15
 / \
3   7

这是一棵 AVL 树，但左子树有 3 个结点，右子树有 1 个结点，结点数差为 2，明显超过了 1。

D 若构造二叉排序树时进行平衡化处理，则根结点的左子树高度与右子树高度的差值一定不超过1

3.对于二维数组a[1…N，1…N]中的一个元素a[i，j](1≤i，J≤N)，存储在a[i，j]之前的元素个数（ ）。

A与按行存储或按列存储方式无关

B在i=j时与按行存储或按列存储方式无关，矩阵是个正方形，元素A恰好落在矩阵的主对角线上。

C在按行存储方式下比按列存储方式下要多 很显然不一定

D在按行存储方式下比按列存储方式下要少 很显然不一定

先明确一个前提：二维数组在内存中是按一维线性排列的，有两种常见的存储方式：

按行存储（Row-major）：先存完第一行，再存第二行……

按列存储（Column-major）：先存完第一列，再存第二列……

当 i = j 时，两种存储方式下 a[i, j] 前面的元素个数相等，与存储方式无关。当 i ≠ j 时，个数不同。

4.设有n阶三对角矩阵A，即非零元素都位于主对角线以及与主对角线平行且紧邻的两条对角线上

现对该矩阵进行按行压缩存储，若其压储空间用数组B表示，A的元素下标从0开始，B的元素下标从1开始。

已知A［0,0］存储在B［1］，A［n-1，n-1］存储在B［3n-2］，那么非零元素A［i,j］（0≤ i＜n，0≤ j＜n，│i-j│≤1）存储在B［（ ）］

A 2i+j-1

B 2i+j

C 2i+j+1

D 3i-j+1

阵 A（4×4 三对角矩阵）
非零元素只在三条对角线上（主对角线 + 紧邻的上下对角线）：

text
        j=0   j=1   j=2   j=3
i=0    [0,0] [0,1]  ×     ×
i=1    [1,0] [1,1] [1,2]  ×
i=2     ×    [2,1] [2,2] [2,3]
i=3     ×     ×    [3,2] [3,3]

第 0 行的 2 个元素：[0,0]、[0,1]

第 1 行中它是第 2 个非零元：[1,0]、[1,1]

拿 A[0, 0] 来试，它肯定存在第一个位置，即 B[1]。

• A 选项：2i+j−1=0+0−1=−12i+j−1=0+0−1=−1 → ❌ 明显错

• B 选项：2i+j=0+0=02i+j=0+0=0 → ❌ 明显错

• C 选项：2i+j+1=0+0+1=12i+j+1=0+0+1=1 → ✅ 符合

• D 选项：3i−j+1=0−0+1=13i−j+1=0−0+1=1 → ✅ 也符合

选 A[0, 1]，它紧跟在 A[0,0] 后面，应该在 B[2]。

• C 选项：2×0+1+1=22×0+1+1=2 → ✅ 符合

• D 选项：3×0−1+1=03×0−1+1=0 → ❌ 不符合（和 A[0,0] 冲突了）

5.用哈希表存储元素时，需要进行冲突（碰撞）处理，冲突是指（ ）。

关键字不同的元素被映射到相同的存储位置

6.对有n个结点、e条边且采用数组表示法（即邻接矩阵存储）的无向图进行深度优先遍历，时间复杂度为（ ）。

邻接矩阵的特点

它是一个大小为 n × n 的二维数组，用来表示 n 个顶点之间的连接关系。

无论图中有多少条边 e，哪怕 e 是 0，矩阵依然要占用 O(n²) 的空间。

时间复杂度看矩阵规模，是 O(n²)；如果是邻接表，才是 O(n+e)。

7.令序列X、Y、Z的每个元素都按顺序进栈，且每个元素进栈和出栈仅一次。则不可能得到的出栈序列是（ ）。

栈的特点是 先进后出（FILO），逐个分析选项：进栈顺序严格为：X → Y → Z（X 最先进栈，Y 第二，Z 第三）。

A X Y Z：X Y Z 先后出，正常顺序

B X Z Y：X进了然后就出了，然后Y进不出，到Z进Z又出，最后出Y

C Z X Y：

D Y Z X：X进、Y进然后出，Z进然后出，最后出X

8.以下关于单链表存储结构特征的叙述中，不正确的是（ ）。

A 表中结点所占用存储空间的地址不必是连续的

这是链式存储的天然特性。每个结点在物理上分散存储，地址不要求连续，靠结点的指针域串联起来。

B 在表中任意位置进行插入和删除操作都不用移动元素

链表的插入和删除，核心操作是修改相邻结点的指针指向，不需要像顺序表（数组）那样大量搬移其后所有元素。

C 所需空间与结点个数成正比

每个结点需要存储数据和指针。空间复杂度确实是 O(n)，

D 可随机访问表中的任一结点

链表只能顺序访问，要想找到第 i 个元素，必须从表头开始顺着指针一个一个往后数，时间复杂度是 O(n)。而“随机访问”是指能根据下标在 O(1) 时间内直接找到目标，那是顺序表（数组）的特性。

9.B-树是一种平衡的多路查找树。以下关于B-树的叙述中，正确的是（ ）。

A 根结点保存树中所有关键字且有序排列

B-树中，所有非终端结点也就是非叶子结点，都会包含关键字

B 从根结点到每个叶结点的路径长度相同

B-树通过分裂和调整保证所有的叶子结点都在同一深度，不存在一条分支比另一条分支深的情况。

C 所有结点中的子树指针个数都相同

D 所有结点中的关键字个数都相同

              [30]
               |
      ┌────────┼────────┐
    [10,20]           [50,60,70]
      |      \          |   \    \
   [5,8]   [25]    [35,45] [55] [80,90]

10.对于给定的关键字序列｛47, 34, 13, 12, 52, 38, 33, 27, 5｝，若用链地址法（拉链法）解决冲突来构造哈希表，且哈希函数为H(key)=key%11，则（ ）。

哈希函数与各关键字地址：哈希函数：H(key) = key % 11

47 % 11 = 3

34 % 11 = 1

13 % 11 = 2

12 % 11 = 1

52 % 11 = 8

38 % 11 = 5

33 % 11 = 0

27 % 11 = 5

5 % 11 = 5

根据计算的哈希地址结果：关键字可能算出同一个地址，这就是哈希冲突。34 → 地址 1，12 → 地址 1。两个都想去地址 1，就冲突了。

链地址法（拉链法）的解决方式;把同地址的关键字串成一条链表。

按照数字顺序：34放入1，然后到12的时候， 1 已有 34 → 挂在 34 后面形成链表

也就是1里面 34→12

同理，5里面是38→27→5

C:34和12在同一个链表中

11.某有向图G的邻接表如下图所示，可看出该图中存在弧＜V2, V3＞,而不存在从顶点V1出发的弧。以下关于图G的叙述中，错误的是（ C ）。

A G中存在回路 回路：V₀→V₂→V₃→V₀，回到起点 ✅

B G中每个顶点的入度都为1 看蓝色图入度即是每个顶点被几个人指向？这里都是1

C G的邻接矩阵是对称的 V0指向V1V2则为1...无向图或有向图中每条边都有反向边才能对错

D 不存在弧＜V3, V1＞

根据邻接表，这里存在4个有向弧，分别为V0→V2，V0→V1（V₀ → V₂ → V₁），V2→V3，V3→V0。

12.已知有序数组a的前10000个元素是随机整数，现需查找某个整数是否在该数组中。以下方法中，（ ）的查找效率最高。

二分查找法:对于有序序列的查找，二分法效率较高。

13.14.15.在常见的数据结构中，（ 13 ）是只能通过访问它的一端来实现数据存储和检索的一种线性数据结构，它的修改遵循先进后出的原则； （ 14 ）是一种先进先出的线性表。（ 15 ）是取值范围受限的线性表。

栈 队列 串：串，就是字符串，是一种由零个或多个字符组成的有限序列。

16.二叉树遍历是按照某种策略访问树中的每个结点，且仅访问一次。按照遍历左子树要在遍历右子树之前进行的原则，根据访问（ ）位置的不同，可得到二叉树的前序、中序和后序三种遍历方法。

A 根节点

B 导航节点

C 叶子结点

D 兄弟节点

左→右

前序：最先访问根节点，然后左子树，最后右子树。

中序：先左子树，中间访问根节点，然后右子树。

后序：先左子树，再右子树，最后才访问根节点。

其他选项都无法决定二叉树三种深度优先遍历的命名基础。

17.以下有关哈夫曼树的说法中，错误的是（ ）。

A 哈夫曼树又被称为最优二叉树

B 哈夫曼树是一种带 权路径长度最短的树

C 具有n个叶子结点的权值为W1，W2， ... Wn的最优二叉树是唯一的

形成的结构可以是对称但不同的树，只要带权路径长度最小，可能存在多种形态不同的哈夫曼树。

D 哈夫曼树可以用来进行通信电文的编码和解码

18.查找算法中，（ ）要求查找表进行顺序存储并且按照关键字有序排列，一般不进行表的插入与删除操作。

A 顺序查找 可插入

B 折半查找 必须有序，因为要取中间值然后比大小 一般不进行插入删除

C 分块查找 可插入

D 动态查找 要求链式存储（如二叉排序树）

19.以下关于哈希函数的说法中，不正确的是（ ）。

A 哈希表是根据键值直接访问的数据结构

通过哈希函数把键映射到桶位置，实现近似 O(1) 的访问。

B 随机预言机是完美的哈希函数

在密码学中，随机预言机是一个理想化模型，它输出的哈希值完全随机且没有任何规律，被视为完美的哈希函数。

C 哈希函数具有单向性

给定输出，想倒推出原始输入在计算上不可行。

D 哈希函数把固定长度输入转换为变长输出

这句话说反了。哈希函数通常是把任意（变长）输入压缩成固定长度输出

20.一个栈的输入序列为1，2，3，4，5，不可能得到的输出序列是（ ）。

A 2,3,4,1,5 1进，不出，234依次进又出，最后5进又出

B 5,4,1,3,2

C 2,3,1,4,5

D 1,5,4,3,2

21.（ ）算法是不稳定的排序算法。

A 简单选择：反复从剩余序列中挑出最小的，依次和对应位置交换。在选择最小值并交换的过程中，可能会把前面的元素直接换到后面，从而打乱相同元素的原始顺序。

B 冒泡 当两元素相等时不交换，顺序能保持。

C 直接插入

插入时“大于则后移，相等或小于时停下”，保证相等元素不会跑到前面去。（直接插入排序 插入 理扑克牌：摸一张新牌（当前元素），从右往左在手里已排好序的牌中找位置，插进去。）

D 归并排序

在合并两个子序列时，如果元素相等，会优先取左边子序列的元素，保持原顺序。（整理档案：把一堆档案不断分成小堆，分到每堆只剩一份。然后每次取两堆档案，逐份比对，合并成有序的一大堆。）

22.（ ）是一种先进先出的线性表，只允许在表的一端插入元素，而在表的另一端删除元素。

B队列

23.一棵5层的二叉树，其最多有（ 23 ）个结点，第5层最多有（ 24 ）个结点。

1、在二叉树的第i层上最多有2^i-1个结点（i≥1）；

2、深度为k的二叉树最多有2^k -1个结点（k≥1）；

2⁵-1=31

2^5-1=16

25.分析以下选项（ ）排序又被称为缩小增量排序，是对直接插入排序方法的改进。

A 简单选择：每次选最大或最小，交换位置，没有“增量”概念。

B 冒泡：相邻两两比较交换，本质是“一点点冒上来”，没有增量。

C 快速：从两头交替扫描：从右往左找比 pivot 小的元素，挖出放入左空位；

从左往右找比 pivot 大的元素，挖出放入右空位。直到左右指针相遇，把 pivot 填入中间位置。此时 pivot 左边都小于它，右边都大于它。然后对左右重复操作

D 希尔：设定一个增量 gap（通常初始为数组长度的一半）。把整个数组中间隔 gap 的元素分到同一组，对每组分别进行直接插入排序。把 gap 减半（或缩小），重复上述分组排序过程。

26.如果经常使用范围查询，（ ）会更高效。

A B树索引：B树（以及最常见的变种 B+ 树）的叶子节点形成有序链表，可以支持精确键值查找和范围查询（如 >、<、BETWEEN），遍历时不需要反复扫描全表。适合于频繁做范围查询的场景。

B 散列索引 散列不适合范围查询

C 位图索引 在等值查询和多条件且/或组合时效率高，但不适合频繁更新的场景

D 倒序索引 主要用于全文搜索（如文档中的词语查找），擅长关键词匹配

27.已知一个有序表为(12，18，24，35，47，50，62，83，90，115，134)，当折半查找值为90的元素时，经过（ ）次比较后查找成功。

mid = ⌊(low + high) / 2⌋（向下取整）

假设low下标是1，high下标是11，则中间元素就是6.如果是偶数向下取整

共11个元素，中间第6个值50开始比较

要查账的90大于50，那么90在有序表的 右边，开始第二次比较

第二次是62 ~ 134

7+11/2=9,第九个元素直接就是90

完成查找，共用2次

28.若一棵二叉树的先序遍历序列为EFHIGJK，中序遍历序列为HFIEJKG，则该二叉树根结点的右孩子为（ ）。

先序序列的第一个结点就是整棵树的根：

根 = E

中序序列中，E 的左边是左子树，右边是右子树：

中序：H F I ← 左子树 → E ← 根 → J K G ← 右子树

也就是左子树有 3 个结点：H、F、I，右子树有 3 个结点：J、K、G

所以再重新回到先序的顺序中，FHI是左边的，右边的就是GJK的G了

29.如果一棵二叉树有10个度为2的结点，5个度为1的结点，那么度为0的结点个数为（ 9 ）。

n0​=n2​+1 度为0的结点数是度为2的结点数+1

• n0​ 是度为 0 的结点数（叶子结点）

• n2​ 是度为 2 的结点数

30.设有一个具有头结点的单链表，指针h指向其头结点，则当（ 5 ）时该单链表为空；如果该单链表非空，且指针p指向链尾，那么（ 6 ）。

当h->next==NULL时为空，如果指针p指向链尾，那么p->next==NULL.（也就是后面没有结点了）

31.如果一个线性表最常用的操作是存取第i个元素及其后继（若存在）的值，那么使该操作最快的存储方式是（ ）。

D数组

数组是顺序存储结果，优点是查询速度快，缺点是在插入和删除数据需要移动数据。而链表结果的优点是插入和删除数据快，缺点是查询速度慢。

32.（ ）的基本思想是先将待排的记录划分为独立的两个部分，然后分别对这两部分记录再执行该排序算法，最终使整个序列有序。

A快速排序 根据基准值（pivot）将序列分为左、右两部分，左边都小于基准，右边都大于基准。然后左右两边再重复执行这个操作

B冒泡排序 交换：每一趟把最大（或最小）元素“冒”到最后

C堆排序 先建大顶堆 + 反复把堆顶（最大值）扔到最后并调整剩余堆。

D希尔排序 设定一个增量 gap（通常初始为数组长度的一半）。把整个数组中间隔 gap 的元素分到同一组，对每组分别进行直接插入排序。把 gap 减半（或缩小），重复上述分组排序过程。

33.折半查找要求查找表中的数据为（ ）。

A顺序存储、有序排列

34.以下关于串的叙述中，错误的是（ ）。

串只可以采用顺序存储方式

串是由零个或多个任意字符组成的有限序列。串可以采用多种存储方式

35.依次在初始为空的队列中插入元素5、6、7、8以后，紧接着做了两次删除操作，此时的队头元素是（ 7）。

36.计算机在处理算术表达式78+21*（36-34）时，先将其转换成＂（ 12 ）＂的后缀形式表示，然后利用（ 栈 ）进行计算。

1. 操作数 → 直接输出

2. 运算符 → 和栈顶比优先级

   • 栈空或栈顶是 ( → 直接压栈，不比较优先级

   • 新进栈的运算符优先级更高 → 不弹栈，继续压入

   • 新进栈的运算符优先级更低或相对→ 弹出旧的栈顶

3. ( 一直压栈，直到遇到 ） ，右括号不进栈，直接把括号内剩余的运算符弹出，左括号扔掉。所以最后的结果不会有任何括号

78 21 36 34直接输出

+ * ( - 依次压入栈，因为乘除优先级比加号高，因为括号不参与比较，所以中间没有任何符号被弹出

最后遇到右括号，那么就弹出减号，然后呢再把星和加号弹出

78 21 36 34 - * +