考研数据结构——简答题总结

数据结构的4种基本结构及特点：

数组（Array）：

1. 特点：数组是一种线性数据结构，使用连续的内存空间存储元素，可以通过索引直接访问任意位置的元素。
2. 优点：访问速度快，因为元素是连续存储的，所以可以通过基址和偏移量快速定位到任意元素。
3. 缺点：大小固定，一旦声明了数组的大小，在运行时就不能改变；插入和删除操作效率低，因为可能需要移动大量元素来维持元素的连续性。

链表（Linked List）：

1. 特点：链表是一种线性数据结构，由一系列节点组成，每个节点包含数据部分和指向下一个节点的指针。
2. 优点：大小动态，可以根据需要随时增加或减少节点；插入和删除操作效率高，因为只需要改变指针即可，不需要移动元素。
3. 缺点：访问速度慢，因为不能通过索引直接访问元素，需要从头节点开始遍历链表；额外的内存开销，每个节点需要存储指针。

栈（Stack）：

1. 特点：栈是一种遵循后进先出（LIFO）原则的线性数据结构，只能在一端（栈顶）进行数据的添加和删除操作。
2. 优点：操作受限，只有push（入栈）和pop（出栈）操作，实现简单；可以作为函数调用的内存模型，用于管理函数调用的上下文。
3. 缺点：只能从一端进行操作，不适用于需要从两端操作的场景。

队列（Queue）：

1. 特点：队列是一种遵循先进先出（FIFO）原则的线性数据结构，数据从一端加入（队尾），从另一端移除（队首）。
2. 优点：操作受限，只有enqueue（入队）和dequeue（出队）操作，适用于需要保持元素顺序的场景，如任务调度。
3. 缺点：只能从两端进行操作，队首和队尾的操作是分离的，不适合需要随机访问的场景

栈定义常见的三种栈操作：

1. 入栈（Push）：将元素添加到栈顶。
2. 出栈（Pop）：移除栈顶元素。
3. 查看栈顶（Peek/Top）：查看栈顶元素但不移除。 五种栈的应用：
4. 函数调用的堆栈：用于存储函数调用时的局部变量和返回地址。
5. 表达式求值：用于中缀、前缀和后缀表达式的计算。
6. 回溯算法：用于解决八皇后问题、迷宫问题等。
7. 撤销操作：在文本编辑器中用于撤销和重做功能。
8. 括号匹配：在编译器中用于检查代码中的括号是否正确匹配。

散列查询方法与传统的查找方法区别：

1. 散列（哈希）查询：通过散列函数将键值映射到表中一个位置，快速定位元素，平均时间复杂度为O(1)。
2. 传统查找方法：如顺序查找、二分查找等，需要遍历数据结构中的元素，时间复杂度取决于数据结构和查找算法。

在二叉树链式结构中，有三个指针域：左孩子、右孩子和双亲指针域，证明n个结点有n+2个空指针域：

1. 每个节点除了根节点外，都有两个孩子指针域和一个双亲指针域，因此对于n个节点，总共有3n个指针域。
2. 其中，除了根节点的双亲指针域是空的外，每个节点的双亲指针域指向其父节点，因此有n-1个非空的双亲指针域。
3. 同理，每个节点除了叶子节点外，都有两个非空的孩子指针域，因此有2(n-1)个非空的孩子指针域。
4. 因此，空指针域的数量为3n - (n-1 + 2(n-1)) = n+2。

什么是算法，算法的需要达到的目标是什么？

1. 算法是解决问题的一系列明确定义的计算步骤，它可以接受输入，产生输出，并在有限时间内完成。
2. 算法的目标包括：正确性（能解决问题）、效率（时间复杂度和空间复杂度低）、可读性（易于理解和维护）、健壮性（能处理异常情况）。

ADT（Abstract Data Type）：抽象数据类型，是指一个数学模型及定义在此数学模型上的一组操作。它描述了数据的逻辑结构和数据上的运算，而不考虑数据的物理结构和运算的具体实现。

生成树：在一个无向图中，一个子图，它包括图中的所有顶点，并且是一棵树。

有向完全图：一个有向图，其中每一对不同的顶点之间都恰好有一条有向边。

树的遍历有几种方式？分别都是什么？

