2018 七牛云校招笔试题 [卷二]

旧城等待， 2022-03-08 17:50 365阅读 0赞

1. 找出规律填写空白的数字，2, 3, 7, 16, \_\_\_, 57, 93 （）

> 2，3，7（3+4），16（7+9）\_\_\_\_（16+16），57（32+25），93（57+36）
> 
> 答案: 32

2. 在局域网上执行 ping www.qiniu.com 没有涉及到的网络协议是？（）  
    A. ARP  
    B. DNS  
    C. TCP  
    D. ICMP

> ping协议使用的协议自顶向下为：UDP,IP,ARP,因为www.qiniu.com是一个网址，我们需要将其转化为IP，所以需要用到DNS，并未用到TCP.

3. 有三个节点，可以构成多少种二叉树？（）

3  
    4  
    5  
    6

> 一定有头节点，所以可能的二叉树为：左2头->（两种，最下面的节点可能在左，也可能在右），左1头右1(一种)，头右2（两种，理由同上.）

4. 下列对于数据库索引的说法一定是错误的（）

A. 索引不会影响表的更新、插入和删除操作的效率  
    B. 全表扫描不一定比使用索引执行效率低  
    C. 对于只有很少数据值的列，不应该创建索引  
    D. 索引可以加速表和表之间的连接查询

> 索引的本质是通过某种数据结构(一般是平衡树，也就是B，B+数)来加快查询速度，本质上就是一种为了加快查询，稍微降低增删改的速度，所以A错。
> 
> B选项说的是不一定，当数据只有很少的时候(一条)，索引可能还没直接搜索快。
> 
> C同上，索引的建立和维护都是需要付出代价，如果查询速度并没有到让人担心的地步，不要多此一举。
> 
> D项，当我们使用某一个外键作为索引时，自然可以加快连接查询的速度。

5. 以下程序输出多少个“-”()

int main(void) \{  
        int i;  
        for (i = 0; i < 2; i++) \{  
            fork();  
            printf("-");  
        \}  
        return 0;  
    \}

> 答案为：D，解析请参考：[fork()][fork]

6. Linux 下两个进程同时打开同一个文件，这时以下描述正确的是：（）

A. 两个进程中会生成同一个fd  
    B. 如果有一个进程删除该文件，另一个进程会立刻出现读/写文件失败  
    C. 操作系统会禁止两个进程同时向文件进行写入操作  
    D. 进程可以通过系统调用对文件加锁，从而实现对文件内容的保护

=> D

7. 255.255.254.0 网段最多能支持 \_\_\_\_\_ 台主机？ （）

> 总共有9个位置为 0 ，也就是有512个位置，但是需要保留两个IP作为广播地址(全 1)和网络地址(全 0)，所以答案为510个。

8. 如果一个数组（长度超过10万）仅由0-10的整数组成，以下哪种排序算法对该数组排序效率最高？（）

快速  
    冒泡  
    基数  
    希尔

> 快速是O(nlog n)，冒泡是O（n^2）,希尔是O(nlogn),基数排序是O(n\*len)\{len的意思是待排序数字的长度.\}

9. 下面关于Linux文件系统的描述中错误的是：（）  
    A. inode 和文件名是一一对应的  
    B. 通过inode可以获得文件占用的块数  
    C. 文件执行了删除操作之后，仍可通过之前创建的硬链接进行正常访问  
    D. inode 描述了文件大小和指向数据块的指针

> A通常情况下是成立的，但是在Linux中，硬链接会将多个文件名指向同一个inode，这样导致了当某个用户删除掉其中一个文件名时，其余文件名不会受到影响，但是当某个用户通过硬链接修改文件内容后，所有的硬链接指向的内容都被修改，简而言之，硬链接就是用不同的文件名，对应相同的inode，从而获取到对应的内存块。
> 
> B，D选项：inode可以获得文件占用的块数，文件的大小和只想数据块的指针。
> 
> C，在A中已解释。
> 
> 多说一句，我一直认为优盘的缺少部分(16G优盘，普遍只有14.2G左右)就是被操作系统划分给了inode区，也就是用于文件的管理。

