2017年大连海洋大学917数据结构复试考研大纲

　　考试科目：917数据结构

　　考试大纲

　　一、考试性质

　　《数据结构》课程考试是为大连海洋大学招收计算机科学与技术硕士专业学位研究生而设置的具有选拔性质的研究生考试复试科目，其目的是科学、公平、有效地测试考生是否具备继续攻读计算机科学与技术专业学术型硕士研究生所需要的基础知识和基本技能，评价的标准是高等学校计算机相关专业本科毕业生能达到的及格或及格以上水平，以利于我校择优选拔，确保计算机科学与技术专业学术型硕士研究生的招生质量。

　　二、考查目标

　　《数据结构》课程在考察课程基本知识、基本理论的同时，注重考查考生运用数据的逻辑结构和物理结构分析、解决实际问题的能力和算法的分析、设计及实现的能力。考生应能：

　　1．理解数据的逻辑结构和物理结构的概念。

　　2.熟练掌握各种逻辑结构上的基本操作，及这些基本操作基于不同物理结构的实现。

　　3.具有针对实际问题选择合适数据结构的能力。

　　4．熟练掌握查找、排序的基本概念及经典的查找、排序算法。

　　5．具有算法的分析、设计及其实现等方面的基本技能和科学作风。

　　三、考试形式和试卷结构

　　一、试卷满分及考试时间

　　本试卷满分为100分，考试时间为60分钟。

　　二、答题方式

　　答题方式为闭卷、笔试。

　　三、试卷题型结构

　　客观题10小题，每小题4分，共40分；主观题4大题，每小题15分，共60分；合计100分。

　　四、考察内容

　　第一章绪论

　　1.理解数据、数据元素、数据结构、抽象数据类型、算法等基本概念

　　2.掌握数据逻辑结构的概念及分类

　　3.掌握数据物理结构的概念及分类

　　4.了解算法描述规范以及如何对算法进行分析和评价的方法

　　第二章线性表

　　1.掌握线性表的逻辑结构、逻辑特性

　　2.掌握线性表的顺序存储结构及链接存储结构

　　3.掌握单链表、循环链表进行插入、删除和查找等基本操作的算法

　　4.了解双向链表进行插入、删除和查找等基本操作的算法

　　第三章栈和队列

　　1.掌握栈和队列的逻辑结构、逻辑特性

　　2.掌握栈和队列的物理结构

　　栈和队列的顺序存储、栈和队列的链接存储

　　3.掌握对栈和队列进行插入、删除等操作的相应算法

　　4.了解利用栈实现递归并解决实际问题的方法

　　第四章串

　　1.理解串的基本概念

　　2.掌握串的物理结构

　　串的顺序存储、串的链接存储

　　3.掌握串的基本运算

　　赋值、连接、求串长、取子串、求子串序号、插入、删除和置换等

　　4.了解各种运算在文本编辑中的应用

　　第五章数组

　　1.理解多维数组和稀疏矩阵的概念

　　2.了解多维数组的顺序存储

　　3.了解稀疏矩阵的压缩存储

　　第六章树和二叉树

　　1.理解树形结构的基本概念

　　树、森林、二叉树、满二叉树、完全二叉树、线索二叉树、哈夫曼（Huffman）树以及与树形结构相关的概念

　　2.掌握二叉树的性质

　　3.掌握树形结构的物理结构

　　二叉树的链式存储结构（二叉链表表示法）、完全二叉树的顺序存储结构、树和森林的顺序存储结构（双亲表示法）和链式存储结构（孩子兄弟表示法）

　　4.掌握树形结构的操作

　　二叉树的遍历方法（前序遍历法、中序遍历法和后序遍历法）、树/森林与二叉树之间的相互转换、树和森林的遍历方法（按宽度方向和按深度方向进行遍历的方法）、二叉树的线索化

　　5.掌握哈夫曼树的构造，求哈夫曼编码

　　第七章图

　　1.理解图的基本概念

　　2.掌握图的物理结构

　　图的相邻矩阵表示法、图的邻接表表示法、图的邻接多重表表示法、图的十字链表表示法

　　3.掌握图的遍历方法

　　图的宽度（广度）优先遍历、图的深度优先遍历

　　4.掌握图的操作

　　求图的生成树或生成森林、求带权图的最短路经、构造网络的最小生成树、对有向图进行拓扑排序

　　第八章查找

　　1.理解静态查找表、动态查找表和哈希表（hash）的基本概念

　　2.掌握静态查找表的查找方法

　　基于无序表的静态查找、基于有序表的静态查找、基于部分有序表的静态查找

　　3.掌握动态查找表的查找方法

　　基于二叉排序树的动态查找、基于平衡二叉排序树的动态查找等

　　4.掌握哈希函数的构造方法和解决冲突的方法

　　第九章内部排序

　　1.理解内部排序的基本概念

　　2.掌握几种典型的排序算法

　　直接插入排序、简单选择排序、起泡排序、快速排序、归并排序

　　3.掌握分析各种排序算法的时间复杂度和空间复杂度

　　4.了解分析各种排序算法的稳定性