V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
Windsooon
V2EX  ›  算法

算法群小测验答案

  •  
  •   Windsooon · 2020-02-20 21:16:06 +08:00 · 1834 次点击
    这是一个创建于 1498 天前的主题,其中的信息可能已经有所发展或是发生改变。

    谢谢各位的参与,总共收到 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%

    7 条回复    2020-02-21 17:59:09 +08:00
    levelworm
        1
    levelworm  
       2020-02-20 22:03:46 +08:00 via Android
    对七道,不错啊,里头有些没学过就是靠推导(猜)
    siyemiaokube
        2
    siyemiaokube  
       2020-02-21 02:35:48 +08:00 via iPhone
    请问群里还要人吗?我算法数据结构贼溜(
    siyemiaokube
        3
    siyemiaokube  
       2020-02-21 02:55:25 +08:00 via iPhone
    为了证明自己的水平,黑一下第九题。。
    虽然大概能明白出题人想说什么,但还是要说一下 x

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

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

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

    所以说这道题欠缺的条件相当多。一般应该说明对 dp 状态的 io 的需求,作为所需空间的朴素下界。或者如果只考虑额外空间的话,“二维”也是让人摸不着头脑的描述,对于常见的线性的动态规划,所需的空间的下界取决于决策数;而某些特殊形式的动态规划,一般至少能给出状态数作为空间的朴素上界。
    vvqqdd
        4
    vvqqdd  
       2020-02-21 07:52:11 +08:00
    @siyemiaokube #3 小哥哥可以教教我算法嘛,我算法贼弱(。・・)ノ
    Windsooon
        5
    Windsooon  
    OP
       2020-02-21 08:51:09 +08:00
    @siyemiaokube 你好,欢迎申请,请把此算法题的最佳解法及思路,发到 contact
    @ osjobs.net

    “给定一个数据流,这个数据流会不断新增整数作为元素,请实现一个函数,返回此数据流最新的 20 个元素中,去掉最小的 5%的元素,去掉最大的 5%元素之后,中间的 90% 元素的和”,也就是在任意时刻,可以获取最近的 20 个 元素的中间 90% 元素的和。”
    tt67wq
        6
    tt67wq  
       2020-02-21 08:56:51 +08:00 via iPhone
    那么群呢
    xupefei
        7
    xupefei  
       2020-02-21 17:59:09 +08:00
    @Windsooon 招新人直接上 Google onsite 题?
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3336 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 13:22 · PVG 21:22 · LAX 06:22 · JFK 09:22
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.