(笔试时间 120 分钟)一、简答题(本题共 30 分)1.列出至少 6 中内部排序算法,并阐明复杂度及稳定性。(10 分)2.多线程同步互斥的措施有哪些?(10 分)3.进程间通信方式有哪些?哪种通信方式速度最快?(10 分)二、算法与程序设计题(本体共 45 分)1.设计一种算法,迅速查找二叉树上任意两个节点的近来共同父节点,请给出算法描述和代码实现(15 分)2.给定一种有序链表,删除所有反复的元素,仅保留至出现一次的元素,请给出算法描述和代码实现(15 分)3.给定一颗二叉树,判断其与否为平衡二叉树(左右子树之差的绝对值不超过 1)(15分)三、系统设计题(本体共 25 分)1.一种分布式检索服务系统(500 台服务器),不一样 query 的检索处理时间相差很大(例如有的 query 需要十几毫秒,有的需要上百毫秒甚至更多),目前发现线上诸多检索由于该服务的处理超时(处理超时是指处理时间超过了上游模块设置的最大的等待处理时间。这里我们假定为 200ms)而查询失败。为了处理这个问题,需要为这个服务设计一种内存级 cache 功能,规定如下:(1)、最大程度的减少服务超时率;(2)、假如原数据有变化,尽量展现最新数据;(3)、尽量提高 cache 的命中率;为了实现上述规定,除了设计 cache 内部逻辑以外,你可以提出详细调整查询祈求在分布式系统中的分派规则。