DAA 面试题及答案

下面列出了最常问的 DAA 面试题 及答案。

1) 什么是算法？

“算法”这个名字指的是必须遵循的指令序列，以清晰地解决一个问题。

这是执行一项基本功能所需的指令的逻辑描述。

算法通常是独立于主要语言生成的，也就是说，一个算法可以用多种编程语言实现。

阅读更多

2) 什么是渐近记法？

一种在极限或无界情况下表示函数行为的方式。

这些记法用定义域为自然数集 N={0, 1, 2} 的方法来描述。

这些记法在定义最坏情况运行时间函数 T(n) 时非常方便。

它也可以扩展到实数域。

阅读更多

3) 算法的时间复杂度是多少？

算法的时间复杂度表示程序运行到完成所需的总时间。它通常使用 大 O 记法来表示。

4) 解释冒泡排序算法并举一个合适的例子。

在冒泡排序技术中，列表被分成两个子列表：已排序和未排序。最小的元素从未排序子列表中“冒泡”出来。移动最小元素后，虚拟墙会向前移动一个元素。冒泡排序最初是为了将最大的元素冒泡到列表中。但无论冒泡的是最大的还是最小的元素，都没有区别。这种技术易于理解，但耗时。在这种类型中，比较两个相邻的元素并进行交换。这样，逐步检查整个数组中的元素。对于一个包含“n”个元素的列表，冒泡排序最多需要 n-1 次遍历来排序记录。

阅读更多

5) 解释选择排序算法并举一个合适的例子。

在选择排序中，列表被分成两个子列表：已排序和未排序。这两个列表由一道虚拟墙分隔。我们从未排序的子列表中找到最小的元素并将其交换到开头。然后墙向前移动一个项目，已排序的列表增加，未排序的列表减少。

假设我们有一个包含 n 个元素的列表。通过应用选择排序，第一个元素与所有剩余的 (n-1) 个元素进行比较。最小的元素被放置在第一个位置。再次，第二个元素与剩余的 (n-1) 个元素进行比较。在比较过程中，较小的元素与较大的元素进行交换。类似地，检查整个数组以找到最小的元素，然后相应地进行交换。这里我们需要 n-1 次遍历或重复才能完全重新排列数据。

阅读更多

6) 解释快速排序（分区交换排序）算法并举一个合适的例子。

快速排序基于分治法。它也称为分区交换排序。快速排序方法的基本概念是选择数组中的一个元素，并围绕该元素重新排列其余的元素。这个元素会将主列表分成两个子列表。这个选定的元素称为枢轴（pivot）。一旦选择了枢轴，它会将所有小于枢轴的元素移到枢轴值的左边，将所有大于枢轴的元素移到右边。这个选择枢轴和划分列表的过程会递归地进行，直到子列表只包含一个元素。

阅读更多

7) 什么是 NP 完全问题？

NP 完全问题是 NP 中的一个问题，它与其他 NP 中的问题一样困难，因为 NP 中的任何其他问题都可以以多项式时间将其归约到它。

8) 区分时间效率和空间效率？

时间效率通过估算基本算法函数执行的次数来衡量。空间效率通过计算算法消耗的额外内存单元的数量来衡量。

9) 什么是算法的阶？

算法的阶是算法的标准文档，它被开发出来以表示一个任务，该任务限制了算法的估算时间。算法的阶是定义其效率的一种方法。它通常被称为 O 记法。

10) 什么是穷举搜索？

穷举搜索是一种直接的解决问题的方法，通常直接基于问题的陈述和概念的描述。

11) 有哪些用于提高算法有效性的各种标准？

输入 (Input) - 提供零个或多个外部量。

输出 (Output) - 至少生成一个量。

明确性 (Definiteness) - 每个指令都必须简单且明确。

有限性 (Finiteness) - 如果我们跟踪算法的指令，那么对于所有步骤，算法都会在有限数量的步骤后完成。

有效性 (Effectiveness) - 每个指令都必须是基本的。

12) 解释归并排序算法并举一个合适的例子。

归并排序的基本概念是将列表分成两个大小相对相等的较小子列表。递归地重复此方法，直到子列表中只剩下一个项目。之后，将各种已排序的子列表合并以形成一个已排序的父列表。此过程一直递归，直到得到原始已排序列表。

阅读更多

13) 什么是线性搜索？

