数据结构与算法考试大纲

《数据结构与算法考试大纲》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《数据结构》考试大纲I.考查目标考试目标是了解常见数据结构的概念，掌握数据结构的构造方法以及相应的算法思想，会对重点数据结构的操作方法和算法进行简单的伪代码编写。II.考试形式和试卷结构一、试卷总分及考试时间试卷总分为100分，考试时间180分钟。二、答题方式答题方式为闭卷、笔试。III．考查内容第一章、线性表1.线性表的逻辑结构2.线性表的顺序存储结构3.线性表的链式存储结构3.1单链表3.2循环链表3.3双向链表第二章、栈与队列1.栈1.1栈的基本概念1.2顺序栈1.3链式栈2.队列2.1队列的基本概念2.2链队列2.3循环队列——队列的顺序存储结构第三章、串1.

2、串类型的定义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树和森林与二叉树

3、的转换5.哈夫曼树与哈夫曼编码1.1哈夫曼树的基本概念1.2哈夫曼树构造算法1.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所有顶点之间的最短路径第八章、查找1.查找的基本概念2.静态表的查找2.1顺序查找2.2有序表的查找3.动态查找表3.1二叉排序树4.散列表4.1散列表的概念4.2构造散列函数的方法4.3处理冲突的方法第九章

4、、排序1.排序概述1.插入排序1.1直接插入排序1.2Shell排序2.交换排序2.1冒泡排序2.2快速排序3.选择排序3.1普通选择排序3.2堆排序4.归并排序IV主要参考书籍[1]唐宁九、游宏跃、朱宏、杨秋辉.数据结构与算法(C++版)。北京：清华大学出版社，2009.[2]严蔚敏,吴伟民.数据结构。北京：清华大学出版社 ，2007.