某笔试题

一 简答题（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])

[[1,2,3]，[1,3,2]，[2,1,3]，[2,3,1]，[3,1,2]，[3,2,1]]

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

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

[[]，[1]，[2]，[1,2]，[3]，[1,3]，[2,3]，[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分）