绪论

1.【数据相关基本概念】说一说数据，数据元素，数据项，数据对象，数据结构之间的区别？

  数据是能够输入到计算机中并且能够被计算机处理的符号集合。

  数据项是构成数据元素的最小单位，如学生的学号，年龄；对应关系型数据库中的一个属性；

  数据元素是数据的基本单位，如一个学生，对应关系型数据库中的一条记录；

  数据对象是性质相同的数据元素的集合，如一个班的所有学生，对应关系型数据库中一张学生表；

  数据结构描述的是数据元素之间的关系，以及能够对数据元素施加的操作，包含逻辑结构，物理结构和数据的运算。

2.【数据结构】数据结构中，逻辑结构和物理结构有什么区别？常见的逻辑结构和物理结构有哪些？线性结构和非线性结构的区别？

  逻辑结构描述的是数据元素之间的逻辑关系，它与数据在计算机中如何存储无关，常见的逻辑结构有集合结构，线性结构，树形结构和图状结构。

  物理结构是数据元素之间的关系在计算机中的表示，常见的物理结构有顺序存储，链式存储，索引存储，散列存储。

  逻辑结构也可以按照线性和非线性两种划分；线性结构中数据元素之间的一对一的关系，除了第一个和最后一个结点以外，每一个都有一个唯一的前驱结点和后继结点，如线性表、字符串、队列、栈；而非线性结构包含集合结构（无序性，数据元素之间没有对应关系），一对多关系的树形结构和多对多关系的图状结构。

3.【数据类型】说一下数据类型和抽象数据类型的区别？

  数据类型是一组性质相同的数据集合以及定义在这个集合上的一组操作；它包含基本数据类型如整型，浮点型，字符型和复合数据类型，如结构体，类等；

  而抽象数据类型指的是一个数学模型以及定义在这个数学模型上的一组操作；它包含数据对象，数据关系和基本操作三部分。
// 联想链表这个类，有value属性 - 数据对象； 有next指针 - 数据关系； 有find，insert，delete等操作。

4.【算法和程序的关系】算法和程序之间的关系是什么？

  算法是求解特定问题的方法和步骤，是指令的有限序列；描述算法可以用流程图，伪代码，程序等，所以程序是用特定的编程语言对算法的具体实现。

5.【算法的特性和设计要求】算法的几个特性是什么？算法的设计有哪几个要求？

  算法的特性有五个，分别是输入，输出，有穷性，确定性，可行性。

  算法设计的要求有四个，包括正确性，健壮性，高效性，可读性。

6.【算法的性能评价】算法好坏的衡量标准有哪些？常见的时间复杂度有哪些？如何求一个算法的时间复杂度？

  有时间复杂度和空间复杂度。

  常见的时间复杂度从低到高有O(1),O(logn),O(n),O(nlogn),O(n²)，O(n³),O(2ⁿ)，O(n!)。

  找到和问题规模n有关的且执行频率最高的部分，然后判断代码执行的次数的数量级和n的关系，如和n是线性关系，说明时间复杂度是O(n)，再如发现随着n的增大，执行频率呈指数级下降，说明时间复杂度是O(logn)等。如冒泡排序中执行频次最多的是两层循环，且内层循环中的执行频次和n²成正比，所以时间复杂度是O(n²)。

线性表顺序存储和链表

1.【线性表特点】说说线性表有什么特点？顺序表和链表的区别？

  线性表中数据元素具有一对一的关系，第一个元素具有唯一的后继，最后一个元素具有唯一的前驱；中间的元素有唯一的前驱和后继。

  顺序表是线性表的顺序实现，数据元素在内存中连续，可以实现快速访存，缺点是需要提前开辟固定大小的空间，而且插入和删除开销大，满时需要扩充。而链表是线性表的链式实现，数据元素在内存中不一定连续，不需要提前开辟内存，插入和删除方便，但是查找速度较慢。

2.【链表分类】链表中的单链表、双链表、循环链表有什么关系和区别？

  单链表的结点的指针域只有一个next指针，指向下一个结点或者空；双链表的指针域有两个指针，一个是指向前驱结点的pre，一个是指向后继结点的next指针，可以双向遍历；循环链表也包含循环单链表和循环双链表，以循环单链表为例，其尾节点的next不指向空，而是指向头结点。

