算法群小测验答案

谢谢各位的参与，总共收到 266 份完成的问卷。问卷共包括十道题，其中有些题目表达可能并不严谨，不过从结果来说，每道题的正确答案也是最多人选择的。以下是我认为的正确答案，如果各位有不同的意见，欢迎留言。

以下哪种数据结构最常用作判断字符串是否有包含合法的括号，（例如：(ab)）

答案：栈

分析：正确率 85.9%
递归比非递归的算法要使用更多的内存，因为

答案：每次调用递归都需要存储起来

分析：正确率：41.4% 选项 “递归使用了栈而不是队列” 是本身是正确的，但是不是使用更多内存的原因。
以下哪种算法最常使用 memoization?

答案：动态规划

分析：正确率 64.1%
链表中，node 代表一个节点，代码 node.next = node.next.next 会导致

答案：链表无法访问原本的 node.next 的值

分析：正确率 82.5%
在一个最小堆里面

答案：子节点比父节点要大

分析：正确率 64.1%
对一个二分查找树做中序遍历会得到

答案：有序列表

分析：正确率 75.7%
以下哪个数据结构是图的广度优先查找算法会使用的

答案：队列

分析：正确率 68.5%
将 1000 万个范围从 1 到 256 的数字进行排序，使用以下什么算法最快最节省空间：

答案：桶排序

分析：正确率 64.1%，其实圆形排序的在这个情况下也能达到桶排序的效果。
一个常见的二维动态规划算法，一般会占用多少空间：

答案：O(n^2)

分析：正确率 61.8%
在表达式 T(n) = 2T(n/2) + O(1) 与 T(1) = O(1) 中，T(n) 的时间复杂度为多少？

答案：O(n)

分析：正确率 51.0%

siyemiaokube

2020-02-21 02:55:25 +08:00

为了证明自己的水平，黑一下第九题。。
虽然大概能明白出题人想说什么，但还是要说一下 x

“常见的二维动态规划算法”和“一般会占用多少空间”其实是非常非常不准确的说法。稍微精准一点儿的描述是形如“1d/1d”这样的，两个数字表示状态数与决策量的复杂度的多项式系数。

一般的动态规划也需要两个参数来描述，如果不需要对所有状态进行 io，只考虑我们一般比较关心的额外空间的话，对于我们一般讨论的线性的动态规划，所需的空间的复杂度是决策量的复杂度。

极端地，如果不能保证动态规划的过程一定不是 dag，还可能需要高斯消元来求解。（当然有些定义下默认动态规划至少是 dag ）

所以说这道题欠缺的条件相当多。一般应该说明对 dp 状态的 io 的需求，作为所需空间的朴素下界。或者如果只考虑额外空间的话，“二维”也是让人摸不着头脑的描述，对于常见的线性的动态规划，所需的空间的下界取决于决策数；而某些特殊形式的动态规划，一般至少能给出状态数作为空间的朴素上界。