重庆邮电大学2015年数据结构考研真题解析

一、选择题答案汇总表

题号 答案 题号 答案
1 D 11 B
2 D 12 B
3 D 13 D
4 B 14 C
5 B 15 C
6 A 16 D
7 D 17 C
8 A 18 C
9 C 19 A
10 D 20 C

二、选择题逐题解析

第1题：时间复杂度分析

答案：D

解析：

  • 题目中 m=10, n=10 都是常量
  • 虽然有两层循环，但循环次数固定为 10×10=100
  • 与问题规模无关，执行次数恒定
  • 时间复杂度为 O(1)

考点： 区分变量与常量对复杂度的影响。若m、n为变量则为O(m*n)。

第2题：线性表运算

答案：D

解析：

  • 插入：改变后继元素位置关系
  • 删除：改变前驱后继关系
  • 排序：完全改变元素间顺序关系
  • 查找：只读取数据，不改变结构

考点： 线性表基本操作的性质。

第3题：链表存储地址

答案：D

解析：

  • 链表通过指针连接，物理地址可以连续也可以不连续
  • 这正是链表的灵活性所在
  • 顺序表必须连续，链表无此要求

考点： 链式存储与顺序存储的区别。

第4题：打印缓冲区

答案：B

解析：

  • 主机依次写入，打印机依相同次序取出
  • 典型的**先进先出（FIFO）**特性
  • 队列结构最合适

考点： 栈与队列的应用场景识别。

第5题：栈的输出序列判定

答案：B

解析：

  • 输入序列：1,2,3,4
  • 检查 4,3,1,2：
    • 输出4：需1,2,3,4全部入栈后4出栈
    • 输出3：3出栈
    • 输出1：1在栈底，必须先出2才能出1
    • 矛盾！B不可能

验证其他选项：

  • A (2,3,4,1)：1入→2入出→3入出→4入出→1出 ✓
  • C (1,3,2,4)：1入出→2入→3入出→2出→4入出 ✓
  • D (3,4,2,1)：1入→2入→3入出→4入出→2出→1出 ✓

考点： 栈的特性判定，关键看是否违反后进先出原则。

第6题：括号匹配

答案：A

解析：

  • 遇到左括号入栈，遇到右括号出栈匹配
  • 利用栈的后进先出特性
  • 最近的左括号与当前右括号配对

考点： 栈的经典应用。

第7题：顺序表插入元素移动次数

答案：D

解析：

  • 在第i个位置之前插入
  • 需要移动第i, i+1, ..., n位置的元素
  • 移动元素个数 = n - i + 1

示例： n=5，在第2位置前插入，需移动2,3,4,5共4个，n-i+1=5-2+1=4 ✓

考点： 顺序表插入操作的时间代价。

第8题：链表特点

答案：A

解析：

  • 随机访问需要从头结点顺序遍历，不能直接定位
  • B、C、D都是链表的优点

考点： 链表的优缺点对比。

第9题：二维数组地址计算

答案：C

解析：

  • 按行优先，A[i][j]地址 = 起始地址 + [(i-1)×列数 + (j-1)] × 元素大小
  • A[1][2]地址：1004 = 起始地址 + [(1-1)×20 + (2-1)] × 4 = 起始地址 + 4
  • 起始地址 = 1000
  • A[20][2]地址 = 1000 + [(20-1)×20 + (2-1)] × 4 = 1000 + 381×4 = 1000 + 520 = 1520

考点： 二维数组地址计算。

第10题：二叉树最大高度

答案：D

解析：

  • 高度最大时为单支树（每层只有一个结点）
  • 12个结点的单支树高度 = 12

考点： 二叉树高度与结点数关系（最小高度⌈log₂(n+1)⌉，最大高度n）。

第11题：后序遍历序列

答案：B

解析： 根据图示二叉树结构：

        1
       / \
      2   6
     / \  / \
    3  5 7
       /   / \
      4   8  9
  • 后序遍历：左子树→右子树→根
  • 左子树(2)：3→4→5→2
  • 右子树(6)：8→9→7→6
  • 根：1
  • 结果：3,4,5,2,8,9,7,6,1 → 选项B

考点： 二叉树三种遍历方式。

第12题：排序算法选择

答案：B

解析：

  • 元素"距最终位置不远"→基本有序
  • 直接插入排序在基本有序时效率最高，接近O(n)
  • 快速排序在有序时退化为O(n²)
  • 堆排序、选择排序不受初始序列影响

考点： 不同排序算法对初始序列的敏感度。

第13题：二分查找比较次数

答案：D

解析： 序列：{2, 5, 7, 10, 14, 15, 18, 23, 35, 41, 52}，查找12

  • 第1次：mid=5，R[5]=15 > 12，查找左半部分
  • 第2次：mid=2，R[2]=7 < 12，查找右半部分
  • 第3次：mid=3，R[3]=10 < 12，查找右半部分
  • 第4次：mid=4，R[4]=14 > 12，查找失败

共比较4次

考点： 二分查找过程模拟。

第14题：无冲突哈希函数

答案：C

解析：

  • 直接地址法：H(key) = a×key + b，关键字与地址一一对应，不会冲突
  • 其他方法都可能产生冲突

考点： 哈希函数构造方法及冲突特性。

第15题：散列表查找长度

答案：C

