1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
| # 考试形式和试卷结构
## 试卷满分及考试时间
- 满分：150分
- 时间：3小时
## 答题形式
- 闭卷
- 笔试
## 试卷内容结构
### 计算机组成原理
- 小题：11道/22分
- 大题: 2道/23分
### 数据结构
#### 小题：11道/22分
#### 大题：2道/23分
##### 算法题
- 说明算法思想
- 手写代码
- 分析复杂度
##### 应用题
- 画图
- 数据结构定义等
### 操作系统
- 小题：10道/16分
- 大题：2道/15分
### 计算机网络
- 小题：8道/16分
- 大题：1道/9分
## 试卷题型结构
- 选择题：40道/80分
- 应用题：7道/70分
# 大纲
## 考查目标
- 1.掌握数据结构的基本概念、基本定理和基本方法
- 2.掌握数据结构的逻辑结构、存储结构及基本操作的实现，能够对算法进行基本的时间复杂度与空间复杂度的分析
- 3.能够运用数据几个偶的基本原理和方法进行问题的分析与求解，能够对算法进行基本的时间复杂度与空间复杂度的分析
## 考察范围
### 一、线性表
#### （一）线性表的基本概念
#### （二）线性表的实现
#### （三）线性表的应用
### 二、栈、队列和数组
#### （一）栈和队列的基本概念
#### （二）栈和队列的顺序存储结构
#### （三）栈和队列的链式存储结构
#### （四）多维数组的存储
#### （五）特殊矩阵的压缩存储
#### （六）栈、队列和数组的应用
### 三、树与二叉树
#### （一）树的基本概念
#### （二）二叉树
- 1.二叉树的定义及其主要特征
- 2.二叉树的顺序存储结构和链式存储结构
- 3.二叉树的遍历
- 4.线索二叉树的基本概念和构造
#### （三）树、森林
- 1.树的存储结构
- 2.森林与二叉树的转换
- 3.树和森林的遍历
#### （四）树与二叉树的应用
- 1.哈夫曼树和哈夫曼编码
- 2.并查集及其应用
### 四、图
#### （一）图的基本概念
#### （二）图的存储及基本操作
- 1.邻接矩阵
- 2.邻接表
- 3.邻接多重表、十字链表
#### （三）图的遍历
- 1.深度优先搜索
- 2.广度优先搜索
#### （四）图的基本应用
- 1.最小生成树
- 2.最短路径
- 3.拓扑排序
- 4.关键路径
### 五、查找
#### （一）查找的基本概念
#### （二）顺序查找法
#### （三）分块查找法
#### （四）折半查找法
#### （五）树型查找
- 1.二叉树搜索树
- 2.平衡二叉树
- 3.红黑树
#### （六）B树及其基本操作、B+树的基本概念
#### （七）散列表hash
#### （八）字符串模式匹配
#### （九）查找算法的分析及其应用
### 六、排序
#### （一）排序的基本概念
#### （二）直接插入排序
#### （三）折半插入排序
#### （四）冒泡排序
#### （五）简单选择排序
#### （六）希尔排序（shell sort）
#### （七）快速排序
#### （八）堆排序
#### （九）二路归并排序
#### （十）基数排序
#### （十一）外部排序
#### （十二）排序算法的分析及其应用
|
