国考专业课-数据结构

Author Avatar
Mo Yu 11月 25, 2024

第八章 数据结构

第一节 数据结构与算法

考点一 数据结构

逻辑结构包括：

1.集合：数据结构中的元素之间除了“同属一个集合” 的相互关系外，别无其他关系；
2.线性结构：数据结构中的元素存在一对一的相互关系；
3.树形结构：数据结构中的元素存在一对多的相互关系；
4.图形结构：数据结构中的元素存在多对多的相互关系。

数据的逻辑结构在计算机中存储表示实现叫做数据的存储结构，也叫物理结构。数据的存储结构依赖于计算机 。
一般来说，一种数据结构的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序存储、链式存储、索引存储和哈希存储等。数据的顺序存储结构的特点是：借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系；非顺序存储的特点是：借助指示元素存储地址的指针表示数据元素之间的逻辑关系。

考点二 算法与算法分析

  1. 定义：
    • 算法分析是对算法的性能进行评估和比较的过程，通常涉及时间复杂度和空间复杂度的分析。
  2. 时间复杂度：
    • 时间复杂度是衡量算法执行时间随输入规模增长而增长的速率。常用的时间复杂度表示方法有O(1)（常数时间）、O(n)（线性时间）、O(n^2)（平方时间）等。
    • 分析时间复杂度时，通常关注算法中执行次数最多的部分，即最坏情况或平均情况下的执行时间。
  3. 空间复杂度：
    • 空间复杂度是衡量算法在执行过程中临时占用存储空间的大小。这包括算法所需的内存、数组、栈等数据结构的大小。
    • 与时间复杂度类似，空间复杂度也使用类似的表示方法，如O(1)、O(n)等。

第二节 线性表、栈和队列

考点一 线性表

线性表主要有两种存储结构：顺序存储结构和链式存储结构。

  1. 顺序存储结构：使用一段连续的存储单元依次存储线性表的数据元素，通过元素的物理位置来表示元素之间的逻辑关系。这种存储方式便于随机存取表中任一元素，但插入和删除操作可能需要移动大量元素，导致时间复杂度较高。
  2. 链式存储结构：通过指针（或链）来表示数据元素之间的逻辑关系，每个数据元素除了存储自身的信息外，还需要存储一个或多个指向其他数据元素的指针。这种存储方式在插入和删除操作上更加高效，但查找操作需要遍历链表，时间复杂度为O(n)。

考点二 栈

栈是一种线性表，但与普通线性表不同的是，栈的插入和删除操作仅限定在表的某一端进行，这一端被称为栈顶（Top），另一端则被称为栈底（Bottom）。在栈中，新元素总是被添加到栈顶，而删除操作也总是从栈顶开始，即最后添加的元素最先被删除。

考点三 队列

队列是一种特殊的线性表，它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。这种操作方式使得队列具有先进先出（First In First Out，FIFO）的特性。

第三节 二叉树

考点一 二叉树

二叉树是n个有限元素的集合，该集合或者为空、或者由一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个节点。

二叉树（binary tree）是指树中节点的度不大于2的有序树，它是一种最简单且最重要的树。二叉树的递归定义为：二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树。

二叉树性质

二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2^（i − 1）个结点;深度为k的二叉树至多有2^k − 1个结点;对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0 = n2 + 1。二叉树算法常被用于实现二叉查找树和二叉堆。

考点二 完全二叉树

满二叉树：如果一棵二叉树只有度为0的节点和度为2的节点，并且度为0的节点在同一层上，则这棵二叉树为满二叉树。

完全二叉树：深度为k，有n个节点的二叉树当且仅当其每一个节点都与深度为k的满二叉树中编号从1到n的节点一一对应时，称为完全二叉树。

完全二叉树的特点是叶子节点只可能出现在层序最大的两层上，并且某个节点的左分支下子孙的最大层序与右分支下子孙的最大层序相等或大1

多种二叉树区别

考点三 二叉树的遍历

遍历是对树的一种最基本的运算，所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有节点，使每一个节点都被访问一次，而且只被访问一次。由于二叉树是非线性结构，因此，树的遍历实质上是将二叉树的各个节点转换成为一个线性序列来表示。