10. 21点是一种扑克游戏。如果玩家拿到扑克牌的点数总和超过21点则称为爆点，被判失败。  
    其中A牌可以被记为11点或者1点，J, Q, K 都记为10点。如果用一副牌玩游戏（52张牌），玩家手上拿到一个J和7。那他再抽两张牌会爆点的可能性约有多大？（C）

17, 4

11. 5个骰子，六个面分别标有1-6，现在将五个同时随机投掷，五个点数之和概率最大的点数是

> 明显是一个正态分布，正态分布的对称轴时概率最大时，也就是期望值，所以我们直接计算对应的期望值即可。
> 
> ((1+2+3+4+5+6) / 6) \* 5 = 3.5\* 5 = 17.5,也就是说概率最大的点数是：17，18。

12. 验证远端服务器（IP：180.97.72.166）的 1935 端口是否开启的命令是

> 使用telnet指令，比如我们检测百度的某台服务器的80端口，可以
> 
> telnet baidu.com 80
> 
> 出现Connected to baidu.com即说明端口已经开启
> 
> 所以答案是: telnet 180.97.72.166 1935

13. 根据下面递归函数：调用函数fun（2），返回值是

int fun(int n) {
        if(n==5)
            return 2;
        else
            return 2 * fun(n+1);
    }

>   很明显可以算出:
> 
> 2\*2\*2\*2\*2 = 2 ^5 =32
> 
> 1 2  3 4 5   // 对应的n值。

14. 有一组关键字序列 \[5, 8, 14, 20, 31, 55, 78, 81, 93, 97, 111\]，使用二分法查找关键字97需要进行 () 次比较

> head= 0, last = 10 , mid = 5--->55--> \[5, 8, 14, 20, 31, 55, 78, 81, 93, 97, 111\]
> 
> head= 6, last = 10 , mid = 8--->93--> \[5, 8, 14, 20, 31, 55, 78, 81, 93, 97, 111\]
> 
> head= 9, last = 10 , mid = 9--->97--> \[5, 8, 14, 20, 31, 55, 78, 81, 93, 97, 111\]

15.（简答题）在Linux中，file.sh 的权限用数值表示是 645。请简述这个文件权限数值的含义。

>     user group other  
>     1: r  
>     2: w  
>     4: x
> 
> user ->   6 = 4 + 2: w + x  
> group -> 4            : x  
> other ->  5 = 4 + 1: r + x

16.（简答题）一个单向链表从头到尾遍历每个节点只会访问到一次，则为无环链表，如果存在节点会被重复遍历，则为有环链表。试解答：  
    (1)如何判断一个单向链表是否存在环？（4分）  
    (2)如果链表有环，如何找到环的入口节点？（8分）  
    (3)如何计算环的长度？（3分)

> 使用快慢指针法，
> 
> // 定义两个指针，fast 和 low.都指向链表的头节点.
> 
> // 使用fast != null ,作为while循环条件。
> 
> // 循环体内先让fast向后走2步(判越界),让low指针向后走一步
> 
> // 之后判断fast == low 是否成立，如果成立，则有环。(1)
> 
> // 接下来固定住fast,只让low每次前进一步并使用count计步，当low==fast再次发生时，得出环的长度len。(3)
> 
> // 已知环的长度，那么我们将fast和low都指向头节点，让fast先走len步，之后两个指针一定会在入口处相撞.  (2).

17.（编程题）请编写一个函数，获得输入整数的平方根，如果结果不是整数则向下取整。

> 我第一反应是二分法，时间是log(n)，牛顿啥的没学会。

18. （编程题）请使用字符串来表达任意大小的长整数，使用你熟悉的编程语言编写程序来计算两个长整数之和。例如:sum(“123”,”456”) 返回的结果是”579”。

> //Java有大整数，但是我觉得没人会允许我用这个。
> 
> // 所以采用模拟法，模拟我们日常中的计算，从后位开始计算，用一个值保存进位。

19. （论述题）当线上服务CPU使用过高的时候。你会用什么方法对程序进行分析、发现服务的瓶颈？

> 20.   Linux的进程通信方式有哪些 ()（至少给出3个）  
>

[fork]: https://blog.csdn.net/fei86155/article/details/76130256