计算机科学与技术考研 数据结构可能会问到的问题

总结了 涉及 计网 操作系统 数据结构 数据库 软件工程 程序语言等课程

个人觉得可能会问到的问题 部分问题过于简单或抽象就不写答案了

自己总结 漏洞疏忽可能比较多 口述答案

有错告知会改正 勿喷

数据结构

1. 数据结构的三要素 ：物理结构 逻辑结构 运算
2. 数据结构的逻辑结构与物理结构分为

逻辑结构：顺序存储 链式存储 索引存储 散列存储

物理结构：集合 线性 树 图

1. 算法的五大特征 :有穷性 确定性 可行性 输入 输出
2. 时间复杂度和空间复杂度是什么 :语句执行频度 占用内存空间
3. 什么时候用链表 什么时候用数组
4. 栈和队列的定义 循环队列的优点 利用率高 没有假溢出
5. 树的定义 二叉树 满二叉树 完全二叉树 存储结构

最多只有2个结点的树 除了叶子结点外都有2个结点 和满二叉树的序号一致

顺序存储 链式存储

1. 二叉树的非递归遍历

• 非递归先序遍历：1. 沿着根的左孩子，先访问，再入栈，直到左为空

  2. 栈顶出栈，有又子树，1。

• 非递归中序遍历：

  一直左入栈，出栈看右孩，有则1 无则2

  1. 沿着根的左孩子依次入栈，直到左孩子为空

  2. 栈顶元素出栈并访问，右孩子为空继续执行，若右孩子为空，接着入栈左孩子。

• 非递归后序遍历：

  1. 从根节点开始，入栈，沿着左子树搜索，直到没有左孩子。

  2. 如果有右子树，按同样的方法访问。

  3. 栈顶元素为空，要么右子树为空，要么右子树刚被访问完。（左子树已经被访问）

• 层次遍历：借助队列 根节点，左右节点依次入队。

1. 线索二叉树 : 解决方便寻找某种序列的前驱
2. 哈弗曼树 最优二叉树 带权路径最小的二叉树
3. 树的表示方法 树和森林的遍历

双亲表示法 孩子表示法 孩子兄弟表示法

二森先中树先后

1. 二叉排序树 删除二叉排序树

左＜根节点＜右 中序遍历是升序

删除：

叶节点直接删

有一个孩子直接代替

有俩孩子 用直接前驱或者后继

1. 图的组成 图的分类 什么是连通 边集和结点集
2. 图的存储方法

邻接表法 邻接矩阵法 十字链表法（有） 邻接多重表（无）

1. 图的深度优先遍历和广度优先遍历 栈/队列
2. 最小生成树（详细阐述）[贪心算法]

Prim算法：从某个顶点开始，依次加入当前结点集中路径最短的结点到结点集中，直到把所有的结点都加入进去。不依赖与边 时间复杂度O（V²） 适合稠密图

Kruskal算法：从最短的边开始，依次选择最短符合条件的边，直到所有的点都连通

不依赖与点 适合稀疏图 时间复杂度O（Elog2E）

1. 最短路径（详细阐述）

迪杰斯特卡算法：引进两个集合S和U。S的作用是记录已求出最短路径的顶点(以及相应的最短路径长度)，而U则是记录还未求出最短路径的顶点(以及该顶点到起点s的距离)

(1) 初始时，S只包含起点s；U包含除s外的其他顶点，且U中顶点的距离为"起点s到该顶点的距离"[例如，U中顶点v的距离为(s,v)的长度，然后s和v不相邻，则v的距离为∞]。

(2) 从U中选出"距离最短的顶点k"，并将顶点k加入到S中；同时，从U中移除顶点k。

(3) 更新U中各个顶点到起点s的距离。之所以更新U中顶点的距离，是由于上一步中确定了k是求出最短路径的顶点，从而可以利用k来更新其它顶点的距离；例如，(s,v)的距离可能大于(s,k)+(k,v)的距离。

弗洛伊德算法[动态规划]：通过图的权值矩阵，逐步将各点作为中间结点，看是否会比之前的路径更短。