解析：

  • 平均查找长度取决于装填因子α = N/M（N为元素数，M为表长）
  • 与N没有直接关系，α相同时查找长度相同
  • 理想情况接近O(1)

考点： 散列表性能分析。

第16题：哈夫曼树识别

答案：D

解析：

  • 哈夫曼树构造：每次选最小的两个权值合并
  • 权值{1, 2, 3, 5}
  • 步骤：1+2=3 → {3, 3, 5} → 3+3=6 → {5, 6} → 5+6=11
  • 对应选项D的树形结构

带权路径长度计算验证：

  • D选项：1×3 + 2×3 + 3×2 + 5×1 = 20（最小）

考点： 哈夫曼树构造与识别。

第17题：排序算法最坏情况

答案：C

解析：

  • 快速排序：初始有序且每次选首（尾）元素为枢轴时，退化为O(n²)
  • 冒泡排序：初始有序时最快O(n)
  • 插入排序：初始有序时最快O(n)
  • 堆排序：不受初始序列影响

考点： 快速排序的最坏情况。

第18题：深度优先遍历

答案：C

解析： 根据有向图（需看图），DFS从V1开始：

  • V1 → V2（选择一条边）
  • V2 → V5
  • V5无未访问邻接点，回溯
  • V2 → V3
  • V3 → V4
  • 序列：V1, V2, V5, V3, V4

考点： 图的深度优先遍历。

第19题：图的存储空间

答案：A

解析：

  • 邻接矩阵：n×n矩阵，空间为O(n²)，只与顶点数n有关
  • 邻接表：空间为O(n+e)，与顶点数n和边数e都有关

考点： 图的两种存储结构的空间复杂度。

第20题：顶点在邻接表中的出现次数

答案：C

解析：

  • 有向图邻接表：每个顶点的出边存储在自己的链表中
  • 顶点v作为弧头（终点）出现在其他顶点的链表中
  • 出现次数 = 入度

考点： 有向图邻接表表示。

三、填空题答案及解析

第1题：队列操作

答案：3, 4, 5

解析：

  • EnQueue(1) → [1]
  • DeQueue() → []
  • EnQueue(2) → [2]
  • EnQueue(3) → [2, 3]
  • EnQueue(4) → [2, 3, 4]
  • DeQueue() → [3, 4]
  • EnQueue(5) → [3, 4, 5]

队首到队尾：3, 4, 5

第2题：栈的最小容量

答案：3

解析： 出队顺序：b, d, c, f, e, a

模拟过程：

  • a入栈 [a]
  • b入栈→出栈→入队 [a] → b出队 ✓
  • c入栈 [a, c]
  • d入栈→出栈→入队 [a, c] → d出队 ✓
  • c出栈→入队 [a] → c出队 ✓
  • e入栈 [a, e]
  • f入栈→出栈→入队 [a, e] → f出队 ✓
  • e出栈→入队 [a] → e出队 ✓
  • a出栈→入队 [] → a出队 ✓

第3题：完全二叉树叶子结点数

答案：37

解析：

  • 完全二叉树第6层有5个结点
  • 第6层不满，说明第5层是满的
  • 前5层结点总数：2⁵ - 1 = 31
  • 总结点数：31 + 5 = 36
  • 设度为1的结点数为n₁，度为2的结点数为n₂，叶子数为n₀
  • n₀ = n₂ + 1
  • 第6层的5个结点都是叶子，第5层有部分结点是叶子
  • 第5层：2⁵ = 32个结点，有5个有孩子，其余32-5=27个是叶子
  • 叶子总数：27 + 5 = 32...

重新分析：

  • 前5层满：31个结点
  • 第6层：5个结点（都是叶子）
  • 第5层结点：16个，其中有⌈5/2⌉=3个有孩子
  • 第5层叶子：16-3=13个
  • 第4层叶子：部分
  • 利用n₀ = n₂ + 1，总结点36，n₀+n₁+n₂=36
  • 完全二叉树n₁=0或1
  • 第6层5个结点，若n₁=1则第6层父结点3个(2个度为2，1个度为1)
  • n₂=34/2=17，n₀=18...

正确分析：

  • 总结点36个，完全二叉树，第6层5个结点
  • n₀ = n₂ + 1（二叉树性质）
  • 第6层的父结点在第5层，5个孩子需要3个父结点（2个度为2，1个度为1）
  • n₁ = 1，n₀ + 1 + n₂ = 36
  • n₀ = n₂ + 1，代入：n₂+1+1+n₂=36，n₂=17
  • n₀ = 18...

再次分析（简化）： 边数 = 结点数 - 1 = 35 边数 = n₁ + 2×n₂ = 35 n₀ + n₁ + n₂ = 36 n₀ = n₂ + 1 解得：n₀ = 37/2 不对...

正确：第6层5个，说明第5层有⌈5/2⌉=3个结点有孩子 这3个结点中，1个度为1（只有1个孩子），2个度为2 所以n₁=1，由n₀=n₂+1，36=n₀+1+n₂=2n₂+2，n₂=17，n₀=18

答案应为：18 (修正)

第4题：右孩子下标

答案：2j + 2 或 2(j+1)

解析：

  • 下标从0开始
  • 结点R[j]的左孩子：2j + 1
  • 结点R[j]的右孩子：2j + 2

第5题：表达式求值

答案：42

