本文非原创，转载自csdn一匹好人呀

1. 软件工程和计算机有什么区别？

• 基础课程重复度较高。+ 计算机偏学术研究，软件工程偏工程实践。一般来说计算机的学习偏重学习计算机的原理。学习偏理论，学习内容涉及软件也涉及硬件。软件工程，简称 (SE)。SE 的学习主要是围绕着软件的应用、设计、开发、维护架构这几个模块等，偏应用、工程、实践，学习内容涉及一些基本的硬件，但更多是工程的理论和大量的软件实践知识。+ 软件工程培养计划里面一般有项目管理，架构，测试等科目。

2. 算法的基本特征和复杂度

（1）基本特征

  输入、输出、有穷性、确定性、可行性

（2）算法的复杂度

  时间复杂度、空间复杂度

3. 用循环比递归效率高吗？

  递归和循环两者完全可以互换。不能完全决定性地说循环地效率比递归的效率高。

（1）递归算法

• 优点：代码简洁、清晰，并且容易验证正确性。 + 缺点：它的运行需要较多次数的函数调用，如果调用层数比较深，需要增加额外的堆栈处理（还有可能出现堆栈溢出的情况），比如参数传递需要压栈等操作，会对执行效率有一定影响。但是，对于某些问题，如果不使用递归，那将是极端难看的代码。在编译器优化后，对于多次调用的函数处理会有非常好的效率优化，效率未必低于循环。

（2）循环算法

• 优点：速度快，结构简单。 + 缺点：并不能解决所有的问题。有的问题适合使用递归而不是循环。如果使用循环并不困难的话，最好使用循环。

4. P问题、NP问题、NP完全问题的概念

1) P (polynominal) 问题 - 多项式问题

• 存在多项式时间算法的问题。

2) NP (Nondeterministic Polynominal) 问题 - 非确定多项式问题

• 能在多项式时间内验证得出一个正确解的问题。 + 关于 P 是否等于 NP 是一个存在了很久的问题，这里不做讨论。 + 通俗的理解这两个问题的话：在借助计算机的前提下，P 问题很容易求解；NP 问题不容易求解，但对于某一答案我们可以很快验证这个答案是否正确。

举例：

• 最简单，最基本的：枚举集合 $S$ 的所有子集的问题 + 旅行推销员问题 + $N$ 皇后问题 + 背包问题（是一种组合优化的 NP 完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。）

3) NPH (Nondeterminism Polynomial Hard) 问题 - NP难问题

• 它不一定是一个 NP 问题 + 其他属于 NP 的问题都可在多项式时间内归约成它。通俗理解，NP 难问题是比所有 NP 问题都难的问题。

4) NPC (Nondeterminism Polynomial Complete) 问题 - NP 完全问题

• 它是一个 NP 问题 + 其他属于 NP 的问题都可在多项式时间内归约成它。 + 通俗理解，NP 完全问题是介于 NP 问题和 NP 难问题之间的一类问题。

     各问题的关系

5. 几种树

（1）二叉搜索树 (Binary Search Tree)

  二叉搜索树满足的条件：

• 非空左子树的所有键值小于其根节点的键值+ 非空右子树的所有键值大于其根节点的键值
• 左右子树都是二叉搜索树

（2）AVL 树 (Self-balancing Binary Search Tree)

  AVL 树又称为高度平衡的二叉搜索树。一棵 AVL 树或者是空树，或者是具有下列性质的二叉搜索树：它的左子树和右子树都是 AVL 树，且左子树和右子树的高度之差的绝对值不超过 1。

（3）红黑树 (Red-Black Tree)

  红黑树是这样的一棵二叉搜索树：数中的每一个结点的颜色不是黑色就是红色。可以把一棵红黑树视为一棵扩充二叉树，用外部结点表示空指针。其特性描述如下：

• 特性1：根结点和所有外部结点的颜色是黑色。
• 特性2：从根结点到外部结点的途中没有连续两个结点的颜色是红色。
• 特性3：所有从根到外部结点的路径上都有相同数的黑色结点。

  从红黑树中任一结点 $x$ 出发（不包括结点 $x$），到达一个外部结点的任一路径上的黑结点个数叫做结点 $x$ 的黑高度，亦称为结点的阶（rank），记作 $b_h(x)$。红黑树的高度定义为其根结点的黑高度。

  对普通二叉搜索树进行搜索的时间复杂度为 $O(h)$，对于红黑树则为 $O(log_2n)$。

（4）B 树（特例：2-3树、2-3-4树）

  一棵 $m$ 阶 B 树 (balanced tree of order m) 是一棵平衡的 $m$ 路搜索树，它或者是空树，或者是满足下列性质的树：

• 根结点至少有两个子女。
• 除根结点以外的所有结点（不包括失败节点）至少有 $⌈m/2⌉$ 个子女。
• 所有的失败结点都位于同一层。

（5）B+ 树

  B+ 树是 B 树的一个升级版，B+ 树是 B树 的变种树，有 $n$ 棵子树的节点中含有 $n$ 个关键字，每个关键字不保存数据，只用来索引，数据都保存在叶子节点。是为文件系统而生的。

  相对于 B 树来说 B+ 树更充分的利用了节点的空间，让查询速度更加稳定，其速度完全接近于二分法查找。   

• 特点：在 B 树的基础上每个节点存储的关键字数更多，树的层级更少所以查询数据更快，所有指关键字指针都存在叶子节点，所以每次查找的次数都相同所以查询速度更稳定。
• 应用场景： 用在磁盘文件组织 数据索引和数据库索引。

（6）Trie 树（字典树）

  Trie，又称前缀树，是一种有序树，用于保存关联数组，其中的键通常是字符串。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。一般情况下，不是所有的节点都有对应的值，只有叶子节点和部分内部节点所对应的键才有相关的值。   

6. 邻接矩阵与邻接表

• 邻接矩阵表示法：在一个一维数组中存储所有的点，在一个二维数组中存储顶点之间的边的权值。 + 邻接表表示法：图中顶点用一个一维数组存储，图中每个顶点 $v_i$ 的所有邻接点构成单链表。

对比

• 在邻接矩阵表示中，无向图的邻接矩阵是对称的。矩阵中第 $i$ 行或第 $i$ 列有效元素个数之和就是顶点的度。在有向图中第 $i$ 行有效元素个数之和是顶点的出度，第 $i$ 列有效元素个数之和是顶点的入度。 + 在邻接表的表示中，无向图的同一条边在邻接表中存储的两次。如果想要知道顶点的度，只需要求出所对应链表的结点个数即可。有向图中每条边在邻接表中只出现一次，求顶点的出度只需要遍历所对应链表即可。求入度则需要遍历其他顶点的链表。 + 邻接矩阵与邻接表优缺点 · 邻接矩阵的优点是可以快速判断两个顶点之间是否存在边，可以快速添加边或者删除边。而其缺点是如果顶点之间的边比较少，会比较浪费空间。因为是一个 $n\times n$ 的矩阵。 · 邻接表的优点是节省空间，只存储实际存在的边。其缺点是关注顶点的度时，就可能需要遍历一个链表。

7. 最小生成树 (Minimum Spanning Tree, MST)

  一个有 $n$ 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 $n$ 个结点，并且有保持图连通的最小权值的边。最小生成树可以用 Kruskal（克鲁斯卡尔）算法或 Prim（普里姆）算法求出。

（1）Kruskal（克鲁斯卡尔）算法

  此算法可以称为“加边法”，初始最小生成树边数为 $0$，每迭代一次就选择一条满足条件的最小代价边，加入到最小生成树的边集合里。

  针对边展开，稀疏图有优势。   

（2）Prim（普里姆）算法

  此算法可以称为“加点法”，每次迭代选择代价最小的边对应的点，加入到最小生成树中。算法从某一个顶点s开始，逐渐扩大到覆盖整个连通网的所有顶点。

  针对顶点展开，稠密图有优势。   

8. 最短路径算法 (Shortest Path Algorithm)

（1）Dijkstra 算法——从某一源点到其余各顶点的最短路径，$O(n^2)$

  算法特点：

• 每次找出前一次迭代后具有最低费用的节点，添加到集合中。
• 第 $k$ 次迭代后，可以知道源点到 $k$ 个目的节点的最低费用路径。

（2）Floyd 算法——每一对顶点之间的最短路径，$O(n^3)$

  基本思想：最开始只允许经过1号顶点进行中转，接下来只允许经过 $1$号和 $2$ 号顶点进行中转…允许经过 $1\sim n$ 号所有顶点进行中转，来不断动态更新任意两点之间的最短路程。即求从 $i$ 号顶点到 $j$ 号顶点只经过前 $k$ 号点的最短路程。

（3）深度或广度优先搜索算法（解决单源最短路径）

9. 深度优先搜索（Depth-First-Search, DFS）和广度优先搜索（Breadth-First-Search, BFS）

（1）深度优先搜索（DFS）

  深度优先搜索在搜索过程中访问某个顶点后，需要递归地访问此顶点的所有未访问过的相邻顶点。

  初始条件下所有节点为白色，选择一个作为起始顶点，按照如下步骤遍历：

• 选择起始顶点涂成灰色，表示还未访问。+ 从该顶点的邻接顶点中选择一个，继续这个过程（即再寻找邻接结点的邻接结点），一直深入下去，直到一个顶点没有邻接结点了，涂黑它，表示访问过了。+ 回溯到这个涂黑顶点的上一层顶点，再找这个上一层顶点的其余邻接结点，继续如上操作，如果所有邻接结点往下都访问过了，就把自己涂黑，再回溯到更上一层。+ 上一层继续做如上操作，直到所有顶点都访问过。

（2）广度优先搜索（BFS）

  广度优先搜索在进一步遍历图中顶点之前，先访问当前顶点的所有邻接结点。

• 首先选择一个顶点作为起始结点，并将其染成灰色，其余结点为白色。+ 将起始结点放入队列中。+ 从队列首部选出一个顶点，并找出所有与之邻接的结点，将找到的邻接结点放入队列尾部，将已访问过结点涂成黑色，没访问过的结点是白色。如果顶点的颜色是灰色，表示已经发现并且放入了队列，如果顶点的颜色是白色，表示还没有发现。+ 按照同样的方法处理队列中的下一个结点。 基本就是出队的顶点变成黑色，在队列里的是灰色，还没入队的是白色。

10. 并查集 (Union-Find Set)

  并查集顾名思义就是有“合并集合”和“查找集合中的元素”两种操作的关于数据结构的一种算法。

  并查集，在一些有 $N$ 个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。

  并查集是一种树形的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。

  并查集也是使用树形结构实现。不过，不是二叉树。每个元素对应一个节点，每个组对应一棵树。在并查集中，哪个节点是哪个节点的父亲以及树的形状等信息无需多加关注，整体组成一个树形结构才是重要的。类似森林。

11. 什么是稳定性排序？为什么排序要稳定？

  如果两个具有相同键的对象以相同的顺序出现在排序输出中，则排序算法是稳定的。（假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，$r[i]=r[j]$，且 $r[i]$ 在 $r[j]$ 之前，而在排序后的序列中，$r[i]$ 仍在 $r[j]$ 之前，则称这种排序算法是稳定的；否则称为不稳定的。）

  稳定性的好处：排序算法如果是稳定的，那么从一个键上排序，然后再从另一个键上排序，第一个键排序的结果可以为第二个键排序所用。 基数排序就是这样，先按低位排序，逐次按高位排序，低位相同的元素其顺序再高位也相同时是不会改变的。

