真题总结

主要记录各年主要涉及的知识点以及值得深思的地方

2014

1. 论述 算法的优劣标准 查找方式的优缺点
2. 循环队列满的条件
3. 根据一棵树的先根和后根来确定一棵树,可以引申到二叉树的前后续确定树
4. 扩充二叉树的证明题,这些路径长度,实际上也可引申到节点的比较次数
5. 用prim画出构造生成MST的过程
6. 流程图写出冒泡排序算法
7. 从大到小的堆排序 应该建立的是小顶堆

2015

1. 存储数据除了存储元素的值,还需要元素之间的关系
2. 论述 拓扑排序定义及其应用场景,哈夫曼树,哈夫曼编码
3. 循环队列的判空判满的表达式及其出队入队的伪代码,和出入队的数据变化
4. 利用kruskal求MST的过程
5. 流程图写出选择排序的算法
6. 构建散列表和BST,插入相同的关键字出现错误的情况

2016

1. 论述 评价算法,堆的定义,对比分析栈和队列 比较散列和BST 比较邻接矩阵和邻接表区别 树转换成二叉树的好处
2. 应用prim找MST
3. 应用dij找最短路

2017

1. 调整最小堆的操作
2. 给定节点个数,画出二叉树的所有形态
3. 用归纳法证明,包含n个分支节点的哈夫曼树,E(外路径长度)=I(内路径长度)+2n
4. 两个栈模拟一个队列
5. 论述 完全二叉树
6. dij找最短路

2018

1. 中后缀表达式转前缀
2. 广义表的操作
3. 哈夫曼树的合理性
4. 论述渐进复杂度分析,和O的数学定义 共享栈的定义 BST和散列的比较
5. 共享栈判空判满的条件,和入栈出栈的程序
6. 标出MST,求其中一些边的值域
7. 给出AOE网,要求画出来网络,并且求各个活动的最早最晚发生时间
8. 使用再散列法插入
9. 初始化最小值堆,调整的过程

2019

1. 给出具体不同规模下的运行时间,推算另一个规模的运行时间 注意这里可以将时间进行近似,没必要非常精确
2. 用一个队列实现栈的进出操作
3. 论述 简单环 最小支撑树
4. 利用kruskal求MST 缩短一条MST以外的边,判断MST是否需要更改
5. MST的唯一性 第二权值是否会出现在MST中

2020

1. 二分查找需要最多的比较次数,可以考虑其他几种查找的最坏比较次数,以及快排的比较次数
2. 论述 散列表定义 AVL树的定义
3. 流程图画字符串逆序的算法,利用栈和非空队列
4. AVL树的插入操作左右旋的
5. 用dij求解最短路时,其中边的取值范围
6. 各种排序算法以及特点的匹配
7. 用双亲表示法和孩子兄弟表示法来表示一棵树

2021

1. 具体衡量算法优劣性标准的解释
2. 循环队列的插入删除操作
3. 论述 算法的渐近性分析 递归过程中存储在栈中的信息 外节点的定义 外节点的路径长度
4. 多路合并的策略

2022

1. 链栈的实现方式
2. 几种数据结构的特点 链表,AVL,BST,Hash,Heap
3. 归并函数的具体代码思路,和归并的含义
4. 论述 的数学定义
5. 四个元素组成的小根堆形态个数
6. 根据给定的MST,求解未知边的值域
7. 改进Dij,求解最短路径的个数
8. 给定序列,判断使用排序的种类

2023

1. 开散列的装填因子
2. 抽象数据类型的定义
3. 哈夫曼的压缩率
4. 论述 的定义以及一个关系证明
5. 循环队列的出入队代码
6. 构建AVL树的操作,必须要万无一失
7. 大量点的Dij操作