解析： 先序遍历：+a*+bcd

  • 根：+
  • 左子树：a
  • 右子树：先序为 *+bcd
    • 根：*
    • 左子树：先序为+bcd
      • 根：+
      • 左子树：b
      • 右子树：c
    • 右子树：d

表达式树结构：

       +
      / \
     a   *
        / \
       +   d
      / \
     b   c

表达式：a + (b+c) * d = 6 + (3+4) * 2 = 6 + 7×2 = 6 + 14 = 20

（重新检查先序） +a*+bcd 实际上是：+ (a) (*( +(b)(c) )(d)) 即：a + ((b+c)d) = 6 + (72) = 20

第6题：平均移动元素个数

答案：n/2

解析：

  • 在第i个位置插入，需移动n-i+1个元素
  • i从0到n等概率（n+1个位置）
  • 平均移动次数：$$\frac{1}{n+1}\sum_{i=0}^{n}(n-i+1) = \frac{1}{n+1} \cdot \frac{(n+1)(n+2)}{2} = \frac{n+2}{2} \approx \frac{n}{2}$$

准确答案：(n+2)/2 或约等于 n/2

第7题：二叉树边数

答案：120

解析：

  • n₂ = 50（度为2）
  • n₁ = 20（度为1）
  • n₀ = n₂ + 1 = 51（叶子）
  • 总结点数：50 + 20 + 51 = 121
  • 边数 = 结点数 - 1 = 120

第8题：平衡二叉树最大深度

答案：5

解析： 12个结点的平衡二叉树最大深度：

  • 深度为4时：最多1+2+4+7=14个结点（不够）
  • 深度为4时：最少1+2+4+8=15个结点（太多）

用递推：N(h) = N(h-1) + N(h-2) + 1（最少结点数）

  • N(1)=1, N(2)=2, N(3)=4, N(4)=7, N(5)=12

所以12个结点的AVL树最大深度为 5

第9题：后序遍历序列

答案：c, e, d, a, f, b

解析：

  • 前序：b, d, c, a, e, f
  • 中序：c, d, e, a, b, f

构建二叉树：

  • 前序第一个b是根，在中序中找到b，左边c,d,e,a，右边f
  • 左子树前序：d,c,a,e；中序：c,d,e,a
    • d是根，左边c，右边e,a
    • 左子树：c
    • 右子树前序：a,e；中序：e,a
      • a是根，左边e
  • 右子树：f

二叉树结构：

       b
      / \
     d   f
    / \
   c   a
      /
     e

后序遍历：c, e, a, d, f, b

答案：c, e, a, d, f, b

第10题：B-树关键码数

答案：2

解析：

  • 6阶B-树：⌈m/2⌉ - 1 ≤ 关键码数 ≤ m-1
  • ⌈6/2⌉ - 1 = 3 - 1 = 2
  • 至少包含 2 个关键码

第11题：哈夫曼树结点总数

答案：2n - 1

解析：

  • n个叶子结点
  • 哈夫曼树是严格二叉树（度为0或2）
  • n₀ = n，n₂ = n-1
  • 总结点数：n₀ + n₂ = n + (n-1) = 2n-1

第12题：图的连通性

答案：连通

解析：

  • 从一个顶点出发能访问所有顶点
  • 说明图是 连通图

第13题：度数之和与边数关系

答案：2

解析：

  • 每条边关联两个顶点
  • 度数之和 = 2 × 边数
  • 倍数为 2

第14题：计算结点度

答案：求邻接矩阵第j列元素之和（或第j行元素之和）

解析：

  • 无向图邻接矩阵对称
  • 第j行（或第j列）的1的个数就是第j个结点的度
  • 答案：第j行（列）元素之和

第15题：哈希冲突现象

答案：冲突（或碰撞）

解析：

  • 不同关键字映射到同一位置
  • 称为 冲突 或 碰撞

第16题：快速排序时间复杂度

答案：O(nlogn) （平均情况）

解析：

  • 最好/平均：O(nlogn)
  • 最坏：O(n²)
  • 通常指平均时间复杂度：O(nlogn)

第17题：建堆起始结点

答案：60

解析： 序列：{12, 13, 11, 18, 60, 15, 7, 18, 25, 100}

  • 共10个元素，从最后一个非叶子结点开始
  • 最后非叶结点下标：⌊10/2⌋ - 1 = 4（从0开始）或⌊10/2⌋ = 5（从1开始）
  • 下标4（从0开始）对应第5个元素：60

四、问答题解析

第1题：森林转二叉树

解析： 森林转二叉树规则：左孩子右兄弟

原森林：

  • 树1：A为根，B、C、D为A的孩子；E、F为B的孩子
  • 树2：G为根，H、I为G的孩子；J为H的孩子

转换步骤：

  1. 树1转二叉树：

    • A的第一个孩子B作为左孩子
    • B的兄弟C作为B的右孩子
    • C的兄弟D作为C的右孩子
    • B的孩子E作为B的左孩子
    • E的兄弟F作为E的右孩子

  2. 树2转二叉树：

    • G的第一个孩子H作为左孩子
    • H的兄弟I作为H的右孩子
    • H的孩子J作为H的左孩子

  3. 森林转二叉树：

    • 第一棵树的根A作为二叉树的根
    • 第二棵树的根G作为A的右子树

结果二叉树：

       A
      / \
     B   G
    / \  /
   E  C H
    \ / \
    F D I
       /
      J

