Charles Z.

阿里实习笔试总结

Filed under Coding Interview on 30 Mar, 2014

有同学做出了答案，感觉有的不准确，有的没有给出详细解答，这里我再总结一下

第一部分 单选题（前10题2分，后10题3分）

选对得满分，选错倒扣1分，不选0分

1.假设一个主机的IP地址为192.168.5.121，而子网掩码为255.255.255.248，那么该主机的网络号部分（包括子网部分）为_______.

192.168.5.120

【知识点】：

  • IP 地址 = {<网络号><主机号>}
  • 网络号 = IP地址与子网掩码做与运算
  • 主机号 = 取反后的子网掩码与IP地址做与运算
  • 我们知道，从IP数据报的首部并不知道源主机或目的主机所连接的网络是否进行了子网的划分。这是因为32位的IP地址本身以及数据报的首部都没有包含任何有关子网划分的信息，这时候就要使用子网掩码。
  • 不管网络有没有划分子网，只要把子网掩码和IP地址进行按位的与运算，就立即得出网络地址来。
  • 如果一个网络不划分子网，那么使用默认子网掩码
2.64位系统上，定义的变量int *a[2][3] 占据_______字节。

48

【知识点】： - 很容易不知道这是个啥，其实它是一个指针二维数组，数组共有6个元素，每个元素存放的是int类型的指针 - 64位操作系统上指针的长度是8

3.Linux中使df -h /home和du -sh /home所查看的已使用的磁盘容量不同，可能的原因是_______

【知识点】

  • du和df命令都被用于获得文件系统大小的信息：df用于报告文件系统的总块数及剩余块数，du -s /用于报告文件系统使用的块数。但是，我们可以发现从df命令算出的文件系统使用块数的值与通过du命令得出的值是不一致
  • 由于du与df命令实施上的不同: du -s命令通过将指定文件系统中所有的目录、符号链接和文件使用的块数累加得到该文件系统使用的总块数；而df命令通过查看文件系统磁盘块分配图得出总块数与剩余块数。
  • 文件系统分配其中的一些磁盘块用来记录它自身的一些数据，如i节点，磁盘分布图，间接块，超级块等。这些数据对大多数用户级的程序来说是不可见的，通常称为Meta Data。
  • du命令是用户级的程序，它不考虑Meta Data，而df命令则查看文件系统的磁盘分配图并考虑Meta Data。df命令获得真正的文件系统数据，而du命令只查看文件系统的部分情况。
4.C语言程序运行在32位机器上。程序中定义了三个变量xyz，其中x和z是int型，y是short。x=127，y=-9，执行赋值语句z= x+y之后，xyz分别是多少？______
5.有下面的定义，myArray[2][2]的值是？
int[][] myArray = new int[3][]{
    new int[3]{5,6,2},
    new int[5]{6,9,7,8,3},
    new int[2]{3,2}
};

【上述定义在我机器上不能编译通过。。】

8.下面代码的输出是？______
void f(char *x){
    x++;
    *x = 'a';
}

int main(int argc, const char * argv[])
{

    char str[sizeof("hello")];
    strcpy(str, "hello");
    f(str);
    cout<< str;
    return 0;
}
11.在一台机器上，调用f(35)所需要的时间大概是？______
int f(int x){
    int s = 0;
    while (x-- > 0) s+=f(x);
    return max(s,1);
}

【答案】几小时，为什么？

12.在一棵度为4的树中，有20个4度的节点，10个3，1个2，10个1，则该树的叶子节点数？______

【分析】

  • 出度 = 80 + 30 + 2 + 10 = 112
  • 入度 = 20 + 10 + 1 + 10 = 39
  • 叶子节点数 = 出度 - 入度 - 1 = 82
  • 上个公式-1是因为要考虑根节点（每个节点占据一个入，根节点除外）
15.最大流问题：

代码

20.某国家重男轻女，若一户人家生了一个女孩，便再要一个，直到生下男孩为止。假设生男生女概率一样，请问平均每户人家有几个女孩？______

参考1

21.以下有关C语言的说法中，错误的是？

A.内存泄露一般是指程序申请了一块内存，使用完后，没有及时将这块内存释放，从而导致程序占用大量内存。 B.无法通过malloc(size_t)函数调用申请超过该机器物理内存大小的内存块。 C.无法通过内存释放函数free(void *)直接将某块已经使用完的物理内存直接还给操作系统。 D.可以通过内存分配函数malloc(size_t)直接申请物理内存。

22.下面关于BST说法正确的包括？

A.待删除节点有左子树和右子树时，只能使用左子树的最大值节点替换删除节点 B.给定一颗BST的前序和后序，无法确定这颗二叉搜索书 C.给定一颗BST，根据节点值大小进行排序所需时间复杂度是线性的 D.给定一颗BST，可以线性时间复杂度内转换为平衡二叉搜索树

【答案】C

Show Comments