3.【链表的实现细节】链表中的头指针、头结点、首元结点有什么区别？链表中设置头结点的优缺点？

  头指针是指向头结点的指针变量；头结点也叫做虚节点、哨兵节点，不实际存储真实的数据；而首元结点是第一个存储真实数据的结点；设置头结点的缺点是带来了额外的空间开销，优点是统一了操作，如对于单链表的头插操作，表空时和表不空时，带头结点的操作是统一的，不需要额外判断表空；还可以利用头结点的数据域来记录表长。

队列和栈

1.【栈和队列】队列和栈的区别？

  栈和队列都是线性表的一种特殊情况。栈是后进先出的，元素从栈顶入，也从栈顶出，而队列是先进先出的，从队尾入，从队头出。

2.【共享栈】简单说说共享栈？

  共享栈即两栈共享同一段数组空间，两个栈的栈底分别在数组的两头，两个栈的栈顶往中间延伸，这样的好处是可以更充分的利用存储空间，只有在整个数组都被用完的时候，才会因为空间不足而溢出。

3.【循环队列】如何区分循环队列中队空还是队满？

  循环队列中设置一个front指针代表队头，一个rear指针代表队尾，入队时，rear = （rear +1 ）% MAXSIZE；出队时，front = (front + 1) % MAXSIZE；如果所有位置都来存储数据，那么将无法区分队空和队满，因为判断条件都是rear == front；

  解决方案①是舍弃一个存储元素的位置，初始化时，仍然是rear = front；即判空条件是rear == front；但是判满的条件是(rear + 1 )%MAXSIZE == front; ②第二种方法就是类内增加size属性用来管理队列的元素个数，size == 0时为空，size == MAXSIZE时为满。

4.【栈的应用】说说栈在括号匹配中的思想？

  遍历括号序列，如果是左括号就入栈，如果是右括号就弹栈一次，代表一对括号匹配成功；遍历完成之后，如果栈空证明给定括号序列是有效的配对括号，否则说明不是有效的括号，即左括号有余。

5.【栈的应用】说说栈在后缀表达式求值中的思想？

  遍历表达式，如果是数，就入栈，如果是运算符，就依次弹栈两次得到op2和op1，然后计算op1 op op2，得到运算结果并压栈；最后如果栈的大小为1，说明运算结束，栈顶元素就是结果。否则说明后缀表达式不合法。

6.【栈的应用】说说栈在计算机系统中的应用？

  ①函数调用：函数调用的调用栈用到了栈，以及递归这种特殊的函数调用方式本质上也是栈；函数调用之前，操作系统会用栈来保存现场，函数调用完成之后，弹栈恢复现场。 ②括号匹配； ③逆波兰表达式的运算等。

7.【队列的应用】说说队列在计算机系统中的应用？

  ①任务调度：如进程调度算法中的先来先服务应用的就是队列的思想； ②消息传递：消息队列可以实现异步通信，多个组件之间通过把消息放入队列进行通信，接收者可以从队列中取出并处理消息； ③缓冲区管理：网络通信、磁盘IO等通常会使用队列来处理数据缓冲区。

8.说说递归的栈溢出问题？循环比递归的效率高吗？

  递归本质上是用系统栈保存现场和恢复现场，当递归的深度达到一定规模，系统栈就会因为栈满而溢出，要想解决这个问题，可以用循环解决。

  不一定。循环和递归各有优缺点：递归的优点是代码结构简洁，容易排查错误，可读性好；缺点是需要带来额外的空间开销；而循环的优点是没有额外的空间开销和额外上下文切换的开销，但是有一些问题只能用递归解决，不能用循环解决，如不知道要多少层循环才能暴力解决，只能用递归。

字符串⭐

1.【KMP算法】字符串的匹配算法有哪些？最高效的是哪种，介绍一下。

// 参考labuladong的笔记：labuladong - 知乎

  字符串的匹配的暴力匹配，时间复杂度是O(m * n) - 因为每次匹配失败都需要重新让j从0开始；最高效的是KMP算法，时间复杂度是O(m+n).