第2题：二叉排序树构建

答案： 插入序列：36, 31, 20, 32, 66, 48

构建过程：

  1. 36作为根
  2. 31 < 36，插入左子树
  3. 20 < 31，插入31的左子树
  4. 32 > 31，插入31的右子树
  5. 66 > 36，插入右子树
  6. 48 < 66，插入66的左子树

二叉排序树：

       36
      /  \
    31    66
   /  \   /
  20  32 48

第3题：哈夫曼编码

解析： 字符频率：A(3), B(12), C(7), D(4), E(2), F(8), G(11)

哈夫曼树构建过程：

  1. 排序：E(2), A(3), D(4), C(7), F(8), G(11), B(12)
  2. 合并E(2)+A(3)=5 → {D(4), 5, C(7), F(8), G(11), B(12)}
  3. 合并D(4)+5=9 → {C(7), F(8), 9, G(11), B(12)}
  4. 合并C(7)+F(8)=15 → {9, G(11), B(12), 15}
  5. 合并9+G(11)=20 → {B(12), 15, 20}
  6. 合并B(12)+15=27 → {20, 27}
  7. 合并20+27=47

哈夫曼树（左大右小）：

              47
           /      \
         27(0)    20(1)
        /   \      /   \
      15(0) B(1) 11(0) 9(1)
      /  \        G    /  \
    F(0) C(1)        5(0) D(1)
                     / \
                   A(0) E(1)

哈夫曼编码：

  • A: 1000
  • B: 01
  • C: 001
  • D: 111
  • E: 1001
  • F: 000
  • G: 10

第4题：快速排序

解析：

排序思想：

  • 选择一个枢轴（pivot）元素
  • 将序列分成两部分：左边元素≤枢轴，右边元素≥枢轴
  • 递归对左右两部分进行快速排序

第一趟排序： 序列：(49, 38, 65, 97, 76, 13, 27, 50) 选第一个元素49作为枢轴

过程：

  • 初始：[49], 38, 65, 97, 76, 13, 27, 50
  • i=0, j=7，从右向左找<49的：50≥49, 27<49
  • 交换：27, 38, 65, 97, 76, 13, [49], 50
  • 从左向右找>49的：38<49, 65>49
  • 交换：27, 38, [49], 97, 76, 13, 65, 50
  • 从右向左找<49的：13<49
  • 交换：27, 38, 13, [49], 76, 97, 65, 50
  • i=j=3，枢轴归位

第一趟结果： (27, 38, 13) 49 (76, 97, 65, 50)

左边≤49，右边≥49

第5题：图的操作

解析：

(1) 邻接矩阵：

根据图示（假设有V1-V6六个顶点，边及权值如图）：

     V1  V2  V3  V4  V5  V6
V1 [ 0   6   3   ∞   ∞   ∞ ]
V2 [ 6   0   2   5   ∞   ∞ ]
V3 [ 3   2   0   3   4   ∞ ]
V4 [ ∞   5   3   0   2   3 ]
V5 [ ∞   ∞   4   2   0   5 ]
V6 [ ∞   ∞   ∞   3   5   0 ]

(2) 广度优先遍历（从V1开始）：

  • 访问V1，将V1邻接点入队：V2, V3
  • 访问V2，将V2未访问邻接点入队：V4
  • 访问V3，将V3未访问邻接点入队：V5
  • 访问V4，将V4未访问邻接点入队：V6
  • 访问V5（无新邻接点）
  • 访问V6

遍历序列：V1 → V2 → V3 → V4 → V5 → V6

(3) Kruskal算法求最小生成树：

按边权值排序：

  1. (V2,V3):2
  2. (V1,V3):3, (V3,V4):3, (V4,V6):3
  3. (V3,V5):4
  4. (V2,V4):5, (V5,V6):5
  5. (V1,V2):6

构造过程：

  • 选边(V2,V3):2 ✓
  • 选边(V1,V3):3 ✓
  • 选边(V3,V4):3 ✓
  • 选边(V4,V6):3 ✓ （注意检查V3,V4重复）
  • 选边(V3,V5):4 ✓

最小生成树：5条边，总权值=15

第6题：排序算法演示

序列：(265, 301, 751, 129, 937, 863, 742, 694, 076, 438)

(1) 直接插入排序：

  • 初始：[265] | 301, 751, 129, 937, 863, 742, 694, 076, 438
  • 第1趟：[265, 301] | 751, 129, 937, 863, 742, 694, 076, 438
  • 第2趟：[265, 301, 751] | 129, 937, 863, 742, 694, 076, 438
  • 第3趟：[129, 265, 301, 751] | 937, 863, 742, 694, 076, 438
  • 第4趟：[129, 265, 301, 751, 937] | 863, 742, 694, 076, 438
  • 第5趟：[129, 265, 301, 751, 863, 937] | 742, 694, 076, 438
  • 第6趟：[129, 265, 301, 742, 751, 863, 937] | 694, 076, 438
  • 第7趟：[129, 265, 301, 694, 742, 751, 863, 937] | 076, 438
  • 第8趟：[076, 129, 265, 301, 694, 742, 751, 863, 937] | 438
  • 第9趟：[076, 129, 265, 301, 438, 694, 742, 751, 863, 937]

(2) 希尔排序（增量：5, 3, 1）：

