2015-2016学年第1学期数据结构期末考试复习提纲。
一、 题型：
1. 选择题（每空1分，共15分）
2. 填空题（每空1分，共15分）
3. 判断题（每题1分，共10分）
4. 算法填空题（每空2分，共10分）
说明：只涉及到线性结构的算法。
5. 应用题（每题10分，共50分）：
说明：栈、二叉树、图、查找、排序各一题，不要求写算法，只要求掌握算法思路，根据实际问题给出解题过程。
二、 考查的主要内容：
第1章概论（重点复习章节：1.1节，1.2节，1.4节）
掌握数据、数据对象、数据项、数据元素、数据结构等基本概念和术语，算法的时间复杂度的分析和表示方法。
第2章线性表（2.1节，2.2节，2.3.1节）
掌握线性表的逻辑结构、存储结构（顺序表、单链表）、操作（插入、删除、查找），每种算法的时间复杂度，顺序表和单链表的对比（知道什么情况下使用顺序表？什么情况下使用单链表？）
第3章栈和队列（3.1节，3.2节，3.4.1节，3.4.2节）
掌握栈的逻辑结构定义及操作特性；栈的顺序存储结构；栈的操作（push,pop，判断栈空栈满的条件）；栈有哪些应用？
掌握队列的逻辑结构定义及操作特性；队列的顺序存储结构——循环队列；循环队列的操作（入队、出队、判断队列为空/满的条件）；队列的应用。
第5章数组和广义表（5.1节，5.2节，5.3节，5.4节）
数组的定义、二维数组的顺序表示、矩阵的压缩存储（对称矩阵的压缩存储、稀疏矩阵的三元组顺序表存储思想）
广义表的定义，表头、表尾、表的长度和表的深度。
第6章树和二叉树（6.1节、6.2节、6.3.1节、6.6节）
树的基本概念和术语，二叉树的定义，二叉树与树的差别？
二叉树的五个特性；二叉树的顺序存储方式和二叉链表存储方式；遍历二叉树。
哈夫曼树和哈夫曼编码。
第7章图（7.1节、7.2.1节，7.2.2节，7.3节，7.4.3节，7.5.1节、7.6.1节）
图的定义及基本术语；图的邻接矩阵和邻接表存储结构；图的遍历（dfs，bfs）；
图的最小生成树算法（prim、kruskal）；拓扑排序；单源最短路径问题（dijkstra算法）
第9章查找（9.1.1节，9.1.2节，9.2.1节）
基本概念：什么是查找表？什么是关键字（主关键字、次关键字）？什么是静态查找表和动态查找表？
顺序表的查找和有序表的查找算法思想（查找过程）、性能分析（计算asl）、二者的对比。
什么是二叉排序树（又叫二叉查找树）？怎么建立二叉排序树？在二叉排序树上进行查找的过程？
第10章内排序（10.2节，10.3节，10.4节，10.5节，10.7节）
四类排序方法：1、插入类（直接插入排序、希尔排序）；2、交换类（冒泡法排序、快速排序）；3、选择类（简单选择排序、堆排序）；4、合并类（二路归并排序）
要求掌握每一种排序方法的算法思路（即排序过程）、算法的时间复杂度、空间复杂度及稳定性能。
数据结构复习提纲
软件学院数据结构与算法复习提纲。data structures and algorithms 概念 type,类型 一组值的集合。type,简单类型例如整数，因为它的值不含有子结构。aggregate type,复杂类型，一个记录含有多项信息。银行账户含有多项信息如姓名 地址 composite t...
数据结构复习提纲
第一章概论 1 数据结构的基本概念和术语。数据 数据元素 数据项 数据对象 数据结构等基本概念。数据结构的逻辑结构，存储结构及数据运算的含义及其相互关系。数据结构的四种逻辑结构及四种常用的存储表示方法。第二章算法分析技术。1 算法的描述和分析。无穷大阶的几种描述方法的区别。算法 算法的时间复杂度和空...
数据结构复习提纲
第一部分试题说明。1 试卷考试时间为90分钟。2 试题类型 选择题 20个，每题2分，共40分 简答题 6个，每题5分，共30分 和算法设计题 2个，每题15分，共30分 第二部分各章知识点。第1章绪论。1 数据结构的概念。2 数据结构的形式化表示方法 ds d，r 要求给定一个形式化表示，能够画出...