数据结构通关指南

白忠建老师的考前划重点

考试范围 教材全部
机考 编码实现算法
题量两个小时

第一章：了解时间复杂度 空间复杂度，理解题目的意思是什么就行

第二章：线性表

概念掌握 ：逻辑结构（唯一前驱，唯一后继）和存储结构（数组存储，链式结构链表）

掌握线性表的插入和删除，查找，排序（考虑边界条件

长度为n顺序表，插入位置从1开始计，可插入1到n+1，删除范围从1到n

链表：头节点和头指针了解区别

第三章：栈和队列

栈 后进先出 教材p89栈消除递归 push pop IsEmpty 三大函数 树图深度搜索

队列 先进先出 进队 出队 判断是否为空 树图广度搜索

第四章：串

BF算法 暴力搜索字串算法

KMP算法不考

第五章：数组和广义表

广义表不管

数组：十字链表表示法

第六章：树

二叉树的表示法：二叉链表的表示法

先序中序后序遍历

先序伪代码： 
判空
return
visit
递归访问L
递归访问R

了解非递归遍历（）看我博客https://www.cnblogs.com/ch3n/p/18205148

树的广度优先遍历 用 队列

掌握 兄弟节点表示法 转化为 二叉树 还有了解他的先根遍历（先序）和后根遍历（中序）

哈夫曼树掌握 根据数据 生成哈夫曼树 得到哈夫曼编码

第七章：图

图的概念

图掌握 邻阶矩阵表示法 邻接表

图的DFS BFS 掌握思想，不要求代码

了解最小生成树的算法prim 和 克鲁斯卡尔算法

拓扑排序 关键路径的计算 起点到终点计算每个时间最早开始时间 从终点到起点计算最晚开始时间 从起点到终点计算每条边最早开始时间

从终点到起点倒算每条边的最晚开始时间 如果最早和最晚时间相等，就是关键路径 ，使用表格法，来计算

贪心算法 迪杰斯特拉算法 掌握精髓 通过算法找到最短路径

第八章：查找

树型查找 二叉排序树和二叉平衡树的原理 查找过程 二叉平衡树概念 如何左旋和右旋 旋转的原理

hash函数构造，比如对质数取余，冲突的解决（再hash，链值法）

第九章：排序

掌握每一种算法的思路 复杂的不要求编码

其他老师的考前划重点

23级的数据结构真题(回忆版)

早上
1.将顺序表T中所有元素插入L中
2.利用队列实现层次遍历
3.将键值数组所有值插入Hash表HT中
4.输出最小生成树
5.求图中某个顶点的出度

下午（记不清题目顺序了，只记得考了下面几种类型）
头插法尾插法
栈实现树的前中后序遍历
迪杰斯特拉 弗洛伊德算法
prim和克鲁斯卡尔算法
关键路径问题(填空题，只需要了解算法思路就行，不用写代码)
简单的冒泡排序
图的入度