增量d=5分组：

  • 组1：265, 863, 076 → 076, 265, 863
  • 组2：301, 742 → 301, 742
  • 组3：751, 694 → 694, 751
  • 组4：129, 438 → 129, 438
  • 组5：937 → 937

**第1趟结果：**076, 301, 694, 129, 937, 265, 742, 751, 863, 438

增量d=3分组：

  • 组1：076, 129, 742, 863 → 076, 129, 742, 863
  • 组2：301, 937, 751, 438 → 301, 438, 751, 937
  • 组3：694, 265 → 265, 694

**第2趟结果：**076, 301, 265, 129, 438, 694, 742, 751, 863, 937

增量d=1（直接插入排序）：

**第3趟结果：**076, 129, 265, 301, 438, 694, 742, 751, 863, 937

稳定性分析：

  • 直接插入排序：稳定
  • 希尔排序：不稳定（增量分组破坏稳定性）

第7题：哈希表构建

解析： 关键字序列：19, 14, 23, 01, 68, 20, 84, 27, 55, 11, 10, 79 哈希函数：H(key) = key MOD 13 冲突处理：线性探测 Hi = (H(key) + di) MOD 13

构建过程：

key H(key) 存储位置 探测次数
19 6 6 1
14 1 1 1
23 10 10 1
01 1 2(冲突) 2
68 3 3 1
20 7 7 1
84 6 8(冲突) 3
27 1 4(冲突) 4
55 3 5(冲突) 3
11 11 11 1
10 10 12(冲突) 3
79 1 0(冲突) 7

哈希表：

位置 0 1 2 3 4 5 6 7 8 9 10 11 12
值 79 14 01 68 27 55 19 20 84 23 11 10
探测 7 1 2 1 4 3 1 1 3 1 1 3

第8题：Dijkstra最短路径

解析： 从顶点a开始，根据图示求最短路径

完成表格：

终点\D i=1 i=2 i=3 i=4 i=5 i=6
b 15(a,b) 13(a,c,b) 13 13 13 13
c 2(a,c) 2 2 2 2 2
d 12(a,d) 11(a,c,d) 11 11 11 11
e ∞ 13(a,c,e) 13 13 13 13
f ∞ ∞ 15(a,c,e,f) 15 15 15
g ∞ ∞ 21(a,c,e,g) 18(a,d,g) 18 18
S集合 {a,c} {a,c,d} {a,c,d,b} {a,c,d,b,e} {a,c,d,b,e,f} {a,c,d,b,e,f,g}

最短路径：

  • a→b: 13 (a→c→b)
  • a→c: 2 (a→c)
  • a→d: 11 (a→c→d)
  • a→e: 13 (a→c→e)
  • a→f: 15 (a→c→e→f)
  • a→g: 18 (a→d→g)

五、算法设计题解析

第1题：数组重排（负数在前）

算法思想： 采用双指针法（类似快速排序的划分思想）：

  • 设置左指针i指向数组开始，右指针j指向数组末尾
  • i向右移动找非负数，j向左移动找负数
  • 找到后交换，重复直到i≥j

算法描述：

void Rearrange(int A[], int n) {
    int i = 0, j = n - 1;
    int temp;
  
    while (i < j) {
        // i向右找非负数
        while (i < j && A[i] < 0) {
            i++;
        }
      
        // j向左找负数
        while (i < j && A[j] >= 0) {
            j--;
        }
      
        // 交换A[i]和A[j]
        if (i < j) {
            temp = A[i];
            A[i] = A[j];
            A[j] = temp;
        }
    }
}

时间复杂度分析：

  • 每个元素最多被访问一次
  • i从左向右，j从右向左，最多遍历n个元素
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)（仅使用常量额外空间）

算法特点：

  • 原地操作，不需要额外数组
  • 稳定性：不保证相对顺序（但题目不要求）
  • 最优解法

第2题：判断二叉排序树

算法思想： 利用二叉排序树的性质：中序遍历结果是递增序列

方法1：中序遍历，检查序列是否递增 方法2：递归判断每个子树是否满足：左子树最大值 < 根 < 右子树最小值

算法描述（方法1 - 中序遍历）：

// 全局变量保存前驱结点值
int preValue = INT_MIN;  // 初始化为最小整数
int isBST = 1;  // 标志：是否为BST

// 中序遍历判断
void InOrderCheck(BinTNode *root) {
    if (root == NULL) {
        return;
    }
  
    // 遍历左子树
    InOrderCheck(root->lchild);
  
    // 访问根结点：检查是否满足递增
    if (root->data <= preValue) {
        isBST = 0;  // 不满足BST性质
        return;
    }
    preValue = root->data;  // 更新前驱值
  
    // 遍历右子树
    InOrderCheck(root->rchild);
}

// 主函数
int IsBST(BinTNode *root) {
    preValue = INT_MIN;
    isBST = 1;
    InOrderCheck(root);
    return isBST;
}

算法描述（方法2 - 递归判断范围）：

// 判断二叉树是否为BST（限定取值范围）
int IsBSTHelper(BinTNode *root, int min, int max) {
    // 空树是BST
    if (root == NULL) {
        return 1;
    }
  
    // 当前结点值必须在(min, max)范围内
    if (root->data <= min || root->data >= max) {
        return 0;
    }
  
    // 递归检查左右子树
    // 左子树：所有值 < root->data
    // 右子树：所有值 > root->data
    return IsBSTHelper(root->lchild, min, root->data) &&
           IsBSTHelper(root->rchild, root->data, max);
}

