搜狐研发⼯程师笔试题-2016年

⼀. 单项选择题

1. linux下给⽂件start.sh设置权限为自己可读可修改可执⾏,组内用户为可读可执⾏不可修改,其余用户没有任何权限,那么设置该⽂件权限的命令为()

A、chmod start.sh 706
B、chmod start.sh 750
C、chmod start.sh 705
D、chmod start.sh 777

2. 以下哪种http状态下,浏览器会产⽣两次http请求?()

A、304
B、404
C、302
D、400

3. 某学校获取到⼀个B类地址段,要给大家分开子网使用,鉴于现在上网设备急剧增多,管理员给每个网段进⾏划分的子网掩码设置为255.255.254.0,考虑每个网段需要有网关设备占⽤⼀个地址的情况下,每个网段还有多少可用的主机地址()

A、509
B、511
C、512
D、510

4. 某种产品,合格品率为0.96,⼀个合格品被检查成次品的概率是0.02,⼀个次品被检查成合格品的概率为0.05,  问题:求⼀个被检查成合格品的产品确实为合格品的概率()

A、0.9978
B、0.9991
C、0.9855
D、0.96

5. 设某公路上经过的货车与客车的数量之比为2:1,货车中途停车修理的概率为0.02,客车为0.01,今有⼀辆汽车中途停车修理,求该汽车是货车的概率()
A、0.67
B、0.33
C、0.91
D、0.8

6. 以下多线程对int型变量x的操作,哪个不需要进行同步()
A、++x
B、x=y
C、x++
D、x=1

7.

#define A(x) x+x
int i=5*A(4)*A(6);
cout<<i;

以上程序输出是多少?

A、50
B、100
C、120
D、480

8. 以下关于PMF(概率质量函数),PDF(概率密度函数),CDF(累积分布函数)描述错误的是()

A、PDF描述的是连续型随机变量在特定取值区间的概率
B、CDF是PDF在特定区间上的积分
C、PMF描述的是离散型随机变量在特定取值点的概率
D、有⼀个分布的CDF函数H(x),则H(a)等于P(X<=a)

9. ⼀个全局变量tally,两个线程并发执行(代码段都是ThreadProc),问两个线程都结束后,tally取值范围为_______

int tally=0;//全局变量
void ThreadProc(){
    for(int i=1;i<=50;i++)
    tally+=1;
}

A、[50,100]
B、[100.100]
C、[1275,2550]
D、[2550,2550]

10. 下⾯四个类A,B,C,D,在32位机器上sizeof(A),sizeof(B),sizeof(C),sizeof(D)值分别为()

class A{
};
class B{
    char ch;
    int x;
};
class C{
public:
    void Print(void){}
};
class D
{
public:
    virtual void Print(void){}
};

A、0,5,0,0
B、1,8,4,4
C、1,8,1,4
D、1,5,1,4

11. 下列关于GIT的描述不恰当的⼀项是()

A、可以采用公钥认证进行安全管理
B、可以利用快照签名回溯历史版本
C、必须搭建Server才能提交修改
D、属于分布式版本控制工具

12. 已知下面的class层次,其中每⼀个class都定义有⼀个default constructor和⼀个virtual destructor;

class X{...};
class A{...};
class B:public A{...};
class C:public B{...};
class D:public X,public C{...};

下⾯()执⾏dynamic_cast不会失败

A、A *pa=new D;X *px=dynamic_cast<X*>(pa);
B、D *pd=new D;A *pa=dynamic_cast<A*>(pd);
C、B *pb=new B;D *pd=dynamic_cast<D*>(pb);
D、A *pa=new C;C *pc=dynamic_cast<C*>(pa);

13. 某⼀系统功能,需要⼀次性加载N(N在1000左右)个随机数,后续只对该集合进⾏遍历.最宜采用哪种结构存
放？
A、Hash表
B、⼆叉树
C、链表
D、图

⼆. 问答题

14. 将⼀颗多叉树存储在⼀个txt⽂件中,格式如下:
id1,parentld1,weight1
id2,parentld2,weight2
id3,parentld3,weight3
.....
其中,⼀行表示⼀个节点,id表示节点的序号,parentld表示节点对应父节点的序号,weight表示该节点的权重, 根节点的parentld是⾃⾝id.请实现⼀个函数,输入是⼀个多叉树节点的数组和长度,要求打印出每⼀个节点的总权重 (总权重=节点自身权重+节点对应所有子节点的权重).自定义需要的数据结构,说明时间和空间复杂度(要求时间 复杂度优先,空间复杂度尽量低)

参考答案

一、1.B、2.C、3.A、4.A、5.D、6.D、7.A、8.A、9.A、10.C、11.C、12.C、13.C

二、14.参考如下：

思路：

• 首先建立id_index的hash表，该表的作用为将节点id映射到节点在array中的下标，方便以后查询
• 算法的主要思想是先处理叶子节点（叶子节点state为0)，处理叶子节点时，将叶子节点的权重添加到其父节点上，并将叶子节点标记为删除（将对应的斯state设置为-1)，这时原来高度为1的所有节点又变成新的叶子节点，然后迭代处理，直到处理完根节点
• 其中state和weight分别为数组array中对应节点的状态(-1, 0, 1)和权重

#include <unordered_map>
#include <iterator>
#include <stdexcept>
#include <set>
#include <iostream>
using namespace std;
 
typedef struct {
    size_t id;
    size_t parentId;
    size_t weight;
} Node;
 
void print_weight_of_tree(Node array[], size_t len)
{
    if (len == 0) {
        return;
    }
 
    unordered_map<size_t, size_t> id_index;
    id_index.rehash(2 * len);
    for(size_t i = 0; i != len; i++) {
        id_index.emplace(array[i].id, i);
    }
 
    int *state = new int [len]();
    size_t *weight = new size_t [len];
    for(size_t i = 0; i != len; i++) {
        weight[i] = array[i].weight;
        //root node
        if(array[i].id == array[i].parentId)
            continue;
        auto it = id_index.find(array[i].parentId);
        if(it == id_index.end()) {
            throw logic_error("parent not Found");
        }
        //tag
        state[it->second] = 1;
    }
    bool end = false;
    set<size_t> new_leaf_index;
    while(!end) {
        for(auto leaf_index : new_leaf_index) {
            state[leaf_index] = 0;
        }
        new_leaf_index.clear();
        for(size_t i = 0; i != len; i++) {
            if(state[i] == 0) {
                size_t parent = array[i].parentId;
                //root node
                if(parent == array[i].id) {
                    state[i] = -1;
                    end = true;
                    break;
                } else {
                    size_t parent_index = id_index.find(parent)->second;
                    new_leaf_index.insert(parent_index);
                    weight[parent_index] += weight[i];
                    state[i] = -1;
                }
            }
        }
    }
 
    for(size_t i = 0; i < len; i++) {
        cout << "id: " << array[i].id << " weight: " << weight[i] << endl;
    }
    delete [] state;
    delete [] weight;
}
 
int main()
{
    size_t len;
    cin >> len;
    Node *array = new Node[len];
    for(size_t i = 0; i != len; i++) {
        cin >> array[i].id >> array[i].parentId >> array[i].weight;
    }
    print_weight_of_tree(array, len);
        delete [] array;
    return 0;
}