085211计算机技术硕士考试大纲
业务课（自命题）考试大纲
《数据结构》
Ⅰ考试性质
普通高等学校专业硕士生招生考试。
Ⅲ考试形式及题型分值
(4)考试形式：闭卷、笔试。
(6)题型分值：单项选择题、填空题、判断对错题、应用题、程序阅读题、算法设计题。满分150分，考试时间180分钟。
Ⅲ考试内容
要求掌握基本数据结构（线性表、栈与队列、数组、二叉树、图等）的特点及其不同实现，掌握常用的算法，同时对算法的时间复杂度有一定的分析能力，并考察学生能否运用数据结构解决实际问题的能力。具体知识点和考核要求如下：
(10)绪论
64掌握数据、数据元素、数据项、数据类型等基本概念和术语；
65掌握数据结构的四种逻辑结构和两种存储结构表示方法及其关系；
66理解算法五个要素；
68掌握算法设计的基本要求以及语句频度和算法时间复杂度的计算方法。
(11)线性表
69深刻理解线性结构及线性表；
70熟练掌握顺序表和单链表的组织方法；
71熟练掌握线性表在顺序存储结构和链式存储结构上的查找、插入及删除算法；
72了解顺序表与链表的特点；
73了解循环链表及双链表的组织方法和特点。
(12)栈和队列
75理解栈和队列的定义、特点及与线性表的异同；
78掌握顺序栈的组织方法及进栈、退栈等基本算法，弄清栈满和栈空的条件及利用栈解决简单的实际问题，如：数制转换、表达式求值等；
79掌握链栈的组织方法及进栈、退栈等基本算法；
80掌握链队列上实现的入队、出队等基本算法；
83掌握循环队列上实现的入队、出队等基本算法，及队满、队空的条件，弄清顺序队列的“假溢出”现象及其原因。
(13)串
84掌握串的有关概念和术语、串的逻辑结构和特点；
85掌握串的存储结构；
86掌握模式匹配的定义及KMP算法。
(14)数组和广义表
87掌握多维数组存在一维数组中的两种存储表示方法并综合运用数组在以行为主的存储结构中的地址计算方法；
89掌握对特殊矩阵(对称矩阵,下三角矩阵等)进行压缩存储时的下标变换公式；
90了解稀疏矩阵的三元组压缩存储表示方法及有关算法；
91理解并掌握广义表的定义、存储结构。
(15)树和二叉树
92理解树的概念并熟悉有关术语的含义（如孩子、兄弟、深度、度等概念）；
94深刻领会二叉树的定义和结构特性，了解相应的证明方法；
95理解常见的二叉树（如满二叉树、完全二叉树）的概念；
96深刻领会二叉树的顺序存储和链式存储结构；
97熟悉二叉树的遍历次序并熟练掌握遍历算法；
98掌握二叉树线索化的实质及线索化的过程；
99了解树和森林的定义、树的存储结构并掌握树、森林与二叉树之间的相互转换方法；
100掌握赫夫曼（Huffman）树的概念及其构造赫夫曼树的方法。
(16)图
101理解图的概念并熟悉有关术语（如：顶点、边、有向图、无向图、入度、出度、连通性与生成树等）；
102熟练掌握邻接矩阵表示法和邻接表表示法；
104掌握连通图遍历的基本思想和算法（深度优先和广度优先），能够给出两种遍历的顶点访问序列；
105掌握非连通图的遍历方法及图的连通分量的求法；
106理解最小生成树的概念及普里姆（Prim）算法和克鲁斯卡尔算法（Kruskal）,并能根据算法用图示法表示出给定网的一棵最小生成树的过程；
107了解AOE有向无环网的关键路径,关键活动的计算思路；
109掌握拓扑排序的基本思想，对给定的有向图（若拓扑序列存在）能够写出所有拓扑序列；
110掌握求单源点最短距离的狄克斯特拉（Dijkstra）算法。
(17)查找
111熟练掌握顺序查找算法、折半查找算法；
112掌握查找效率的计算方法-平均查找长度；
113理解二叉排序树的构造和查找算法；
116掌握哈希表、哈希函数的构造方法、以及处理冲突的方法。
(18)内部排序
117理解内部排序的定义和各种排序算法的基本思想及其特点；
124了解各种内部排序（插入，希尔，选择，冒泡，快速，堆，归并等排序）的排序过程及其依据的原则；
125一般了解排序方法“稳定”的含义；
126了解各种内部排序算法的优缺点、各种排序算法的时间花费。
