川大计算机考研知识点总结
第三部分 栈和队列
▲知识点：基本定义、基本操作、这两种数据结构的基本运用
栈：后进先出，只允许在栈顶操作
队列：先进先出，队尾入队，队首出队
循环队列：假溢出现象
▲基本操作：
栈：初始化、入栈、出栈、取栈顶
队列：初始化、出队、入队、取队头
▲考点：
1、基本概念
给定一个入栈或者是出栈序列判断是否可能
组合栈和队列的操作判断栈或是队列的容量
满、空 等状态的判断条件
2、用栈或是队列完成某些操作：
★用两个栈模拟一个队列操作
★用一个数组实现两个栈
★循环队列
★用栈判断括号匹配
★用栈做后缀式转中缀式
第四部分 排序
▲主要知识点：
1、基本定义：排序、稳定性、排序算法的分类
2、排序：将一个给定的无序序列按照需求排成有序序列。
3、稳定性：经过排序处理后，元素之间的相对关系不改变
4、分类：
插入：直接插入排序、折半插入排序、缩小增量排序
交换排序：冒泡、快速排序
选择排序：简单选择排序、堆排序
归并排序：二路归并排序
基数排序：桶排序
内部排序
外部排序
▲本章考点：
各种算法的时间复杂度分析
给定一个序列给出算法的执行步骤
基本概念的判断
最优、最坏、平均情况的比较和分析(时间复杂度，出现的条件)
第五部分 查找
▲基本概念：
1、查找的定义、顺序查找、二分查找、二叉排序树、平衡二叉树、散列表(装填因子)、B树
查找算法的评价：平均查找长度ASL
顺序查找：平均查找长度、
折半查找：前提是代查找的序列是有序的
时间复杂度、平均查找长度(记住结论即可，但是对于一个给定的值需要会计算)
分块查找：块间有序，块内无序
2、二叉排序树：
Key(左)
基本操作：查找、插入、构造、删除(手工调整过程)
3、平衡二叉树：左右子树高度差的绝对值不超过1。
基本操作：初始化、平衡调整、
散列表：
散列表的建立和冲突解决办法(直接地址法、数字拆分法、平方取中法、除数留余法、开放地址法、链地址法)
4、B树的基本操作：
查找、插入、删除(如何调整)