1. 前序遍历（Pre-order）：先访问根节点，然后遍历左子树，最后遍历右子树。
2. 中序遍历（In-order）：先遍历左子树，然后访问根节点，最后遍历右子树。
3. 后序遍历（Post-order）：先遍历左子树，然后遍历右子树，最后访问根节点。
4. 层序遍历（Level-order）：按照树的层次从上到下，从左到右遍历。

图的遍历有几种方式？分别都是什么？

1. 深度优先搜索（DFS）：从一个顶点开始，尽可能深地搜索图的分支。
2. 广度优先搜索（BFS）：从一个顶点开始，先访问所有邻接顶点，然后再对每一个邻接顶点进行同样的操作。
3. 关联矩阵法：使用矩阵来表示图的遍历，适用于稠密图。
4. 关联数组法：使用数组来表示图的遍历，适用于稀疏图。

图（Graph）：图是由顶点（或称为节点）和连接这些顶点的边组成的结构。图可以是无向的，也可以是有向的，分别称为无向图和有向图。

网（Network）：网是一种特殊的图，通常用于表示网络结构，如交通网、通信网等。网中的边通常带有权重，表示成本、距离或时间等。

最小生成树（Minimum Spanning Tree, MST）：最小生成树是指连接图中所有顶点的边的子集，它构成一棵树，并且这棵树的总权重是所有可能的生成树中最小的。

关键路径（Critical Path）：在项目管理中，关键路径是指从项目开始到结束的最长路径，它决定了项目的最短完成时间。关键路径上的任何延迟都会导致整个项目的延迟。

数据结构的基本结构有哪些？它们各有什么特点？

集合结构（Collection Structure）：

特点：集合结构中的数据元素同属于一个集合，元素之间没有顺序关系，也没有前驱和后继的概念。集合中的元素是无序的，且每个元素都是唯一的，即集合中的元素不重复。

线性结构（Linear Structure）：

特点：线性结构中的数据元素之间存在一对一的线性关系，即除了第一个和最后一个元素外，每个元素都有且仅有一个前驱和一个后继。线性结构的典型代表有数组、链表、栈和队列。

数组：在内存中连续存储的元素集合，可以快速进行随机访问。

链表：由一系列节点组成，每个节点包含数据和指向下一个节点的指针，不要求物理上连续存储。

栈：遵循后进先出（LIFO）原则的线性结构，只能在一端（栈顶）进行数据的插入和删除操作。

队列：遵循先进先出（FIFO）原则的线性结构，数据从一端进入（队尾），从另一端离开（队首）。

树形结构（Hierarchical Structure）：

特点：树形结构中的数据元素之间存在一对多的层次关系，即除了根节点外，每个节点有且仅有一个父节点，并且可以有多个子节点。树形结构的典型代表是树和森林。

树：由节点组成的层次结构，有一个根节点，每个节点可以有零个或多个子节点。

森林：由多个树组成的结构，可以看作是树的集合。

图状结构（Graph Structure）：

特点：图状结构中的数据元素之间存在多对多的复杂关系，即图中的任意两个元素之间都可能直接相连。图可以是有向的也可以是无向的，边可以带有权重，表示成本、距离等信息。

无向图：图中的边没有方向，表示两个节点之间的双向连接。

有向图：图中的边有方向，表示从一个节点指向另一个节点的单向连接。

叙述一般顺序队列的“假溢出”现象，并给出解决方案及怎样判定循环队列的空和满？

1. 假溢出现象：在顺序队列中，当队列达到其最大容量时，即使队列中没有元素，也无法再进行入队操作，因为队列的头尾指针已经到达了队列的末尾，这种现象称为“假溢出”。
2. 解决方案：可以通过增加队列的容量或者重新设置头尾指针的位置来解决。
3. 循环队列的空和满的判定：
4. 空队列：front = rear
5. 满队列：(rear + 1) % maxSize = front（其中maxSize是队列的最大容量）

二叉树采用二叉链表存储结构，试解释：在含有n个结点的二叉链表中，空指针有n-1个。

在二叉链表中，每个节点有两个指针，分别指向其左子节点和右子节点。对于n个节点的二叉树，除了根节点外，每个节点都有一个父节点，因此会有n-1个节点有父节点。由于每个节点有两个指针，总共有2n个指针位置，其中n-1个位置被节点占据，剩下的n+1个位置是空指针。

