第三部分 填空与问答(5题，共30分)

　　25. (4分)某无聊的程序员在玩Windows上的记事本程序，不用鼠标，每次可以按以下键或组合之一：A、Ctrl+A(全选)、Ctrl+C(拷贝)、Ctrl+V(粘贴)，那么在10次按键只能可以制造的最长文本长度为 。

　　26. (4分)若初始序列为gbfcdae，那么只会少需要 次两两交换，才能使该序列变为abcdefg。任给一个自由a--g这7个字母组成的排列，最坏的情况下需要至少 次两两交换，才能使序列变为abcdefg。

　　27. (5分)在某恶劣天气，若地图上S点到T点的交通网如下图所示，其中每条边表示一条双向通道，其上的数字为该通路可通行的概率，且该概率两两独立。求S到T的可通行概率 。

　　1/3

　　1/2

　　1/2

　　1/2

　　1/2

　　1/3

　　28. (8分)6度分离假说的含义是，世界上任何两个人要么是朋友，要么是朋友的朋友，或者更高阶的朋友的朋友(如朋友的朋友的朋友)，改论断中“朋友”一词出现的次数为两人之间的距离，那么该距离小于等于6。如果某SNS(如QQ、旺旺等)，有100万用户，其人际关系网咯符合以下两个假设：

　　1) 朋友关系是一种对称关系(如A和B是朋友，那么B和A也是朋友)

　　2) 符合2度分离假说

　　3) 第i个人拥有的朋友的个数为ni ，所有ni 中最大值为n

　　试估算n的最小值 。

　　29. (9分)某电子商务网站进行A、B两种推荐算法的效果对比测试，对用户的访问请求按照1:9的比例随机分配给A和B两种算法处理。产生推荐结果后，按照两种指标对比两种算法产生的结果好坏：第一种指标是CTRPV=该算法下用户的点击展现次数/该算法下所有的展现次数，第二种指标是CTRUV=该算法下有点击的用户数/该算法下所有的用户数。假定每个用户会对该推荐服务2次访问，如果A和B的CTRPV持(假设为0.01)。那么CTRUV哪个大，大的比小的大百分之多少 。

　　第四部分：JAVA附加题(注，阿里有大量JAVA研发工程师需求;选作以下题目有机会增加该方向面试机会)

　　1.以下每个线程输出的结果是什么?(不用关注输出的顺序，只需写出输出的结果集即可)

　　public class TestThread{

　　public static vod main(String[] args){

　　// test1

　　Thread t1 = new Thread(){

　　@Override

　　public void run(){

　　try{

　　int i=0;

　　while(i++<100000000){

　　// nothing

　　}

　　System.out.println("A1");

　　}catch(Exception e){

　　System.out.println("B1");

　　}

　　};

　　};

　　t1.start();

　　t1.interrupt();

　　// test2

　　Thread t2 = new Thread(){

　　public void run(){

　　try{

　　Thread.sleep(5000);

　　System.out.println("A2");

　　}catch(Exception e){

　　System.out.println("B2");

　　}

　　};

　　};

　　t2.start();

　　// t2.interrupt(); //不确定是否有这句话

　　// test3

　　Thread t3 = new Thread(){

　　public void run(){

　　try{

　　Thread.sleep(50000);

　　System.out.println("A3");

　　}catch(Exception e){

　　System.out.println("B3");

　　}

　　};

　　};

　　t3.start();

　　t3.interrupt();

　　// test4

　　Thread t4 = new Thread(){

　　public void run(){

　　try{

　　Thread.sleep(50000);

　　System.out.println("A4");

　　}catch(Exception e){

　　System.out.println("B4");

　　}

　　};

　　};

　　t4.start();

　　t4.interrupt();

　　// test5

　　try{

　　t4.start();

　　System.out.println("A5");

　　}catch(){

　　System.out.println("B5");

　　}

　　}

　　}

　　2. 一个10亿条记录的文本文件，已按照关键字排好字存储，请设计方法，可以快速的从文件中查找指字关键字的记录。

　　【系统工程师】 附加题

　　1.在互联网时代系统的稳定性要求越来越高，为了提升系统的稳定性，高可用技术被广泛运用，请列举至少4中相关的技术解决硬件、系统或网络等层面的单点问题。

　　2.请描述一下TCP建立连接三次握手的过程。

　　3. 搜索引擎是很常用的web应用。大部分搜索引擎需要设计一个抓虫(Crawler)，从很多网站抓去网页，分析数据，供搜索引擎使用。

　　设想你来做一个搜索引擎的爬虫，需要抓去约一百万家网站的网页内容。

　　1) 请画出一个抓虫系统的架构图。

　　2) 重点说明你的爬虫需要如何优化来提升性能。