搜索
数据结构与算法考试大纲一、参考教材唐宁九、游宏跃、朱宏、杨秋辉主编，数据结构与算法(C++版)，清华出版社，2009年二、主要内容课程要求：了解常见数据结构的概念，掌握数据结构的构造方法以及相应的算法思想，会对重点数据结构的操作方法和算法进行简单的伪代码编写。第一章、绪论重点：数据结构的基本概念，算法的基本概念，算法的时间复杂度以及空间复杂度的计算。1．数据结构的基本概念1.1数据1.2数据元素与数据项1.3数据结构2．算法与算法分析2.1算法2.2算法分析第二章、线性表重点：线性表的顺序存储和链式存储结构，链式存储结构中的单链表、循环链表以及双向链表的查找、插入以及删除操作。1.线性表的逻辑结构2.线性表的顺序存储结构3.线性表的链式存储结构3.1单链表3.2循环链表3.3双向链表第三章、栈与队列重点：栈与队列的概念，二者的区别，栈数据中的查找、出栈和入栈操作，队列的查找、插入和删除。1.栈1.1栈的基本概念1.2顺序栈1.3链式栈2.队列2.1队列的基本概念2.2链队列2.3循环队列——队列的顺序存储结构第四章、串重点：理解串这种数据结构，知道简单字符串匹配、首尾字符串模式匹配以及KMP匹配算法的思想。1.串类型的定义2.字符串的实现3.字符串模式匹配算法3.1简单字符串模式匹配算法3.2首尾字符串模式匹配算法3.3KMP模式匹配算法第五章、数组和广义表重点：数组与广义表的概念、特殊矩阵(特别是稀疏矩阵)的表示方法、广义表的存储结构，广义表的长度和深度。1.数组1.1数组的基本概念1.2数组的顺序存储方式2.矩阵2.1矩阵的定义和操作2.2特殊矩阵2.3稀疏矩阵3.广义表3.1基本概念3.2广义表的存储结构第六章、树和二叉树重点：树的定义，二叉树的性质，二叉树的遍历(前序、中序、后序、层次)，哈夫曼树的定义和构造。1.树的基本概念1.1树的定义1.2基本术语2.二叉树2.1二叉树的定义2.2二叉树的性质2.3二叉树的存储结构3.二叉树的遍历3.1遍历的定义3.2遍历算法4.树和森林4.1树的存储表示4.2森林的存储表示4.3树和森林的遍历4.4树和森林与二叉树的转换5.哈夫曼树与哈夫曼编码5.1哈夫曼树的基本概念5.2哈夫曼树构造算法5.3哈夫曼树编码第七章、图重点：图的邻接矩阵，邻接表表示方法，图的遍历，图的最小代价生成树算法，有向无环图的拓扑排序算法，关键路径以及图中顶点的最短路径问题。1.图的定义和术语2.图的存储表示2.1邻接矩阵2.2邻接表3.图的遍历3.1深度优先搜索3.2广度优先搜索4.图的最小代价生成树4.1Prim算法4.2Kruskal算法5.有向无环图的应用5.1拓扑排序5.2关键路径6.最短路径问题6.1单源点最短路径6.2所有顶点之间的最短路径第八章、查找重点：静态表查找与动态查找表、二叉排序树、散列表（hash表）。1.查找的基本概念2.静态表的查找2.1顺序查找2.2有序表的查找3.动态查找表3.1二叉排序树4.散列表4.1散列表的概念4.2构造散列函数的方法4.3处理冲突的方法第九章、排序重点：插入排序、交换排序、选择排序、归并排序的思想，各种排序算法的时间复杂度以及空间复杂度。1.排序概述2.插入排序2.1直接插入排序2.2Shell排序3.交换排序3.1冒泡排序3.2快速排序4.选择排序4.1普通选择排序4.2堆排序5.归并排序6.各种内部排序算法讨论第十章、文件重点:顺序文件、索引文件和散列文件。1.文件的常用文件结构1.1顺序文件1.2索引文件1.3散列文件第十一章、常用算法重点：了解贪心算法、递归算法、分治算法和动态规划算法的思想1.算法设计1.1递归算法1.2分治算法1.3动态规划算法1.4贪心算法