百度2019大连地区笔试题

一简答题（10x3=30分）

1. 用ssh登陆远程的linux/unix系统，如果网络中断，linux/unix端运行的程序将会中断。

这种问题发生的原理？通过何种途径去避免？这种途径的原理是什么？

2.一个最小值堆，同时是一棵完全二叉树，顺序存储在一个数组a中，126438759

1) 对于任意结点的a[n]，其在二叉树中左、右子节点访问方式；

2) 完成函数，向堆中加入一个元素仍然满足堆的原有性质；void add_element(int *a,int size,int val)

3) 完成函数，取出栈顶最小元素后仍然满足堆的原有性质。

3.有某种hash算法，让用户稳定的均匀分布到一个区间内，大小为100%,最小粒度0.1%，这种区间叫做一层，两个区间a,b，如何让a中的任意子区间都均匀分布到层b的100%中。

现有超过10层，每一层都需要这种关系，如何解决？

二算法与程序题（20x2=40分）

1.给定一个数字编码n，大多数情况下可以找到一个数字编码m，其位数与编码n相等(编码可以从0开始)，各位数字之和与编码n中各位数字之和相等，并且m是数值大于n的所有码中最小的一个，也可能要找的编码m不存在。

如给定编码n=134,则编码m=143;给定编码n=020,则编码m=101，形式化表述为f(n)=m,如果m不存在，则f(n)=-1。

现在给定一个起始编码n， n的数字位数最大不超过1000，n 的数值最大不超过10^500，要求给出序列s(n)，其中s(0)=n，s(1)=f(n)，s(2)=f(s(1))，s(3)=f(s(2)).当s(i+1)<0时序列结束，但小于0的元素不包含在序列中，要求给出算法思路和函数。

2.给定一个序列s=[a1,a2,..an];

1)构造一个算法，生成序列s的全排列；

举例：>>permu([1,2,3])

2)构造一个算法，生成序列s的所有组合；

举例：>>comb([1,2,3])

说明：算法均可用伪**表示。

三系统设计题30分。

设计一个支持高级语法查询的单机大数据量的磁盘检索系统，机器内存为10gb，磁盘空间不限，数据格式如下，单条数据数据由termid，签名[unit64_t]，urlnocount[unit32_t]，urlno[unit32_t]列表组成，urlno列表长度不定，平均长度为10万个：

1）设计一种数据存储格式与读取方法，主要从查询性能考虑，兼顾资源利用（10分）；

2）设计一种检索线程模型，需要支持多线程并发查询（5分）；

3）设计一种算法，支持and，or，sub（差集），1>需要支持括弧操作，譬如如下查询。

id1 sub(id2 and id3) or id4（10分）；

2>考虑如何支持截断优化策略的当前获得到前100个最终urlno结果后停止后续检索过程（5分）