数据结构2016复习60学时汇编.ppt

数据结构复习提纲 2016-2017-1 2016年12月 单项选择题 30分 填空题 15分 作图题 20分 应用题 27分 算法题 8分 第一章 绪论 1.基本概念和术语 2.数据结构有哪些种类？每种结构的特点？ 3.算法和算法分析，算法效率的度量方法， 重点掌握时间复杂度的计算，语句频度的 计算。 第二章 线性表 1.线性表的类型定义 2.线性表的顺序表示与实现 掌握顺序存储的特点及存储地址的计算,插 入、删除结点操作的实现 3.线性表的链式表示和实现 掌握链式结构的特点、插入、删除操作时指针的变化情况及顺序。 4.各种操作的算法时间复杂度的计算。 5.掌握线性表的常见操作的算法实现。 第三章 栈和队列 1.栈 掌握栈的定义、特点、顺序栈中指针的操 作特点，顺序栈的入栈、出栈操作。 2.队列 掌握队列的定义、特点，循环队列的判 空、判满条件，入队、出队操作，循环 队列的长度？ 掌握链队列的入队、出队操作。 第四章 串 1.串类型的定义 2.串的表示和基本操作。 第五章 数组和广义表 1.数组的定义 2.数组的顺序表示和实现 掌握行主序、列主序的存储位置的计算。 3.矩阵的压缩存储 掌握特殊矩阵的元素存储位置的计算。 4.广义表的定义 掌握广义表的定义、特点及广义表求表头 和表尾的操作。 第六章 树和二叉树 1.树的定义和基本术语 2. 二叉树 二叉树概念，对二叉树的五个性质会灵活运用，满二叉 树和完全二叉树的特点。 3.遍历二叉树 根据二叉树会写出先序、中序、后序遍历序列； 已知相应的遍历顺序，能够画出相应的二叉树； 4.树和森林 掌握树、二叉树、森林之间的相互转换； 掌握树、森林的遍历方法； 5.赫夫曼树（哈夫曼树）及其应用 掌握赫夫曼树的定义、特点； 掌握赫夫曼树的构造过程、赫夫曼编码的求解。 第七章 图 1. 图的定义和术语 2. 图的存储结构 掌握图的邻接矩阵和邻接表的存贮结构，可以根据图画出相应的存储实现，也可以根据存储实现画出相应的图。 3. 图的遍历 掌握图的遍历序列，可以根据图的邻接表存储方法得到图的遍历序列；深度优先生成树，广度优先生成树。 4. 掌握Prim（普里姆）、Kruskal（克鲁斯卡尔）算法构造最小生成树的思想及过程。 5. 有向无环图及其应用 掌握AOV-网的特点并能够写出其所有的拓扑排序序列； 掌握AOE-网的特点，并能求解工程完工的最短时间、关键路径、每项活动（或事件）最早及最晚发生时间。 第九章 查找 1.掌握查找表的逻辑结构及动态、静态查找表的特点和区别; 2.静态查找表 掌握顺序表查找的查找思想及性能分析； 掌握折半查找的特点及查找过程中指针的变化情况，二叉判定树，平均查找长度分析； 3.动态查找表 掌握二叉排序树的定义、特点及构造方法； 掌握平衡二叉树的概念、特点； 4.哈希表 根据已知的哈希函数和解决冲突的方法，构造哈希表，并求等概率下查找成功和查找不成功时的平均查找长度； 第十章 内部排序 1.掌握各种排序方法的算法思想（冒泡排序、 选择排序、希尔排序、快速排序、堆排序、 2-路归并），优点及时间复杂度。 2.对给定的待排序列，按某种排序方法，可 以写出每趟排序后的结果。