005计算机科学与技术学院考试大纲.docx

《005计算机科学与技术学院考试大纲.docx》由会员分享，可在线阅读，更多相关《005计算机科学与技术学院考试大纲.docx（3页珍藏版）》请在第一文库网上搜索。

1、计算机科学与技术学院硕士研究生招生考试考试大纲科目代码：880科目名称：数据结构考试范围：一、绪论1、考核知识点数据的逻辑结构与物理结构；抽象数据类型；算法及其度量。2、考核要求(1)理解数据结构的基本概念和术语；(2)掌握抽象数据类型的表示与实现；(3)掌握算法的基本概念和算法的性能分析方法。3、考核重点(1)数据的逻辑结构与物理结构；(2)算法时间复杂度性能分析的方法。二、线性表1、考核知识点线性表；顺序表的表示与实现；链表的表示与实现；顺序与链式存储的比较。2、考核要求(1)理解线性表的定义和逻辑结构特性；(2)掌握线性表的顺序存储方法和常用算法；(3)掌握线性表的链式存储方法和常用算法

2、；(4)了解用线性表表示一元多项式和稀疏多项式的方法考核重点(1)顺序存储结构与链式存储结构的区别；(2)顺序表和单链表的常用经典算法。三、栈和队列1、考核知识点栈与队列的特点；栈的递归算法；链队列；循环队列。2、考核要求(1)熟练掌握栈的类型定义、表示和基本操作的实现；(2)灵活运用栈的特性设计算法；(3)掌握递归算法的设计方法和设计思路；(4)熟练掌握队列的类型定义、表示和基本操作的实现考核重点(1)栈和队列的特性；(2)栈与队列基本操作的实现；(3)栈的递归算法应用。四、串1、考核知识点串，模式匹配算法。2、考核要求(1)掌握串类型的定义及其表示方法；(2)掌握串基本算法的实现方法；(3

3、)掌握KMP算法。3、考核重点KMP算法五、数组和广义表1、考核知识点数组；稀疏矩阵的压缩存储；广义表。2、考核要求(1)了解数组的定义和数组的顺序表示方法；(2)数组元素顺序存储的地址计算；(3)掌握特殊矩阵和稀疏矩阵的压缩存储方法；(4)了解广义表的定义和存储结构。考核重点(1)数组元素的地址计算方法；(2)矩阵的压缩存储；(3)广义表的基本性质。六、树和二叉树1、考核知识点二叉树的定义、性质与存储结构；二叉树的遍历及其应用；树与森林的表示与遍历；哈夫曼树与哈夫曼编码。2、考核要求(1)理解树和二叉树的定义、术语；(2)理解二叉树的基本性质；(3)理解二叉树存储结构；(4)理解二叉树的遍历

4、算法思想，掌握递归和非递归遍历算法实现；(5)掌握二叉树遍历算法的应用；(6)了解树、森林的存储方法及与二叉树间的转换方法；(7)掌握哈夫曼树及其应用。考核重点(1)二叉树的基本特性；(2)二叉树的遍历及其应用算法；(3)哈夫曼树及哈夫曼编码七、图1、考核知识点图的逻辑结构；邻接表与邻接矩阵；深度优先遍历；广度优先遍历；最小生成树、拓扑排序、关键路径、最短路径。2、考核要求(1)理解并掌握图的基本概念、术语和基本逻辑结构特征；(2)理解并掌握图的存储结构；(3)掌握图的深度优先和广度优先遍历算法；(4)掌握图结构的典型应用，如最小生成树、拓扑排序、关键路径、最短路径等。3、考核重点(1)图的逻

5、辑结构与存储方法；(2)图的深度优先、广度优先遍历算法；(3)最小生成树算法；(4)拓扑排序算法；(5)单源点最短路算法八、查找1、考核知识点顺序查找；折半查找；分块查找；二叉排序树；平衡二叉树；哈希表。2、考核要求(1)理解静态查找表、动态查找表和哈希查找的基本概念；(2)掌握静态查找表的各种查找方法如：顺序查找、折半查找、分块查找；(3)掌握二叉排序树与平衡二叉树；(4)掌握哈希表的概念、查找以及哈希函数的构造方与解决冲突的基本方法；(5)掌握各种查找算法的效率分析。3、考核重点(1)折半查找算法；(2)二叉排序树；(3)哈希表。九、排序1、考核知识点直接插入排序；希尔排序；冒泡排序；快速排序；堆排序；归并排序；基数排序。2、考核要求(1)理解排序的基本概念；(2)掌握基于插入思想的排序算法如：直接插入排序、希尔排序；(3)掌握基于交换思想的排序算法如：冒泡排序、快速排序；(4)掌握基于选择思想的排序算法如：简单选择排序、堆排序；(5)掌握其它排序算法如：归并排序、基数排序；(6)能够对各种排序算法进行分析比较。3、考核重点(1)快速排序算法及其应用；(2)堆排序算法；(3)归并排序算法。参考书目：数据结构(C语言版)严蔚敏吴伟民编著清华大学出版社