12. 冒泡排序

  冒泡排序顾名思义就是整个过程像气泡一样往上升，单向冒泡排序的基本思想是（假设由小到大排序）：对于给定 $n$ 个记录，从第一个记录开始依次对相邻的两个记录进行比较，当前面的记录大于后面的记录时，交换位置，进行一轮比较和换位后，$n$ 个记录的最大记录将位于第 $n$ 位，然后对前 $(n-1)$ 个记录进行第二轮比较；重复该过程，直到记录剩下一个为止。

13. 快速排序算法

（1）请你介绍一下快排算法

  根据哨兵元素，用两个指针指向待排序数组的首尾，首指针从前往后移动找到比哨兵元素大的，尾指针从后往前移动找到比哨兵元素小的，交换两个元素，直到两个指针相遇，这是一趟排序，经常这趟排序后，比哨兵元素大的在右边，小的在左边。经过多趟排序后，整个数组有序。

• 稳定性：不稳定 + 平均时间复杂度：$O(nlogn)$

（2）简述快速排序过程

• 选择一个基准元素，通常选择第一个元素或者最后一个元素。 + 通过一趟排序将待排序的记录分割成独立的两部分，其中一部分记录的元素值均比基准元素值小，另一部分记录的元素值均比基准元素值大。 + 此时基准元素在其排好序后的正确位置。 + 然后分别对这两部分记录用同样的方法继续进行排序，直到整个序列有序。

（3）快排是稳定的吗？

  快排算法是不稳定的排序算法。例如：待排序数组：int a[] ={1, 2, 2, 3, 4, 5, 6}；

• 若选择 $a[2]$（即数组中的第二个 $2$）为枢轴，而把大于等于比较子的数均放置在大数数组中，则 $a[1]$（即数组中的第一个 $2$）会到 $pivot$ 的右边，那么数组中的两个 $2$ 非原序。+ 若选择 $a[1]$ 为比较子，而把小于等于比较子的数均放置在小数数组中，则数组中的两个 $2$ 顺序也非原序。

（4）快排算法最差情况推导公式

  在快速排序的早期版本中呢，最左面或者是最右面的那个元素被选为枢轴，那最坏的情况就会在下面的情况下发生啦：

• 数组已经是正序排过序的。 （每次最右边的那个元素被选为枢轴） + 数组已经是倒序排过序的。 （每次最左边的那个元素被选为枢轴） + 所有的元素都相同（1、2的特殊情况）

  因为这些案例在用例中十分常见，所以这个问题可以通过要么选择一个随机的枢轴，或者选择一个分区中间的下标作为枢轴，或者（特别是对于相比更长的分区）选择分区的第一个、中间、最后一个元素的中值作为枢轴。有了这些修改，那快排的最差的情况就不那么容易出现了，但是如果输入的数组最大（或者最小元素）被选为枢轴，那最坏的情况就又来了。

  快速排序，在最坏情况退化为冒泡排序，需要比较 $O(n^2)$ 次（$n(n - 1)/2$ 次）。

（5）其他关于快速排序的知识

  以从小到大为例：快速排序的基本思想是任取待排序序列的一个元素作为中心元素(可以用第一个，最后一个，也可以是中间任何一个)，习惯将其称为 $pivot$，枢轴元素；将所有比枢轴元素小的放在其左边，将所有比它大的放在其右边，形成左右两个子表；然后对左右两个子表再按照前面的算法进行排序，直到每个子表的元素只剩下一个。

  可见快速排序用到了分而治之的思想。

  将一个数组分成两个数组的方法为：先从数组右边找到一个比枢轴元素小的元素，将数组的第一个位置赋值为该元素；再从数组的左边找到一个比枢轴元素大的元素，将从上面取元素的位置赋值为该值；依次进行，直到左右相遇，把枢轴元素赋值到相遇位置。

  快速排序之所比较快，因为相比冒泡排序，每次交换是跳跃式的。每次排序的时候设置一个基准点，将小于等于基准点的数全部放到基准点的左边，将大于等于基准点的数全部放到基准点的右边。这样在每次交换的时候就不会像冒泡排序一样每次只能在相邻的数之间进行交换，交换的距离就大的多了。因此总的比较和交换次数就少了，速度自然就提高了。当然在最坏的情况下，仍可能是相邻的两个数进行了交换。因此快速排序的最差时间复杂度和冒泡排序是一样的都是 $O(n^2)$，它的平均时间复杂度为 $O(nlogn)$。

（6）解释下快排为什么快？不要说快排的什么复杂度或者算法过程，回答为什么快。（这问题我蒙蔽的一匹，最后听老师意思是说从存储中内存和硬盘读取数据频率那里谈，莫非是数据量太大的时候其他排序涉及到外排序、快排二分几次后就避免了外排序的硬盘交互问题？？）

（7）归并排序的最坏时间复杂度优于快排，为什么我们还是选择快排？

• 快排查找的常量要比归并小。 + 绝大多数情况下，快排遇到的都是平均情况，也就是最佳情况，只有极个别的时候会是最坏情况，因此往往不考虑这种糟糕的情况。

或：

• C++ 模板有很强的 inline 优化机制，比较操作相对于赋值（移动）操作要快的多（尤其是元素较大时） + 另一方面，一般情况下，归并排序的比较次数小于快速排序的比较次数，而移动次数一般多于快速排序的移动次数，二者大约都是 2~3 倍的差距。

  因为这样，在 C++ 中快排要比归并排序更快，但其实在 Java 中恰恰相反，移动（赋值）一般比比较快。

14. 快速排序和归并排序的优缺点

1) 快速排序的优缺点

• 优点：快，平均性能好，时间复杂度为 $O(nlogn)$。 + 缺点：不稳定，初始序列有序或基本有序时，时间复杂度降为 $O(n^2)$。

2) 归并排序的优缺点

• 优点：快，时间复杂度为 $O(nlogn)$；是一种稳定的算法；是最常用的外部排序算法（当待排序的记录放在外存上，内存装不下全部数据时，归并排序仍然适用，当然归并排序同样适用于内部排序）。 + 缺点：空间复杂度高（需要 $O(n)$ 的辅助空间）。

15. 插入排序

（1）基本思想

  每一步将一个待排序的数据插入到前面已经排好序的有序序列中，直到插完所有元素为止。

  插入排序的工作方式像许多人排序一手扑克牌。开始时，我们的左手为空并且桌子上的牌面向下。然后，我们每次从桌子上拿走一张牌并将它插入左手中正确的位置。为了找到一张牌的正确位置，我们从右到左将它与已在手中的每张牌进行比较。拿在左手上的牌总是排序好的，原来这些牌是桌子上牌堆中顶部的牌。

  插入排序是指在待排序的元素中，假设前面 $n-1$(其中 $n>=2$)个数已经是排好顺序的，现将第 $n$ 个数插到前面已经排好的序列中，然后找到合适自己的位置，使得插入第 $n$ 个数的这个序列也是排好顺序的。按照此法对所有元素进行插入，直到整个序列排为有序的过程，称为插入排序。

（2）复杂度

  插入排序的平均时间复杂度也是 $O(n^2)$，空间复杂度为常数阶 $O(1)$，具体时间复杂度和数组的有序性也是有关联的。

16. 希尔排序 (Shell sort)

  希尔排序 (Shell’s Sort) 是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。

  它通过比较相距一定间隔的元素来进行，各趟比较所用的距离随着算法的进行而减小，直到只比较相邻元素的最后一趟排序为止。

  基本思想：希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

17. 选择排序

（1）基本思想

  找到当前数字序列中最大（最小）的数，记录其所在位置，将其和最前面（最后面）的数进行交换，使最大（最小）的元素上浮（下沉）到本次排序的最前面（最后面），从而完成一趟(pass)排序。下一趟排序时，已经有序的元素不再参与。这样的话，$n$ 个元素需要进行 $n-1$ 趟排序！！！

（2）举个例子

  $4$ 个数字 $4,6,7,5$ 进行从大到小的排序。

• 第一趟：参与数字序列：$4,6,7,5$ · 找到该数字序列中最大的数 7，记录其所在位置，将其和第一个位置的数 4 进行比较，7 大于 4，所以 7 和 4 交换，得到新的序列 $(7),6,4,5$ · 经过第一趟的排序，使数字序列中最大的数 7 上浮到最前面，此时7属于有序的元素，不需要参与到下一趟的排序。 + 第二趟排序：参与数字序列：$6,4,5$ · 找到该数字序列中最大的数 6，记录其所在位置，将其和第一个位置的数 6 进行比较，6 等于 6，不需要交换，得到新的序列 $(7,6),4,5$ · 经过第二趟的排序，使数字序列中第二大的数 6 上浮到第二个前面，此时 7, 6 属于有序的元素，不需要参与到下一趟的排序。 + 第三趟排序：参与数字序列 $4,5$ · 找到该数字序列中最大的数 5，记录其所在位置，将其和第一个位置的数4进行比较，5 大于 4，所以 5 和 4 交换，得到新的序列 $(7,6,5),4$ · 经过第三趟的排序，使数字序列中第三大的数 5 上浮到第三个前面，此时 7, 6, 5 属于有序的元素，不需要参与到下一趟的排序。 + 最后就剩下一个数 4，就不需要进行排序，排序最终得到的数字序列为：$7,6,5,4$。

（3）选择排序的关键点

• 采用双层循环：时间复杂度是 $O(n^2)$ · 外层循环表示的是排序的趟数，$n$ 个数字需要 $n-1$ 趟，因此，外层循环的次数是 $n-1$ 次；同时也代表数的位置。 · 内层循环表示的是每一趟排序的数字。根据选择排序的思想，第 $i$ 趟排序时，最前面的位置就是 $i$，用一个循环来不断更新。 + 找到最值数的位置，将该位置的数和当前序列最前面（最后面）位置的数进行交换。（稳定排序）

18. 堆排序

（1）堆排序的基本思路

• 将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆（一般升序采用大顶堆，降序采用小顶堆）。+ 将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端。+ 重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整 + 交换步骤，直到整个序列有序。

（2）堆的操作

  在堆的数据结构中，堆中的最大值总是位于根节点（在优先队列中使用堆的话堆中的最小值位于根节点）。堆中定义以下几种操作：

• 最大堆调整（Max Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点。+ 创建最大堆（Build Max Heap）：将堆中的所有数据重新排序。+ 堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算。

（3）堆排序的优缺点

• 比快速排序的优点：在最坏情况下它的性能很优越。 + 比归并排序的优点：使用的辅助存储少。 + 缺点：不适合太小的待排序列（因为需要建堆）；不稳定，不适合对象的排序。

