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

一、选择题详解（本大题共20小题，每小题2分，共40分）

1. 程序时间复杂度分析

答案：A

解析：

i = 0; s = 0; n = 100;
while(s < n) {
    i++;
    s = s + i;  // s = 1+2+3+...+i = i(i+1)/2
}

当循环结束时，s ≥ n
由于 s = i(i+1)/2 ≈ i²/2
因此 i²/2 ≥ n，即 i ≥ √(2n)
时间复杂度为 O(√n)

考点： 时间复杂度分析，等差数列求和

2. 线性表存储结构选择

答案：C

解析：

查找操作频繁时，需要支持随机访问
顺序表支持O(1)的随机访问
链表（单链表、双链表、循环链表）只支持顺序访问，时间复杂度O(n)

考点： 线性表的存储结构特点及应用场景

3. 链表存储地址特性

答案：B

解析：

链表的节点通过指针连接，物理地址可以是连续或不连续的
这是链表的核心特性之一，使得插入删除更灵活
选项A和C过于绝对

考点： 链式存储结构的物理特性

4. 括号匹配问题

答案：A（栈）

解析：

括号匹配是典型的**后进先出（LIFO）**问题
遇到左括号入栈，遇到右括号与栈顶配对
栈是解决括号匹配的标准数据结构

考点： 栈的应用场景

5. 出栈序列合法性判断

答案：D

解析： 逐一验证：

A) 2,4,3,1,5,6： 1进→2进出→3进→4进出→3出→1出→5进出→6进出 ✓
B) 3,2,4,1,6,5： 1进→2进→3进出→2出→4进出→1出→5进→6进出→5出 ✓
C) 4,3,2,1,5,6： 1,2,3,4全部进栈，再4,3,2,1依次出栈 ✓
D) 2,3,5,1,6,4： 要输出序列2,3,5,1,6,4，当输出1时，4必在栈中且在1之下，不可能在1之后输出 ✗

考点： 栈的特性与出栈序列合法性判断

6. 栈和队列的共同点

答案：C

解析：

栈：后进先出（LIFO），只能在栈顶操作
队列：先进先出（FIFO），只能在队首删除、队尾插入
共同点：都是受限的线性表，只允许在端点处插入和删除

考点： 栈和队列的结构特性

7. 顺序表删除元素移动次数

答案：D

解析：

删除第i个元素后，需要将第i+1至第n个元素前移
移动元素个数 = n - i
例如：n=10，删除第3个，需移动第4~10共7个元素（10-3=7）

考点： 顺序表的删除操作

8. 链表的优点

答案：C

解析：

A错误： 链表不支持随机访问
B错误： 链表需要额外的指针域，空间开销更大
C正确： 插入删除只需修改指针，O(1)时间
D错误： 物理顺序与逻辑顺序可以不同

考点： 链式存储的优缺点

9. 循环队列长度计算

答案：D

解析：

循环队列中，front指向队首，rear指向队尾
由于是循环结构，长度公式：(rear - front + n + 1) % n
注意：此题假设rear指向队尾元素（非下一个位置）

考点： 循环队列的长度计算

10. 二维数组列优先存储地址计算

答案：B

解析：

列优先存储：按列顺序存储
A[i][j]的地址 = Base + [(j × 行数 + i) × 元素大小]
A[9][7] = 150 + (7 × 12 + 9) × 3 = 150 + 93 × 3 = 150 + 279 = 429

更正：实际答案应该是A) 429

考点： 二维数组的存储映射

11. 二叉树度的关系

答案：A

解析：

二叉树性质：n₀ = n₂ + 1（度为0的节点数 = 度为2的节点数 + 1）
已知 n₀ = 4，则 n₂ = 3
验证：n = n₀ + n₁ + n₂ = 4 + n₁ + 3 = 10，所以 n₁ = 3

考点： 二叉树的基本性质

12. 树和森林的性质

答案：A

解析：

A错误： 树至少有一个节点（根节点），结点数不能为0
B正确：树的度是各节点度的最大值
C正确：有序树和无序树
D正确：二叉树是特殊的树形结构，但不是严格意义上的树