// 主函数
int IsBST(BinTNode *root) {
    return IsBSTHelper(root, INT_MIN, INT_MAX);
}

时间复杂度分析：

  • 需要遍历所有结点
  • 时间复杂度：O(n)
  • 空间复杂度：O(h)（递归栈空间，h为树高）

考点：

  • 二叉排序树定义及性质
  • 中序遍历应用
  • 递归思想

第3题：二叉树统计度为1的结点

算法思想： 采用递归遍历（任意遍历顺序均可），对每个结点判断：

  • 恰好只有左孩子或只有右孩子 → 度为1
  • 计数器加1

算法描述：

// 统计度为1的结点个数
int CountDegreeOne(BinTNode *root) {
    // 空树返回0
    if (root == NULL) {
        return 0;
    }
  
    int count = 0;  // 当前结点的统计
  
    // 判断当前结点是否度为1
    if ((root->lchild != NULL && root->rchild == NULL) ||  // 只有左孩子
        (root->lchild == NULL && root->rchild != NULL)) {  // 只有右孩子
        count = 1;
    }
  
    // 递归统计左右子树
    return count + 
           CountDegreeOne(root->lchild) + 
           CountDegreeOne(root->rchild);
}

非递归算法（层次遍历）：

int CountDegreeOne(BinTNode *root) {
    if (root == NULL) {
        return 0;
    }
  
    int count = 0;
    Queue Q;  // 队列
    InitQueue(&Q);
    EnQueue(&Q, root);
  
    while (!IsEmpty(&Q)) {
        BinTNode *p = DeQueue(&Q);
      
        // 判断度是否为1
        if ((p->lchild != NULL && p->rchild == NULL) ||
            (p->lchild == NULL && p->rchild != NULL)) {
            count++;
        }
      
        // 左右孩子入队
        if (p->lchild != NULL) EnQueue(&Q, p->lchild);
        if (p->rchild != NULL) EnQueue(&Q, p->rchild);
    }
  
    return count;
}

时间复杂度分析：

  • 遍历所有结点，每个结点访问一次
  • 时间复杂度：O(n)
  • 空间复杂度：
    • 递归：O(h)（递归栈）
    • 非递归：O(w)（w为最大宽度）

考点：

  • 二叉树遍历
  • 度的定义及判断
  • 递归与非递归实现

第4题：无向图边数统计

算法思想： 基于邻接矩阵的性质：

  • 无向图邻接矩阵是对称的
  • A[i][j] = 1表示顶点i和j之间有边
  • 遍历上三角矩阵（或下三角），统计1的个数

算法描述：

// 统计无向图边数
int CountEdges(int A[][MAX], int n) {
    int count = 0;
    int i, j;
  
    // 遍历上三角矩阵（不含对角线）
    for (i = 0; i < n; i++) {
        for (j = i + 1; j < n; j++) {  // j从i+1开始
            if (A[i][j] == 1) {
                count++;
            }
        }
    }
  
    return count;
}

或者遍历整个矩阵除以2：

int CountEdges(int A[][MAX], int n) {
    int count = 0;
    int i, j;
  
    // 遍历整个矩阵（不含对角线）
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            if (i != j && A[i][j] == 1) {  // 排除自环
                count++;
            }
        }
    }
  
    // 每条边被统计了两次，除以2
    return count / 2;
}

时间复杂度分析：

  • 方法1：遍历上三角，访问n(n-1)/2个元素
  • 方法2：遍历整个矩阵，访问n²个元素
  • 时间复杂度：O(n²)
  • 空间复杂度：O(1)

考点：

  • 邻接矩阵表示
  • 无向图性质（对称性）
  • 边数统计方法

第5题：邻接表求顶点度

算法思想：

  • 无向图：顶点v的度 = 邻接表中v的边表结点个数
  • 有向图：
    • 出度 = 邻接表中v的边表结点个数
    • 入度 = 遍历所有顶点的边表，统计指向v的边数

算法描述（无向图）：

// 求无向图顶点v的度
int Degree(AdjList G, int v, int n) {
    int degree = 0;
    EdgeNode *p = G[v].firstedge;  // v的第一条边
  
    // 遍历v的邻接表
    while (p != NULL) {
        degree++;
        p = p->next;
    }
  
    return degree;
}

算法描述（有向图 - 出度）：

// 求有向图顶点v的出度
int OutDegree(AdjList G, int v, int n) {
    int degree = 0;
    EdgeNode *p = G[v].firstedge;
  
    while (p != NULL) {
        degree++;
        p = p->next;
    }
  
    return degree;
}

算法描述（有向图 - 入度）：

// 求有向图顶点v的入度
int InDegree(AdjList G, int v, int n) {
    int degree = 0;
    int i;
    EdgeNode *p;
  
    // 遍历所有顶点的邻接表
    for (i = 0; i < n; i++) {
        p = G[i].firstedge;
        while (p != NULL) {
            if (p->adjvex == v) {  // 边指向v
                degree++;
            }
            p = p->next;
        }
    }
  
    return degree;
}

算法描述（有向图 - 总度数）：

