一、名词解释

1、抽象数据类型

抽象数据类型（Abstract Data Type, ADT）是指一种数学模型和一组定义在该模型上的操 作的集合。ADT 强调的是数据的逻辑结构与功能，而不是其具体的实现细节。它将数据 的存储和操作从具体的实现层次中抽象出来，用户通过定义的操作来使用数据类型，而 不需要关心底层如何实现。例如，栈、队列、列表等都是抽象数据类型，它们有着特定 的操作（如插入、删除等），但其具体实现可以是链表、数组等多种形式。

2、无向完全图

1. 定义

无向完全图是一种特殊的无向图，其中任意两个不同的顶点之间都存在且仅存在一条边。即，每个顶点均与图中所有其他顶点直接相连。

2. 特点

• 顶点连接性：图中不存在孤立顶点，所有顶点均两两相连。
• 边的数量：若图中有 ​n个顶点，则边的总数为​ \frac{n(n-1)}{2}。
• 顶点度数：每个顶点的度均为 ​n−1。

3. 存储方式

• 邻接矩阵：使用 ​n×n的矩阵表示图。矩阵中元素 ​a[i][j]=1表示顶点​ i 与​ j 之间存在边，否则为 0。无向完全图的邻接矩阵为对称矩阵，且除主对角线外所有元素均为 1。
• 邻接表：每个顶点对应一个链表，链表中包含所有与之相邻的顶点。在无向完全图中，每个顶点的邻接表包含其余 ​n−1 个顶点。

4. 遍历方法

• 深度优先搜索（DFS)：从某一顶点出发，沿路径深入访问未访问的顶点，直至无法继续，再回溯至前一顶点继续搜索。
• 广度优先搜索（BFS）：从起始顶点开始，依次访问其所有相邻顶点，再按访问顺序逐层扩展至更远的顶点。

由于无向完全图中所有顶点连通，因此从任意顶点出发均可通过一次遍历访问图中所有顶点。

3、 哈夫曼树

1. 哈夫曼树的定义

哈夫曼树是一种特殊的二叉树，它是由哈夫曼算法构造出来的，用于给定权值集合的最优二叉树。在哈夫曼树中，每个叶子节点都对应一个给定的权值，而每个非叶子节点的权值是它的左右子树权值的和。

2. 哈夫曼树的特点

• 权值分布：哈夫曼树的构造过程中，权值较小的节点距离根节点较远，而权值较大的节点距离根节点较近。
• 无歧义编码：哈夫曼树能够生成无歧义的前缀编码，即没有一个编码是另一个编码的前缀。
• 最小带权路径长度：在所有可能的二叉树中，哈夫曼树的带权路径长度（WPL）是最小的。

3. 构造过程

哈夫曼树的构造过程是一个贪心算法的过程，具体步骤如下：

1. 将给定的权值集合按照权值从小到大排序。
2. 取出两个最小的权值，创建一个新的内部节点，其权值为这两个最小权值的和。
3. 将新创建的内部节点的权值加入到权值集合中，并重新排序。
4. 重复步骤 2 和 3，直到集合中只剩下一个节点，这个节点即为哈夫曼树的根节点。

4. 哈夫曼编码

哈夫曼树的一个重要应用是生成哈夫曼编码，这是一种最优的前缀编码方法，用于数据压缩。具体方法如下：

• 从根节点开始，向左的分支代表 0，向右的分支代表 1。
• 对于每个叶子节点，从根节点到该叶子节点的路径上，分支的方向序列即为该叶子节点对应字符的哈夫曼编码。

4. 回路

1. 回路的定义

回路是指在一个图中，从某个顶点出发，沿着一些边移动，最终回到该顶点的路径。在 (简单)回路 中，除了起点和终点相同外，其余顶点不重复出现。

2. 回路的类型

简单回路：如果一个回路中的顶点不重复出现（除起点与终点重合外），那么这样的回路称为简单回路。
复杂回路：如果一个回路中的边或顶点可以重复出现，那么这样的回路称为复杂回路。

3. 回路的特点

闭合性：回路的起点和终点是同一个顶点。
边和顶点的重复性：在简单回路中，边和顶点不重复；在复杂回路中，边和顶点可能重复。

4. 回路的判定

在无向图中，可以通过以下方法判断是否存在回路：
深度优先搜索（DFS）：在 DFS 过程中，如果访问到一个已经被访问过的顶点（且不是当前顶点的父节点），则图中存在回路。
广度优先搜索（BFS）：在 BFS 过程中，一般不会直接发现回路，但可以通过 BFS 生成树，如果在生成树中存在边连接非父子关系的顶点，则图中存在回路。