二叉树的遍历主要有三种方式：前序遍历、中序遍历和后序遍历。

  1. ‌前序遍历（Preorder Traversal）‌：前序遍历首先访问根节点，然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根节点，然后遍历左子树，最后遍历右子树。如果二叉树为空则结束返回。
  2. ‌中序遍历（Inorder Traversal）‌：中序遍历首先遍历左子树，然后访问根节点，最后遍历右子树。在中序遍历中，左子树的所有节点都会在根节点之前被访问。
  3. ‌后序遍历（Postorder Traversal）‌：后序遍历首先遍历左子树，然后遍历右子树，最后访问根节点。在后序遍历中，根节点会在所有子节点之后被访问。

这些遍历方式在算法实现上可以通过递归或非递归的方式完成。前序遍历的递归算法通常形式为“访问根节点 -> 前序遍历左子树 -> 前序遍历右子树”，中序遍历为“前序遍历左子树 -> 访问根节点 -> 前序遍历右子树”，而后序遍历为“前序遍历左子树 -> 前序遍历右子树 -> 访问根节点”。

二叉树访问示例

先序遍历这棵二叉树的过程是：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
访问根节点 1；
进入 1 的左子树，执行同样的步骤：
    访问结点 2；
    进入 2 的左子树，执行同样的步骤：
        访问结点 4；
        结点 4 没有左子树；
        结点 4 没有右子树；
    进入 2 的右子树，执行同样的步骤：
        访问结点 5；
        结点 5 没有左子树；
        结点 5 没有右子树；
进入 1 的右子树，执行同样的步骤：
    访问结点 3；
    进入 3 的左子树，执行同样的步骤：
        访问结点 6；
        结点 6 没有左子树；
        结点 6 没有右子树；
    进入 3 的右子树，执行同样的步骤：
        访问结点 7；
        结点 7 没有左子树；
        结点 7 没有右子树；

经过以上过程，就访问了二叉树中的各个结点，访问的次序是：

1 2 4 5 3 6 7

中序遍历这棵二叉树的过程是：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
进入结点 1 的左子树，访问左子树中的结点；
    进入结点 2 的左子树，访问左子树中的结点；
        试图进入结点 4 的左子树，但该结点没有左子树；
        访问结点 4；
        试图进入结点 4 的右子树，但该结点没有右子树；
    访问结点 2；
    进入结点 2 的右子树，访问右子树中的结点；
        试图进入结点 5 的左子树，但该结点没有左子树；
        访问结点 5；
        试图进入结点 5 的右子树，但该结点没有右子树；
访问结点 1；
进入结点 1 的右子树，访问右子树中的结点；
    进入结点 3 的左子树，访问左子树中的结点；
        试图进入结点 6 的左子树，但该结点没有左子树；
        访问结点 6；
        试图进入结点 6 的右子树，但该结点没有右子树；
    访问结点 3；
    进入结点 3 的右子树，访问右子树中的结点；
        试图进入结点 7 的左子树，但该结点没有左子树；
        访问结点 7；
        试图进入结点 7 的右子树，但该结点没有右子树；

最终，中序遍历图 1 中的二叉树，访问各个结点的顺序是：

4 2 5 1 6 3 7

后序遍历这棵二叉树的过程是：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
从根节点 1 出发，进入该结点的左子树；
    进入结点 2 的左子树，遍历左子树中的结点：
        进入结点 4 的左子树，但该结点没有左孩子；
        进入结点 4 的右子树，但该结点没有右子树；
        访问结点 4；
    进入结点 2 的右子树，遍历右子树中的结点：
        进入结点 5 的左子树，但该结点没有左孩子；
        进入结点 5 的右子树，但该结点没有右孩子；
        访问结点 5；
    访问结点 2；
进入结点 1 的右子树，遍历右子树中的结点：
    进入结点 3 的左子树，遍历左子树中的结点：
        进入结点 6 的左子树，但该结点没有左孩子；
        进入结点 6 的右子树，但该结点没有右子树；
        访问结点 6；
    进入结点 3 的右子树，遍历右子树中的结点：
        进入结点 7 的左子树，但该结点没有左孩子；
        进入结点 7 的右子树，但该结点没有右孩子；
        访问结点 7；
    访问结点 3；