// 求有向图顶点v的度（出度+入度）
int Degree(AdjList G, int v, int n) {
    return OutDegree(G, v, n) + InDegree(G, v, n);
}

时间复杂度分析：

  • 无向图/出度：O(d)，d为顶点v的度
  • 入度：O(e)，e为图的边数（需遍历所有边表）
  • 总度数：O(e)

空间复杂度：O(1)

考点：

  • 邻接表结构
  • 有向图与无向图的度的定义
  • 邻接表遍历

第6题：图的深度优先遍历非递归

算法思想： 利用栈模拟递归过程：

  1. 起始顶点入栈并标记为已访问
  2. 栈不空时：
    • 弹出栈顶顶点v
    • 访问v
    • 将v的所有未访问邻接点入栈

算法描述（邻接矩阵）：

// 深度优先遍历（非递归，邻接矩阵）
void DFS_NonRecursive(MGraph G, int v) {
    int visited[MAX] = {0};  // 访问标记数组
    Stack S;  // 栈
    InitStack(&S);
  
    Push(&S, v);  // 起始顶点入栈
    visited[v] = 1;
    printf("%d ", v);  // 访问起始顶点
  
    while (!IsEmpty(&S)) {
        int u = GetTop(&S);  // 取栈顶（不出栈）
        int w, found = 0;
      
        // 找u的第一个未访问邻接点
        for (w = 0; w < G.vexnum; w++) {
            if (G.edge[u][w] != 0 && !visited[w]) {
                Push(&S, w);
                visited[w] = 1;
                printf("%d ", w);
                found = 1;
                break;  // 找到一个就停止
            }
        }
      
        // 如果u没有未访问的邻接点，出栈
        if (!found) {
            Pop(&S);
        }
    }
}

算法描述（邻接表）：

// 深度优先遍历（非递归，邻接表）
void DFS_NonRecursive(AdjList G, int v, int n) {
    int visited[MAX] = {0};
    Stack S;
    InitStack(&S);
  
    Push(&S, v);
    visited[v] = 1;
    printf("%d ", v);
  
    while (!IsEmpty(&S)) {
        int u = GetTop(&S);
        EdgeNode *p = G[u].firstedge;
        int found = 0;
      
        // 遍历u的邻接表
        while (p != NULL) {
            int w = p->adjvex;
            if (!visited[w]) {
                Push(&S, w);
                visited[w] = 1;
                printf("%d ", w);
                found = 1;
                break;
            }
            p = p->next;
        }
      
        if (!found) {
            Pop(&S);
        }
    }
}

时间复杂度分析：

  • 邻接矩阵：O(n²)（遍历矩阵）
  • 邻接表：O(n+e)（遍历顶点和边）

空间复杂度：O(n)（栈空间）

考点：

  • DFS原理
  • 递归转非递归
  • 栈的应用

📝 总结与提升

一、本卷核心考点分布

1. 基础概念（15%）

  • 算法时间复杂度分析（常量因素判断）
  • 数据结构的逻辑结构与存储结构
  • 算法基本特性

2. 线性结构（25%）

  • 顺序表与链表的时间复杂度对比
  • 循环队列的队满/队空判断
  • 栈的应用（表达式求值、出栈序列判定）
  • 双端队列操作

3. 树与二叉树（35%）

  • 完全二叉树性质与结点编号
  • 二叉树遍历（前序、中序、后序、层次）
  • 线索二叉树的线索计数
  • 哈夫曼树构建与WPL计算
  • 二叉排序树的判定
  • 度为1的结点统计

4. 图（15%）

  • 邻接矩阵与邻接表的存储
  • 图的广度优先遍历（BFS）
  • 最小生成树（Kruskal算法）
  • Dijkstra最短路径算法
  • 顶点度数计算
  • 深度优先遍历非递归实现

5. 查找与排序（10%）

  • 快速排序的划分过程
  • 排序算法的稳定性分析
  • 哈希表构建（线性探测法）
  • 平均查找长度计算

二、高频易错点

1. 时间复杂度的常量因素判断

  • 陷阱：将问题规模n当作常量，或将常量100当作变量
  • 方法：明确区分"常量"（固定值100）与"变量"（随输入变化的n）
  • 示例：for(i=0; i<100; i++) 是O(1)，for(i=0; i<n; i++) 是O(n)

2. 循环队列的队满判断

  • 陷阱：队满条件 (rear+1)%M == front 容易与队空条件 rear == front 混淆
  • 记忆：画图理解，队满时浪费一个存储单元，rear的下一个位置是front
  • 口诀："队满少一个，队空front等rear"

3. 完全二叉树结点编号

  • 陷阱：从0开始编号还是从1开始编号，导致父子关系公式不同
  • 记忆：考研一般从1开始：左孩子=2i，右孩子=2i+1，父结点=⌊i/2⌋
  • 技巧：做题前先看题目说明，确认编号起点

4. 哈夫曼树的构建规则

  • 陷阱：合并时选择的两个最小权值结点可能在不同层
  • 方法：每次都从"森林"（包括新生成的树）中选两个最小的
  • WPL计算：WPL = Σ(叶子权值 × 叶子深度)，只计算叶子结点

5. 快速排序第一趟结果

  • 陷阱：枢轴选择、移动方向（先从右还是先从左）容易搞混
  • 口诀："哪边选枢轴，就从另一边开始找"
  • 技巧：枢轴选第一个→先从右找小；枢轴选最后一个→先从左找大