在有向图中，回路的存在性可以通过 DFS 判断：若在搜索过程中，访问到一個在當前递归栈中的顶点，则存在回路。

在树中，由于树是一种特殊的无向图，它不包含任何回路。
在无向完全图中，由于每个顶点都与其他所有顶点相连，因此必然存在多个回路。

5. 回路的应用

拓扑排序：在有向无环图（DAG）中进行拓扑排序时，图中不能存在回路，因为回路会导致排序无法进行。
网络流问题：在最大流问题中，通常要求图中的流网络是无环的，但有时也会考虑含有回路的流网络。

5. 森林

森林（Forest）：

定义：森林是由 ​n（n≥0）棵互不相交的树组成的集合。如果 n=0，即森林为空，不包含任何树。

特性：

• 每棵树都是独立的，没有公共的顶点或边。
• 森林中的每棵树都可以独立地进行遍历、查找、插入和删除等操作。
• 森林中的树的数量可以是任意的，包括零棵树（即空森林）。

与树的关系：

• 一棵树去掉根节点后，其子节点组成的森林就是该树的子树森林。
• 任意一棵树都可以看作是一个特殊的森林，即只包含一棵树的森林。

存储表示：

• 森林可以通过多种方式存储，常见的方法有孩子兄弟表示法，其中每个节点包含两个指针，一个指向它的第一个孩子，另一个指向它的下一个兄弟。
• 森林也可以通过将每棵树的根节点存储在一个数组中来表示，数组中的顺序可以是任意的。

操作：

• 森林的遍历通常是对森林中的每棵树分别进行遍历。
• 森林的创建、销毁、添加树、删除树等操作都是基于树的操作。

---

二、简答题

1、线性结构、树形结构、图状结构(网状结构)中数据元素分别是什么关系？

1. 数据元素关系

线性结构中的数据元素存在一对一的关系，即每个数据元素最多只有一个直接前驱和一个直接后继（除了第一个元素没有前驱和最后一个元素没有后继）。
特点：元素按照某种线性顺序排列，例如数组、链表、栈、队列等。
示例：

• 数组：元素按照索引顺序排列，每个元素都有一个唯一的直接前驱和直接后继（除了数组的第一个和最后一个元素）。

• 链表：元素通过指针链接，每个元素（节点）包含数据和指向下一个元素的指针。

2. 树形结构
数据元素关系：树形结构中的数据元素存在一对多的层次关系，即每个数据元素（除根节点外）有且只有一个直接前驱（父节点），但可以有多个直接后继（子节点）。
特点：具有明显的层次特性，没有形成闭环。
示例：

• 二叉树：每个节点最多有两个子节点，分别是左子节点和右子节点。

• 多叉树：每个节点可以有多个子节点。

3. 图状结构（网状结构）
数据元素关系：图状结构中的数据元素存在多对多的关系，即每个数据元素（节点）可以有多个直接前驱和多个直接后继。
特点：节点之间的关系可以是任意的，没有固定的顺序，可能形成闭环。
示例：

• 无向图：节点之间的边没有方向。

• 有向图：节点之间的边有方向，形成有向边。

• 网络：在图的边上可以赋予一定的权重，表示从一个节点到另一个节点的代价。

总结：线性结构是元素间一对一的关系，树形结构是元素间一对多的层次关系，而图状结构则是元素间多对多的复杂关系。

2、数据的逻辑结构与存储结构有什么区别和联系？

数据的逻辑结构与存储结构是数据组织与管理的两个不同方面，它们之间既有区别又有联系。

区别：

• 逻辑结构
  • 定义：逻辑结构是数据元素之间的逻辑关系，是独立于计算机的抽象结构，反映了数据元素之间的逻辑关系。
  • 特点：
    • 抽象性：不考虑数据的物理存储，只关心数据元素之间的逻辑关系。
    • 灵活性：逻辑结构可以有多种不同的形式，如线性结构、树形结构、图形结构等。
    • 不变性：逻辑结构通常不会因为程序的执行而改变。
• 存储结构（物理结构）
  • 定义：存储结构是指数据在计算机中的实际存储方式，是逻辑结构在计算机中的具体实现。
  • 特点：
    • 具体性：必须考虑数据如何在计算机的内存或外存中存放。
    • 限制性：受限于计算机系统的存储能力，存储结构必须高效利用存储空间。
    • 可变性：存储结构可能会随着程序的执行而动态变化，如动态分配内存。

联系：