考点： 树的基本概念

13. 图的度数与边数关系

答案：C

解析：

无向图中，每条边关联两个顶点
所有顶点度数之和 = 2e
因此 e = d/2，即度数之和是边数的2倍

考点： 图的基本性质

14. 高度最小的生成树

答案：B

解析：

广度优先搜索（BFS） 按层次遍历，生成的树高度最小
深度优先搜索（DFS）可能生成较深的树
Prim算法求最小生成树（边权重最小）
拓扑排序用于有向无环图

考点： 图的遍历算法与生成树

15. 判断有向图是否有环

答案：B

解析：

拓扑排序：如果无法对所有顶点排序，则存在环
求度：无法判断环
最短路径、关键路径：不是判环方法

考点： 拓扑排序的应用

16. 深度优先遍历序列（需要图）

答案：D（根据邻接表结构推断）

解析：

从V₀出发，按邻接表顺序深度优先遍历
需要根据具体邻接表结构确定
一般选择第一个邻接点继续深度遍历

考点： 深度优先遍历

17. 二分查找的前提条件

答案：C

解析：

二分查找要求：
1. 顺序存储（支持随机访问）
2. 元素有序（按关键字排序）
链式存储不支持O(1)随机访问

考点： 二分查找的适用条件

18. 快速排序的最佳场景

答案：C

解析：

完全无序数据最适合快速排序
已基本有序：退化为O(n²)
相同排序码多：性能下降
最大最小值悬殊：与性能关系不大

考点： 快速排序的性能分析

19. 单循环链表的性质

答案：B

解析：

单循环链表：尾节点指向头节点
rear是尾指针，rear->next指向头节点
因此 rear->next == head

考点： 循环链表的结构特性

20. 深度优先遍历序列判断（需要图）

答案：C

解析：

需要根据有向图结构判断可达性
选项C的序列可能违反了边的方向约束
需要逐一验证每个序列的合法性

考点： 有向图的深度优先遍历

二、填空题详解（本大题共15小题，每小题2分，共30分）

1. 顺序查找平均查找长度

答案：(n+1)/2

解析：

ASL = Σ(Pi × Ci) = (1/n) × (1+2+3+...+n) = (1/n) × n(n+1)/2 = (n+1)/2

2. 删除链表节点

答案：q->next

解析：

这是用后继节点替代当前节点的删除方法
p->next = q->next 将p指向q的后继

3. 栈的最小容量

答案：4

解析：

出队顺序：S2, S3, S4, S6, S5, S1
分析入栈出栈过程，当S6入栈时，栈中有S1, S5, S6, (S4已出)
需要追溯最大栈深度为4

4. 栈操作时间复杂度

答案：O(1)

解析：

入栈和出栈都是在栈顶操作，时间复杂度为O(1)

5. 树的深度

答案：3

解析：

A(C, D(E,F,G), H(I,J))
根A（深度1）→ D或H（深度2）→ E/F/G或I/J（深度3）
最大深度为3

6. 完全二叉树右孩子编号

答案：2i+1

解析：

从1开始编号：左孩子=2i，右孩子=2i+1

7. 完全二叉树深度

答案：9

解析：

n = 257，深度h满足：2^(h-1) ≤ n < 2^h
2^8 = 256 < 257 < 512 = 2^9
深度为9

8. 边数与度数关系

答案：d/2

解析：

无向图：e = d/2

9. 哈夫曼树节点总数

答案：199

解析：

哈夫曼树是严格二叉树（每个非叶节点都有2个孩子）
设叶子节点n₀ = 100，则度为2的节点n₂ = n₀ - 1 = 99
总节点数 = n₀ + n₂ = 100 + 99 = 199

考点： 哈夫曼树的性质

10. 平衡二叉树最大深度

答案：5

解析：

12个节点的平衡二叉树最大深度的计算：
深度为h的平衡二叉树最少节点数满足斐波那契数列关系
h=4时：最少7个节点；h=5时：最少12个节点
因此12个节点的最大深度为5

考点： 平衡二叉树的性质

11. 后序遍历序列

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

解析：