访问结点 1。

最终，后序遍历图 1 中的二叉树，访问各个结点的顺序是：

4 5 2 6 7 3 1

第四节 查找与排序

考点一 查找

查找是在数据集合中，寻找满足某种条件的数据元素的过程。查找表（查找结构）是用于查找的数据集合，关键字是数据元素中某个数据项的值，用它可以标识一个数据元素。

常见的查找方法有以下几种：

  1. 顺序查找：从线性表的第一个元素开始，逐个将线性表的元素与被查元素比较。在平均情况下，大约需要比较n/2次。特殊情况包括：线性表是无序表时，不管是顺序存储结构还是链式存储结构，都只能用顺序查找；线性表是有序的，如果采用链式存储结构，也只能用顺序查找。
  2. 二分查找：又称折半查找，要求线性表是有序表，且使用顺序存储结构。每次查找都取中间元素进行比较，如果中间元素正好是要查找的元素，则查找过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。在最坏的情况下，每次比较都将搜索区间缩小一半。时间复杂度为O(logn)。
  3. 哈希表查找：利用哈希表能够在O(1)的时间内查找某一元素，是效率最高的查找方式。但其缺点是需要额外的空间来实现哈希表，且哈希函数的设计以及冲突解决策略对性能有较大影响。
  4. 二叉排序树查找：二叉排序树是一种特殊的二叉树，其左子树上所有节点的值均小于根节点的值，右子树上所有节点的值均大于根节点的值。查找时从根节点开始，根据待查找值与当前节点值的比较结果决定向左子树还是右子树递归查找。

考点二 排序

排序是将一个无序序列整理为按值非递减顺序（或非递增顺序）排列的一种方式。排序算法的性能评价主要包括时间复杂度和空间复杂度两个方面。

常见的排序方法有以下几种：

  1. 插入排序：包括直接插入排序和希尔排序。直接插入排序的基本思想是将n个元素看成是一个有序表和一个无序表。开始时，有序表里只有一个元素，无序表里有n-1个；取无序表的第一个元素插入有序表的恰当位置，生成新的有序表。重复此操作直到所有元素都插入完成为止。希尔排序是插入排序的一种改进，它先将整个待排序的记录序列分割成若干个子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。
  2. 交换排序：包括冒泡排序和快速排序。冒泡排序的基本思想是通过相邻元素的比较和交换，将关键字较小的元素逐渐从前移向后部，关键字较大的元素逐渐从前部移向后部。快速排序则通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
  3. 选择排序：包括简单选择排序和堆排序。简单选择排序的基本思想是先从所有待排序的数据元素中选择最小的元素，将该元素与第一个元素交换，再从剩下的n-1个元素里选择最小的元素与第二个元素交换。重复上述操作直至所有元素有序为止。堆排序是一种树形选择排序方法，在排序过程中，将待排序序列看成是一颗完全二叉树的顺序存储结构，利用完全二叉树中双亲节点和孩子节点之间的内在关系，在当前无序区中选择关键字最大（或最小）的元素，并与无序区的最后一个元素交换，然后对新的无序区重复上述操作，直到整个序列有序。
  4. 归并排序：归并排序的基本思想是将两个或两个以上的有序表组合成一个新的有序表。它采用分治法，首先将待排序序列分成若干个子序列，每个子序列是有序的；然后再将这些有序子序列逐步合并，最终得到完全有序的序列。归并排序的时间复杂度为O(nlogn)，且是一种稳定的排序算法。
  5. 基数排序：基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。具体做法是，先取整数的最低位（或最高位）作为关键字进行排序；然后取次低位（或次高位）作为关键字进行排序；依此类推，直到最高位（或最低位）排序完成。基数排序的时间复杂度为O(d(n+r))，其中d为待排序序列的位数，r为进制数（如十进制时r=10）。基数排序通常用于对数字进行排序，也可以用于对字符串进行排序（此时r为字符集的大小）。