数据结构与算法 考试大纲

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

1、《数据结构与算法》考试大纲题型分布：(1)选择题：15题，每题2分，共30分(2)填空题：10空，每空2分，共20分(3)简答题：4小题，每题6-8分，共30分(4)设计题：2小题，每题10分，共20分第1章绪论(1)数据、数据元素、数据项、数据类型、抽象数据类型等基本概念和术语的含义；(2)数据结构的四种逻辑结构和两种存储结构的表示方法，逻辑结构和存储结构之间的关系；(3)算法五个特性的确切含义；（有穷、确定、可行、输入、输出）(4)算法设计的基本要求（正确、健壮、可读、高效）以及计算语句频度和算法时间复杂度的方法

2、。第2章线性表(1)线性结构的特点以及线性表的概念；(2)顺序表和单链表的表示方法；(3)线性表在顺序存储结构和链式存储结构上的插入、查找和删除等基本操作；(4)顺序表与链表的区别与优缺点；(5)循环链表和双链表的表示方法及特点；（了解）(6)线性表的应用：一元多项式的表示及相加。（了解）第3章栈和队列(1)栈和队列的定义、特点及与线性表的区别；(2)顺序栈的表示方法与进栈、出栈等基本操作；(3)链栈的表示方法与进栈、出栈等基本操作；(4)熟悉判断栈满和判断栈空的条件；(5)栈的应用：数制转换、表达式求值等；(6)链

3、队列的表示方法与入队、出队等基本操作；(7)循环队列的表示方法与入队、出队等基本操作；(8)判断队满和判断队空的条件；(9)使用循环队列解决顺序队列的“假溢出”。第4章串（不作考试要求）3第5章递归(1)递归的定义(2)递归调用的实现原理(3)递归算法的设计第6章数组和广义表（不作考试要求）第7章树和二叉树(1)树的概念和有关术语的含义（如孩子、兄弟、度、深度等概念）；(2)二叉树的定义和特征；(3)满二叉树、完全二叉树的概念；(4)二叉树的顺序存储结构和链式存储结构；(5)二叉树的先序、中序、后序遍历；(6)线索二

4、叉树的基本概念与线索化的过程；（了解）(7)树和森林的定义，树的存储结构；(8)树的带权路径长度、赫夫曼（Huffman）树的构造、赫夫曼编码。第8章图(1)图的概念及有关术语（如：顶点、边、有向图、无向图、入度、出度、连通性与生成树等）；(2)图的存储结构：邻接矩阵、邻接表；(3)图的遍历：深度优先搜索、广度优先搜索；(4)最小生成树的概念及构造最小生成树的算法：普里姆（Prim）算法、克鲁斯卡尔算法（Kruskal）,能根据算法画出构造最小生成树的过程；(5)拓扑排序的方法，对给定的有向图构造其顶点的拓扑有序序列

5、；(6)迪杰斯特拉（Dijkstra）算法求解单源点的最短路径。（了解）第9章查找(1)查找的基本概念；(2)顺序查找算法；(3)折半查找算法；(4)查找效率的计算方法即平均查找长度；(5)二叉排序树的构造过程与查找过程；(6)哈希表的基本概念、哈希函数的构造方法、处理冲突的方法（如开放定址法、链地址法等）。3第10章内排序(1)排序的基本概念；(2)排序方法“稳定”的含义；(3)插入排序：直接插入排序、希尔排序（了解）；(4)交换排序：冒泡排序、快速排序；(5)选择排序：简单选择排序、堆排序（了解）；(6)归并排序

6、：2-路归并排序；(7)以上各种排序算法的基本思想、排序过程；(8)以上各种排序算法的比较及时间复杂度。第11章外排序（不作考试要求）第12章文件（不作考试要求）第13章采用面向对象的方法描述算法（不作考试要求）3