【2012】408联考数据结构真题整理

2012年

1

题目

解析

递归

2

题目

答案：A

解析

3

题目

解析

4

题目

答案：B

解析

• T1：1
• T2：2
• T3：2 + 1 + 1 = 4
• T4：T3 + T2 + 1 = 2 + 4 + 1 = 7
• T5：T4 + T3 + 1 = 7 + 4 + 1 = 12
• T6：T5 + T4 + 1 = 12 + 7 + 1 = 20
  

5

题目

解析

图的遍历：

• 深度优先搜索（DFS） 类似树的先序遍历（根左右），借助栈实现
  • 是一个递归算法，借助递归工作栈，空间复杂度O(V)
  • 邻接矩阵表示：时间复杂度O(V^2)
  • 邻接表表示：时间复杂度O(e + v)
  • 例：遍历序列：V1 V2 V4 V8 V5 V3 V6 V7
• 广度优先搜索（BFS） 类似树的层次遍历（依次每一层），借助队列实现
  • 借助队列，空间复杂度O(V)
  • 邻接矩阵：时间复杂度O(V^2)
  • 邻接表：时间复杂度O(e + v)
  • 例：遍历序列：V1 V2 V3 V4 V5 V6 V7 V8
    
    

6

题目

解析

• 举例：
  • o -> o
  • o -> o **+** -> o

7

题目

解析

8

题目

解析

I、代价唯一且最小 -> 最小生成树

9

题目

解析

B-Tree（B树、B-树）

10

题目

答案：A

解析

41

题目

解析

42

题目

答案：
代码如下：

3）O(m + n) 或 O(MAX(m, n)) => O(n)

解析