算法群小测验答案

[Windsooon]

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

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

   答案：栈

   分析：正确率 85.9%

2. 递归比非递归的算法要使用更多的内存，因为

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

   分析：正确率：41.4% 选项 “递归使用了栈而不是队列” 是本身是正确的，但是不是使用更多内存的原因。

3. 以下哪种算法最常使用 memoization?

   答案：动态规划

   分析：正确率 64.1%

4. 链表中，node 代表一个节点，代码 node.next = node.next.next 会导致

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

   分析：正确率 82.5%

5. 在一个最小堆里面

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

   分析：正确率 64.1%

6. 对一个二分查找树做中序遍历会得到

   答案：有序列表

   分析：正确率 75.7%

7. 以下哪个数据结构是图的广度优先查找算法会使用的

   答案：队列

   分析：正确率 68.5%

8. 将 1000 万个范围从 1 到 256 的数字进行排序，使用以下什么算法最快最节省空间：

   答案：桶排序

   分析：正确率 64.1%，其实圆形排序的在这个情况下也能达到桶排序的效果。

9. 一个常见的二维动态规划算法，一般会占用多少空间：

   答案：O(n^2)

   分析：正确率 61.8%

10. 在表达式 T(n) = 2T(n/2) + O(1) 与 T(1) = O(1) 中，T(n) 的时间复杂度为多少？

    答案：O(n)

    分析：正确率 51.0%

[levelworm]

对七道，不错啊，里头有些没学过就是靠推导（猜）

[siyemiaokube]

请问群里还要人吗？我算法数据结构贼溜（

[siyemiaokube]

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

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

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

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

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

[vvqqdd]

@siyemiaokube #3 小哥哥可以教教我算法嘛，我算法贼弱(。・・)ノ

[Windsooon]

@siyemiaokube 你好，欢迎申请，请把此算法题的最佳解法及思路，发到 contact
@ osjobs.net

“给定一个数据流，这个数据流会不断新增整数作为元素，请实现一个函数，返回此数据流最新的 20 个元素中，去掉最小的 5%的元素，去掉最大的 5%元素之后，中间的 90% 元素的和”，也就是在任意时刻，可以获取最近的 20 个 元素的中间 90% 元素的和。”

[tt67wq]

那么群呢

[xupefei]

@Windsooon 招新人直接上 Google onsite 题？