山东航空学院考研招生考试数据结构科目考试大纲

站在新的起点上，每一位怀揣梦想的考生都在为即将到来的硕士研究生入学考试做着充分的准备。作为一门重要的专业基础课程，数据结构不仅是计算机科学的核心组成部分，也是山东航空学院硕士研究生招生考试中的重要科目之一。为了让各位考生能够更加清晰地了解数据结构科目的考试大纲，本文将对其进行详尽的介绍，助力大家高效备考。

一、考试要求
《数据结构》考试大纲适用于山东航空学院电子信息（计算机技术）硕士专业学位研究生入学考试。《数据结构》科目考试要求考生掌握数据结构的基本概念、基本原理和基本方法。掌握数据的逻辑结构、存储结构及基本操作的实现，能够对算法进行基本的时间复杂度与空间复杂度的分析。能够运用数据结构基本原理和方法进行问题的分析与求解，具备采用C或C++语言设计与实现算法的能力。

二、考试内容
1.绪论
①主要知识点：数据的逻辑结构与物理结构；抽象数据类型；算法及其性能度量。
②重点：数据的逻辑结构与物理结构；算法时间复杂度的分析方法。
2.线性表
①主要知识点：线性表；线性表的顺序表示和实现；线性表的链式表示和实现；顺序存储与链式存储的比较。
②重点：顺序存储结构与链式存储结构的区别；顺序表和单链表的常用算法。
3.栈和队列

①主要知识点：栈与队列的基本操作和特点；栈表示和实现；栈与递归算法；链队列；循环队列；栈和队列的应用。
②重点：栈和队列的特点；栈与队列基本操作的实现；栈与递归算法的应用。
4.串
①主要知识点：串的基本操作，串的模式匹配算法。
②重点：KMP算法。
5.数组和广义表
①主要知识点：稀疏矩阵的压缩存储；广义表。
②重点：数组元素的地址计算方法；矩阵的压缩存储；广义表的基本性质。
6.树和二叉树
①主要知识点：二叉树的定义、性质与存储结构；二叉树的遍历及其应用；树与森林的表示与遍历；赫夫曼树与赫夫曼编码。
②重点：二叉树的性质；二叉树的遍历及其应用算法；赫夫曼树及赫夫曼编码。
7.图
①主要知识点：图的逻辑结构；邻接矩阵与邻接表；深度优先遍历；广度优先遍历；最小生成树、拓扑排序、关键路径、最短路径。

②重点：图的逻辑结构与常用存储方法；图的深度优先、广度优先遍历算法；最小生成树算法；拓扑排序算法；关键路径算法；最短路径算法。
8.查找
①主要知识点：顺序查找；折半查找；分块查找；二叉排序树；平衡二叉树；哈希表。
②重点：折半查找算法；二叉排序树；哈希表。
9.排序
①主要知识点：直接插入排序；希尔排序；冒泡排序；快速排序；简单选择排序；堆排序；归并排序；基数排序；各种内部排序算法的比较。
②重点：快速排序算法及其应用；堆排序算法；归并排序算法。

三、考试时间
考试形式为闭卷笔试，考试时间为3小时，满分为150分。

四、参考书目
《数据结构（C语言版）》，严蔚敏、吴伟民编著，清华大学出版社，2007年。