顺序查找，二分查找，哈希查找的时间复杂度分别为O(n),O(log2n),O(1),那么既然有了高效的查找方法，为什么低效的方法还不放弃？请从上述算法本身的特点进行分析

1. 顺序查找：适用于数据量小或无序数据的查找，实现简单，不需要额外的存储空间。
2. 二分查找：适用于有序数据，需要预先排序，且数据量较大时效率较高。
3. 哈希查找：适用于大量数据的快速查找，需要良好的哈希函数以减少冲突，但可能需要额外的存储空间。

尽管哈希查找和二分查找在理论上更高效，但顺序查找由于其简单性和对数据无序性的要求较低，仍然有其应用场景。

什么是算法？算法的重要特性有哪些？

算法：算法是解决特定问题的明确和有限的步骤序列。

重要特性：

1. 有穷性：算法必须在执行有限步骤后终止。
2. 确定性：算法的每一步骤都必须有明确的定义。
3. 可行性：算法的每一步都必须足够基本，以至于可以准确地执行。
4. 输入：一个算法有0个或多个输入。
5. 输出：一个算法有一个或多个输出。

简述数据与数据元素的关系与区别:

凡是能被计算机存储、加工的对象统称为数据,数据是一个集合。数据元素是数据的基本单位，是数据的个体。数据元素与数据之间的关系是元素与集合之间的关系。

简述数据逻辑结构与存储结构的关系

在数据结构中,逻辑结构与计算机无关，存储结构是数据元素之间的逻辑关系在计算机中的表示。存储结构不仅将逻辑结构中的所有数据元素存储到计算机内存中，而且还要在内存中存储各数据元素间的逻辑关系。通常情况下,一种逻辑结构可以有多种存储结构,例如线性结构可以采用顺序存储结构或链式存储乡构表示。

简述线性表的两种存储结构的主要特点

线性表的两种存储结构分别是顺序存储结构和链式存储结构。顺序存储结构的主要特点如下:

(1)数据元素中只有自身的数据域,没有关联指针域,因此顺序存储结构的存储密度

较大。

(2)顺序存储结构需要分配一整块比较大的存储空间,所以存储空间的利用率较低

(3)逻辑上相邻的两个元素在物理上也是相邻的,通过元素的逻辑序号可以直接获取其元素值,即具有随机存取特性。

(4)插入和删除操作会引起大量元素的移动。

链式存储结构的主要特点如下:

(1)数据结点中除自身的数据域以外还有表示逻辑关系的指针域,因此链式存储结构比顺序存储结构的存储密度小。

(2)链式存储结构的每个结点是单独分配的,每个结点的存储空间相对较小,所以存储空间利用率较高。

(3)在逻辑上相邻的结点在物理上不一定相邻,因此不具有随机存取特性

(4)插入和删除操作方便、灵活,不必移动结点,只需修改结点中的指针域即可

简述单链表设置头结点的主要作用

(1)对于带头结点的单链表,在单链表的任何结点之前插入结点或删除结点,所要做的都是修改前一个结点的指针域,因为任何结点都有前驱结点(若单链表没有头结点,则首结点没有前驱结点,在其前插入结点和删除该结点时操作复杂一些),所以算法设计方便。

(2)对于带头结点的单链表,在表空时也存在一个头结点,因此空表与非空表的处理是一样的。

哪些链表从尾结点出发可以访问到链表中的任意结点?

循环单链表和循环双链表从尾指针出发可以访问到链表中的任意结点

为什么在不带头结点的循环单链表中设置尾指针比设置首指针更好?

尾指针是指向尾结点的指针，用它来标识循环单链表可以使得查找链表的首结点和尾结点都很方便。设循环单链表的尾指针为rear，则首结点和尾结点的地址分别是rear->next和rear,查找时间都是O(1)。

带头结点的双链表和循环双链表相比有什么不同?在何时使用循环双链表?

在带头结点的双链表中，尾结点的后继指针为NULL，头结点的前驱指针不使用;在带头结点的循环双链表中，尾结点的后继指针指向头结点，头结点的前驱指针指向尾结点。当需要快速找到尾结点时可以使用循环双链表

在以下几种存储结构中哪个最适合用作链栈?

(1)带头结点的单链表。

(2)不带头结点的循环单链表。

(3)带头结点的双链表。‘

