2014年10月13日百度校园招聘北京站笔试题

2014 年 10 月 13 日百度校园招聘北京站笔试题 一、简答题 1、OSI 的七层模型。(10 分) OSI 的七层模型如下图所示： 2、请列举下不同进程之间共享数据的方式(至少举出三种)。(10 分) 1、文件映射(Memory-Mapped Files))能使进程把文件内容当作进程地址间一块内存 那样来对待 2、共享内存(Shared Memory)实际就是文件映射的一种特殊情况 3、命名管道(Named Pipe)是服务器进程和一个或多个客户进程之间通信的单向或双 向管道 4、邮件槽(Mails)lots))提供进程间单向通信能力，任何进程都能建立邮件槽成为邮件槽 服务器 5、剪贴板(Clipped Board)为不同应用程序之间共享不同格式数据提供了一条捷径 6、动态连接库(DLL)中的全局数据可以被调用 DLL 的所有进程共享 3、请描述下 TCP 和 UDP 的差别，并且各列举出一个上层协议。(10 分) TCP---传输控制协议,提供的是面向连接、可靠的字节流服务。当客户和服务器彼此交 换数据前，必须先在双方之间建立一个 TCP 连接，之后才能传输数据。TCP 提供超时重发， 丢弃重复数据，检验数据，流量控制等功能，保证数据能从一端传到另一端。 UDP---用户数据报协议，是一个简单的面向数据报的运输层协议。UDP 不提供可靠性， 它只是把应用程序传给 IP 层的数据报发送出去，但是并不能保证它们能到达目的地。由于 UDP 在传输数据报前不用在客户和服务器之间建立一个连接，且没有超时重发等机制，故 而传输速度很快。 经常使用“ping””命令的原理就是向对方主机发送 UDP 数据包，ftp 等就是使用到的 TCP 协议 二、算法与程序设计 1、给出一个数据 A={a_0,a_1,a_2…a_n}(其中 n 可变)，打印出该数值元素的所有 组合。(15 分) 因为题目要求 n 可变，所以不可能是 n 层 for 循环的方式，可以采用递归的方式来实现， 每次取一个元素，在剩下元素的数组中递归，要注意递归结束的条件。 2、有这样一个数组 A，大小为 n，相邻元素差的绝对值都是 1，如 A={4,5,6,5,6,7,8,9,10,9}，现在给定数组 A 和目标整数 t，请找到 t 在 A 中的位置。 (15 分) 最简单的方式是循环遍历每一个元素之后比较，找到 t 在 A 中的位置，此种方法效率 最低； 改进：因为相邻元素差的绝对值都是 1，那么任意两个元素相距的位置至少是两元素差 的绝对值个，假设要找的元素是 t，t 和 a(0)的差为 y1=abs)(t-a[0]),那么 t 和 a[0]的距离 至少是 y1，再求一次差值 y2=abs)(t-a[y1]),t 和 a[y1+y2]的距离至少是 y2，继续向后 查找，直到相等为止，此种方法效率较前一种高 3、有一颗二叉树，定义树的高度为从根到叶子节点的最长距离，树的宽度为每层节 点的最大值，树的面积定义为高度和宽度的乘积。写一个函数计算一个二叉树的面积。 (15 分) 广度遍历求树的宽度，深度遍历求树的高度，之后计算面积 三、系统设计题(25 分)