江苏自动化研究所2011数据结构与程序设计考研大纲

江苏自动化研究所硕士研究生入开云kaiyun(中国)考试数据结构与程序设计考试大纲

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

　　(一)、数据结构部分

　　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、内排序

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