19. 计数排序 (Counting Sort)

  计数排序，不是基于元素比较，而是利用数组下标确定元素的正确位置。

  计数排序是一个非基于比较的排序算法。它的优势在于在对一定范围内的整数排序时，它的复杂度为 $Ο(n+k)$（其中 $k$ 是整数的范围），快于任何比较排序算法。当然这是一种牺牲空间换取时间的做法，而且当 $O(k)>O(nlogn)$ 的时候其效率反而不如基于比较的排序（基于比较的排序的时间复杂度在理论上的下限是 $O(nlogn)$，如归并排序，堆排序）。计数排序是一个稳定的排序算法。

20. 介绍下桶散列

21. 桶排序 (Bucket sort)

（1）基本思想：划分多个范围相同的区间，每个子区间自排序，最后合并

  桶排序是将待排序集合中处于同一个值域的元素存入同一个桶中，也就是根据元素值特性将集合拆分为多个区域，则拆分后形成的多个桶，从值域上看是处于有序状态的。对每个桶中元素进行排序，则所有桶中元素构成的集合是已排序的。

（2）算法过程

• 根据待排序集合中最大元素和最小元素的差值范围和映射规则，确定申请的桶个数；
• 遍历待排序集合，将每一个元素移动到对应的桶中；
• 对每一个桶中元素进行排序，并移动到已排序集合中。

22. 基数排序 (Radix Sort)

  基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

  基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或 bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为 $O (nlog(r)m)$，其中r为所采取的基数，而 $m$ 为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。

  基数排序的方式可以采用 LSD（Least significant digital）或 MSD（Most significant digital），LSD 的排序方式由键值的最右边开始，而 MSD 则相反，由键值的最左边开始。   

  基数排序是一种稳定的排序算法，但有一定的局限性：

• 关键字可分解。+ 记录的关键字位数较少，如果密集更好。+ 如果是数字时，最好是无符号的。

23. 基数排序 vs 计数排序 vs 桶排序

  这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：

• 基数排序：根据键值的每位数字来分配桶。
• 计数排序：每个桶只存储单一键值。
• 桶排序：每个桶存储一定范围的数值。

24. 各类排序算法对比

（1）时间复杂度

• 平方阶 $O(n^2)$ 排序 —— 各类简单排序：直接插入、直接选择和冒泡排序
• 线性对数阶 $O(nlog_2n)$ 排序 —— 快速排序、堆排序和归并排序 + $O(n^{1+§})$ 排序，$§$ 是介于 0 和 1 之间的常数 —— 希尔排序 $O(n^{1.3})$
• 线性阶 $O(n)$ 排序 —— 基数排序，此外还有桶、箱排序

说明：

• 当原表有序或基本有序时，直接插入排序和冒泡排序将大大减少比较次数和移动记录的次数，时间复杂度可降至 $O(n)$。
• 而快速排序则相反，当原表基本有序时，将蜕化为冒泡排序，时间复杂度提高为 $O(n^2)$。
• 原表是否有序，对简单选择排序、堆排序、归并排序和基数排序的时间复杂度影响不大。

（2）稳定性

  排序算法的稳定性：若待排序的序列中，存在多个具有相同关键字的记录，经过排序，这些记录的相对次序保持不变，则称该算法是稳定的；若经排序后，记录的相对次序发生了改变，则称该算法是不稳定的。

• 稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序 + 不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序

（3）选择排序算法准则

  一般而言，需要考虑的因素有以下四点：

  设待排序元素的个数为 $n$.

• 当 n 较大，则应采用时间复杂度为 $O(nlog_2n)$ 的排序方法：快速排序、堆排序或归并排序。+ 当 n 较大，内存空间允许，且要求稳定性：归并排序。+ 当 n 较小，可采用直接插入或直接选择排序。 · 直接插入排序：当元素分布有序，直接插入排序将大大减少比较次数和移动记录的次数。 · 直接选择排序：元素分布有序，如果不要求稳定性，选择直接选择排序。+ 一般不使用或不直接使用传统的冒泡排序。

25. 冒泡排序算法的改进

• 设置一标志性变量 $pos$，用于记录每趟排序中最后一次进行交换的位置。由于 $pos$ 位置之后的记录均已交换到位，故在进行下一趟排序时只要扫描到 $pos$ 位置即可。 + 传统冒泡排序中每一趟排序操作只能找到一个最大值或最小值，我们考虑利用在每趟排序中进行正向和反向两遍冒泡的方法一次可以得到两个最终值(最大值和最小值) , 从而使排序趟数几乎减少了一半。

26. 快速排序的改进

（1）只对长度大于 $k$ 的子序列递归调用快速排序，让原序列基本有序，然后再对整个基本有序序列用插入排序算法排序

  实践证明，改进后的算法时间复杂度有所降低，且当 $k$ 取值为 8 左右时，改进算法的性能最佳。

（2）选择基准元的方式

  对于分治算法，当每次划分时，算法若都能分成两个等长的子序列时，那么分治算法效率会达到最大。也就是说，基准的选择是很重要的。选择基准的方式决定了两个分割后两个子序列的长度，进而对整个算法的效率产生决定性影响。最理想的方法是，选择的基准恰好能把待排序序列分成两个等长的子序列。

[1] 方法1 固定基准元

  如果输入序列是随机的，处理时间是可以接受的。如果数组已经有序时，此时的分割就是一个非常不好的分割。

[2] 随机基准元

  这是一种相对安全的策略。由于基准元的位置是随机的，那么产生的分割也不会总是会出现劣质的分割。在整个数组数字全相等时，仍然是最坏情况，时间复杂度是 $O(n^2)$。实际上，随机化快速排序得到理论最坏情况的可能性仅为 $1/2^n$。所以随机化快速排序可以对于绝大多数输入数据达到 $O(nlogn)$的期望时间复杂度。

[3] 三数取中

• 引入的原因：虽然随机选取基准时，减少出现不好分割的几率，但是还是最坏情况下还是 $O(n^2)$，要缓解这种情况，就引入了三数取中选取基准。 + 分析：最佳的划分是将待排序的序列分成等长的子序列，最佳的状态我们可以使用序列的中间的值，也就是第 $N/2$ 个数。可是，这很难算出来，并且会明显减慢快速排序的速度。这样的中值的估计可以通过随机选取三个元素并用它们的中值作为基准元而得到。事实上，随机性并没有多大的帮助，因此一般的做法是使用左端、右端和中心位置上的三个元素的中值作为基准元。

27. 散列表（哈希表）查找

（1）哈希表

  哈希表（Hash table，也叫散列表），是根据关键码值 (Key value) 而直接进行访问的数据结构。

（2）解决哈希冲突的方法

  [1] 线性探测法   [2] 平方探测法   [3] 伪随机序列法   [4] 拉链法

28. 哈希表除留取余法的桶个数为什么是质数？

  除留取余，就是使用哈希函数将关键字被某个不大于哈希表长 $m$ 的数 $p$ 除后所得的余数作为哈希地址。如果散列值的因数越多，可能导致的散列分布越不均匀，所以在 $p$ 的选择上需要选择约数少的数值，所以往往将桶个数设置为质数或不包含小于 $20$ 的质因数的合数。

29. 字符串的，模式匹配算法

（1）BF算法（属于朴素的模式匹配算法）

（2）KMP算法

• 在一个字符串中查找是否包含目标的匹配字符串。其主要思想是每趟比较过程让子串向后滑动一个合适的位置。当发生不匹配的情况时，不是右移一位，而是移动（当前匹配的长度 - 当前匹配子串的部分匹配值）位。 + 核心：避免不必要的回溯。

30. 贪心算法 vs 动态规划 vs 分治法

  分治法，动态规划法，贪心算法这三者之间有类似之处，比如都需要将问题划分为一个个子问题，然后通过解决这些子问题来解决最终问题。

（1）分治法

  分治法（divide-and-conquer）：将原问题划分成 n 个规模较小而结构与原问题相似的子问题；递归地解决这些子问题，然后再合并其结果，就得到原问题的解。

  分治模式在每一层递归上都有三个步骤：

• 分解（Divide）：将原问题分解成一系列子问题；+ 解决（Conquer）：递归地解各个子问题。若子问题足够小，则直接求解；+ 合并（Combine）：将子问题的结果合并成原问题的解。

  合并排序（merge sort）是一个典型分治法的例子。其对应的直观的操作如下：

• 分解：将 n 个元素分成各含 n/2 个元素的子序列；+ 解决：用合并排序法对两个子序列递归地排序；+ 合并：合并两个已排序的子序列以得到排序结果。

（2）动态规划

  动态规划算法的设计可以分为如下 4 个步骤：

• 描述最优解的结构+ 递归定义最优解的值+ 按自底向上的方式计算最优解的值+ 由计算出的结果构造一个最优解

   分治法是指将问题划分成一些独立的子问题，递归地求解各子问题，然后合并子问题的解而得到原问题的解。与此不同，动态规划适用于子问题独立且重叠的情况，也就是各子问题包含公共的子问题。 在这种情况下，若用分治法则会做许多不必要的工作，即重复地求解公共的子问题。动态规划算法对每个子子问题只求解一次，将其结果保存在一张表中，从而避免每次遇到各个子问题时重新计算答案。

  适合采用动态规划方法的最优化问题中的两个要素：最优子结构和重叠子问题。

• 最优子结构：如果问题的一个最优解中包含了子问题的最优解，则该问题具有最优子结构。 + 重叠子问题：适用于动态规划求解的最优化问题必须具有的第二个要素是子问题的空间要很小，也就是用来求解原问题的递归算法课反复地解同样的子问题，而不是总在产生新的子问题。对两个子问题来说，如果它们确实是相同的子问题，只是作为不同问题的子问题出现的话，则它们是重叠的。

   分治法：各子问题独立     动态规划：各子问题重叠

（3）贪心算法

  贪心算法是使所做的选择看起来都是当前最佳的，期望通过所做的局部最优选择来产生出一个全局最优解。贪心算法对大多数优化问题来说能产生最优解，但也不一定总是这样的。

  贪心算法与动态规划与很多相似之处。特别地，贪心算法适用的问题也是最优子结构。贪心算法与动态规划有一个显著的区别，就是贪心算法中，是以自顶向下的方式使用最优子结构的。贪心算法会先做选择，在当时看起来是最优的选择，然后再求解一个结果子问题，而不是先寻找子问题的最优解，然后再做选择。

  贪心算法是通过做一系列的选择来给出某一问题的最优解。对算法中的每一个决策点，做一个当时看起来是最佳的选择。这一点是贪心算法不同于动态规划之处。在动态规划中，每一步都要做出选择，但是这些选择依赖于子问题的解。因此，解动态规划问题一般是自底向上，从小子问题处理至大子问题。贪心算法所做的当前选择可能要依赖于已经做出的所有选择，但不依赖于有待于做出的选择或子问题的解。因此，贪心算法通常是自顶向下地做出贪心选择，不断地将给定的问题实例归约为更小的问题。贪心算法划分子问题的结果，通常是仅存在一个非空的子问题。

31. 求拓扑排序的几种方法

32. 如何判断一个图是否有环？

33. 给你 20G 的数据，在 3G 内存里进行排序，怎么操作？

34. 堆和栈

1) 程序内存的区域

a) 栈区（stack）

  由编译器自动分配释放 ，存放函数的参数值，局部变量的值等，内存的分配是连续的，类似于平时我们所说的栈，如果还不清楚，那么就把它想成数组，它的内存分配是连续分配的，即，所分配的内存是在一块连续的内存区域内．当我们声明变量时，那么编译器会自动接着当前栈区的结尾来分配内存。

