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

问几道笔试题目。。。。。

  •  
  •   linzhi · 2013-09-20 13:24:55 +08:00 · 6680 次点击
    这是一个创建于 4066 天前的主题,其中的信息可能已经有所发展或是发生改变。
    1:递归式的先序遍历一个n节点,深度为d的二叉树,则需要栈空间的大小为:

    A: O(n) B:O(d) C:O(logn) D:(nlogn)


    2. 假设把整数关键码K散列到N个槽列表,以下哪些散列函数是好的散列函数

    A: h(K)=K/N;

    B: h(K)=1;

    C: h(K)=K mod N;

    D: h(K)=(K+rand(N)) mod N, rand(N)返回0到N-1的整数


    3、一个有10亿条记录的文本文件,已按照关键字排好序存储。请设计算法,可以快速的从文件中查找指字关键字的记录


    4、关于Linux系统的负载,以下表述正确的是:

    A: 通过就绪和运行的进程数来反映

    B: 通过TOP命令查看

    C: 通过uptime查看

    D: Load:2.5,1.3,1.1表示系统的负载压力在逐渐变小
    12 条回复    1970-01-01 08:00:00 +08:00
    nybux
        1
    nybux  
       2013-09-20 13:45:14 +08:00
    A,C,文件长度二分,ABC
    slixurd
        2
    slixurd  
       2013-09-20 14:03:27 +08:00
    2,3,4题和楼上一致
    不过第一题= =
    大概B,C是一样的,不过为什么要O(n)不是O(d),不是到叶子就回溯么?
    linzhi
        3
    linzhi  
    OP
       2013-09-20 14:05:36 +08:00
    @slixurd
    @nybux 第一个我觉得是B啊 别的倒没啥问题
    yomuse
        4
    yomuse  
       2013-09-20 14:08:30 +08:00
    话说这几道阿里题,搜下不是有答案了么...
    linzhi
        5
    linzhi  
    OP
       2013-09-20 14:09:27 +08:00
    @yomuse 搜了几个答案 很多错误的 好多作者不负责啊 所以发贴问下~~~
    slixurd
        6
    slixurd  
       2013-09-20 14:13:19 +08:00
    问题是B和C是一样的,求复杂度常数去掉,n=2^d-1
    那B和C一样还能选?当然有可能也是双选....
    主要是我不知道栈空间怎么算
    nybux
        7
    nybux  
       2013-09-20 14:14:09 +08:00
    @slixurd
    @linzhi
    是B,我错了
    linzhi
        8
    linzhi  
    OP
       2013-09-20 14:35:51 +08:00
    @slixurd 如果题目改成n个节点 求需要的辅助栈空间最大长度多少呢?
    slixurd
        9
    slixurd  
       2013-09-20 14:46:45 +08:00
    @linzhi O(logn)吧,我本来就觉得B,C都行
    bengol
        10
    bengol  
       2013-09-20 22:59:57 +08:00
    @slixurd 不一定是平衡二叉树吧
    slixurd
        11
    slixurd  
       2013-09-21 01:48:04 +08:00
    哦= =对,不一定是完全二叉树.....
    稍微剪枝一下就肯定不会用完全二叉树这么没效率的东西了,尤其是深度比较大的时候
    itfanr
        12
    itfanr  
       2013-09-21 11:13:36 +08:00
    阿里题目
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   5393 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 01:26 · PVG 09:26 · LAX 17:26 · JFK 20:26
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.