1. 栈中元素之间的逻辑关系属线性关系,可以采用单链表、循环单链表和双链表之一来存储,而栈的主要运算是进栈和出栈。
2. 当采用(1)时,前端作为栈顶,进栈和出栈运算的时间复杂度为O(1)。
3. 当采用(2)时,前端作为栈顶,当进栈和出栈时首结点都发生变化,还需要找到尾结点，通过修改其next域使其变为循环单链表,算法的时间复杂度为O(n)。
4. 当采用(3)时,前端作为栈顶,进栈和出栈运算的时间复杂度为O(1)。
5. 但单链表和双链表相比,其存储密度更高,所以本题中最适合用作链栈的是带头结点的单链表。

什么是队列的上溢现象和假溢出现象?解决假溢出有哪些方法？

在队列的顺序存储结构中，设队头指针为front、队尾指针为rear，队的容量(存储空间的大小)为MaxSize。当有元素进队时，若rear=MaxSize(初始时rear=0),则发生队列的上溢现象，不能做进队操作。所谓队列假溢出现象是指队列中还有剩余空间但元素却不能进入队列，造成这种现象的原因是队列的设计不合理。

解决队列假溢出的方法有以下几种:

(1)建立一个足够大的存储空间，但这样做会造成空间的使用效率降低。

(2)当出现假溢出时可采用以下几种方法。

1. 采用平移元素的方法:每当进队一个元素时，队列中已有的元素向队头移动一个位置(当然要有空闲的空间可供移动)。这种方法对应进队运算的时间复杂度为O(n)。
2. 每当出队一个元素时,依次移动队中的元素,始终使front指针指向队列中的第一个元素位置。这种方法对应出队运算的时间复杂度为O(n)
3. 采用环形队列方式：把队列看成一个首尾相接的环形队列,在环形队列上进行进队或出队运算时仍然遵循“先进先出”的原则。这种方法对应进队和出队运算的时间复杂度均为 O(1)。

对于稠密图和稀疏图,采用邻接矩阵和邻接表哪个更好一些?

邻接矩阵适合于稠密图,因为邻接矩阵占用的存储空间与边数无关。邻接表适合于稀疏图,因为邻接表占用的存储空间与边数有关

Dijkstra算法用于求单源最短路径，为了求一个图中所有顶点对之间的最短路径，可以以每个顶点作为源点调用 Dijkstra算法,Floyd算法和这种算法相比有什么优势?

对于有n个顶点的图,求所有顶点对之间的最短路径，若调用Dijkstra算法n次，其时间复杂度为 O(n^3)。Floyd算法的时间复杂度也是O(n^3)。但Floyd算法更快,这是因为前者每次调用Dijkstra算法时都是独立执行的，路径比较中得到的信息没有共享，而Floyd算法中每考虑一个顶点时所得到的路径比较信息保存在A数组中,会用于下次的路径比较，从而提高了整体查找最短路径的效率。

简述图有哪两种主要的存储结构，并说明各种存储结构在图中的不同运算(如图的遍历、求最小生成树、最短路径和拓扑排序等)中有什么样的优性?

图的存储结构主要有邻接矩阵和邻接表。

(1)邻接矩阵:容易判定中任意两个顶点之间是否有边相连,所以对于图的遍历是可行的。同时特别方便提取一条边的权值,所以在求最小生成对和最短路径时采用邻接矩阵作为存储结构

(2)邻接表:容易找到任一顶点的所有邻接点，所以邻接表对于图的遍历也是可行的，并且方便拓扑排序。但要判断任意两个顶点i和j之间是否有边相连,则需搜索第i个及第j个单链表,这一点不如邻接矩阵方便

哈希表查找的时间性能在什么情况下可以达到 O(1)?

如果哈希函数设计得好，不出现同义词冲突现象,此时哈希表查找的时间性能可以达到O(1),这是一种理想情况。在存储的数据集是确定的情况下，并且关键字为整数，可以证明能够设计出这样的哈希函数。

为什么哈希表不支持元素之间的顺序查找?

哈希表是通过哈希地址来查找对应关键字的记录的,对哈希表来说顺序查找没有任何意义,也没有提供顺序查找机制。

用开放定址法构造哈希表,其装填因子为何不能超过1?而用拉链法构造哈希表，其装填因子为何可以超过1?