b) 堆区（heap）

  一般由程序员分配释放， 若程序员不释放，程序结束时可能由操作系统回收。类似于链表，在内存中的分布不是连续的，它们是不同区域的内存块通过指针链接起来的。一旦某一节点从链中断开，我们要人为的把所断开的节点从内存中释放。

c) 全局区（静态区）（static）

  全局变量和静态变量的存储是放在一块的，初始化的全局变量和静态变量在一块区域，未初始化的全局变量和未初始化的静态变量在相邻的另一块区域。 程序结束后由系统释放。

d) 文字常量区

  常量字符串就是放在这里的。 程序结束后由系统释放。

e) 程序代码区

  存放函数体的二进制代码。   

2) 堆和栈的区别

1. 概念 · 栈 stack：存放函数的参数值、局部变量，由编译器自动分配释放。 · 堆 heap：是由 new 分配的内存块，由应用程序控制，需要程序员手动利用 delete 释放，如果没有，程序结束后，操作系统自动回收。 2. 因为堆的分配需要使用频繁的 new/delete，造成内存空间的不连续，会有大量的碎片。 3. 堆的生长空间向上，地址越大，栈的生长空间向下，地址越小。

a) 申请方式不同

• 栈：由系统自动分配。例如：在函数中定义一个局部变量 int a = 0; 系统会在栈上自动开辟相应大小。 注意：系统首先会去查看栈上是否有足够的区域去开辟该空间，如果有就直接开辟，如果没有则栈溢出。 + 堆：由程序员自己去申请开辟，并且指明大小。(利用 new/malloc)

b) 申请大小的限制

• 栈：在 Windows 下，栈是向低地址扩展的数据结构，是一块连续的内存的区域。这句话的意思是栈顶的地址和栈的最大容量是系统预先规定好的，在 Windows 下，栈的大小是 2M（也有的说是 1M，总之是一个编译时就确定的常数），如果申请的空间超过栈的剩余空间时，将提示 overflow。因此，能从栈获得的空间较小。 + 堆：堆是向高地址扩展的数据结构，是不连续的内存区域。这是由于系统是用链表来存储的空闲内存地址的，自然是不连续的，而链表的遍历方向是由低地址向高地址。堆的大小受限于计算机系统中有效的虚拟内存。由此可见，堆获得的空间比较灵活，也比较大。

c) 申请效率的比较

• 栈：由系统自动分配，速度较快。但程序员是无法控制的。 + 堆：是由 new/malloc 分配的内存，一般速度比较慢，而且容易产生内存碎片,不过用起来最方便。（new/malloc 后一定要显示的调用 free/delete 去释放内存）

  另外，在 Windows 下，最好的方式是用 VirtualAlloc 分配内存，他不是在堆，也不是在栈，是直接在进程的地址空间中保留一快内存，虽然用起来最不方便。但是速度快，也最灵活。

d) 堆和栈中的存储内容

• 栈： 在函数调用时，第一个进栈的是主函数中后的下一条指令（函数调用语句的下一条可执行语句）的地址，然后是函数的各个参数，在大多数的 C 编译器中，参数是由右往左入栈的，然后是函数中的局部变量。注意静态变量是不入栈的。 当本次函数调用结束后，局部变量先出栈，然后是参数，最后栈顶指针指向最开始存的地址，也就是主函数中的下一条指令，程序由该点继续运行。 + 堆：一般是在堆的头部用一个字节存放堆的大小。堆中的具体内容由程序员安排。

e) 底层不同

• 栈：是连续的空间。 + 堆：不是连续的空间。

  请注意：在栈上所申请的内存空间，当我们出了变量所在的作用域后，系统会自动我们回收这些空间，而在堆上申请的空间，当出了相应的作用域以后，我们需要显式的调用 delete 来释放所申请的内存空间，如果我们不及时得对这些空间进行释放，那么内存中的内存碎片就越来越多，从而我们的实际内存空间也就会变的越来越少，即，孤立的内存块越来越多。在这里，我们知道，堆中的内存区域不是连续的，还是将有效的内存区域经过链表指针连接起来的，如果我们申请到了某一块内存，那么这一块内存区将会从连续的（通过链表连接起来的）内存块上断开，如果我们在使用完后，不及时的对它进行释放，那么它就会被孤立开来，由于没有任何指针指向它，所以这个区域将成为内存碎片，所以在使用完动态分配的内存（通过 new 申请）后，一定要显式的对它进行 delete 删除．对于这一点，一定要切记．．．

35. 如何用栈实现汉诺塔问题？

  汉诺塔实现的基本思路是：不断将 $n$ 个盘的汉诺塔问题转换为 $2$ 个 $(n-1)$ 个盘的汉诺塔问题，用递归实现比较好理解。设 $n$ 盘问题为 $(n, a, b, c)$，其中参数如下结构体所定义，第一个参数表示需要移动的盘子的数量，第二个参数表示 $n$ 个盘子起始所在柱子 $a$，第三个参数表示会被借用的柱子 $b$，第四个参数表示这 $n$ 个盘子所在的目标柱子 $c$。

1) 递归思路

  假设 $(n, a, b, c)$ 表示把 $a$ 柱子上的 $n$ 个盘借助 $b$ 柱子移动到 $c$ 柱子上，这个问题的递归求解方式是：

• 先把 $a$ 柱子的 $(n-1)$ 盘子借助 $c$ 柱子移动到 $b$ 柱子上 $(n-1, a, c, b)$,+ 然后把 $a$ 柱子剩下的一个盘子移动到 $c$ 柱子上 $(1, a, b, c)$，+ 最后把 $b$ 柱子上的 $(n-1)$ 个盘子移动到 $c$ 柱子上 $(n-1, b, a, c)$.

  则问题求解可转换为对 $(n - 1, a, c, b)$、$(1, a, b, c)$、$(n - 1, b, a, c)$ 这三个问题的求解，其中 $(1, a, b, c)$ 不需要递归，可直接实现，将 $n$ 个盘的汉诺塔问题转换为 $2$ 个 $(n-1)$ 个盘的汉诺塔问题，然后使用递归将 $(n-1)$ 盘问题转换成 $(n-2)$ 盘问题，直到盘数为 $1$。

2) 非递归的方式

  使用 $3$ 个栈模拟 $3$ 个塔，每一步的移动，都按照真实情况进行。

  递归方式本质上使用栈来实现的，所以如果采用非递归的方式也是使用栈来辅助实现。

  但是若是用堆栈来实现的话，当将分解出的上述三个问题压入栈时，应该按照“需要先求解的问题后压入”的顺序，也就是压入顺序为：$(n - 1, b, a, c), (1, a, b, c), (n - 1, a, c, b)$.

1
2
3
4
5
6

typedef struct {　　//汉诺塔问题的结构类型
    int N;
    char A;        //起始柱
    char B;        //借助柱
    char C;        //目标柱
}ElementType;    //汉诺塔问题的结构类型

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

