type
status
date
slug
summary
tags
category
icon
password
Property
Jun 23, 2023 11:48 AM
1.简述数据结构的定义和组成
答：数据结构是相互之间存在的一种或多种特定关系的数据元素的集合，数据结构包括三个方面：逻辑结构，存储结构和数据的运算
逻辑结构：分两个方面的话有线性结构和非线性结构。其中：
线性结构：线性表，栈，队列
非线性结构：集合、树、图
存储结构：顺序存储，链式存储，索引存储，散列存储
线性表：
首先，什么是线性表？就是一种连续或间断存储的数组，这里的连续和间断是针对物理内存空间中线性表元素之间是否连续，其中连续数组对应内置数组的实现方式，间断数组对应的是指针的实现方式，这种方式也称为链表实现。
也就是说，线性表有两种实现方式，一种是内置数组实现，另一种是链表实现，最好把链表就理解为线性表的一种实现方式，而且从链表的定义来看，它的本质是一种数据结构，其定义如下
而我们通常自定义的链表中，一般使用typedef ListNode* List; 这其实就是一个ListNode节点的next域，正是由于有next域的存在，所以我们通常会以一种逻辑结构理解的链表（大多数数据结构教程中确实也是这么表示的）。
栈：
首先，栈就是一种线性结构的表，也就是线性表，那么也就是说它有两种实现方式，一种是用内置数组实现，一种是以链表实现。
其次，栈有自己的结构特性：栈可以动态增长和缩减，即（一般）可以向一个栈添加或从一个栈删除元素，但这种添加和删除操作只能从栈的栈顶进行操作，这种限制也造就了栈的先进后出特性。
最后，注意上面只是说一般我们可以用内置数组和链表两种方式来实现栈，但是，根据栈的特性，其实还可以用其他结构来实现栈，只要这种结构能实现栈的先进后出，而且只能从栈的栈顶进行插入和删除操作，最常见的就是我们可以用两个队列来实现栈（当然，后面会解释，其实队列也是用数组和链表来实现的）。
比如，用内置数组来实现栈，则可以这样定义栈的结构：
栈的链表实现：
如果采用链表方式来实现栈，则一般需要有一个表头，因为栈需要在表头位置来进行插入和删除操作。
队列：
首先，队列也是一种线性表（线性的数据结构），则队列也可以用数组和链表两种方式来实现；
其次，队列也有自己的结构特性：队列是先进先出的线性表，它同时维护表的两端，但只能在表尾进行插入，在表头进行删除操作（这是有队列的先进先出特性决定的）。
所以，不管是用数组还是用链表实现队列，都需要遵循队列的先进先出特性。
用内置数组实现队列，则队列结构定义为：
用链表实现队列，则队列结构定义为：
不管是队列的数组还是链表实现，在进行删除和插入操作之后都需要维护队列头和尾的指向性元素（即front和real），以及队列当前元素个数size。
树：
它具有以下的特点：每个结点有零个或多个子结点；没有父结点的结点称为根结点；每一个非根结点有且只有一个父结点；除了根结点外，每个子结点可以分为多个不相交的子树；
树结构是一种非线性存储结构，存储的是具有“一对多”关系的数据元素的集合。
树的种类
二叉树是数据结构中一种重要的数据结构，也是树表家族最为基础的结构。
二叉树的定义：二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2i-1个结点；深度为k的二叉树至多有2k-1个结点；对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。
二叉树的基本概念
二叉树：二叉树是每个节点最多有两个子树的树结构。
根节点：一棵树最上面的节点称为根节点。
父节点、子节点：如果一个节点下面连接多个节点，那么该节点称为父节点，它下面的节点称为子 节点。
叶子节点：没有任何子节点的节点称为叶子节点。
兄弟节点：具有相同父节点的节点互称为兄弟节点。
节点度：节点拥有的子树数。上图中，13的度为2，46的度为1，28的度为0。
树的深度：从根节点开始（其深度为0）自顶向下逐层累加的。上图中，13的深度是1，30的深度是2，28的深度是3。
树的高度：从叶子节点开始（其高度为0）自底向上逐层累加的。54的高度是2，根节点23的高度是3。
对于树中相同深度的每个节点来说，它们的高度不一定相同，这取决于每个节点下面的叶子节点的深度。上图中，13和54的深度都是1，但是13的高度是1，54的高度是2。
满二叉树和完全二叉树：
满二叉树：除最后一层无任何子节点外，每一层上的所有结点都有两个子结点。也可以这样理解，除叶子结点外的所有结点均有两个子结点。节点数达到最大值，所有叶子结点必须在同一层上。
满二叉树的性质：
1) 一颗树深度为h，最大层数为k，深度与最大层数相同，k=h;
2) 叶子数为2h;
3) 第k层的结点数是：2k-1;
4) 总结点数是：2k-1，且总节点数一定是奇数。
完全二叉树：若设二叉树的深度为h，除第 h 层外，其它各层 (1～(h-1)层) 的结点数都达到最大个数，第h层所有的结点都连续集中在最左边，这就是完全二叉树。
注：完全二叉树是效率很高的数据结构，堆是一种完全二叉树或者近似完全二叉树，所以效率极高，像十分常用的排序算法、Dijkstra算法、Prim算法等都要用堆才能优化，二叉排序树的效率也要借助平衡性来提高，而平衡性基于完全二叉树。
2.数据结构的复杂度O(1)是什么意思？
答：时间复杂度：算法中所有语句的频度
空间复杂度：指算法运行过程中所使用的辅助空间
时间复杂度：
若存在函数 f(n)，使得当n趋近于无穷大时，T(n)/ f(n)）的极限值为不等于零的常数，则称 f(n)是T(n)的同数量级函数。记作 T(n)= O(f(n))，称O(f(n))为算法的渐进时间复杂度，简称时间复杂度。
简单理解就是一个算法或是一个程序在运行时，所消耗的时间（或者代码被执行的总次数）。
在下面的程序中：
上面的结果如果用函数来表示为：f(n) = 3n+3，那么在计算机算法中的表示方法如下。
表示方法
大O表示法：算法的时间复杂度通常用大O来表示，定义为T(n) = O(f(n))，其中T表示时间。
即：T(n) = O(3n+3)
这里有个重要的点就是时间复杂度关心的是数量级，其原则是：
- 省略常数，如果运行时间是常数量级，用常数1表示
- 保留最高阶的项
- 变最高阶项的系数为1
如 2n 3 + 3n2 + 7，省略常数变为 O(2n 3 + 3n2)，保留最高阶的项为 O(2n 3 )，变最高阶项的系数为1后变为O(n 3 )，即O(n 3 )为 2n 3 + 3n2 + 7的时间复杂度。
同理，在上面的程序中 T(n) = O(3n+3)，其时间复杂度为O(n)。
注：只看最高复杂度的运算，也就是上面程序中的内层循环。
时间复杂度的阶
时间复杂度的阶主要分为以下几种
常数阶O(1)
不管n等于多少，程序始终只会执行一次，即 T(n) = O(1)
对数阶O(logn)
i 的值随着 n 成对数增长，读作2为底n的对数，即f(x) = log2n，T(n) = O( log2n)，简写为O(logn)
线性阶O(n)
n的值为多少，程序就运行多少次，类似函数 y = f(x)，即 T(n) = O(n)
线性对数阶O(nlogn)
线性对数阶O(nlogn)其实非常容易理解，将对数阶O(logn)的代码循环n遍的话，那么它的时间复杂度就是 n * O(logn)，也就是了O(nlogn)，归并排序的复杂度就是O(nlogn)。
平方阶O(n2)
若 n = 2，则打印4次，若 n = 3，则打印9，即T(n) = O(n2)
以上5种时间复杂度关系为：
从上图可以得出结论，当x轴n的值越来越大时，y轴耗时的时长为：
O(1) < O(logn) < O(n) < O(nlogn) < O(n2)
在编程算法中远远不止上面4种，比如O(n3)，O(2n)，O(n!)，O(nk)等等。
注：以下数据来自于Big-O Cheat Sheet，常用的大O标记法列表以及它们与不同大小输入数据的性能比较。
大O标记法 | 计算10个元素 | 计算100个元素 | 计算1000个元素 |
O(1) | 1 | 1 | 1 |
O(logN) | 3 | 6 | 9 |
O(N) | 10 | 100 | 1000 |
O(NlogN) | 30 | 600 | 9000 |
O(N2) | 100 | 10000 | 1000000 |
O(2N) | 1024 | 1.26e+29 | 1.07e+301 |
O(N!) | 3628800 | 9.3e+157 | 4.02e+2567 |
常见数据结构操作的复杂度
数据结构 | 连接 | 查找 | 插入 | 删除 |
数组 | 1 | n | n | n |
栈 | n | n | 1 | 1 |
队列 | n | n | 1 | 1 |
链表 | n | n | 1 | 1 |
哈希表 | - | n | n | n |
二分查找树 | n | n | n | n |
B树 | log(n) | log(n) | log(n) | log(n) |
红黑树 | log(n) | log(n) | log(n) | log(n) |
AVL树 | log(n) | log(n) | log(n) | log(n) |
数组排序算法的复杂度
名称 | 最优 | 平均 | 最坏 | 内存 | 稳定 |
冒泡排序 | n | n2 | n2 | 1 | 是 |
插入排序 | n | n2 | n2 | 1 | 是 |
选择排序 | n2 | n2 | n2 | 1 | 否 |
堆排序 | n log(n) | n log(n) | n log(n) | 1 | 否 |
归并排序 | n log(n) | n log(n) | n log(n) | n | 是 |
快速排序 | n log(n) | n log(n) | n2 | log(n) | 否 |
希尔排序 | n log(n) | 取决于差距序列 | n (log(n))2 | 1 | 否 |
空间复杂度
空间复杂度表示的是算法的存储空间和数据之间的关系，即一个算法在运行时，所消耗的空间。
空间复杂度的阶
空间复杂度相对于时间复杂度要简单很多，我们只需要掌握常见的O(1)，O(n)，O(n2)。
常数阶O(1)
线性阶O(n)
平方阶O(n2)
3.什么是抽象数据结构？
答：相当于定义了数据的逻辑结构和数据的运算
4.数据的基本单位和最小单位分别是什么？
答：数据的基本单位：数据元素
数据的最小单位：数据项，学生的记录就是一个数据元素；由姓名，学号，性别等数据项组成
5.简述一个好的算法应该达到哪些目标？
答：
(1)正确性：算法应当能够正确地解决求解问题
(2)可读性：算法应当具有良好的可读性
(3)健壮性：当输入非法数据时，不会产生莫名其妙的输出结果
(4)效率与低存储量需求：
- 效率是算法执行的空间
- 存储量需求是指算法执行过程中所需的最大存储空间
6.算法的五个重要的特征
答：（1）有穷性：一个算法必须在有限的步骤和有限的时间内完成
(2)确定性：相同的输入只能得出相同的输出
(3)可行性：算法是可行的
(4)输入：一个算法有0个或者多个的输入
(5)输出：一个算法有0个或者多个的输出
7.线性表和顺序表以及链表的区别
答：线性表是逻辑结构，表示元素之间一对一的相邻关系
顺序表和链表是存储结构，顺序表是逻辑上相邻的两个元素在物理位置上也是相邻的
链表指不要求逻辑上相邻的元素在物理位置上也是相邻的
8.顺序表和链表存储的优缺点
答：顺序表存储：优点：存取速度高效，可以实现随机存取，数据存取密度比较大
缺点：插入和删除比较慢，不可以增加长度
链表存储：优点：插入和删除速度快，保留原有的物理顺序，不会发生存储溢出的问题
缺点：查找速度慢，需要循环链表访问
9.头指针和头结点的区分
答：头指针是指链表指向第一结点的指针，若链表有头结点，则是指向头结点的指针。
头结点是为了操作的统一和方便而设立的，放在第一个元素的结点之前，其数据域一般无意义
10.简述链表中引入头结点带来的优点
答：（1）第一个位置的插入删除更加方便
（2）使用头结点，无论表是否为空，头指针都指向头结点
11.头插法和尾插法的区别
答：头插法：不断得将新结点插入到头结点，但头插法会改变数据输入顺序
尾插法：将新结点插入到队尾，不会改变数据的顺序
12.数组与线性表的关系
答：线性表与数组都是数据结构，只是描述的角度不同。
线性表是从逻辑结构的角度来说，而数组是从物理存储的角度来说的
线性表可以用数组存储，也形成顺序表
13.数组和链表的区别（比较经典的问题）
答：（1）物理存储结构不同：数组是顺序存储结构，链表是链式存储结构
(2)内存分配方式不同：数组的存储空间一般采用静态分配；链表的存储空间一般采用动态分配
(3)元素的存取方式不同：数组元素为直接存取，链表元素的存取需要遍历链表
(4)元素的插入和删除方式不同：数组在进行元素插入和删除时，需要移动数组的元素
而链表在进行元素插入和删除时无需移动链表内的元素
14.循环队列的顺序表中，为什么要空一个位置？
答：为了区分队空和队满的情况，如果不空一个位置，则判断队空和队满的条件是一样的
15.串是一种特殊的线性表，请从存储和运算两方面来分析它的特殊之处
答：串：是零个或多个任意字符组成的有限序列
从存储方面来看，串中每个存储单元只存储一个字符
从运算方面来看，串有连接、判串相等、求子串和子串替换等基本运算。
16.介绍下字符串模式匹配算法：朴素模式匹配算法和KMP算法
答：串的模式匹配：在主串中找到与模式串相同的子串，并返回其所在位置
朴素模式匹配算法：将模式串的字符与主串中的每一个子串一一进行比对
KMP算法：指向主串的指针不回溯，依次往后进行比较，而指向模式串的指针需要回溯，当某个位置的字符匹配失败时，模式串指针根据next数组指向相应的位置，再进行匹配。
17.二叉树与度为2的有序树的区别
答：（1）度为2的树至少有3个结点，而二叉树可以为空
(2)二叉树无论孩子是否有两个，均需要区分左右孩子
而度为2的有序树只有一个孩子的话，不需要区分左右孩子
18.完全二叉树和满二叉树的区别
答：满二叉树指树中的每层都含有最多的结 点
完全二叉树指一个有n个结点的二叉树，最后一个分支结点的序号是n/2
19.二叉排序树和平衡二叉树的区别
答：二叉排序树：左子树上所有结点的关键字均小于根节点的关键字，右子树上所有结点的关键字均大于根结点的关键字，并且左右子树又各是一棵二叉排序树
平衡二叉树：左子树和右子树的深度之差不超过1
20.什么叫二叉树的遍历？
答：沿着某条搜索路径，依次对树中每个结点仅做一次访问
21.哈夫曼树与哈夫曼编码的作用是什么？什么是前缀编码？
答：哈夫曼树：带权路径长度WPL最小的二叉树
哈夫曼树的作用：用来实现哈夫曼编码，以及后续的解码
哈夫曼编码的作用：用来压缩网络传输的文件
前缀编码是一编码不是任何其他编码前缀的编码
22.线性表，树，图，哪些可以是空的？
答：线性表可以为空（空表），树可以为空（空树），图不可以为空图（必须要有一个顶点，但是边可以为空）
23.什么是完全图？
答：任意两个顶点之间都存在边（任意两点都相邻）
24.什么是极大连通子图？什么是极小连通子图？
答:极大连通子图：在一个连通子图中，包含和顶点有关所有的边，就是极大连通子图（连通分量）
极小连通子图：既要保持图连通，又要使得边数最小的子图，那就是极小连通子图（生成树）
25.简述下邻接表与邻接矩阵的区别
答：（1）对于任一确定的无向图，邻接矩阵是唯一的，但邻接表不唯一
（2）邻接矩阵的空间复杂度为0（n^2），而邻接表的空间复杂度为0(n+e)
（3）在邻接表上容易找到任意一顶点的第一个邻接点和下一个邻接点，而邻接矩阵不方便。
（4）邻接矩阵多用于稠密图的存储，而邻接表多用于稀疏图的存储
26.什么叫图的遍历？并简述下广度优先遍历和深度优先遍历
答：从图中任意一个顶点出发，对图中所有顶点只访问一次
广度优先遍历：指的是从图的一个未遍历的结点出发，先遍历这个节点的相邻节点，再依次遍历，每个相邻节点的相邻节点。类似树的层次遍历。
深度优先遍历：指从图中一个未访问的顶点V开始，沿着一条路一直走到底，然后从这条路尽头的结点回退到上一个结点，再从另一条路开始走到底....不断递归重复此过程，直到所有的顶点都遍历完成。类似树的先序遍历。
（通俗来讲就是，一条路走到黑，先走完一条路，再换条路继续走）
27.什么是最短路径？
答：指在一个赋权图的两个节点之间找到一个具有最小权的路径
28.简述下迪杰斯特拉（dijkstra）算法？
答：迪杰斯特拉（dijkstra）算法是典型求单源（一个顶点到另外一个顶点）最短路径算法，用于计算一个结点到其他结点的最短路径。它的主要特点是以起始点为中心向外层层扩散（广度优先遍历思想），直到扩散到终点为止。
29.什么是最小生成树？最小生成树是不是唯一的？
答：最小生成树：图的所有生成树中具有边上的权值之和最小的树
最小生成树不唯一：如果最小生成树的其中一条边或者几条边可以被其他边取代，最后生成的最小生成树权重一样，就表明最小生成树不唯一
30.简述下求最小生成树的2种算法
答：第一种是克鲁斯卡尔（kruskal）算法。它的要点就是选边。即从最短的边开始生成森林，最后连成树。
第二种是普里姆（prim）算法。它的要点就是选点。即从某一点出发，在两个点之间选择权重最小的一条边，连接两个点，加入生成树之中。
31.简述下AOV网、AOE网、拓扑排序以及关键路径？
答：AOV网：用顶点表示活动，用弧表示活动间的优先关系的有向图
AOE网：是以边表示活动的网，其中用顶点表示事情，弧表示活动，权值表示两个活动持续的时间。
拓扑排序：将AOV网中所有活动排成一个序列，使得每个活动的前驱活动都排在该活动的前面。
关键路径：AOE网中从源头到汇点的最长路径的长度
32. 顺序查找、折半查找（二分查找）、分块查找的优缺点
答：（1）顺序查找
优点：
算法简单而且使用面广；
对表的储存结构没有任何要求，顺序存储和链式存储均可；
它并不要求结点之间关键字是否有序。
缺点：
平均查找长度大，特别是当待查找集合中元素较多时，查找效率低。
（2）折半查找
优点：查找效率高。
缺点：它要求表必须是有序表，且只适用于顺序存储。
（3）分块查找
优点：块内记录是任意的，在表中进行插入，删除运算比较容易，不需要移动大量记录。
缺点：需要增加一个辅助数组的存储空间和将初始表分块的排序运算。
33.什么是B树？
答：B树即平衡查找树，一般理解为平衡多路查找树
34.静态查找和动态查找的区别
答：有插入，删除是动态查找，而静态查找只对表执行查找操作，并不会动态添加元素
顺序查找、折半查找、分块查找、散列表适用于静态查找
二叉排序树、平衡二叉树、B树是动态查找
35.什么现象叫“冲突”？什么是同义词？
答：发生了碰撞就叫冲突，
这些发生碰撞的不同关键字就叫同义词
36.什么是散列表的装填因子？有什么特点？
答：装填因子α：散列表中的元素个数与散列表大小的比值
特点：α越小，填入表中的元素较少，产生冲突的可能性就越小。
37.什么是算法的稳定性？
答：稳定的排序算法就是序列中两个相同的数字在排序前后位置顺序未改变。
38.简述内部排序与外部排序的区别
答： 内部排序是在内存中进行排序
外部排序是由于信息庞大，无法将整个文件放在内存中进行排序，需要将待排序的记录存储在外存上，排序时候再把数据一部分一部分调用内存进行排序。
39.数据结构有哪些排序算法？说一到两个排序算法的优劣？并比较时间复杂度
（各方法如何实现要会用语言描述）
答：内部排序包括：插入排序、选择排序、交换排序、归并排序、基数排序。
其中插入排序包括：直接插入排序、折半插入排序、希尔排序；选择排序包括：简单选择排序，堆排序；交换排序包括：冒泡排序、快速排序。
（1）直接插入排序（稳定）：基本思想为：将序列分为有序部分和无序部分，从无序部分依次选择元素与有序部分比较找到合适的位置，将原来的元素往后移，将元素插入到相应位置上。
时间复杂度为：0（n^2）,空间复杂度为0（1）
（2）折半插入排序（稳定） ：基本思想为：顺序地把待排序的序列中的各个元素按其关键字的大小，通过折半查找插入到已排序的序列的适当位置。
优点是：比较次数大大减少
平均时间复杂度为0（n^2）,空间复杂度为0（1）
（3）希尔排序（不稳定）基本思想为：把元素按下标的一定增量进行分组，对每组使用直接插入排序。随着增量逐渐减少，当增量减至1时，整个文件恰被分为一组，算法终止。
优点是：让关键字值小的元素能够很快移动到前面，且序列基本有序时进行直接插入排序时间效率会提升很多
空间复杂度为0(1）
（4）简单选择排序（不稳定）：基本思想为：从头到尾顺序扫描序列，找出最小的元素，和剩下的元素中第一个元素进行交换，重复该操作，直至最终数组有序。
优点是：实现简单，缺点是：每一趟只能确定一个元素的位置，时间效率低。
时间复杂度为0（n^2），空间复杂度为0（1）
（5）堆排序（不稳定）：基本思想为：将无序序列构建成一个堆，根据升序和降序需求选择大根堆或者小根堆，将堆顶元素与末尾元素交换，将最大元素“沉”到数组末端，重新调整堆，反复执行调整交换步骤，直到整个序列有序。
优点：对大文件效率明显提高，但对小文件效率不明显
时间复杂度为0（nlog2n)，空间复杂度为0（1）。
(6）冒泡排序（稳定）基本思路为：对所有相邻记录的关键字值进行比较，如果是逆顺则将其交换，最终达到有序化
时间复杂度为0（n^2）,空间复杂度为0（1）。
（7）快速排序（不稳定）：基本思路为：在序列中任意选择一个元素作为中心，比它大的元素一律向后移动，比它小的元素一律向前移动，形成左右两个子序列，再把子序列按上述操作进行调整，直到所有的子序列中都只有一个元素时序列即为有序。
优点是；每一趟不仅能确定一个元素，时间效率较高。
时间复杂度为O（nlog2n)，空间复杂度为0(log2n)
（8）归并排序（稳定）：基本思想为：把两个或者两个以上的有序表合并成一个新的有序表。
时间复杂度为0（nlogn），空间复杂度和待排序的元素个数相同。
40.简述堆与栈的区别
答： 栈是由系统自动分配的，而堆是人为申请开辟的
栈是连续的空间，而堆是不连续的空间
栈由系统自动分配，速度较快，而堆一般速度比较慢。
- 作者:百川🌊
- 链接:https://www.baichuanweb.cn/article/example-55
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。