1. 用开放定址法构造哈希表,无论是否发生冲突,所有元素都放在同一个表内,因此
2. 表的空间要设计得足够大,一般不能装满,所以装填因子应小于1。
3. 用拉链法构造哈希表,每个哈希地址是一个链表的表头指针,所有元素另开辟空间存放,并未占用基本空间,表中元素个数可能大大超过表的大小,所以其装填因子可以超过 1。

在采用线性探测法处理冲突的哈希表中,所有同义词在表中是否一定相邻?

不一定相邻。

在线性探测法中,哈希地址为i(0<=i<=m-1)的关键字和为了解决冲突形成的探测序列(即i的非同义词)都争夺哈希地址i,所以同义词在表中不一定相邻。

直接插入排序算法在含有n个元素的初始数据正序、反序和数据全部相等时时间复杂度各是多少?

1. 含有n个元素的初始数据正序时，直接插入排序算法的时间复杂度为O（n）
2. 含有n个元素的初始数据反序时，直接插入排序算法的时间复杂度为O（n^2）
3. 含有n个元素的初始数据全部相等时，直接插入排序算法的时间复杂度为O（n）

回答以下关于直接插入排序和折半插入排序的问题

(1)使用折半插入排序所要进行的关键字比较次数是否与待排序的元素的初始状态

有关?

(2)在一些特殊情况下,折半插入排序比直接插入排序要执行更多的关键字比较,这句话对吗?

(1)使用折半插入排序所要进行的关键字比较次数与待排序的元素的初始状态无关。无论待排序序列是否有序,已形成的部分子序列是有序的。折半插入排序首先查找插入位置,插入位置是判定树失败的位置(对应外部结点),失败位置只能在判定树的最下两层上。

(2)在一些特殊情况下,折半插入排序的确比直接插入排序需要更多的关键字比较,例

如在待排序序列正序的情况下便是如此。

在堆排序、快速排序和二路归并排序中:

(1)若只从存储空间考虑,应首先选取哪种排序方法?其次选取哪种排序方法?最后选取哪种排序方法?

(2)若只从排序结果的稳定性考虑,则应选取哪种排序方法?

(3)若只从最坏情况下的排序时间考虑,则不应选取哪种排序方法?

答:(1)若只从存储空间考虑,则应首先选取堆排序(空间复杂度为O(1)),其次选取快速排序(空间复杂度为O(1og2n)),最后选取二路归并排序(空间复杂度为O(n))。

(2)若只从排序结果的稳定性考虑,则应选取二路归并排序,其他两种排序方法是不稳定的。

(3)若只从最坏情况下的排序时间考虑,则不应选取快速排序方法。因为快速排序方法的最坏情况下的时间复杂度为〇(n^2),其他两种排序方法在最坏情况下的时间复杂度为O(nlog2n)。

在基数排序过程中用队列暂存排序的元素,是否可以用栈来代替队列?为什么?

不能用栈来代替队列。

基数排序是一趟一趟进行的,从第2趟开始必须采用稳定的排序方法,否则排序结果可能不正确,若用栈代替队列,这样可能使排序过程变得不稳定:

线性表有顺序表和链表两种存储方式,不同的排序方法适合不同的存储结构。对于常见的内部排序方法,说明哪些更适合于顺序表?哪些更适合于链表?哪些两者都适合?

1. 更适合于顺序表的排序方法有希尔排序、折半插入排序、快速排序、堆排序和归并排序。
2. 更适合于链表的排序方法是基数排序。
3. 两者都适合的排序方法有直接插入排序、冒泡排序和简单选择排序

指出堆和二叉排序树的区别

以小根堆为例,堆的特点是双亲结点的关键字必然小于等于孩子结点的关键字,而两个孩子结点的关键字没有次序规定。在二叉排序树中,每个双亲结点的关键字均大于左子树结点的关键字,每个双亲结点的关键字均小于右子树结点的关键字,也就是说,每个双亲结点的左、右孩子的关钱建字有次序关系。

基数排序过程通常用单链表存放排序的元素，是否适合用顺序表来存放排序的元素?为什么?

1. 单链表在进行元素插入和删除时不需要移动元素，而基数排序过程涉及大量的元素插入和删除，所以采用单链表存放排序的元素时排序效率更高。如果采用顺序表来存放排序的元素,会大大降低排序性能。
2. 所以说基数排序过程不适合用顺序表来存放排的元素,但不是说基数排序过程不能够用顺序表来存放排序的元素。