type
status
date
slug
summary
tags
category
icon
password
线性结构
1.各种排序模拟（第二轮）
2.分析时间复杂度
3.数组地址 行主映射 列主映射
4.比较数组链表优缺点区别、哈希跳表优缺点（多个角度 空间 结构 时间 某个优势） 栈和队列区别？ 模拟指针优点 复杂度记一记（简单）
5.栈 队列 模拟
6.hash映射存储？ m%k
2022
1.给定一个序列，写出冒泡排序，归并排序，选择排序第二趟的结果
2.给了下面两段程序，分别分析时间复杂度
3.有一个数组为a[10][20]，数组首地址是200，整数占4个字节，求a[4][5]的地址。当地址为400时，求对应的a[][]
200+(4*20+5)*4=540
1*20*4=80
a[2][10]
4.比较数组和链表的优缺点
2021
一、线性结构（20分）
1.行主映射和列主映射，一个二维数组A[20][30]的首地址为100，每个元素占据四个字节，采用行主映射的方式，A[2][3]的地址，给出地址300，给出当前元素在数组中的表示位置。
2.一组序列，有八个数，给出该组整数序列经过冒泡排序，选择排序，插入排序第二趟结束之后的整数序列。
3.已知矩阵（n*n个元素）的表示如下所示，"x"表示这里表示非零元素，其余表示零元素，请给出该矩阵在一维数组中存储时的映射公式。
4.组序列1，2，3，4，…，n依次进栈，出栈顺序为p1,p2,p3,…pn,若p1=n，请问pi=?
5.请比较跳表与HASH的区别与联系。
2020
1、入栈序列为ABCDE，是否可能存在BCAED和DBACE的出栈序列， 说明原因。
2、给出四维矩阵的映射公式。
3、给了一串序列，要求写出AVL树。
4、一个m叉的B-树，非叶子节点有k个，至少有多少个关键字。
5、简述拓扑排序的算法思想，并写出下图的所有拓扑序列。
层次结构
1.二叉树 高度 总结点个数 非叶节点个数 二叉搜索树 AVL树（平衡二叉树）
先序、中序、后序、层次遍历序列
2.霍夫曼编码（必考） 给数字 权重 两两最小组合 记得答全给出编码 A：001 B：010….
3. 最大（小）堆初始化 插入 删除
4.二叉搜索树 find伪代码
5.m-阶 B树（插入删除思想） 计算？ 高度h问关键字多少个 高度最大最小
2022
1.给定一个二叉树先序序列和中序序列，要求写出后序序列
2.给定8个字母出现的频率，建立哈夫曼树，并求每个字母的哈夫曼编码，要求频率小的在右边。
3.给定一个序列，问该完全二叉树是否是个最大堆。如果不是，请初始化成最大堆。
4.写出二叉搜索树find（const &theKey）的伪代码
2021
1.给定二叉树的前序遍历序列FGHK，后续遍历序列HKGF，请画出所有可能的二叉树，并给出这些二叉树中可能的二叉树有m个与二叉树中度为1的节点数量s之间的关系。
2.哈夫曼树的算法思想，给了一组序列（序列中元素出现的频度）。请构造哈夫曼树，并给出每个字母的编码。
3.给出一组序列（7个整数），在实现堆排序的过程中，需要按照元素递增顺序输出，请画出堆排序初始化的图示。
4.请说出B-树在元素插入过程中的算法思想。
5.若一颗m叉搜索树的树高为h，请分析该m叉搜索树的节点个数的范围。
2020
1、给出一串序列，利用线性探测解决冲突，写出散列表和删除一个数字之后的散列表。
2、n×n的反对角矩阵， a i , j a_{i,j}ai,j=0当i+j≠n+1时。
（1）写出一个4×4反对角矩阵。
（2）写出将反对角矩阵压缩到一个长度为n的数组中的映射公式。
3、给出一个二叉树的前序、中序遍历，要求写出后序遍历。
4、给出一串数字序列，分别写出删除两个最小数字后的堆。
网状结构
1.最小生成树prim/krusal（在这个算法中如何判定是否存在回路？）算法思想及模拟过程 时间复杂度 伪代码？可能 看一下吧
2.拓扑序列写出结果 Dijksta模拟过程求最短路径 算法思想 复杂图
3.BFS/DFS伪代码 伪代码证明连通性 思想 （不知道会不会考拓扑排序思想 伪代码）
2022
1.第一问写出prim算法核心思想，第二问用prim算法求出题目中给出的无向图的最小生成树（写出求解过程）
2.第一问，写出题目中给定的有向图的所有拓扑序列。
第二问
（i）使用动态规划思想的floyd算法求出该有向图每个顶点对之间的最短路径长度
（ii）写出A点到每个点的最短路径
3.写出图的BFS伪代码
2021
- Kruskal算法的算法思想，然后给了一个有向图的各边权重，求最小数生成树的过程。
- 给出一个有向图各边权重的表，请写出该有向图的一个拓扑序列，请说出Dijkstra算法思想，求出从A点出发的最短路径与最短路径长度。
- 请给出判断n个顶点的无向图是否为连通图的算法思想。
2020
用prim算法写出一个图的最小生成树。
算法题
排序（选择 插入 基数 堆 快速 冒泡 归并） 时间复杂度
链表上的操作 合并两个链表
基于树结构的操作（BFS/DFS、递归）
动态规划（背包 切割木棍 最长上升子序列 打家劫舍 矩阵乘法先后匹配） 贪心（导弹拦截）
2022
1.上台阶可以一次上一级，也可以一次上两级，用动态规划的思想求出上11级台阶有多少种走法。写出算法思想，c++实现，时间复杂度
2.中值快速排序，先从a[leftEnd]，a[（leftEnd+rightEnd）/2]，a[rightEnd]中挑一个大小适中的元素，以他为支点进行中值快速排序。以此类推，最终序列会变成有序。写出算法思想，c++实现，以及第一趟中值快速排序的结果。
给定序列：x x x x x x
2021
- 一元素大小依次递增的链表，存在重复元素，请设计算法去除链表中重复元素。
- （2014年研究生408研究生入学考试题）
算法设计要求给出算法思想，C++代码实现（必要处请给出注释），分析你所设计的算法的复杂度。
2020
1、将一串数字中所有的奇数移到偶数前面，编写程序利用C++实现，要求时间复杂度最低并分析你所写代码的时间复杂度。
时间复杂度为O(n)，空间复杂度为O(1)
2、将一棵二叉树的叶子节点存储在一个单向链表中，编写代码利用 C++实现，并分析复杂度。
节点结构如下：
lchild | data | rchild |
线性表 20
树 25
图 25
编程 30
编程
- 上台阶可以一次上一级，也可以一次上两级，用动态规划的思想求出上11级台阶有多少种走法。写出算法思想，c++实现，时间复杂度
- 已知一颗二叉树按顺序存储结构进行存储，设计一个算法， 求编号分别为i和j的两个结点的最近的公共祖先结点的值。
- 二叉树统计叶节点的个数
- 给定先序序列，按照该序列创建对应的二叉树，并输出该二叉树度为0,1和2的结点个数。
- 二叉树求高度
- 前序序列和中序序列创建树
背包问题
例：背包总容量为20
拦截导弹
打家劫舍
此处采用较慢的 递归
复杂度分析：
空间复杂度：O(n)【每个栈空间复杂度为O(1)】O(n*1)=O(n)
时间复杂度：O(2^n)
2023考前重点
矩阵 数组映射
给两个序列画树算法思想 伪代码
二叉树统计叶节点个数 度为1/2的节点个数 计算节点祖先 树的高度
拓扑排序思想 伪代码
制定一个贪婪算法，从左到右分布构造拓扑序列。每一步选择一个新定点加入序列中，选择新顶点的依据是贪婪准则：从剩余的顶点中选择一个顶点w，它没有这样的入边(v,w)，其中顶点v不在序列中。
如果算法失败，则说明有向图中含有回路。
图是否为连通图，图的连通构件，是否存在环路等算法思想和伪代码
Kruskal，Prim最小耗费生成树，Dijkstra，Floyd单源和多源最短路径算法的思想，计算过程，满足的特征等
动态规划 贪心算法 伪代码 时间复杂度
DFS BFS
附赠手写笔记
2023 数据结构回忆版
（From 考 bk 的老东西 爱来自 22 级 503）
线性结构
1.一个地址 4 字节 数组 A[12][20] A[0][0]=100 A[2][19]是哪个数 地址 500 是多少
2.上三角二维数组映射到一维数组的思想和映射函数
3.选择插入冒泡归并 一个数组 两次排序后的结果
4.给一个散列 求散列和查询次数
5.求程序段的时间复杂度
层次结构
1.最大堆的初始化和原地重排
2.给一个字符串霍夫曼树 给定一个字符串求频率 画霍夫曼树
3.Avl 插入一个元素 写出旋转过程和一般化公式做法
网状结构
1.克鲁斯卡尔算法思想 然后手写过程 （给出了边的权值和连接结点）
2.加权有向图求 floyd 算法的过程 矩阵表示 能不能有负边
3.判断加权有向图是否有回路算法思想
算法题
1.一个每个元素值都不同的树 输出值为 x 的结点所有祖先
2.一个线性表 A 存了学号加姓名 一个 B 存了学号加成绩 A 长度为 M B 长度为 N 学号在两表内单独递增 求学号相同时的姓名加成绩 时间复杂度要求为 O(M+N)
- 作者:Rainnn
- 链接:https://tangly1024.com/article/4e6d37c7-912d-43ea-89aa-ff0da416bfaa
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。