电子与信息工程学院
学院概况

首页
学院概况
师资队伍
学科学位
科学研究
党建工作
招生就业
本科生培养
研究生培养


学院   > 招生就业   > 招生信息   > 正文


作者:无
时间:2007年10月16日 【浏览量:次】


2008年全日制硕士(数据结构)初试考试大纲

考试科目代码及名称: 数据结构  816

考查要点:

1、基本概念:理解什么是数据、数据对象、数据元素、数据结构、数据的逻辑结构与物理结构、抽象数据类型、算法及算法时间复杂度。

2、线性表的基本概念:线性表的顺序表示和实现、线性表的链表表示和实现、链表运算(线性链表、循环链表、双向链表)。

3、栈的特性、栈的基本运算、栈满及栈空条件、栈的应用(表达式计算、递归与栈); 队列的特性、队列的基本运算(循环队列中队头与队尾指针的表示,队满及队空条件,队列的链表实现,链式队列中的队头与队尾指针的表示、双向队列的插入与删除算法)、队列的应用。

4、串的特点、串的基本运算、串的模式匹配算法(简单算法及改进算法)。

5、数组的定义、数组的按行顺序存储与按列顺序存储地址计算、矩阵的压缩存储;

   广义表定义、长度、深度、表头、表尾,用图形表示广义表的存储结构,广义表的递归算法(包括复制、求深度、求长度等算法)。

6、树的定义、树的基本运算,二叉树定义、二叉树的性质及基本运算,完全二叉树的顺序存储、完全二叉树的双亲、子女和兄弟的位置,二叉树的前序、中序、后序遍历的递归算法及层序遍历算法,哈夫曼树的构造方法、哈夫曼编码、带权路径长度的计算。

7、图的定义与图的存储表示(邻接矩阵表示、      邻接表与逆邻接表表示,邻接多重表表示);深度优先遍历与广度优先遍历;   会画出用Prim算法构造最小生成树的过程;最短路径(单源最短路径、任意顶点间的最短路径);关键路径。

8、静态查找表的基本概念、静态查找的基本方法(顺序表、有序表、静态树表、索引顺序表的查找);动态查找表的基本概念、二叉查找树概念及查找算法、二叉排序树的基本概念及查找算法、B-树和B+树的基本概念、哈希表的基本概念、哈希函数的构造方法、冲突处理的方法、哈希表的查找算法及分析。

9、排序的基本概念:关键码、初始关键码排列、关键码比较次数、数据移动次数、稳定性、附加存储、内部排序、外部排序;

熟悉以下常用排序算法及稳定性、算法的复杂度:

插入排序、选择排序、快速排序、二路归并排序、堆排序。

考试总分:150

考试时间:3小时

考试方式:笔试

考试题型:填空(20分,占13%

选择(30分,占20%

简答(70分,占47%

算法与程序设计(30分,占20%

参考书目(包括书名、作者、出版社、出版时间):

主要参考书:

1. 数据结构(第二版C语言版). 严蔚敏等著,清华大学出版社,1997

         2. 数据结构(CC++描述)郑丽英等著,兰州大学出版社,2003