//借助栈的非递归实现
void Hanoi(int n)
{
    ElementType P, toPush;
    Stack S;

    P.N = n; P.A = 'a'; P.B = 'b'; P.C = 'c';
    S.top = -1;

    Push(&S, P);
    while (S.top != -1)        //当堆栈不为空时
    {
        P = Pop(&S);
        if (P.N == 1)
            printf("%c  -> %c\n", P.A, P.C);
        else
        {
            toPush.N = P.N - 1;
            toPush.A = P.B; toPush.B = P.A; toPush.C = P.C;
            Push(&S, toPush);        //将第二个待解子问题(n - 1, b, a, c)入栈
            toPush.N = 1;
            toPush.A = P.A; toPush.B = P.B; toPush.C = P.C;
            Push(&S, toPush);        //将可直接求解的子问题(1, a, b, c)入栈
            toPush.N = P.N - 1;
            toPush.A = P.A; toPush.B = P.C; toPush.C = P.B;
            Push(&S, toPush);        //将第一个待解子问题(n - 1, a, c, b)入栈
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

//借助栈的非递归实现
void Hanoi(int n)
{
    ElementType P, toPush;
    Stack S;

    P.N = n; P.A = 'a'; P.B = 'b'; P.C = 'c';
    S.top = -1;

    Push(&S, P);
    while (S.top != -1)        //当堆栈不为空时
    {
        P = Pop(&S);
        if (P.N == 1)
            printf("%c  -> %c\n", P.A, P.C);
        else
        {
            toPush.N = P.N - 1;
            toPush.A = P.B; toPush.B = P.A; toPush.C = P.C;
            Push(&S, toPush);        //将第二个待解子问题(n - 1, b, a, c)入栈
            toPush.N = 1;
            toPush.A = P.A; toPush.B = P.B; toPush.C = P.C;
            Push(&S, toPush);        //将可直接求解的子问题(1, a, b, c)入栈
            toPush.N = P.N - 1;
            toPush.A = P.A; toPush.B = P.C; toPush.C = P.B;
            Push(&S, toPush);        //将第一个待解子问题(n - 1, a, c, b)入栈
        }
    }
}

36. 编译与解释

  翻译高级语言编写的程序的方式有编译和解释两种。

  编译 (compile) 是用编译器 (complier) 程序把高级语言所编写的源程序 (source code) 翻译成用机器指令表达的目标代码，使目标代码和源程序在功能上完全等价，通过连接器 (linker) 程序将目标程序与相关连接库连接成一个完整的可执行程序。其优点是执行速度快，产生的可执行程序可以脱离编译器和源程序存在，反复执行。

  解释 (interpret) 是用解释器 (interpreter) 程序将高级语言编写的源程序逐句进行分析翻译，解释一句，执行一句。当源程序解释完成时目标程序也执行结束，下次运行程序时还需要重新解释执行。其优点是移植到不同平台时不用修改程序代码，只要有合适的解释器即可。

37. new、delete、malloc、free 的关系

• malloc 与 free 是 C++/C 语言的标准库函数，new/delete 是 C++ 的运算符。它们都可用于申请动态内存和释放内存。 + delete 会调用对象的析构函数，和 new 对应，new 调用构造函数，free 只会释放内存。 + 对于非内部数据类型的对象而言，光用 maloc/free 无法满足动态对象的要求。对象在创建的同时要自动执行构造函数，对象在消亡之前要自动执行析构函数。由于 malloc/free 是库函数而不是运算符，不在编译器控制权限之内，不能够把执行构造函数和析构函数的任务强加于 malloc/free。 + 因此 C++ 语言需要一个能完成动态内存分配和初始化工作的运算符 new，以及一个能完成清理与释放内存工作的运算符 delete。注意 new/delete 不是库函数。

1) C++ 中 new 和 malloc 的区别

[1] 属性

  new 和 delete 是 C++ 关键字，需要编译器支持；malloc 和 free 是库函数，需要头文件支持。

[2] 参数

   使用new操作符申请内存分配时无须指定内存块的大小，编译器会根据类型信息自行计算。而malloc则需要显式地指出所需内存的尺寸。

[3] 返回类型

   new 操作符内存分配成功时，返回的是对象类型的指针，类型严格与对象匹配，无须进行类型转换，故 new 是符合类型安全性的操作符。而 malloc 内存分配成功则是返回 void* ，需要通过强制类型转换将 void* 指针转换成我们需要的类型。

[4] 自定义类型

   new 会先调用 operator new 函数，申请足够的内存（通常底层使用 malloc 实现）。然后调用类型的构造函数，初始化成员变量，最后返回自定义类型指针。delete 先调用析构函数，然后调用 operator delete 函数释放内存（通常底层使用 free 实现）。

   malloc/free 是库函数，只能动态的申请和释放内存，无法强制要求其做自定义类型对象构造和析构工作。

[5] “重载”

   C++ 允许自定义 operator new 和 operator delete 函数控制动态内存的分配。

内存区域

   new 做两件事：分配内存和调用类的构造函数，delete 是：调用类的析构函数和释放内存。而 malloc 和 free 只是分配和释放内存。

   new 操作符从自由存储区（free store）上为对象动态分配内存空间，而 malloc 函数从堆上动态分配内存。自由存储区是 C++ 基于 new 操作符的一个抽象概念，凡是通过 new 操作符进行内存申请，该内存即为自由存储区。而堆是操作系统中的术语，是操作系统所维护的一块特殊内存，用于程序的内存动态分配，C 语言使用 malloc 从堆上分配内存，使用 free 释放已分配的对应内存。自由存储区不等于堆，如上所述，布局 new 就可以不位于堆中。

[6] 分配失败

   new 内存分配失败时，会抛出 bac_alloc 异常。malloc 分配内存失败时返回 NULL。

[7] 内存泄漏

   内存泄漏对于 new 和 malloc 都能检测出来，而 new 可以指明是哪个文件的哪一行，malloc 确不可以。

38. C++有哪些性质（面向对象特点）

  封装，继承和多态。

39. 多态性 (polymer phism)

• 多态是指相同的操作或函数、过程可作用于多种类型的对象上并获得不同的结果。不同的对象，收到同一消息可以产生不同的结果，这种现象称为多态。 + 多态是指同样的消息被不同类型的对象接收时导致不同的行为。 所谓消息是指对类成员函数的调用，不同的行为是指不同的实现，也就是调用了不同的函数。（C++ 课本） + 多态性是指允许同一个函数（或操作符）有不同的版本，对于不同的对象执行不同的版本。C++ 支持以下两种多态性：（数据结构课本） [1] 编译时的多态性，表现为函数名（或操作符）的重载； [2] 运行时的多态性，通过派生类和虚函数来实现。

40. 虚函数 (virtual function) 与纯虚函数 (pure virtual function)

（1）虚函数

  一个虚函数是一个在基类中被声明为 “virtual”，并在一个或多个派生类中被重定义的函数。

  虚函数只能是类中的一个成员函数，且不能是静态的。

  利用虚函数，可在基类和派生类中使用相同的函数名定义函数的不同实现，从而实现“一个接口、多种方式”。当用基类指针或引用对虚函数进行访问时，系统将根据运行时指针或引用的实际对象来自动确定调用对象所在类的虚函数版本。

  使用虚函数，系统要增加一定的空间开销用来存储虚函数表，但系统在进行动态联编时的时间开销是很少的，因此，多态性是高效的。

（2）纯虚函数

  在许多情况下，不能在基类中为虚函数给出一个有意义的定义，这时可以将它说明为纯虚函数，将具体定义留给派生类去做。纯虚函数的定义形式为：virtual 返回类型 函数名(形式参数列表) = 0;即在虚函数的声明原型后加上 “=0”，表示纯虚函数根本就没有函数体。

  纯虚函数的作用是在基类中为其派生类保留一个函数的名字，以便派生类根据需要对它进行定义。如果在一个类中声明了纯虚函数，而在其派生类中没有对该函数定义，则该虚函数在派生类中仍然为纯虚函数。

（3）虚函数表

  虚函数（Virtual Function）是通过一张虚函数表（Virtual Table）来实现的，简称为 V-Table。在这个表中，主要是一个类的虚函数的地址表，这张表解决了继承、覆盖的问题，保证其真实反应实际的函数。这样，在有虚函数的类的实例中这个表被分配在了这个实例的内存中，所以，当我们用父类的指针来操作一个子类的时候，这张虚函数表就显得由为重要了，它就像一个地图一样，指明了实际所应该调用的函数。

  C++ 的编译器应该是保证虚函数表的指针存在于对象实例中最前面的位置（这是为了保证取到虚函数表有最高的性能 —— 如果有多层继承或是多重继承的情况下）。 这意味着我们通过对象实例的地址得到这张虚函数表，然后就可以遍历其中函数指针，并调用相应的函数。

（4）在内存中的存储

  C++ 中，

• 虚函数表位于只读数据段（.rodata），即：C++ 内存模型中的常量区。+ 虚函数代码则位于代码段（.text），也就是C++ 内存模型中的代码区。

（5）哪些函数不能声明成虚函数

  在 C++，有五种函数不能被声明成虚函数，分别是：非成员函数、构造函数、静态成员函数、内联成员函数、友元函数这五种，下面分别解释为什么这五种函数不能被声明成虚函数。

• 非成员函数： 非成员函数只能被重载 (overload)，不能被继承 (override)，而虚函数主要的作用是在继承中实现动态多态，非成员函数早在编译期间就已经绑定函数了，无法实现动态多态，那声明成虚函数还有什么意义呢？ + 构造函数： 要想调用虚函数必须要通过“虚函数表”来进行的，但虚函数表是要在对象实例化之后才能够进行调用。而在构造函数运行期间，还没有为虚函数表分配空间，自然就没法调用虚函数了。 + 静态成员函数： 静态成员函数对于每个类来说只有一份，所有的对象都共享这一份代码，它是属于类的而不是属于对象。虚函数必须根据对象类型才能知道调用哪一个虚函数，故虚函数是一定要在对象的基础上才可以的，两者一个是与实例相关，一个是与类相关。 + 内联成员函数： 内联函数是为了在代码中直接展开，减少函数调用花费的代价，虚函数是为了在继承后对象能够准确的执行自己的动作，并且inline函数在编译时被展开，虚函数在运行时才能动态地绑定函数。 + 友元函数： 因为 C++ 不支持友元函数的继承，对于没有继承特性的函数没有虚函数的说法。友元函数不属于类的成员函数，不能被继承。

41. 关于链表的一些问题（涉及到了一点顺序表）

42. 数组和链表的区别

• 从逻辑结构上来看，数组必须实现定于固定的长度，不能适应数据动态增减的情况，即数组的大小一旦定义就不能改变。当数据增加时，可能超过原先定义的元素的个数；当数据减少时，造成内存浪费；链表动态进行存储分配，可以适应数据动态地增减的情况，且可以方便地插入、删除数据项。 + 从内存存储的角度看，数组从栈中分配空间（用 new 则在堆上创建），对程序员方便快速，但是自由度小；链表从堆中分配空间，自由度大但是申请管理比较麻烦。 + 从访问方式类看，数组在内存中是连续的存储，因此可以利用下标索引进行访问；链表是链式存储结构，在访问元素时候只能够通过线性方式由前到后顺序地访问，所以访问效率比数组要低。

43. 如何判断一个链表是否有环，如何找到这个环的起点？

  给定一个单链表，只给出头指针 h：

• 如何判断是否存在环？+ 如何知道环的长度？+ 如何找出环的连接点在哪里？+ 带环链表的长度是多少？

解法：

• 对于问题 1，使用追赶的方法，设定两个指针 slow、fast，从头指针开始，每次分别前进 1 步、2 步。如存在环，则两者相遇；如不存在环，fast 遇到 NULL 退出。 + 对于问题 2，记录下问题1的碰撞点 p，slow、fast 从该点开始，再次碰撞所走过的操作数就是环的长度s。 + 问题 3：有定理：碰撞点 p 到连接点的距离 = 头指针到连接点的距离，因此，分别从碰撞点、头指针开始走，相遇的那个点就是连接点。 + 问题 3 中已经求出连接点距离头指针的长度，加上问题 2 中求出的环的长度，二者之和就是带环单链表的长度。

44. 既然已经有数组了，为什么还要链表？

  链表是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存储到下一个节点的指针 (Pointer)。

  从本质上来讲，链表与数组的确有相似之处，他们的相同点是都是线性数据结构，这与树和图不同，而它们的不同之处在于数组是一块连续的内存，而链表可以不是连续内存，链表的节点与节点之间通过指针来联系。

45. 单向链表和双向链表的优缺点及使用场景

（１）单向链表：只有一个指向下一个节点的指针。

• 优点：单向链表增加删除节点简单。遍历时候不会死循环； + 缺点：只能从头到尾遍历。只能找到后继，无法找到前驱，也就是只能前进。 + 适用于节点的增加删除。

（２）双向链表：有两个指针，一个指向前一个节点，一个后一个节点。

• 优点：可以找到前驱和后继，可进可退； + 缺点：增加删除节点复杂，需要多分配一个指针存储空间。 + 适用于需要双向查找节点值的情况。

46. 循环链表

  循环链表是一个所有节点相互连接，形成一个环的数据结构。链表尾部没有 null 节点。循环链表可以是一个单向链表，也可以是双向链表。   

循环链表的好处

• 任何节点都可以做为头节点。可以从任何节点开始进行链表的遍历。只要当第一个节点被重复访问时，则意味着遍历结束。 + 用于实现队列数据结构是很有帮组的。如果使用循环链表，则不需要为了队列而维护两个指针(front 以及 rear)。只需要维护尾节点一个指针即可，因为尾节点的后向节点就是 front 了。 + 循环链表常用于各应用程序中。例如，当运行多个应用程序时，操作系统通常会把这些程序存入至一个链表，并进行循环遍历，给每个应用程序分配一定的时间来执行。此时循环链表对于 OS 是很有帮助的，当达到链表尾部时，可以方便的从头部重新开始遍历。 + 循环双向链表可以用于实现高级数据结构，例如斐波那契堆 (Fibonacci Heap)。

47. 指针和引用

（1）指针

a) 概念

  一个对象的地址称为该对象的指针。

  通过对象地址访问对象的方式称为指针间接访问。

  用来存放对象地址（即指针）的变量称为指针变量。

b) 指针的有效性

  程序中的一个指针必然是以下 3 种状态之一：1. 指向一个已知对象；2. 值；3. 未初始化的、或未赋值的、或指向未知对象。

• 如果指针的值为０，称为 0 值指针，又称空指针 (null pointer)，空指针是无效的。 + 如果指针未经初始化，或者没有赋值，或者指针运算后指向未知对象，那么该指针是无效的。 · 一个指针还没有初始化，称为“野指针” (wild pointer)。严格地说，每个指针在没有初始化之前都是“野指针”，大多数的编译器都对此产生警告。 · 一个指针曾经指向一个已知对象，在对象的内存空间释放后，虽然该指针仍是原来的内存地址，但指针所指已是未知对象，称为“迷途指针” (dangling pointer)。

  在实际编程中，程序员要始终确保引用的指针是有效的，对尚未初始化或为赋值的指针一般先将其初始化为0值，引用指针之前检测它是否为 0 值。

