留学生计算机专业本科算法题目和答案讲解

　　算法是计算机编程当中很重要的一个内容，但它同时也是令很多同学感到比较有挑战的部分。今天我们主要给大家分享一些本科阶段的算法真题和答案解析，有需要的小伙伴们，建议收藏起来噢，或许会对你的算法作业和考试有一定的帮助。

　　一、算法真题(解题思路题目最后)

　　(一)Asymptotics & Recurrences

　　eg1：通过增加增长的顺序来对以下功能进行排序。即，找到满足g1 = O(g2)、g2 = O(g3)、g3 = O(g4)、g4 = O(g5)、g5 = O(g6)、g6 = O(g7)、g1、g8的任意配置g1、g2、g3、g4)、g5、g6、g68、g7)、g7 = O(g8)。

　　eg2：找到一个递归T (n) = T(n/3)+ T(2n/3)+ Θ(n)的解决方案。

　　eg3：找到以下递归式的渐近解。用Θ符号来表达你的答案，并给出一个简短的理由。

　　(二)True/False

　　判断题，你认为下面的表述是T正确还是F错误?

　　eg1：二进制插入排序(使用二进制搜索来查找每个插入点的插入排序)需要O(n log n)总操作。

　　eg2：在合并排序执行树中，在树的每个级别上完成的工作量大致相同。

　　eg3：在BST中，我们可以在O (1)时间内找到给定元素的下一个最小元素。

　　eg4：在AVL树中，在插入操作期间，最多需要两个旋转。

　　eg5：计数排序是一种稳定的、就地的排序算法。

　　eg6：在最小堆中，任何元素的下一个最大元素都可以在O(log n)时间中找到。

　　eg7：乘法满足简单的一致哈希假设。

　　eg8：双哈希满足一致哈希假设。

　　eg9：Python生成器可用于迭代具有O (1)内存的潜在无限可数集。

　　二、真题答案&思路分析

　　(一)

　　eg1：f1(n), f5(n), f3(n), f8(n), f7(n), f6(n), f4(n), f2(n).

　　分析：我们计算这个问题的分数为ROUND(10·L-1/N-1)，其中N是函数的数量(这个例子的N=8)，L是我们的解和学生的答案之间的最长公共子序列的长度。最长公共子序列背后的直觉是，我们想从学生的答案中剔除尽可能少的函数，这样剩下的函数将被正确地排序。谁说6.006岁的员工并不好?我们使用L−1N1来规范化分数，因为一个完全错误的答案仍然会使−与正确的答案共享一个长度为1的共同子序列。最长的公共子序列可以使用动态编程来计算，这将在学期末的6.006中教授。

　　eg2：绘制递归树。在每一层上，做Θ(n)工作。级别数是log3/2 n = Θ(lg n)，所以猜测T (n) = Θ(n lg n)，并使用替代方法来验证猜测。

　　eg3：T(n) = Θ(log n).

　　分析：为了看到这一点，请注意，如果我们用T (n)不断替换T (n)的公式来扩展T (n)，我们得到：

　　(二)

　　eg1：F

　　虽然二进制插入排序提高了为下一个被插入的元素找到正确位置所需的时间，但它可能仍然需要O (n)个时间来执行所需的交换时间。这导致了一个O(n²)运行时间，与插入排序相同。

　　eg2：T

　　eg3：F

　　找到下一个最小的元素，即前身，可能需要沿着树的高度向下移动，使运行时间为O (h)。

　　eg4：T

　　eg5：F

　　计算排序是稳定的。但是，它并不到位，因为我们必须腾出额外的空间来存储各种元素的计数。这个空间需求会随着输入的大小的增加而增加。此外，我们必须做一个单独的输出数组来使用计数排序产生答案。

　　eg6：F

　　最小堆不能提供O(log n)时间内的下一个最大元素。要找到下一个最大的元素，我们需要做一个线性的，O (n)，搜索通过堆的数组。

　　eg7：F

　　我们并不知道满足简单均匀哈希假设的哈希函数。

　　eg8：F

　　这些笔记指出，双哈希关系“很接近”。双哈希只提供了n²个排列，而不是n!。

　　eg9：T
　　以上就是本科阶段的算法真题讲解，希望对大家有所帮助。课程学习中遇到难题，欢迎咨询考而思的专业老师!