考研复试问题总结-数据结构（1）

1. 说一下你对数据结构的理解

我觉得数据结构不仅仅是存数据的“容器”，更是一种思维方式。其实，在我们写程序时，经常会遇到各种各样的数据操作需求，而不同的数据结构能解决问题的效率和方式都不一样，所以选择合适的数据结构非常重要。

举个例子，如果你的程序主要操作是查找，那你可能会选用数组或者哈希表，因为它们支持快速的随机访问；但如果你的操作更多是插入和删除，链表或平衡树可能就更合适，因为它们在这些操作上的开销较低。同时，如果数据本身具有层次结构，比如文件系统或组织架构，那么用树结构能更直观地表示这种关系，而如果数据之间的关系比较复杂，比如社交网络的关系，那图就更适合。

另外，我们在选择数据结构时，还需要考虑算法的时间复杂度和空间复杂度。很多时候为了提高查找效率，我们可能会用更多的内存，比如哈希表就是这样一个典型的例子。还有，具体应用场景也会影响我们的选择：比如在实时性要求高的系统中，我们可能需要那些能提供稳定性能的数据结构；而在对数据动态扩展性要求高的场景中，灵活的结构如链表或者动态数组会更好。

总的来说，选择数据结构其实是一个权衡问题，需要根据具体操作（查找、插入、删除等）、数据规模、内存限制以及业务场景来做出合理选择，就像选工具一样，每种工具都有最适合的应用场景

2. 数据结构在计算机网络和操作系统中的应用

老师好，我从两个学科领域分别说明数据结构的核心应用：

计算机网络方面​

1. ​路由表存储：使用哈希表快速定位目的 IP 对应的下一跳节点
2. ​流量控制：滑动窗口机制依赖循环队列管理待发送的数据包序列，接收方通过指针移动控制窗口大小

操作系统方面​

1. ​进程调度：优先级队列（通常用堆实现）管理就绪进程
2. ​内存管理：
   • 页表采用哈希表加速虚拟地址到物理页框的映射
   • 空闲内存管理使用双向链表合并相邻空闲块
3. ​同步机制：信号量通过等待队列（链表实现）记录阻塞进程，PV 操作涉及队列的入队/出队原子操作

3. 链表和数组区别

---

老师，我来简要说说链表和数组的区别：​​

第一，存储结构不同。
数组存储在连续的内存块中，元素通过索引直接访问（时间复杂度 O(1)），但中间插入或删除元素需要移动后续所有元素（时间复杂度 O(n)）。链表则由分散的内存节点组成，每个节点包含数据和指向下一个节点的指针，插入和删除只需调整相邻指针（时间复杂度O(1)），但访问第 k 个元素必须从头部开始遍历（时间复杂度O(n)）。

第二，内存占用不同。​
数组需预分配固定大小，可能导致内存浪费（如申请过大空间但实际元素少）；链表动态按需分配节点，内存利用率更高，但每个节点额外存储指针（约 4-8 字节），总空间略高于数组。此外，数组内存连续，缓存命中率高，适合性能敏感场景。

第三，适用场景不同。​
数组适用于数据量大且需频繁随机访问的场景（如图像处理、数据库索引）；链表适用于频繁插入/删除或数据规模动态变化的场景（如消息队列、LRU 缓存）。

4. 一个数字数组排序你会选择什么排序算法？

如果只是一个数字数组排序，我会先看一下数据的特点和要求。比如说，如果数组元素较多且数据是随机分布，我通常会选快速排序，因为它在平均情况下能达到O(n log n)的时间复杂度，性能上也非常高效。不过，快速排序在最坏情况下可能退化到O(n²)，所以如果对最坏情况有严格要求，可能会考虑堆排序或者归并排序。

堆排序能够在最坏情况下保证O(n log n)的性能，而且是原地排序，但在常数时间上可能略逊色；归并排序稳定性好，尤其适合对排序稳定性有要求的场景，不过需要额外的内存空间。

另外，如果数据接近有序，那么插入排序或者更现代的Timsort可能会表现得更好。总之，选择哪种排序算法得看具体的数据规模、数据分布以及是否有稳定性或者空间上的特殊要求。

5. 说说哈夫曼树以及它的应用

哈夫曼树是一种根据字符出现的频率来创建的最优二叉树。创建的时候，频率最低的两个字符会被合并成一个新节点，直到所有字符合并成一棵树。在这棵树上，频率高的字符离根节点近，编码短；频率低的字符离根节点远，编码长。通过这种方式，数据能得到有效压缩，因为高频字符占用的存储空间更小。 哈夫曼树的应用很广泛，最典型的就是数据压缩，比如在ZIP文件格式和JPEG图片格式中就用了哈夫曼编码。另外，它也被应用在网络通信、语音编码等领域，能有效减少传输数据的成本。这种树结构的好处就是能根据实际数据的特点动态调整编码，使得整个过程非常高效。

6. 图的存储结构

老师，我认为图主要有两种常见的存储结构：邻接矩阵和邻接表。邻接矩阵就是用一个二维数组来存储图的信息。如果图有 n 个顶点，那么我们就用一个 n×n 的矩阵，每个元素表示两个顶点之间是否有边（还可以记录权值）。这种方法的优点是判断两个顶点是否相邻非常快，操作简单；缺点则是对于边较少的稀疏图来说，空间利用率低，会浪费不少空间。邻接表则是为每个顶点建立一个链表，存储所有与之相邻的顶点及相关信息。这样对于稀疏图来说，空间利用更高效，因为只存储实际存在的边；不过，如果要判断两个顶点是否直接相连，可能需要遍历链表，相对来说查找速度不如邻接矩阵。另外，对于有向图，还可以使用十字链表来同时记录每个顶点的入边和出边。

总的来说，选择哪种存储结构主要看图的特点：如果是稠密图，邻接矩阵可能更方便；如果是稀疏图，邻接表能更好地节省空间；

7. 迪杰斯特拉算法

老师，我理解的迪杰斯特拉算法其实就是用来解决单源最短路径问题的一种方法。我们先把起点到各个节点的距离都初始化为无穷大，起点设为 0，然后反复地从还没有确定最短距离的节点中找出一个距离最小的，把这个节点确定下来，再利用它去更新它邻近节点的距离。整个过程就是不断“贪心”地选择当前最短路径，并用这个路径去优化其他路径。这样一步步进行下去，最后就能得到起点到所有其他节点的最短距离。不过，这个算法要求图中的边权都是非负的，如果有负权边，就不能用了。