（2）如何理解引用 (reference)?

  简单地说，引用就是一个对象的别名 (alias name)，其声明形式为：引用类型&引用名称 = 对象名称,…

  引用的本质是位于某个内存地址上的一个指定类型的对象。

  在 C++ 中，引用全部是 const 类型，声明之后不可更改。引用一经定义，就不能指向别的地址，也不能指向别的类型，编译器不会专门开辟内存单元存储引用，而是将有引用的地方替换为对象的地址，接受引用的地方替换为指针。

（3）引用与指针的区别

• 引用必须被初始化，指针不必。 + 引用初始化以后不能被改变，指针可以改变所指的对象。 + 不存在指向空值的引用，但是存在指向空值的指针。

48. 数组名，数组首地址，数组指针的区别

  例如：int array[5] = {0};

  众所周知，其中的 &array 是整个数组 array 的首地址，array 是数组首元素的首地址（和&array[0]一样），其值相同，但是“意义不同”。

  静态数组中，数组名在进行地址操作时，&arr 和 arr 值虽相同，但意义不同：&arr 移动的单位是整个数组，而 arr 移动的单位是数组元素！！

  数组名字、数组名字取地址、数组首元素取地址、指向首元素的指针这四个变量的数值大小是相等的，但是在后面的地址加 1 的操作中，数组名字取地址所得地址在 +1 之后所得的结果与其他变量不同。

1) 数组指针

  数组指针，指的是数组名的指针，即数组首元素地址的指针。即是指向数组的指针。例：int (*p)[10];p 即为指向数组的指针，又称数组指针。

2) 指针与数组名的区别

• 指针：也是一个变量，存储的数据是地址。 + 数组名：代表的是该数组最开始的一个元素的地址。

1
2
3

int a[10];
int *p;
p = &a[0] // 可以写成 p = a;

• 对数组元素 a[i] 的引用也可以写成 *(a+i) 这种形式。 + 赋值语句 p=&a[0] 也可以写成下列形式: p=a。 + p 是个指针，p[i] 与 *(p+i) 是等价的。

  区别：指针是一个变量，可以进行数值运算。数组名不是变量，不可以进行数值运算。

3) 二维数组中的指针

• a+n 表示第 n 行的首地址，在一维数组中，a+n 表示的是数组的第 n+1 个元素的地址； + &a[0][0] 既可以看作数组 0 行 0 列的首地址，同样还可以看作二维数组的首地址。&a[m][n] 就是第 m 行第 n 列的元素的地址； + &a[0] 是第 0 行的首地址，当然 &a[n] 就是第 n 行的首地址； + a[0]+n 表示第 0 行第 n 个元素的地址； + ((a+n)+m) 表示第 n 行第 m 列元素； + *(a[n]+m) 表示第 n 行第 m 列元素；

4) C++ 中的 int*、int**、int&、int*&、int *a[]、int(*a)[]：

1
2
3
4
5
6
7
8

int a;      //a是一个int型【变量】
int *a;     //a是一个指向int型变量的【指针】
int **a;    //a是一个指向int型变量指针的指针，也就是【二级指针】
int &a;     //a是一个【普通变量型引用】，若int &a = i;则a是变量i的一个别名，&a=&i，即a和i的地址一样
int *&a;    //a是一个【指针变量型引用】，若int *&a = i;则a是指针i的一个引用
int a[2];   //a是一个含有两个int型变量的【数组】
int *a[2];  //a是一个【指针数组】，数组a里存放的是两个int型指针
int (*a)[2];//a是一个【数组指针】，a指向一个含有两个int型变量的数组

49. 函数名，函数指针，函数的入口地址的区别

• 指针函数是指带指针的函数，即本质是一个函数，函数返回类型是某一类型的指针。 + 函数指针是指向函数的指针变量，即本质是一个指针变量。

  主要的区别是一个是指针变量，一个是函数。

  函数指针：1. 指针变量  2. 指针变量指向函数

  这正如用指针变量可指向整型变量、字符型、数组一样。

  在编译时 ，每一个函数都有一个入口地址，该入口地址就是函数指针所指向的地址。

  可利用该指针变量调用函数，就如同用指针变量可引用其他类型变量一样，在这些概念上一致的。事实上，每一个函数，即使它不带有返回某种类型的指针，它本身都有一个入口地址，该地址相当于函数名。尽管函数不是变量，但它在内存中仍有其物理地址，该地址能够赋给指针变量。获取函数方法是：用不带有括号和参数的函数名得到。

  函数名相当于一个指向其函数入口指针常量。

  函数名后面加圆括号，表示函数调用。

  若要得到函数的地址，直接用函数名就可以了

  ##############################################################   指针函数和函数指针的区别：

• 指针函数：指带指针的函数，即本质是一个函数。+ 指针函数返回类型是某一类型的指针。

  ##############################################################

  函数指针有两个用途：调用函数和做函数的参数。函数指针的说明方法为：

数据类型标志符 （指针变量名）（形参列表）；

  注 1 ：“函数类型”说明函数的返回类型，由于“()”的优先级高于“*”, 所以指针变量名外的括号必不可少，后面的“形参列表”表示指针变量指向的函数所带的参数列表。例：

1
2
3

int func(int x); /* 声明一个函数 */
int (*f) (int x); /* 声明一个函数指针 */
f=func; /* 将func函数的首地址赋给指针f */

  赋值时函数 func 不带括号，也不带参数，func 代表函数的首地址。

  注 2：函数括号中的形参可有可无，视情况而定。

  下面的程序说明了函数指针调用函数的方法：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

#include
int max(int x,int y){ return(x>y?x:y); }
void main()
{
	int (*ptr)(int, int);
	int a,b,c;
	ptr=max;
	scanf("%d,%d",&a,&b);
	c=(*ptr)(a,b);
	printf("a=%d,b=%d,max=%d",a,b,c);
}

  实际上 ptr 和 max 都指向同一个入口地址，不同就是 ptr 是一个指针变量，不像函数名称那样是死的，它可以指向任何函数。

  注意，指向函数的指针变量没有 $++$ 和 $–$ 运算。

50. const 与 #define 的比较，const 有什么优点?

• const 常量有数据类型，而宏常量没有数据类型。编译器可以对前者进行类型安全检查。而对后者只进行字符替换，没有类型安全检查，并且在字符替换可能会产生意料不到的错误（边际效应） 。 + 有些集成化的调试工具可以对 const 常量进行调试，但是不能对宏常量进行调试。

51. 内存的分配方式有几种?

• 从静态存储区域分配。内存在程序编译的时候就已经分配好，这块内存在程序的整个运行期间都存在。例如全局变量。 + 在栈上创建。在执行函数时，函数内局部变量的存储单元都可以在栈上创建，函数执行结束时这些存储单元自动被释放。栈内存分配运算内置于处理器的指令集中，效率很高，但是分配的内存容量有限。 + 从堆上分配，亦称动态内存分配。程序在运行的时候用 malloc 或 new 申请任意多少的内存，程序员自己负责在何时用 free 或delete 释放内存。动态内存的生存期由我们决定，使用非常灵活，但问题也最多。

52. 全局变量和局部变量有什么区别？是怎么实现的？操作系统和编译器是怎么知道的？

• 生命周期不同：全局变量随主程序创建和创建，随主程序销毁而销毁；局部变量在局部函数内部，甚至局部循环体等内部存在，退出就不存在。 + 使用方式不同：通过声明后全局变量程序的各个部分都可以用到；局部变量只能在局部使用；分配在栈区。

  操作系统和编译器通过内存分配的位置来知道的，全局变量分配在全局数据段并且在程序开始运行的时候被加载。局部变量则分配在堆栈里面 。

53. 进程 process 与线程 thread

  进程是操作系统分配资源的单位，线程是 CPU 调度的基本单位，线程之间共享进程资源。

  进程与线程的一个简单解释(很形象)

  深入理解进程和线程

  进程与线程概念

（1）进程

  计算机的核心是 CPU，它承担了所有的计算任务，而操作系统是计算机的管理者，它负责任务的调度，资源的分配和管理，统领整个计算机硬件；应用程序是具有某种功能的程序，程序是运行于操作系统之上的。

  进程是一个具有一定独立功能的程序在一个数据集上的一次动态执行的过程，是操作系统进行资源分配和调度的一个独立单位，是应用程序运行的载体。 进程是一种抽象的概念，从来没有统一的标准定义。进程一般由程序，数据集合和进程控制块三部分组成。程序用于描述进程要完成的功能，是控制进程执行的指令集；数据集合是程序在执行时所需要的数据和工作区；程序控制块包含进程的描述信息和控制信息是进程存在的唯一标志。

  进程具有的特征：

• 动态性：进程是程序的一次执行过程，是临时的，有生命期的，是动态产生，动态消亡的。+ 并发性：任何进程都可以同其他进行一起并发执行。+ 独立性：进程是系统进行资源分配和调度的一个独立单位。+ 结构性：进程由程序，数据和进程控制块三部分组成。

（2）线程

  在早期的操作系统中并没有线程的概念，进程是拥有资源和独立运行的最小单位，也是程序执行的最小单位。任务调度采用的是时间片轮转的抢占式调度方式，而进程是任务调度的最小单位，每个进程有各自独立的一块内存，使得各个进程之间内存地址相互隔离。

  后来，随着计算机的发展，对 CPU 的要求越来越高，进程之间的切换开销较大，已经无法满足越来越复杂的程序的要求了。于是就发明了线程，线程是程序执行中一个单一的顺序控制流程，是程序执行流的最小单元，是处理器调度和分派的基本单位。一个进程可以有一个或多个线程，各个线程之间共享程序的内存空间(也就是所在进程的内存空间)。 一个标准的线程由线程 ID，当前指令指针 PC，寄存器和堆栈组成。而进程由内存空间(代码，数据，进程空间，打开的文件)和一个或多个线程组成。

（3）进程与线程的区别

• 线程是程序执行的最小单位，而进程是操作系统分配资源的最小单位. + 一个进程由一个或多个线程组成，线程是一个进程中代码的不同执行路线。 + 进程之间相互独立，但同一进程下的各个线程之间共享程序的内存空间(包括代码段，数据集，堆等)及一些进程级的资源(如打开文件和信号等)，某进程内的线程在其他进程不可见。 + 调度和切换：线程上下文切换比进程上下文切换要快得多。

     线程和进程关系示意图

  总之，线程和进程都是一种抽象的概念，线程是一种比进程还小的抽象，线程和进程都可用于实现并发。在早期的操作系统中并没有线程的概念，进程是能拥有资源和独立运行的最小单位，也是程序执行的最小单位，它相当于一个进程里只有一个线程，进程本身就是线程。所以线程有时被称为轻量级进程。

  后来，随着计算机的发展，对多个任务之间上下文切换的效率要求越来越高，就抽象出一个更小的概念-线程，一般一个进程会有多个(也可以是一个)线程。

（4）任务调度

  大部分操作系统的任务调度是采用时间片轮转的抢占式调度方式，也就是说一个任务执行一小段时间后强制暂停去执行下一个任务，每个任务轮流执行。任务执行的一小段时间叫做时间片，任务正在执行时的状态叫运行状态，任务执行一段时间后强制暂停去执行下一个任务，被暂停的任务就处于就绪状态，等待下一个属于它的时间片的到来。这样每个任务都能得到执行，由于 CPU 的执行效率非常高，时间片非常短，在各个任务之间快速地切换，给人的感觉就是多个任务在“同时进行”，这也就是我们所说的并发。   