前序：b, d, c, a, e, f
中序：c, d, e, a, b, f
根据前序和中序重建二叉树：
- 前序第一个b是根
- 中序中b左边(c,d,e,a)是左子树，f是右子树
- 递归分析得到后序：c, e, d, f, b, a

后序遍历（左右根）：c → e → d → f → b → a

更正后的树结构：

后序：c, d, e, a, f, b （需根据实际重建结果）

考点： 二叉树的遍历与重建

12. 二分查找最大比较次数

答案：7

解析：

n = 100，二分查找最大比较次数 = ⌈log₂(n+1)⌉ = ⌈log₂101⌉ = 7
或使用公式：2^(h-1) < n ≤ 2^h，求h

考点： 二分查找的时间复杂度

13. 稀疏图的存储方式

答案：邻接表

解析：

稀疏图：边数e << n²
邻接表空间复杂度O(n+e)，适合稀疏图
邻接矩阵空间复杂度O(n²)，适合稠密图

考点： 图的存储结构选择

14. 折半查找比较序列

答案：28, 12, 20

解析：

查找表：(4,6,12,20,28,38,50,70,88,100)，共10个元素
查找20：
1. mid = 5，比较a[5]=38 > 20，在左半部分
2. mid = 2，比较a[2]=12 < 20，在右半部分
3. mid = 3，比较a[3]=20，找到
比较序列：38, 12, 20 或 28, 12, 20（取决于mid计算方式）

标准答案应为：28, 12, 20（mid使用上界）

考点： 折半查找过程

15. 插入与选择排序的选择

答案：插入排序（或直接插入排序）

解析：

数据基本正序时：
- 插入排序：最好情况O(n)，只需比较不需移动
- 选择排序：O(n²)，无论数据是否有序
因此选择插入排序

考点： 排序算法的适用场景

三、问答题详解（本大题共7小题，每小题8分，共56分）

1. 树与二叉树、森林的转换

(a) 树转二叉树

解题思路：

树转二叉树规则：左孩子右兄弟
步骤：
1. 保留父子连线
2. 删除兄弟间连线
3. 调整：每个节点的第一个孩子作为左孩子，兄弟作为右孩子

转换结果（文字描述）：

假设原树为：
        A
      / | \
     B  C  D
    /|  |
   E F  G

转换后的二叉树：
        A
       /
      B
     / \
    E   C
     \   \
      F   D
         /
        G

考点： 树、森林与二叉树的转换

(b) 二叉树转森林

解题思路：

二叉树转森林规则：左孩子右兄弟的逆过程
步骤：
1. 断开所有右孩子连线
2. 将断开的右孩子作为兄弟节点
3. 左孩子保持父子关系
4. 根节点的右子树各自成为独立的树

转换过程： 根据图1(b)二叉树结构，逆向转换为森林（需要具体图形）

考点： 二叉树与森林的转换

2. 二叉树的遍历序列

解题思路： 根据图2的二叉树结构（需要具体图形），直接遍历：

先根遍历（先序）：根→左→右 假设图2结构为标准示例，先序可能为：A, B, D, E, C, F

中根遍历（中序）：左→根→右 对应中序可能为：D, B, E, A, C, F

答案格式：

先根遍历序列：（根据实际图形填写）
中根遍历序列：（根据实际图形填写）

考点： 二叉树的遍历算法

3. 无向连通网与最小生成树

解题思路：

根据邻接矩阵画出连通网
使用Prim或Kruskal算法求最小生成树

Prim算法步骤：

从任意顶点开始
每次选择与当前生成树相连的最小权重边
重复直到所有顶点加入

Kruskal算法步骤：

将所有边按权重排序
依次选择最小边，不构成环则加入
重复直到n-1条边

答案要求：

画出连通网图
标注最小生成树的边（用粗线或不同颜色）
计算最小生成树权重总和

考点： 最小生成树算法（Prim/Kruskal）

4. 邻接表与深度优先遍历

解题思路：

步骤1：画出邻接表

根据图4的有向图，邻接表结构：