1. 拓扑排序

由某个集合上的一个偏序得到该集合上的一个全序

应用于工程 或者 判断有向图是否有回路

1. 说一下堆 删除 插入 建堆

优先队列：取出的元素顺序是按照元素的优先权(关键字)大小,而不是元素进入队列的先后顺序。

优先队列的实现

数组、有序数组

链表、有序链表

堆：必须是完全二叉树 且任意一节点是其子树的最大值或者最小值

3. 堆的操作

* 插入：插入到最后一个元素，然后与父节点（parent/2）作比较，大则交换

* 删除：把最后一个元素替补根的位置，

找出较大的孩子（2parent）（2parent+1）换位置。

* 建堆：1. 顺序存入形成完全二叉树

2. 从最小的子树开始调整位置，使其左右子树都变成堆

1. 折半查找与分块查找

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列 O(log2n)

分块查找

1. B树与B+树，区别

1. B树：多路平衡查找树 m路 （5）

   除了根节点外，任何节点至少有m/2个分叉 且关键字数要在[m/2-1,m-1] [2,4]

   所有子树的高度都相同 所有的叶节点都出现在同一层次

2. B树的操作

   1. 插入：满了后 从中间裂开，把中间元素提到父节点，剩下元素放左右

   2. 删除：

   * 删非终端节点：把直接前驱或直接后继替代该元素

   * 删终端节点且左/右兄弟充足 用前驱/后继和的填补空缺

   * 当兄弟不够了 合并

3. B+树 :类似于分块查找和b树的结合 根节点指向放的是叶子节点的最大值

1. 哈希函数的构造方法 哈西函数解决冲突的方法 （Java HashSet？）

哈希表：关键字与存储地址直接相关

冲突的处理方法：

1. 拉链法

2. 线性探测法

3. 平方探测法0 1 -1 4 -4 9 -9…

4. 再散列法 多个哈希函数

1. 排序有哪些 时空复杂度是多少

   

2. 什么是分治算法 动态规划 贪心算法 回溯算法

分治算法：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破

分治的技术问题：子问题相互独立

分治算法的步骤：

1. 划分

2. 递归求解

3. 合并

应用：

1. 二分查找

2. 快速排序

3. 归并排序

动态规划：把原始的问题划分成一系列子问题，每求解一个子问题，将其结果存放在一个表中，以后用到的时候直接存取，不重复计算，自底向上的计算。[子问题的解要被重复利用] 自底向上

动态规划的条件：

1. 优化子结构：一个问题的优化解包含了子问题的优化解，缩小问题的集合

2. 重叠子问题

应用：

1. 矩阵乘法

2. 最长公共子序列

3. 弗洛伊德Floyd算法

贪心算法：做出当前看来最好的选择，希望通过做出局部优化达到全局优化

未必产生最优解 是自顶向下

贪心算法的条件：具有贪心选择性 优化子结构

应用：

1. 克鲁斯卡尔 Kruskal 每次选择一条权值最小的边，直到所有的点都连通

2. Prim算法： 从某个顶点开始，每次选择代价最小的新顶点纳入

3. 任务安排问题

4. 哈夫曼编码

回溯算法：把问题的解空间转化成了图或者树的结构表示，然后使用深度优先搜索策略进行遍历，遍历的过程中记录和寻找所有可行解或者最优解。

应用：

1. 背包问题

2. 旅行售货员问题

3. 迷宫问题

1. 递归和非递归的优缺点

递归的好处：代码相对非递归来说，更为简洁，并且思路清晰。

递归的坏处：由于递归需要系统堆栈，所以消耗空间要比非递归大很多。并且，如果递归深度太深，可能会导致系统奔溃。

非递归的优点：效率高，执行时间只会因为循环的次数增加而增加，没什么额外开销，也不会占用额外空间。

非递归的缺点：并不太容易理解，编写复杂问题时比较困难。

1. 自底向上和自顶向下

↑ 自底向上的分析，是从具体到抽象；

↓ 自顶向下的分析，是从抽象到具体