线性搜索方法也称为顺序搜索技术。线性搜索是一种按顺序在列表中搜索项目的技术。在此技术中，从列表/数组的开头或从最后一个元素到数组的第一个元素开始搜索数组以查找所需项目，并继续进行，直到找到元素或搜索完整个列表/数组。

优点

1. 这是一种简单且传统的查找信息的技术。线性或顺序名称暗示了元素的存储方式是系统的。
2. 列表中的项目可以是任何顺序。也就是说，线性搜索可以应用于已排序或未排序的线性数据结构。

缺点

1. 当列表中存在大量项目时，此过程效率低下。
2. 它消耗更多时间并降低系统的检索率。

时间复杂度：O(n)

14) 什么是二分搜索？

二分搜索比线性搜索效率高。但是，它不能应用于未排序的数据结构。二分搜索基于分治法。二分搜索从检查数组的中间元素开始。这决定了一个对象是位于前半部分还是后半部分。如果对象在前半部分，我们无需检查后半部分；如果对象在后半部分，则无需检查前半部分。类似地，我们重复此过程，直到找到列表中的对象或未找到。

要实现二分搜索技术，项目必须是已排序的。

二分搜索的执行方式如下：

• 将键与数组中间位置的元素进行比较。
• 如果键与元素匹配，则返回它并停止。
• 如果键小于中间位置的元素，则要查找的元素必须在数组的前半部分；否则，它必须在数组的后半部分。
• 对数组的较低（或较高）部分重复此方法，直到找到该元素。

阅读更多

15) 解释插入排序算法并举一个合适的例子。

选择排序和冒泡排序都会交换元素。但插入排序不会交换元素。在插入排序中，元素被插入到合适的位置，类似于插牌。这里列表被分成两部分：已排序和未排序的子列表。在每次遍历中，从未排序的子列表中取出第一个元素，并将其插入到已排序的子列表中，放在合适的位置。假设我们有“n”个项目，我们需要“n-1”次遍历来排序这些项目。

阅读更多

16) 什么是最优解？

给定一个带有输入的问，我们找出一个满足某些约束的子集。任何满足这些约束的子集都称为可行解。一个最大化或最小化给定目标函数的公平解称为最优解。

17) 为什么使用哈希（Hashing）？

假设我们在一个数组中存储了大量数据。查找数组中项目的所需时间为 O(log n) 或 O(n)，具体取决于数组是否已排序。如果数组已排序，则可以使用诸如二分搜索之类的过程来搜索数组。否则，必须对数组进行线性搜索。如果我们处理非常大的数据集，这两种方法可能都不理想。因此，我们讨论了一种称为哈希的新过程，该过程允许我们在常数时间 O(1) 内更新和获取任何条目。常数时间或 O(1) 性能意味着操作所需的时间不取决于数据大小 n。

阅读更多

18) 解释加密算法是如何工作的？

加密是将明文转换为称为“密文”的秘密代码格式的步骤。为了转换内容，该算法使用一串称为“密钥”的比特进行估计。密钥越大，生成密文的潜在模式就越多。大多数加密算法使用固定块输入的代码，其长度约为 64 到 128 位，而有些则使用流技术。

19) 什么是动态规划？

动态规划是处理具有最优子结构的另一种方法：问题的最优解包含子问题的最优解。这并不一定意味着子问题的每个最优解都将有助于主解决方案。

对于分治法（自顶向下），子问题是独立的，因此我们可以按任何顺序解决它们。

对于贪心算法（自底向上），我们总是可以通过贪心选择来选择“正确”的子问题。

在动态规划中，我们解决许多子问题并保存结果：并非所有子问题都将有助于解决更大的问题。由于最优子结构，我们可以确定至少一些子问题将是有用的。

阅读更多

20) 什么是背包问题？

给定 n 个已知重量 wⁱ 和值 vⁱ (i=1, 2, ..., n) 的元素，以及一个容量为 W 的背包，找出适合背包的最有价值的元素子集。方便的做法是按价值-重量比的降序对给定实例的元素进行排序。然后，第一个元素提供每单位重量的最佳回报，最后一个元素提供最差的回报。

阅读更多

21) 什么是 Warshall 算法？

Warshall 算法是动态规划过程的一个函数，用于查找有向图的传递闭包。

22) 什么是贪心算法？

优化问题的贪心技术总是做出当前看起来最好的选择，并将其添加到当前的子解中。

阅读更多

23) 列出贪心算法的优点。