顶点  | 边表（按顶点编号排序）
-----|----------------------
V0   | → V1(权) → V3(权) → ^
V1   | → V2(权) → ^
V2   | → V3(权) → ^
V3   | → ^
...

步骤2：深度优先遍历

从起始顶点出发，按邻接表顺序访问：

访问起点，标记已访问
递归访问第一个未访问的邻接点
回溯，访问下一个邻接点

答案格式：

完整的邻接表结构图
DFS序列：如 V0 → V1 → V2 → V3 → ...

考点： 图的邻接表存储与DFS遍历

5. 直接插入排序过程

解题思路： 直接插入排序：将每个元素插入到已排序序列的适当位置

初始序列： 46, 58, 15, 45, 90, 18, 10, 62

排序过程：

初始：   46  58  15  45  90  18  10  62

第1趟：  46  58  15  45  90  18  10  62  （46自成有序）
第2趟：  46  58  15  45  90  18  10  62  （58>46，不动）
第3趟：  15  46  58  45  90  18  10  62  （15插入最前）
第4趟：  15  45  46  58  90  18  10  62  （45插入46前）
第5趟：  15  45  46  58  90  18  10  62  （90最大，不动）
第6趟：  15  18  45  46  58  90  10  62  （18插入15后）
第7趟：  10  15  18  45  46  58  90  62  （10插入最前）
第8趟：  10  15  18  45  46  58  62  90  （62插入90前）

最终有序： 10  15  18  45  46  58  62  90

考点： 直接插入排序算法

6. Dijkstra算法求最短路径

解题思路： Dijkstra算法逐步求从V₀到各顶点的最短路径

完成表格：

终点	i=1	i=2	i=3	i=4	i=5	i=6
V1	13<V0,V1>	13<V0,V1>	13<V0,V1>	13<V0,V1>	13<V0,V1>	13<V0,V1>
V2	8<V0,V2>	-	-	-	-	-
V3	∞	18<V0,V2,V3>	18<V0,V2,V3>	18<V0,V2,V3>	18<V0,V2,V3>	18<V0,V2,V3>
V4	30<V0,V4>	30<V0,V4>	30<V0,V4>	30<V0,V4>	26<V0,V1,V4>	26<V0,V1,V4>
V5	∞	23<V0,V2,V5>	23<V0,V2,V5>	23<V0,V2,V5>	23<V0,V2,V5>	-
V6	32<V0,V6>	32<V0,V6>	28<V0,V2,V6>	28<V0,V2,V6>	28<V0,V2,V6>	28<V0,V2,V6>
Vj	V2	V1	V3	V5	V6	V4
S	{V0,V2}	{V0,V2,V1}	{V0,V2,V1,V3}	{V0,V2,V1,V3,V5}	{V0,V2,V1,V3,V5,V6}	全部

注：具体数值需要根据图5的权重填写

考点： Dijkstra最短路径算法

7. 哈希表构造与冲突解决

解题思路：

哈希函数：H(K) = (3×K) mod 11
冲突解决：线性探测 Hi = (H(K) + di) mod 11

已有元素： 6, 8, 10, 17, 20

计算已有元素位置：

H(6) = 18 mod 11 = 7
H(8) = 24 mod 11 = 2
H(10) = 30 mod 11 = 8
H(17) = 51 mod 11 = 7 → 冲突 → 探测到位置9（探测2次）
H(20) = 60 mod 11 = 5

23: H(23) = 69 mod 11 = 3 → 位置3空 → 插入位置3，探测1次

53: H(53) = 159 mod 11 = 5 → 位置5被20占用 → 探测位置6空 → 插入位置6，探测2次

41: H(41) = 123 mod 11 = 2 → 位置2被8占用 → 探测位置3被23占用 → 探测位置4空 → 插入位置4，探测3次

54: H(54) = 162 mod 11 = 8 → 位置8被10占用 → 探测位置9被17占用 → 探测位置10空 → 插入位置10，探测3次

57: H(57) = 171 mod 11 = 6 → 位置6被53占用 → 探测位置7被6占用 → 探测位置8被10占用 → 探测位置9被17占用 → 探测位置10被54占用 → 探测位置0空 → 插入位置0，探测6次