• 实现关系：存储结构是对逻辑结构的实现，即逻辑结构是概念上的模型，而存储结构是这个模型在计算机中的具体表示。
• 映射关系：逻辑结构中的每个数据元素在存储结构中都有一个对应的存储位置，这种映射关系可以是直接的（如数组），也可以是间接的（如链表）。
• 相互影响：逻辑结构的选择会影响存储结构的设计，反之，存储结构的限制也可能影响逻辑结构的选择。

举例说明：

• 线性表的逻辑结构是一个序列，其中每个元素都有一个直接前驱和一个直接后继（除了第一个和最后一个元素）。其存储结构可以是顺序存储（如数组）或链式存储（如链表）。
• 树的逻辑结构是一个层次模型，其中每个元素（节点）有一个父节点和多个子节点。其存储结构可以是基于指针的，如每个节点包含一个指向父节点的指针和多个指向子节点的指针。

3、若较频繁地对一个线性表进行插入和删除操作，该线性表宜采用何种存储结构？ 为什么？

若较频繁地对一个线性表进行插入和删除操作，该线性表宜采用链式存储结构，即链表。以下是原因：

1. 插入和删除操作的效率：
   • 在链表中，插入和删除操作通常只需要改变指针的指向，而不需要像数组那样进行大量元素的移动。因此，链表在插入和删除操作上通常比数组更高效。
   • 对于数组，插入或删除一个元素可能需要移动该元素之后的所有元素，其时间复杂度为 O(n)。
   • 对于链表，插入或删除操作的平均时间复杂度为 O(1)，因为只需改变几个指针。
2. 动态空间管理：
   • 链表在存储空间的管理上更加灵活。它可以在运行时动态地分配和释放内存，不需要像数组那样在创建时就确定大小。
   • 对于频繁变动的线性表，链表可以更有效地利用内存空间，因为不需要为了可能的最大大小而预先分配一大块连续的内存。
3. 没有固定的物理大小限制：
   • 数组在创建时需要指定大小，如果线性表的大小频繁变化，使用数组可能导致空间浪费或者需要频繁地进行数组扩容操作，后者同样需要移动大量元素，效率低下。
   • 链表则没有这样的限制，它可以随着元素的增加和减少动态地调整存储空间。

综上所述，对于需要频繁进行插入和删除操作的线性表，链式存储结构更为合适。

不过，需要注意的是，链表在访问特定元素时不如数组高效，因为链表需要从头开始遍历到指定位置，其时间复杂度为 O(n)，而数组可以通过索引直接访问，时间复杂度为 O(1)。因此，在选择存储结构时，还需要根据具体的应用场景来权衡。

4、什么是循环队列？

循环队列是一种线性数据结构，它是一种特殊的队列，使用固定大小的数组来存储元素，并具有两个指针：front（队头）和 rear（队尾）。与普通队列相比，循环队列的一个特点是它能够高效地利用数组空间，因为它允许在数组的末尾之后回绕到数组开头。

以下是循环队列的几个关键点：

1. 空间循环利用：
   • 在普通队列中，当队尾指针到达数组末尾时，如果队列未满，则需要将所有元素向前移动以腾出空间，这是一种低效的操作。
   • 在循环队列中，当队尾指针移动到数组末尾时，它会“环绕”到数组开头，从而形成一个逻辑上的环。这样，数组的每个位置都可以被重复利用，避免了数据搬移。
2. 队空和队满的条件：
   • 对于循环队列，队列为空的条件是 front == rear。
   • 队列满的条件稍微复杂一些，通常有几种实现方式，其中一种常用的方法是保留一个空位，即当 (rear + 1) % capacity == front 时，队列被认为是满的，其中 capacity 是队列的容量。
3. 入队和出队操作：
   • 入队（Enqueue）：在循环队列中添加元素时，首先检查队列是否已满。如果未满，将元素放置在 rear 指针指向的位置，然后 rear 指针向前移动一位（循环地，即 rear = (rear + 1) % capacity）。
   • 出队（Dequeue）：从循环队列中移除元素时，首先检查队列是否为空。如果非空，从 front 指针指向的位置移除元素，然后 front 指针向前移动一位（循环地，即 front = (front + 1) % capacity）。
4. 实现方式：
   • 循环队列通常使用数组实现，并需要维护两个指针：front 和 rear。这两个指针分别用于追踪队列的前端和后端。
   • 循环队列的优点在于它没有队列的“假溢出”问题，即数组中还有空间可用，但由于队列的线性结构，队尾指针无法继续前进而导致的溢出。通过循环利用数组空间，循环队列可以更高效地处理队列操作。

5、对 20 个元素进行升序排列(使用 C 语言实现)

#include <stdio.h>

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // 交换元素
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

int main() {
    int arr[20] = {20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
    int n = 20;

    bubbleSort(arr, n);

    printf("排序后的数组：\n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}