【复习KMP算法】重新认识KMP - 本质上是动态规划 // 忘记之前的next数组

  这里引入一个状态机 - 本质上是一个有向图，联想一下编译原理的词法分析的过程，每次识别字符，在状态机中对应一个状态节点经过某条边转移到另外一个状态节点，我们构造dp数组的过程其实就是在构造这个状态机，而利用dp数组进行search的过程其实就是在状态机上转移状态的过程，遍历txt串，从入口状态j == 0开始，看看匹配过程中能否到达出口状态j == M（M是pat串的长度）。

  dp数组的含义：dp[j][c]表示在状态j时，如果输入是字符c，跳转到的下一个状态。整个dp数组就是一个状态机。

== 名词解释 ==

• 以txt=ABABX，pat=ABABC，此时X和C在匹配为例
• 已匹配成功的部分-ABAB
• 前缀(以首字母开头-从左往右看) 后缀（以最后一个字母结尾-从左往右看）
• 已经匹配成功的部分的最长相同前后缀-AB，特殊地，一个字母的前后缀为空，所以X初始化为0

== KMP ==

• 理解前后缀的意义：前缀对于pat串是有复用价值的，而后缀对于txt串是有复用价值的, 正是由于已经匹配成功的部分pat[0 : j-1]具有最长相同前后缀，才不至于让j每次失败都从0开始（暴力算法）；以上面的例子为例， ABX(这里的AB复用了已经匹配成功部分的[后缀])和ABA（这里的AB复用了已经匹配成功部分的[前缀]）可继续匹配，而没有从pat的第一个A重新开始匹配。
• 理解变量prev的含义：下面用变量prev指向识别已经匹配成功的部分-ABAB的最长相同前后缀-AB的前缀-AB的状态，如0-(A)->1-(B)->2，prev = 2；prev状态和j状态的含义：状态prev维护前缀，状态j维护后缀。

class Solution {
public:
	int strStr(string txt, string pat) {  // txt和pat是由26个小写英文字母构成的字符串
		int M = (int)pat.size(), N = (int)txt.size();
		// 构造dp数组
		vector<vector<int>> dp(M, vector<int>(26, 0));  // 默认失败都回溯到状态0
		dp[0][pat[0]-'a'] = 1;  // 初始化dp[0] - 当且仅当pat[0]作为输入才能够推进状态 - 其它都会回到状态0
		int prev = 0; 
		// 关键在于如何更新prev
		for(int j = 1;j < M;j++) {   // dp[0]已经不需要再更新
			for(int c = 0;c < 26;c++) {
				dp[j][c] = (c == pat[j] - 'a' ? j + 1 : dp[prev][c]); // 识别成功就推进，否则就回溯
			}
			// 更新prev前缀
			prev = dp[prev][pat[j] - 'a']; 
		}
		// search部分
		int j = 0;
		for(int i = 0;i < N;i++) {
			j = dp[j][txt[i] - 'a'];
			if(j == M) return i - M + 1;  // 到达终态-返回起始位置
		}
		return -1;  // 匹配失败
	}
};

【答疑】

• 为什么初始化dp的大小是M而不是M+1？ 因为终态不会再转移到其他状态，所以不需要dp[M]，最大到dp[M-1]就足够；
• 为什么遍历从j = 1开始？ 因为我们在初始化dp的时候是全0,而状态0转移到其它状态的路径只有1条，即通过pat[0]转移到状态1，其它都是转移到自身，所以我们手动构造了dp[0]；
• 为啥需要在内层循环结束后更新prev ？ 因为本轮dp[j]构造完毕之后，已匹配成功的部分变了 - 后缀多了一个pat[j] ，那么为了确保prev的含义（指向识别已成功匹配的部分的最长相同前后缀的前缀的状态）不变，维护前缀的prev自然也要尝试更新 => prev: 在当前的状态prev下，遇到pat[j]之后我要跳转到哪个状态呢 - dp数组的含义会告诉你⬇️
  prev = dp[prev][pat[j] - 'a'];

【练习】28. 找出字符串中第一个匹配项的下标 - 力扣（LeetCode）