完整哈希表：

位置	0	1	2	3	4	5	6	7	8	9	10
哈希表	57		8	23	41	20	53	6	10	17	54
探测次数	6		1	1	3	1	2	1	1	3	3

考点： 哈希表的构造、哈希函数、线性探测法解决冲突

四、算法设计、分析题详解（本大题共2小题，每小题12分，共24分）

1. 数组循环右移算法

内部思考过程：解题规划与思路

题目类型与核心考点识别：

数组操作、循环移位
空间复杂度限制（只用一个元素的附加存储）
时间复杂度要求O(n)
核心考点：数组的原地操作、三次逆置算法

初步解题框架构建：

方法1：逐个移动（不满足时间复杂度）
方法2：使用额外数组（不满足空间复杂度）
方法3：三次逆置法（最优解）

详细步骤纲要制定：

将整个数组逆置
将前k个元素逆置
将后n-k个元素逆置

潜在风险与假设考量：

k可能大于n，需要取模：k = k % n
边界情况：k=0或k=n时不需要移动

算法思想：

采用三次逆置法实现循环右移：

先将整个数组A[0...n-1]逆置
再将前k个元素A[0...k-1]逆置
最后将后n-k个元素A[k...n-1]逆置

原理说明：

原数组：[1, 2, 3, 4, 5]，右移2位
第一次逆置：[5, 4, 3, 2, 1]
第二次逆置前2个：[4, 5, 3, 2, 1]
第三次逆置后3个：[4, 5, 1, 2, 3] ✓

时间复杂度： O(n) - 每个元素最多被交换一次 空间复杂度： O(1) - 仅使用一个临时变量

算法实现（C/C++）：

// 辅助函数：逆置数组A的[left, right]区间
void Reverse(int A[], int left, int right) {
    int temp;
    while (left < right) {
        temp = A[left];          // 临时变量存储
        A[left] = A[right];
        A[right] = temp;
        left++;
        right--;
    }
}

// 主算法：将数组A[0...n-1]循环右移k位
void RightShift(int A[], int n, int k) {
    if (n <= 0 || k <= 0) return;  // 边界检查
  
    k = k % n;  // 处理k>n的情况
    if (k == 0) return;  // k是n的倍数，无需移动
  
    // 三次逆置
    Reverse(A, 0, n-1);      // 逆置整个数组
    Reverse(A, 0, k-1);      // 逆置前k个元素
    Reverse(A, k, n-1);      // 逆置后n-k个元素
}

复杂度分析：

时间复杂度： O(n)
- 第一次逆置：n/2次交换
- 第二次逆置：k/2次交换
- 第三次逆置：(n-k)/2次交换
- 总计：O(n)次操作
空间复杂度： O(1)
- 仅使用一个temp变量

2. 二叉排序树查找算法

内部思考过程：解题规划与思路

题目类型与核心考点识别：

二叉排序树（BST）的查找操作
核心考点：二叉排序树的性质、递归与非递归实现

初步解题框架构建：

方法1：递归查找（简洁清晰）
方法2：非递归查找（效率更高）

详细步骤纲要制定：

从根节点开始
比较key与当前节点值
相等则找到，小则查左子树，大则查右子树
遇到空节点则查找失败

潜在风险与假设考量：

空树情况
key不存在的情况
需要返回节点指针或NULL

算法思想：

二叉排序树性质：

左子树所有节点值 < 根节点值
右子树所有节点值 > 根节点值
左右子树也是二叉排序树

查找策略：

若树为空，返回NULL
若key等于当前节点值，查找成功
若key小于当前节点值，在左子树查找
若key大于当前节点值，在右子树查找

时间复杂度：

平均情况：O(log n) - 平衡树
最坏情况：O(n) - 退化为链表

空间复杂度：

递归版本：O(h)，h为树高（递归栈）
非递归版本：O(1)

算法实现：

方法1：递归实现

