2014百度校园招聘软件开发笔试题(上海站)--第三天

1.描述OSI(开放系统互联基本参考模型)七层结构。

第一层：物理层

第二层：数据链路层

第三层：网络层

第四层：传输层

第五层：会话层

第六层：表示层

第七层：应用层

2.写出进程间数据共享的方式，至少三种。

　　1.使用内存映射文件

　　2.通过共享内存DLL共享内存

　　3.后来我在IBM developerWorks上找到了一个用SystemV实现内存共享的方法，这种方法效率很高而且也很简单。在帖子后面，我也给出了SystemV实现的方法

参考：

http://www.cnblogs.com/timest/archive/2012/05/07/2486975.html

http://www.cnblogs.com/henryzc/archive/2005/11/08/271920.html

3.描述TCP和UDP的区别，并各写出一个他们的上层协议

TCP的HTTP，SMTP，UDP的TFTP

4.给出数组A={a_0,a_1,a_2,...,a_n}(n是可变的)，打印出所有元素的组合

貌似可以这样，不敢保证：

# include<iostream>
# include<cstdio>
using namespace std;
void swap(int &a,int &b)//交换连个元素
{
    int tem;
    tem = a;
    a = b;
    b = tem;
}
void cal(int *a,int first,int length,int r)
{
    if(first == length)//如果递归到深层时，到最后交换的元素即时最后一个元素时就打印出来
    {
        for(int i = 0; i <= r; i++)
            cout<<a[i]<<" ";
        cout<<endl;
    }
    else
    {
        for(int i = first; i <= length; i++)
        {
            //循环遍历使得当前位置后边的每一个元素都和当前深度的第一个元素交换一次
            swap(a[first],a[i]);//使得与第一个元素交换
            cal(a,first+1,length,r);//深入递归，此时已确定前边的元素，处理后边子序列的全排列形式。
            swap(a[first],a[i]);//恢复交换之前的状态
        }
    }
}
int main()
{
    int n;
    int a[1000];
    while(cin>>n)
    {
        for(int i = 0;i < n;i++)
        {
            cin>>a[i];
        }
        cal(a,0,n-1,n-2);
    }
    return 0;
}

5.数组A中任意两个相邻元素大小相差1，现给定这样的数组A和目标整数t，找出t在数组A中的位置

貌似用跳跃遍历

例子：

# include<iostream>
# include<stdio.h>
# include<math.h>
using namespace std;
int search(int a[],int n,int v)
{
    for(int i=fabs(v-a[0]);i<n;i+=2)
        if(a[i] == v)
            return i;
        return -1;
}
int main()
{
    int n,v;
    int a[1000];
    while(cin>>n>>v)
    {
        for(int i = 0;i < n;i++)
        {
            cin>>a[i];
        }
        int k = search(a,n,v);
        cout<<k<<endl;
    }

}

6.求二叉树的面积(高乘宽)，高为二叉树根到叶子节点的最大距离，宽为二叉树最多的节点数。

7.系统设计题 给了一个百度地图的截图，对于地图上的某一点，需要在地图上标注该点的信息，将信息抽象成一个矩形，可以在该点的左边标记，也可以在该点右边标记。但是任意两点标记后的矩形是不能有覆盖的，否则删除其中一个点

问题1，现给一固定区域，有n个点，设计一个算法，要求标记足够多的点

问题2，当点足够多时候，算法会遇到性能瓶颈，需要对算法重新优化。