江苏自动化研究所硕士研究生入学考试数据结构与程序设计考试大纲

　　一、命题范围及考查的知识点

　　(一)、数据结构部分

　　1、概述

　　(1)数据的逻辑结构与存储结构的基本概念;

　　(2)算法的定义、基本性质以及算法分析的基本概念，包括采用大形式表示时间或空间复杂度。

　　2、线性表

　　(1)线性关系、线性表的定义，线性表的基本操作;

　　(2)线性表的顺序存储结构与链式存储结构(包括单链表、循环链表和双向链表)的构造原理;

　　(3)在以上两种存储结构的基础上对线性表实施的基本操作，包括顺序表的插入和删除、链表的建立、插入和删除、检索等操作对应的算法设计(含递归算法的设计)。

　　3、堆栈与队列

　　(1)堆栈与队列(含循环队列)的基本概念、基本操作;

　　(2)堆栈与队列的顺序存储结构与链式存储结构的构造原理;

　　(3)在不同存储结构的基础上对堆栈与队列实施插入与删除等基本操作。

　　4、树与二叉树

　　(1)树与二叉树的基本概念，基本特征、名词术语;

　　(2)完全二叉树、满二叉树的概念、二叉树的基本性质;

　　(3)二叉树的顺序存储结构与二叉链表存储结构的构造原理、二叉树的前序遍历、中序遍历、后序遍历和按层次遍历算法(重点为非递归算法)以及利用遍历解决有关二叉树的其它操作;

　　(4)线索二叉树的基本概念以及构造原理;

　　(5)二叉排序树的基本概念、建立(插入)和查找，在二叉排序树中查找结点的平均查找长度ASL。

　　5、图

　　(1)图的基本概念、名词术语;

　　(2)邻接矩阵存储方法和邻接表存储方法的基本构造原理与特点;

　　(3)图的深度优先搜索和广度优先搜索的过程，图的遍历的基本作用;

　　(4)最小生成树及最短路径的特点、求解过程，拓扑排序及其目的。

　　6、文件及查找

　　(1)顺序查找法、折半查找法以及查找过程对应的“判定树”的构造;

　　(2)索引文件的基本概念;

　　(3)B-树与B+树的构造以及构造上异同，B-树的插入和查找;

　　(4)散列文件的特点，散列函数和散列冲突的概念，处理散列冲突的方法以及散列文件的查找。

　　7、内排序

　　插入排序、选择排序、泡排序、快速排序、堆积排序(大顶堆积)和二路归并排序法等排序方法的排序原理、规律和特点。