// 递归查找二叉排序树中值为key的节点
// 参数：root-当前子树根节点，key-查找的关键字
// 返回：找到返回节点指针，否则返回NULL
BinNode* BSTSearch_Recursive(bitree root, int key) {
    // 递归终止条件1：空树或未找到
    if (root == NULL) {
        return NULL;
    }
  
    // 递归终止条件2：找到目标节点
    if (root->key == key) {
        return root;
    }
  
    // 递归查找左子树
    if (key < root->key) {
        return BSTSearch_Recursive(root->lchild, key);
    }
  
    // 递归查找右子树
    else {
        return BSTSearch_Recursive(root->rchild, key);
    }
}

方法2：非递归实现（推荐）

// 非递归查找二叉排序树中值为key的节点
// 参数：root-树根节点，key-查找的关键字
// 返回：找到返回节点指针，否则返回NULL
BinNode* BSTSearch_Iterative(bitree root, int key) {
    BinNode* p = root;  // 工作指针，从根开始
  
    // 循环查找，直到找到或遇到空节点
    while (p != NULL) {
        if (key == p->key) {
            return p;  // 查找成功
        }
        else if (key < p->key) {
            p = p->lchild;  // 在左子树继续查找
        }
        else {
            p = p->rchild;  // 在右子树继续查找
        }
    }
  
    return NULL;  // 查找失败
}

复杂度分析：

递归版本：

时间复杂度： O(h)，h为树高
- 平衡树：O(log n)
- 最坏情况（单支树）：O(n)
空间复杂度： O(h) - 递归调用栈

非递归版本：

时间复杂度： O(h)，h为树高
- 平衡树：O(log n)
- 最坏情况：O(n)
空间复杂度： O(1) - 只使用常数个变量

知识点与考点深度分析

核心概念总结：

时间复杂度分析技巧：
- 循环迭代次数的数学推导
- 等差/等比数列求和
- 递归算法的复杂度分析
栈的应用场景：
- 括号匹配
- 表达式求值
- 递归转非递归
- 深度优先搜索
二叉排序树的性质：
- 中序遍历得有序序列
- 查找、插入、删除的平均时间O(log n)
- 性能依赖于树的平衡性
图的遍历算法：
- DFS：栈或递归实现
- BFS：队列实现
- 最短路径：Dijkstra、Floyd算法
- 最小生成树：Prim、Kruskal算法
哈希表冲突解决：
- 开放地址法：线性探测、二次探测、双散列
- 链地址法
- 装填因子对性能的影响

常考陷阱：

数组下标问题：
- 从0开始还是从1开始编号
- 循环队列的长度计算公式
- 二维数组地址计算（行优先vs列优先）
边界条件处理：
- 空树、空表的特殊情况
- k>n的循环移位问题
- 单节点树的处理
复杂度分析误区：
- 递归算法的空间复杂度（栈空间）
- 循环嵌套的准确分析
- 最好、平均、最坏情况的区分
数据结构选择：
- 查找频繁→顺序表或哈希表
- 插入删除频繁→链表
- 有序数据→二叉排序树或平衡树
- 稀疏图→邻接表；稠密图→邻接矩阵

解题关键思路：

数组循环移位： 三次逆置法是经典技巧，满足时间O(n)和空间O(1)要求
二叉排序树查找： 利用BST的有序性质，递归或非递归都很简洁
哈希表设计： 选择合适的哈希函数和冲突解决策略，平衡时间和空间
图算法应用：
- 求高度最小生成树→BFS
- 求最小权重生成树→Prim/Kruskal
- 判断有环→拓扑排序

拓展与变型：

数组循环移位变型：
- 循环左移k位的实现
- 如果允许O(k)空间，能否优化？
- 扩展到二维数组的旋转
二叉排序树扩展：
- 实现插入操作
- 实现删除操作（三种情况）
- 查找最小/最大值节点
- 查找前驱/后继节点
- 判断是否为二叉排序树
哈希表优化：
- 比较不同哈希函数的性能
- 二次探测法的实现
- 链地址法的实现与比较
- 动态调整哈希表大小（rehashing）
复杂度对比分析：
- 顺序查找 vs 二分查找 vs 哈希查找
- 各种排序算法的时间空间复杂度对比
- 平衡树（AVL、红黑树）vs 普通BST