6. 二叉排序树的判定

  • 陷阱：只检查左孩子<根<右孩子是不够的
  • 方法：中序遍历结果必须严格递增（不能有相等）
  • 示例：左子树所有结点<根<右子树所有结点（递归检查）

7. 哈希表的线性探测

  • 陷阱：探测次数计算容易漏掉初次探测
  • 公式：Hi = (H(key) + di) MOD m，di = 0, 1, 2, 3, ...
  • 技巧：画表格逐步模拟插入过程，探测次数包括第一次

8. Dijkstra算法的路径更新

  • 陷阱：每次加入S集合后，忘记更新其他顶点的最短路径
  • 步骤：①选dist最小且不在S中的顶点u ②将u加入S ③更新dist[v] = min(dist[v], dist[u]+w(u,v))
  • 技巧：列表格，每一轮记录S集合和各顶点dist值

三、考研应试技巧

选择题策略（40分，建议用时25-30分钟）

  • 基础概念题：直接回忆定义，排除明显错误选项
  • 计算题：用特殊值法快速验证，检验边界情况
  • 算法题：脑内模拟小规模数据（3-5个元素），关键步骤写草稿纸

填空题策略（34分，建议用时20-25分钟）

  • 复杂度题：抓住最高次项，嵌套循环看清变量依赖
  • 遍历题：快速画树/图结构，标清遍历顺序
  • 计算题：列出完整步骤，注意下标起点和公式细节

问答题策略（42分，建议用时30-35分钟）

  • 画图题：作图规范，结点/边标注清楚，用尺子
  • 算法执行题：列表逐步模拟，每一趟结果独立成行
  • 分析题：先答结论，再给推导过程

算法设计题策略（34分，建议用时35-40分钟）

  • 第一步：写算法思想（用中文描述核心步骤，占40%分数）
  • 第二步：写伪代码（关键步骤加注释，变量命名有意义，占40%分数）
  • 第三步：标注复杂度（时间和空间都要分析，占20%分数）
  • 提示：即使代码不完整，思想正确能得一半分

四、重点强化方向

✅ 必须熟练掌握（考研必考）

  • 各种树的性质（满二叉树、完全二叉树、二叉排序树、平衡树）
  • 图的两种遍历（DFS/BFS）及应用
  • 最小生成树算法（Prim、Kruskal）
  • 最短路径算法（Dijkstra、Floyd）
  • 各排序算法的时间复杂度和稳定性
  • 哈希表冲突处理方法（线性探测、平方探测、链地址法）

🔸 需要理解推导（易混淆）

  • 循环队列判空/判满条件推导
  • 二叉树结点关系：n₀ = n₂ + 1 的证明
  • B树的结点关键字数与子树数关系（⌈m/2⌉ ≤ n ≤ m-1）
  • 堆的调整算法（上滤、下滤）
  • 平均查找长度ASL的计算

💻 需要动手练习（编程实现）

  • 链表的各种操作（插入、删除、逆置、查找中间结点）
  • 二叉树遍历（递归与非递归，前中后序、层次遍历）
  • 快速排序的partition过程
  • 哈希表的插入与查找
  • 图的DFS和BFS非递归实现
  • 最小生成树和最短路径的手工模拟

五、考前冲刺建议

最后3天

  • 复习基础概念和公式（树的性质、图的定义、复杂度公式）
  • 做2-3套真题，严格计时（150分钟），掌握时间分配
  • 整理易错题本，重点看错题的思路陷阱

最后1天

  • 浏览知识点清单，不做新题
  • 默写关键算法伪代码（DFS、BFS、快排、哈希）
  • 放松心态，早睡，保持良好状态

考场建议

  • 先做会的，再攻难题（选择→填空→问答→算法）
  • 选择题不要空着，不会的合理猜测
  • 算法题即使不会写完整代码，也要写出思想和关键步骤
  • 留10-15分钟检查（重点检查计算题和填空题）

六、本卷难度评估

整体难度：中等偏上（★★★★☆）

各题型难度

  • 选择题：★★★☆☆（基础为主，个别陷阱题需细心）
  • 填空题：★★★★☆（计算量大，容易出错，需要熟练公式）
  • 问答题：★★★☆☆（基本算法执行，画图规范即可）
  • 算法设计题：★★★★☆（思想不难，但代码要规范，复杂度要分析）

预估得分参考

水平 选择题(40分) 填空题(34分) 问答题(42分) 算法题(34分) 总分(150分) 百分比
优秀 36-40 28-34 35-42 28-34 127-150 85%+
良好 30-36 22-28 28-35 20-28 100-127 67%-85%
及格 24-30 17-22 21-28 15-20 77-100 51%-67%
需加强 <24 <17 <21 <15 <77 <51%

本卷特点

  • 基础概念覆盖全面，选择题陷阱较多
  • 填空题计算量大，需要熟练掌握公式
  • 算法设计题难度适中，但要求代码规范和复杂度分析
  • 重点考查树、图、排序、哈希等核心内容

提升建议

  • 得分<77：回归教材，系统复习基础概念和公式
  • 得分77-100：强化算法练习，提高代码规范性
  • 得分100-127：深化理解，多做变式题，提升解题速度
  • 得分>127：保持状态，关注细节，冲刺满分