1. 贪心方法产生可行解。
2. 贪心方法非常容易解决问题。
3. 贪心方法直接实现最优解。

24) 什么是最小生成树？

连通图的生成树是其顶点集与给定图的顶点集相同的树，其边集是给定图的边集的子集。也就是说，任何连通图都有生成树。

生成树 T 的权重 w(T) 是 T 中所有边的权重之和。最小生成树 (MST) 是具有最小可行权重的生成树。

阅读更多

25) 什么是 Kruskal 算法？

这是一种贪心方法。贪心方法选择局部最优解（即，在 MST 中选择具有最小权重的边）。

Kruskal 算法的工作原理如下：

取一个有 'n' 个顶点的图，不断添加最短（成本最低）的边，同时避免产生环，直到添加了 (n - 1) 条边。通常，两条或多条边可能具有相同的成本。在这种方法中，边的选择顺序无关紧要。可能会产生不同的最小生成树，但它们将具有相同的总成本，该成本始终是最小成本。

阅读更多

26) 什么是排序网络？

排序网络是用于对数字序列进行排序的有线和比较器模块网络的数值模型。每个比较器连接两条线，并通过将较小的值输出到一条线，将较大的值输出到另一条线来对值进行排序。排序网络和比较排序算法的主要区别在于，对于排序网络，比较序列是预先确定的，与先前比较的结果无关。这种比较序列的独立性对于方法的并行执行很有用。

阅读更多

27) 什么是 Floyd 算法？

Floyd 算法是一个函数，用于查找所有对最短路径问题。Floyd 算法适用于有向图和无向加权图，但它们不包含负长度的环。

28) 什么是 Prim 算法？

Prim 算法是一种贪心且高效的技术，用于查找加权连通图的最小生成树。

29) Prim 算法的效率如何？

Prim 方法的效率取决于为图选择的数据结构。

30) 什么是 Dijkstra 算法？

Dijkstra 算法解决了单源最短路径问题，即查找从给定顶点（源）到加权图或有向图的另一个顶点的最短路径。Dijkstra 算法对具有非负权重的图实现了正确解决方案。

阅读更多

31) 什么是 Huffman 树？

Huffman 树是一种二叉树，它通过一组预定义的权重来减小从根到叶的加权路径长度。Huffman 树的基本应用是 Huffman 编码。

32) 什么是 Huffman 编码？

Huffman 编码是一种最优的前缀可变长度编码技术，它根据给定文本中字符的频率为其分配位字符串。

阅读更多

33) 列出 Huffman 编码的优点？

Huffman 编码是重要的文件压缩技术之一。

1. 它很简单。
2. 它具有灵活性。
3. 它实现了最优且最短的编码。

34) 什么是动态 Huffman 编码？

在动态 Huffman 编码中，编码树在每次从源文本读取新字符时都会更新。动态 Huffman n 编码用于克服最简单版本的缺点。

35) 什么是回溯？

带边界的深度优先节点生成方法称为回溯。回溯技术之所以有价值，是因为它能够以远少于 m 次试验的次数产生解决方案。

阅读更多

36) 写出动态规划和贪心方法之间的区别。

动态规划

1. 生成大量决策。
2. 它总是给出最优解。

贪心方法

1. 只生成一个决策序列。
2. 它不一定总是提供最优解。

阅读更多

37) Dijkstra 算法的用途是什么？

Dijkstra 过程用于解决单源最短路径问题：给定加权连通图中的一个顶点（源），找出它到所有其他顶点的最短路径。单源最短路径问题需要一系列路径，每条路径都从源指向图中的不同顶点，尽管某些方向可能共享边。

38) 什么是 n-皇后问题？

该问题是在一个 n×n 的棋盘上放置 n 个皇后，使得任意两个皇后都不在同一行、同一列或同一对角线上。

39) 什么是状态空间树？

回溯的处理是通过构建一个包含所做选择的树来完成的。这称为状态空间树。它的根描述了在开始搜索解决方案之前的初始状态。树的第一层节点描述了为解决方案的第一个元素所做的选择，第二层节点描述了为第二个元素所做的选择，依此类推。

40) 什么是分配问题？

将 'n' 个人分配给 'n' 个工作，以使分配的总成本尽可能低。该问题的实例由一个 n×n 的成本矩阵 C 定义，因此该问题可以描述为在矩阵的每一行中选择一个元素，使得没有两个选定的元素在同一列，并且总成本是最小的。