（5）为何不使用多进程而是使用多线程？

  线程廉价，线程启动比较快，退出比较快，对系统资源的冲击也比较小。而且线程彼此分享了大部分核心对象 (File Handle) 的拥有权。

  如果使用多重进程，但是不可预期，且测试困难。

（6）一个简单的比喻

  做个简单的比喻：进程 = 火车，线程 = 车厢

• 线程在进程下行进（单纯的车厢无法运行） + 一个进程可以包含多个线程（一辆火车可以有多个车厢） + 不同进程间数据很难共享（一辆火车上的乘客很难换到另外一辆火车，比如站点换乘） + 同一进程下不同线程间数据很易共享（A 车厢换到 B 车厢很容易） + 进程要比线程消耗更多的计算机资源（采用多列火车相比多个车厢更耗资源） + 进程间不会相互影响，一个线程挂掉将导致整个进程挂掉（一列火车不会影响到另外一列火车，但是如果一列火车上中间的一节车厢着火了，将影响到所有车厢） + 进程可以拓展到多机，进程最多适合多核（不同火车可以开在多个轨道上，同一火车的车厢不能在行进的不同的轨道上） + 进程使用的内存地址可以上锁，即一个线程使用某些共享内存时，其他线程必须等它结束，才能使用这一块内存。（比如火车上的洗手间）－“互斥锁” + 进程使用的内存地址可以限定使用量（比如火车上的餐厅，最多只允许多少人进入，如果满了需要在门口等，等有人出来了才能进去）－“信号量”

54. 介绍下几种常见的进程调度算法及其流程（FCFS，SJF，剩余短作业优先，优先级调度，轮转法，多级反馈队列等等）

• 先来先服务+ 短作业优先+ 优先级调度+ 最高响应比优先+ 时间片轮转法+ 多级反馈队列调度

55. 虚拟内存

  虚拟内存是计算机系统内存管理的一种技术。它使得应用程序认为它拥有连续可用的内存（一个连续完整的地址空间），而实际上，它通常是被分隔成多个物理内存碎片，还有部分暂时存储在外部磁盘存储器上，在需要时进行数据交换。

56. 内存管理的方式及优点？

  Windows 内存管理方式主要分为：页式管理、段式管理、段页式管理。

（１）页式管理

• 基本原理：将各进程的虚拟空间划分为若干个长度相等的页。把内存空间按页的大小划分为片或者页面，然后把页式虚拟地址与内存地址建立一一对应的页表，并用相应的硬件地址转换机构来解决离散地址变换问题。页式管理采用请求调页和预调页技术来实现内外存存储器的统一管理。 + 优点：没有外碎片，每个内碎片不超过页的大小。 + 缺点：程序全部装入内存，要求有相应的硬件支持，如地址变换机构缺页中断的产生和选择淘汰页面等都要求有相应的硬件支持。增加了机器成本和系统开销。

（２）段式管理

• 基本思想：把程序按内容或过程函数关系分成段，每段有自己的名字。一个用户作业或者进程所包含的段对应一个二维线性虚拟空间，也就是一个二维虚拟存储器。段式管理程序以段为单位分配内存，然后通过地址映射机构把段式虚拟地址转换为实际内存物理地址。 + 优点：可以分别编写和编译，可以针对不同类型的段采取不同的保护，可以按段为单位来进行共享，包括通过动态链接进行代码共享。 + 缺点：会产生碎片。

（３）段页式管理

• 基本思想：系统必须为每个作业或者进程建立一张段表以管理内存分配与释放、缺段处理等。另外，由于一个段又被划分为若干个页，每个段必须建立一张页表以把段中的虚页变换为内存中的实际页面。显然与页式管理时相同，页表也要有相应的实现缺页中断处理和页面保护等功能的表项。 + 优点：段页式管理是段式管理和页式管理相结合而成，具有两者的优点。 + 缺点：由于管理软件的增加，复杂性和开销也增加。另外需要的硬件以及占用的内存也有所增加，使得执行速度下降。

57. 页表、反向页表

58. 计算机是如何启动的？

• BIOS 上电自检+ 查找启动设备+ MBR$\to$引导程序+ 加载 OS 内核+ OS 取得系统控制权

  按下电源开关后，主板各个器件会供电，CPU 供电完成后会进行一段复位的操作。复位完成后会从主板上的存储芯片（BIOS 芯片）里读取一段启动代码进行上电自检。如果硬件设备都检测正常的话，它就会进行下一步：检测启动设备。

  假设它查找的启动设备是一块硬盘。接下来，它会到硬盘的第一个扇区去读取一段程序（主引导记录 Master Boot Record，512 字节——引导程序 + 硬盘分区表、分区表数据 + 结束标志 AA55）。

  当 BIOS 程序找到 MBR 这段数据的时候，它会把数据加载到内存中，然后把系统的控制权交给 MBR 中的那段引导程序。

  MBR 的引导程序取得系统的控制权之后，它会把操作系统的内核加载到内存，然后把系统的控制权交给操作系统的内核。这个时候，操作系统就取得了系统的控制权。接下来的过程就是操作系统正常启动的过程。

59. 数据库系统中事务的概念，事务的特性

（1）事务的概念

• 事务是完成用户某一特定任务的与数据库的一次或多次交互的逻辑单位。 + 对数据库来讲，事务是和数据库交互的一个程序片段。 对于一般意义上的用户来讲，事务是完成一个功能的程序片段或计算机的指令集合。 + 事务（Transaction） 是对数据库进行访问或修改的一个或多个操作，这组操作组成一个单位，共同完成一个任务。（参考资料）

（2）事务的 ACID 特性分别是什么？

• 原子性(Atomicity)：执行事务中的操作要么都做，要么都不做。 + 一致性(Consistency)：一致性要求事务维护数据库的完整性约束。 + 隔离性(Isolation)：并发执行的事务之间不能相互影响。 + 持续性(Durability)：事务一旦提交，它一定是永久生效的。

（3）事务的 ACID 特性怎么保证？（REDO/UNDO 机制）

60. 事务隔离等级

• READ UNCOMMITTED 未提交读取（脏读）——有可能读到别的事务尚未提交的数据 + READ COMMIT 提交读取——只能读到别的事务已经提交的数据 + REPEATABLE READ 可重复读——在同一个事务中，对同一个数据的多次读，值是一样的（取决于第一次读取到的数据），即使在读的过程中别的事务是数据变化了，对你没有影响。 + SERIALIZABLE 串行化——对同一个数据是串行化执行的

61. 黑盒测试和白盒测试

  软件测试要经过的步骤： 单元测试 → 集成测试 → 系统测试 → 验收测试

（1）黑盒测试

  黑盒测试指测试人员通过各种输入和观察软件的各种输出结果来发现软件的缺陷，而不关心程序具体如何实现的一种测试方法。

• 黑盒测试用例设计方法：等价类划分   边界值划分  错误推测法  因果图法  正交表试验法  场景图  功能图

（2）白盒测试

  白盒测试又叫做结构测试，把程序看成装在一个透明的白盒子里，按照程序内部的逻辑测试程序，检测程序中的主要执行通路是否都能按预定要求正确工作。

• 白盒测试常用测试用例设计方法：逻辑覆盖法（逻辑驱动测试）  基本路径测试方法

  白盒测试法的覆盖标准有逻辑覆盖、循环覆盖和基本路径测试。其中逻辑覆盖包括语句覆盖、判定覆盖、条件覆盖、判定/条件覆盖、条件组合覆盖和路径覆盖。六种覆盖标准发现错误的能力呈由弱到强的变化。

• 语句覆盖每条语句至少执行一次。+ 判定覆盖每个判定的每个分支至少执行一次。+ 条件覆盖每个判定的每个条件应取到各个可能的值。+ 判定/条件覆盖的同时满足判定覆盖条件覆盖+ 条件组合覆盖每个判定中各条件的每一种组合至少出现一次。+ 路径覆盖使程序中每一条可能的路径至少执行一次。

62. 关于 5G

  第五代移动通信技术（英语：5th Generation Mobile Communication Technology, 简称 5G）是具有高速率、低时延和大连接特点的新一代宽带移动通信技术，是实现人机物互联的网络基础设施。

  5G 作为一种新型移动通信网络，不仅要解决人与人通信，为用户提供增强现实、虚拟现实、超高清 (3D) 视频等更加身临其境的极致业务体验，更要解决人与物、物与物通信问题，满足移动医疗、车联网、智能家居、工业控制、环境监测等物联网应用需求。最终，5G 将渗透到经济社会的各行业各领域，成为支撑经济社会数字化、网络化、智能化转型的关键新型基础设施。

63. 云计算、云存储、物联网的概念

（1）云计算

  云计算（cloud computing）是分布式计算的一种，指的是通过网络“云”将巨大的数据计算处理程序分解成无数个小程序，然后，通过多部服务器组成的系统进行处理和分析这些小程序得到结果并返回给用户。云计算早期，简单地说，就是简单的分布式计算，解决任务分发，并进行计算结果的合并。因而，云计算又称为网格计算。通过这项技术，可以在很短的时间内（几秒钟）完成对数以万计的数据的处理，从而达到强大的网络服务。

  现阶段所说的云服务已经不单单是一种分布式计算，而是分布式计算、效用计算、负载均衡、并行计算、网络存储、热备份冗杂和虚拟化等计算机技术混合演进并跃升的结果。

（2）云存储

  云存储是一种网上在线存储（英语：Cloud storage）的模式，即把数据存放在通常由第三方托管的多台虚拟服务器，而非专属的服务器上。托管（hosting）公司运营大型的数据中心，需要数据存储托管的人，则透过向其购买或租赁存储空间的方式，来满足数据存储的需求。数据中心营运商根据客户的需求，在后端准备存储虚拟化的资源，并将其以存储资源池（storage pool）的方式提供，客户便可自行使用此存储资源池来存放文件或对象。实际上，这些资源可能被分布在众多的服务器主机上。

（3）物联网

  物联网即物物相连的互联网。物联网是由 Kevin Ashton 教授首次提出，它的基础与核心依旧是互联网，是在互联网的基础上延伸及拓展的网络。

  物联网的用户端延伸和拓展到任何的物品与物品之间，进行通信以及交换信息，即物物相息。物联网广泛应用在网络融合中，它是通过识别技术、智能感知以及普适计算等通信感知的技术来应用的。物联网是继计算机、互联网之后世界信息产业发展的第三次浪潮。

64. 输入网址点击转到之后发生的事

• 用户在浏览器（客户端）里输入或者点击一个连接； + 浏览器向服务器发送 HTTP 请求； + 服务器处理请求，如果查询字符串或者请求体里含有参数，服务器也会把这些参数信息考虑进去； + 服务器更新、获取或者转换数据库里的数据； + 浏览器接受 HTTP 响应； + 浏览器以 HTML 或者其他格式（比如 JPEG、XML 或者 JSON）把 HTTP 响应呈现给用户。

或：

