815-数据结构-考试大纲.docx

《815-数据结构-考试大纲.docx》由会员分享，可在线阅读，更多相关《815-数据结构-考试大纲.docx（3页珍藏版）》请在优知文库上搜索。

1、815数据结构考试大纲【指定参考书】严的敏.数据结构(C语言版).清华商校出版社.2007.9【考核目标】1 .理解数据结构的基本概念,比较系统地驾驭数据结构的理论基础学问：2 .熟识并驾驭税性表、栈、队列、巾、数组、广义表、树和二叉树、图等的逻辑结构、存储结何和对数据的蔚本运算：3 .熟识并驾取抽象数据类型的表示、实现和在程序设计中的作用：4 .理解算法的基本概念、特性、设计要求以及性能分析：5 .理解我找和排序的范本概念，州取各种查找和排序操作的蛆本忠坦和蜕法实现：6 .学会依据计算机所处理数据对象的特性,确定与之相适应的数据结构和存储结构,并设计相应的应用算法.【考核内容】一、*1,学犊

2、学问点数据结构：抽象数据类型；算法：算法的时间用难度：算法的空间困唯度。7 .考核要求(1)理解数据结构的基本概念和术谱：(2)驾驭抽象数据类型的表示与实现：(3)驾驭算法的班本概念和算法的性能分析方法，必需重点驾驭抽象数据类型的丧示：洋法的时间困难性能分析的方法。二、tttt1 .才松学问点线性表；依次表：链表：依次行储结构：透式存储结构，2 .考核要求(I)理解线性友的定义和逻辑结构特性：(2)驾驭线性去的依次存储方法和躯本操作算法实现；(3)驾驭线性表的锋式存储方法和基本操作尊法实现：(4)了解用线性表表示一元多项式和稀疏多项式的方法,并理解稀疏多项式的基本操作实现.必需曳点驾驭线性友的

3、依次存储结构、链式存储结构和依次表和各种林役的算法实现.三、栈和队列1 .考(学问点栈：递归：链队列：撕环队列，2 .X求(I)期熟鬻取校的类型定义、表示和基本操作的实现：(2)收徒运用栈的特性设计算法：(3)驾驭递归算法的设if-方法和一计思路：(4)娴熟驾驭队列的类型定义、表示和基本操作的实现必的曳点驾驭校和队列的特性、基本算法的实现以及应用.四、1 .考核学问点率.模式匹配算法.2 .1竦(1)驾驭率类型的定义及其表示方法；(2)驾驭小基本算法的实现方法：(3) 了解小的应用算法.必需武点驾驭中的表示方法、申的明本算法的实现，五、广义衰1 .考桂学问点数组：稀疏矩阵：压缩存储：广义表.2

4、 .考树K京(1) 了解数组的定义和数组的依次表示方法：(2)数组元素依次存储的地址il!Z:(3)驾驭特别矩阵和稀疏亚阵的压缩存储方法；(4) 了解广义表的定义和存储结肉.必需重点驾驭数组元素的地址计算方法：特别矩阵的压缩存谛：糅疏矩阵的压缩存储“六、树和二叉M1 .考核学问点二叉树的存储结构及其遍历的方法：二又构的线索化：哈夫曼树的构造方法及其端码的生成.2 .考桢要求(I)理解树和：叉树的定义、术语和族本逻辑结构特性：(2)理斛二叉树的基本性质：(3)理解二叉树存谛结构：(4)理解二叉树的遍历算法思想，骂驭递归和非递归遍历算法实现：(5)驾驭践索：乂树的她本概念和相应算法；(6) 了耕树

5、和森林的存储方法及与二叉树的之间的转换方法；(7)与驭哈夫变树及其应用.必羸空点驾驭二叉树的特性：二叉树的遍历：二叉树的线索化：哈夫蛇树及哈夫生编码究法实现。七、S1 .学糠学问点图的逻辑结构：邻接衣：深度优先遍历：广度优先遍历：最小生成树、拓扑排序、关键路径、最短路径.2 .考檀要求(I)理解并驾驭图的基本概念、术语和基本逻辑结构特征：(2)理解并驾驭图的存偌结构：(3)驾驭图的深度优先和广度优先遍历律法：(4)了解并与驭图结构的典型应用.如最小生成树、拓扑排序、关键路径、最短路径等.必需重点驾驭图的逻辑结构：图的存储方法：图的深度优先、广度优先遍历舞法：图的应用.八、三a1 .考犊学问点依

6、次查找；折半杳找；分块查找：二叉排序树；平衡二叉树：哈希表。2 .考糠要求(I)理解静态查找表、动态查找我和哈希IS我的基本概念：(2)驾驭静态传找表的各种杳找方法如；依次告找、折半查找、分块也找；(3)驾驭动态查找衣的各种交找方法如二叉排序树与平衡二叉树，B树等：(4)驾驭哈希表的概念和查找方法和哈布函数的构造方法、解决冲突的基本方法：(5)驾驭各种查找算法的效率分析.必需武点驾驭折半杳找、二叉排序树、平衡：叉树和哈希去的杳找算法的实现,九、排序1 .考桂学问点干脆插入排序：希尔排序：目泡排序：快速排序：堆排序:归并排序：基数排序.2 .考树K京(1)理解排序的基本概念：(2)驾驭基于插入思想的排序算法如：干脆插入排序、吊尔排序：(3)驾驭法于交换思想的排序算法如；祥泡排序、快速排序；(4)驾驭基于选择思想的排序算法如：简洁选择排序、堆持序；(5)与驭其它排序算法如：归并排序、基数排序：(6)能铭对各种排序算法进行分析比较.必需求点驾驭插入排序、快速持序、堆排序、合并排序、班数排序等算法的设计思此.【考核方式】笔试