笔试题 (三)

答案都是个人的理解, 肯定有不正确的地方, 欢迎提供正解

1. 星期天有10个朋友约好一起郊游，在车站的集合时间是早晨9:50:00到10:00:00。已知每个人到达车站的时间是9:50:00到10:00:00内的均匀分布，且彼此独立。那么最后一人最可能到达的时间是
（精确到分钟，向下取整）。

A. 各个分钟概率相等 B. 9:57 C. 9:58 D. 9:59

最后一个人在 9:50 到达的概率是 (0.1)^10

最后一个人在 9:51 ..... C(10,1)*(0.1)*(0.2)^9

... 52 .... C(10,1)*(0.1)*(0.3)^9

所以, 感觉不对, 有什么没考虑到

s = 1 时, 概率 p = 1/(2^10)

s = 2 时, p = C(2,1) * 1/(2^10) *(0.5 + 0.25 + .... 1/(2^10))

...

s = k 时, p = C(k,1)*1/(2^10) * (0.5 + 0.25 +... + 1/(2^10))

然后求期望, 应该是 1024

3. 要提高多线程程序的效率，对锁的控制策略非常重要。一种策略是在锁的个数不太多、控制结构不太复杂的情况下，尽可能降低加锁的粒度；另一种策略是在合适的条件下取消用锁。以下情况中不可能取消锁的是

A. 多线程写一个共同的数据结构，且写操作是原子操作

B. 多线程写一个共同的数据结构，且写操作不是原子操作

C. 多线程读一个共同的数据结构，且读操作不是原子操作

D. 一个线程写，多个线程读一个共同的数据结构，写操作是原子操作，读操作不是原子操作

E. 一个线程写、多个线程读一个共同的数据结构，写操作不是原子操作，读操作是原子操作

B, D 都应该加锁

4. 一颗非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树可能是

A. 所有的结点均无右孩子

B. 只有一个叶子结点

C. 是一颗二叉树索树

D. 所有的结点均无左孩子

A, B, D

5. 以下数字在表示为double（8字节的双精度浮点数）时存在舍入误差的有

A. 根号2 B. 10的30次方 C. 0.1 D. 0.5 E. 100

A,B

typedef struct node_s{
    int item;
    struct node_s* next;
}node_t;

 
void reverse_list(node_t* head)
{
     node_t* n=head;
     head=NULL;
     while(n){

     }
     return head;
}

以下哪项能实现该函数的功能

A. node_t* m=head; head=n; head->next=m; n=n->next;

B. node_t* m=n; n=n->next; m->next=head; head=m;
C. node_t* m=n->next; n->next=head; n=m; head=n;

D. head=n->next; head->next=n; n=n->next;

头插法, 选D

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

a a a a c_a c_c c_v c_v c_v c_v 16个

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

9. 6度分离假说的含义是，世界上任何两个人要么是朋友，要么是朋友的朋友，或者更高阶的朋友的朋友（如朋友的朋友的朋友），该论断中”朋友”一词出现的次数为两人之间的距离，那么该距离小于等于6。如果某SNS（如QQ、旺旺等），有100万用户，其人际关系网咯符合以下两个假设：朋友关系是一种对称关系（如A和B是朋友，那么B和A也是朋友）符合2度分离假说第i个人拥有的朋友的个数为n_i ，所有n_i 中最大值为n试估算n的最小值

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

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

分块查找, 每次内存读入 1G 数据

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

a. 存储. RAID 等数据冗余技术

b. 系统级软件. 引入日志, 能够还原到以前的安全状态

c. 进程的检查点

13. 请描述一下TCP建立连接三次握手四次挥手的过程

第一次握手：主机A发送位码为syn＝1,随机产生seq number=1234567的数据包到服务器，主机B由SYN=1知道，A要求建立联机；
第二次握手：主机B收到请求后要确认联机信息，向A发送ack number=(主机A的seq+1),syn=1,ack=1,随机产生seq=7654321的包
第三次握手：主机A收到后检查ack number是否正确，即第一次发送的seq number+1,以及位码ack是否为1，若正确，主机A会再发送ack number=(主机B的seq+1),ack=1，主机B收到后确认seq值与ack=1则连接建立成功。
完成三次握手，主机A与主机B开始传送数据。

在TCP/IP协议中，TCP协议提供可靠的连接服务，采用三次握手建立一个连接。
第一次握手：建立连接时，客户端发送syn包(syn=j)到服务器，并进入SYN_SEND状态，等待服务器确认；
第二次握手：服务器收到syn包，必须确认客户的SYN（ack=j+1），同时自己也发送一个SYN包（syn=k），即SYN+ACK包，此时服务器进入SYN_RECV状态；第三次握手：客户端收到服务器的SYN＋ACK包，向服务器发送确认包ACK(ack=k+1)，此包发送完毕，客户端和服务器进入 ESTABLISHED状态，完成三次握手。完成三次握手，客户端与服务器开始传送数据.

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

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

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

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

一个爬虫架构

性能提升建议, 参考 http://blog.csdn.net/historyasamirror/article/details/7061059

1. Fetcher, DNS 比较耗时, 考虑使用异步机制

2. URL 去重, 可以使用 bloom filter

3. 镜像网站, 去重