国防科学技术大学2017年《数据结构

国防科学技术大学2017年《数据结构 国防科学技术大学2017年《数据结构》硕士考试大纲 一.考试要求 数据结构主要考查学生对数据结构的基本概念、基本原理和基本方法的掌握；对数据的逻辑结构、存储结构及基本操作的掌握；运用数据结构基本原理和方法进行问题的分析与求解，设计与实现算法的能力。 二、考试内容 1．数据结构概述 数据结构的基本概念和术语，抽象数据类型的表示，算法时空复杂性的分析和度量方法。 2．线性表 线性表的概念，线性表的顺序表示和实现，线性表的链式表示和实现以及相应算法。 3．栈和队列 栈的定义、特点及栈的表示和实现，队列的定义、特点、队列的表示和实现，桟和队列的基本运算，桟和队列的应用。 4．串 串的基本概念、存储结构、基本运算，字符串的模式匹配算法。 5．数组和广义表 数组的逻辑结构定义和存储方法，特殊矩阵和稀疏矩阵的压缩存储，广义表的定义和存储结构。 6．树与二叉树 树、二叉树和森林的定义、基本术语和存储结构，树、二叉树以及森林的遍历，线索二叉树，森林与二叉树的转换，赫夫曼树和赫夫曼编码。 7．图 图的基本概念和图的存储表示，图的深度、广度优先搜索，图的连通性问题，有向无环图及其应用，最短路径。 8．查找 查找的基本概念，顺序查找、折半查找、分块查找，二叉排序树的表示、搜索、插入、删除算法及其性能分析方法，平衡二叉树的构造、性能分析方法，B-树、B+树的搜索和构造方法；散列法，包括散列函数的构造、解决冲突的方法。 9．排序 排序的基本概念，插入排序、交换排序、选择排序、归并排序、基数排序等排序方法及其性能分析方法。 三、考试形式 考试形式为闭卷、笔试，考试时间为3小时，满分150分。 题型包括：选择题、简答题、编写算法题、综合题等。 四、参考目 1．《数据结构》（c语言版）．严蔚敏等编．清华大学出版社，2011。文章来源：文彦考研