• 第一步：对网址进行 DNS 解析 DNS 解析的过程就是寻找在哪台主机上有你需要的资源的过程，我们通常使用机器的域名来访问这台机器，而不是直接使用其 IP 地址，而将机器的域名转换为 IP 地址就需要域名查询服务，这个过程称为 DNS 解析，它主要充当一个翻译的角色，实现网址到 IP 地址的转换。 + 第二步：进行 TCP 连接 TCP 连接也就是我们常说的三次握手，首先客户端向服务器端发送是否可以连接的请求，服务器端接受到请求后确认客户的 SYN，并向客户端发送自己的 SYN 包，客户端接收到服务器发来的包之后向服务器发送确认包从而完成三次握手。 + 第三步：发送 HTTP 请求 在完成 TCP 连接后，接下来做的事情就是客户端向服务器端发送 HTTP 请求。 + 第四步：服务器处理请求并返回 HTTP 报文 服务器端接到HTTP请求后在会作出响应。 + 第五步：浏览器解析渲染页面 浏览器在收到 HTML, CSS, JS 文件后，它将这些信息渲染到客户端页面上。 浏览器是一个边解析边渲染的过程。首先浏览器解析 HTML 文件构建 DOM 树，然后解析 CSS 文件构建渲染树，等到渲染树构建完成后，浏览器开始布局渲染树并将其绘制到屏幕上。这个过程比较复杂，涉及到两个概念: reflow (回流)和 repain (重绘)。DOM 节点中的各个元素都是以盒模型的形式存在，这些都需要浏览器去计算其位置和大小等，这个过程称为 relow; 当盒模型的位置,大小以及其他属性，如颜色,字体,等确定下来之后，浏览器便开始绘制内容，这个过程称为 repain。页面在首次加载时必然会经历 reflow 和 repain。reflow 和 repain 过程是非常消耗性能的，尤其是在移动设备上，它会破坏用户体验，有时会造成页面卡顿。所以我们应该尽可能少的减少 reflow 和 repain。 + 第六步：连接结束，关闭连接请求

65. TCP/IP，TCP 和 UDP 的区别

• TCP/IP 协议 (Transmission Control Protocol / Internet Protocol) 叫做传输控制/网际协议，又叫网络通讯协议，这个协议是 Internet 国际互联网络的基础。 + TCP/IP 是网络中使用的基本的通信协议。虽然从名字上看 TCP/IP 包括两个协议，传输控制协议 (TCP) 和网际协议 (IP)，但 TCP/IP 实际上是一组协议，它包括上百个各种功能的协议，如：远程登录、文件传输和电子邮件等，而 TCP 协议和 IP 协议是保证数据完整传输的两个基本的重要协议。通常说 TCP/IP 是 Internet 协议族，而不单单是 TC P和 IP。 + TCP/IP 是用于计算机通信的一组协议，我们通常称它为 TCP/IP 协议族。它是 70 年代中期美国国防部为其 ARPANET 广域网开发的网络体系结构和协议标准，以它为基础组建的 INTERNET 是目前国际上规模最大的计算机网络，正因为 INTERNET 的广泛使用，使得 TCP/IP 成了事实上的标准。 + 之所以说 TCP/IP 是一个协议族，是因为 TCP/IP 协议包括 TCP、IP、UDP、ICMP、RIP、TELNET、FTP、SMTP、ARP、TFTP 等许多协议，这些协议一起称为 TCP/IP 协议。以下我们对协议族中一些常用协议英文名： + TCP/IP 是供已连接因特网的计算机进行通信的通信协议。 + TCP/IP 指传输控制协议/网际协议 (Transmission Control Protocol / Internet Protocol)。 + TCP/IP 定义了电子设备（比如计算机）如何连入因特网，以及数据如何在它们之间传输的标准。

66. aloha，CSMA/CA，以太网和 Internet 区别，有了以太网为什么还有 Internet？

  以太网只是组成互联网的一个子集，以太网是现在主流的局域网标准，而互联网是指将大量的局域网连接起来，进行资源的分享。

或：

  以太网（英语：Ethernet）是为了实现局域网通信而设计的一种技术，它规定了包括物理层的连线、电子信号和介质访问层协议的内容。以太网是目前应用最普遍的局域网技术，取代了其他局域网标准如令牌环、FDDI 和 ARCNET。

  互联网（英语：Internet）是一个网络的网络，它是由从地方到全球范围内几百万个私人的，政府的，学术界的，企业的和政府的网络所构成，通过电子，无线和光纤网络技术等等一系列广泛的技术联系在一起。简单地说，以太网是一直为了实现局域网通信而设计的一系列方法，包括物理层传输媒介和 CSMA/CD 协议等内容，而互联网是计算机网络。

67. 流量控制在哪一层起作用？

  数据链路层、传输层

68. 解释下什么是 DMA，介绍下 DMA 流程

  通过在 I/O 设备和内存之间开启一个可以直接传输数据的通路，采用 DMA 控制器来控制一个数据块的传输，CPU 只需在一个数据块传输开始阶段设置好传输所需的控制信息，并在传输结束阶段做进一步处理。

69. 程序的编译执行过程

  构建 C 程序需要 4 个步骤，分别使用 4 个工具完成： preprocessor, compiler, assembler, and linker. 四步完成后生成一个可执行文件。

• 第一步，预处理. 这一步处理 头文件、条件编译指令和宏定义。 + 第二步，编译. 将第一步产生的文件连同其他源文件一起编译成汇编代码。 + 第三步，汇编。将第二步产生的汇编源码转换为 object file. + 第四步，链接. 将第三步产生的一些 object file 链接成一个可执行的文件。

或：

  C 语言的编译链接过程要把我们编写的一个 C 程序（源代码）转换成可以在硬件上运行的程序（可执行代码），需要进行编译和链接。编译就是把文本形式源代码翻译为机器语言形式的目标文件的过程。链接是把目标文件、操作系统的启动代码和用到的库文件进行组织，形成最终生成可执行代码的过程。

  从图上可以看到，整个代码的编译过程分为编译和链接两个过程，编译对应图中的大括号括起的部分，其余则为链接过程。   

70. 说说你对编译原理的理解

  “编译原理课程”讲述高级程序设计语言源程序转换成汇编语言或机器语言的程序时使用的技术、数据结构和算法(即编译程序原理)。

  编译器就是将“一种语言(通常为高级语言)”翻译为“另一种语言(通常为低级语言)”的程序。一个现代编译器的主要工作流程:源代码 (source code) → 预处理器 (preprocessor) → 编译器 (compiler) → 目标代码 (object code) → 链接器(Linker) → 可执行程序 (executables)。

71. Top k 问题

1) 排序（选取前 k 个数）

2) 快排

  快排的 partition 划分思想可以用于计算某个位置的数值等问题，例如用来计算中位数；显然，也适用于计算 TopK 问题

  每次经过划分，如果中间值等于 K ，那么其左边的数就是 Top K 的数据；当然，如果不等于，只要递归处理左边或者右边的数即可。

  该方法的时间复杂度是 $O(n)$，简单分析就是第一次划分时遍历数组需要花费 $n$，而往后每一次都折半（当然不是准确地折半），粗略地计算就是 $n + n/2 + n/4 +… < 2n$，因此显然时间复杂度是 $O(n)$。

  缺点：在海量数据的情况下，我们很有可能没办法一次性将数据全部加载入内存，这个时候这个方法就无法完成使命了

3) 利用分布式思想处理海量数据

  面对海量数据，我们就可以往分布式的方向去思考了。

  我们可以将数据分散在多台机器中，然后每台机器并行计算各自的 TopK 数据，最后汇总，再计算得到最终的 TopK 数据。

4) 利用最经典的方法（堆），一台机器也能处理海量数据

  其实提到 Top K 问题，最经典的解法还是利用堆。

  维护一个大小为 K 的小顶堆，依次将数据放入堆中，当堆的大小满了的时候，只需要将堆顶元素与下一个数比较：如果大于堆顶元素，则将当前的堆顶元素抛弃，并将该元素插入堆中。遍历完全部数据，Top K 的元素也自然都在堆里面了。

  当然，如果是求前 K 个最小的数，只需要改为大顶堆即可。

  对于海量数据，我们不需要一次性将全部数据取出来，可以一次只取一部分，因为我们只需要将数据一个个拿来与堆顶比较。

  另外还有一个优势就是对于动态数组，我们可以一直都维护一个 K 大小的小顶堆，当有数据被添加到集合中时，我们就直接拿它与堆顶的元素对比。这样，无论任何时候需要查询当前的前 K 大数据，我们都可以里立刻返回给他。

  整个操作中，遍历数组需要 $O(n)$ 的时间复杂度，一次堆化操作需要 $O(logK)$，加起来就是 $O(nlogK)$ 的复杂度，换个角度来看，如果 $K$ 远小于 $n$ 的话， $O(nlogK)$ 其实就接近于 $O(n)$ 了，甚至会更快，因此也是十分高效的。

  最后，对于 Java，我们可以直接使用优先队列 PriorityQueue 来实现一个小顶堆。

72. 如何写代码计算根号 n

1) 袖珍计算器算法

2) 二分法

3) 牛顿迭代法

73. 如何一次写出正确的程序？\ 如何知道你写的程序是对的？

74. 微信红包随机金额怎么实现？

1) 关于分配算法，红包里的金额怎么算？为什么出现各个红包金额相差很大？

答：随机，额度在 0.01 和剩余平均值 2 之间。

  例如：发 100 块钱，总共 10 个红包，那么平均值是 10 块钱一个，那么发出来的红包的额度在 0.01元～20 元之间波动。当前面 3 个红包总共被领了 40 块钱时，剩下 60 块钱，总共 7 个红包，那么这 7 个红包的额度在：0.01～（60 / 7 * 2）= 17.14之间。

  注意：这里的算法是每被抢一个后，剩下的会再次执行上面的这样的算法（Tim 老师也觉得上述算法太复杂，不知基于什么样的考虑）。这样算下去，会超过最开始的全部金额，因此到了最后面如果不够这么算，那么会采取如下算法：保证剩余用户能拿到最低1分钱即可。如果前面的人手气不好，那么后面的余额越多，红包额度也就越多，因此实际概率一样的。

2) 微信的金额什么时候算？

答：微信金额是拆的时候实时算出来，不是预先分配的，采用的是纯内存计算，不需要预算空间存储。

  为什么采取实时计算金额？原因是：实时效率更高，预算才效率低下。预算还要占额外存储。因为红包只占一条记录而且有效期就几天，所以不需要多大空间。就算压力大时，水平扩展机器是。

75. 概率计算题：一副扑克牌平均分成三堆，大小王同时在一堆的概率

  假设有 1 2 3 三组，我们先求大王小王在同在 1 组的概率：

• 大王在 1 组 P(B)：18/54 + 大王已经在1组的条件下小王在 1 组 P(A|B)：17/53（因为把大王放在 1 组用掉了一个空位） + 那么大王小王同在 1 组的概率 P：P(A,B) = P(B)*P(A|B) = 18/54 * 17/53

  1，2，3 组都有可能选择，3 * 18/54 * 17/53 = 17/53

76. 命题逻辑的联结词有哪些？

  非、析取、合取、蕴涵、等价