一、选择题：15 分 共 10 题
1. 在排序方法中，关键码比较次数与记录地初始排列无关的是：
A. Shell 排序 B. 归并排序 C. 直接插入排序 D. 选择排序
2. 以下多线程对 int 型变量x的操作，哪几个需要进行同步：
A. x=y; B. x++; C. ++x; D. x=1;
3. 代码
void func()
{
static int val;
…
}
中，变量 val 的内存地址位于：
A. 已初始化数据段 B.未初始化数据段 C.堆 D.栈
4. 同一进程下的线程可以共享以下：
A. stack B. data section C. register set D. thread ID
5. TCP 和 IP 分别对应了 OSI 中的哪几层？
A. Application layer B. Data link layer C. Presentation layer D. Physical layer E. Transport layer F. Session layer G. Network layer
6. short a[100]，sizeof(a) 返回？
A. 2 B. 4 C. 100 D. 200 E. 400
7. 以下哪种不是基于组件的开发技术_____。
A. XPCOM B. XP C. COM D. CORBA
8. 以下代码打印的结果是（假设运行在 i386 系列计算机上）：
struct st_t
{
int status;
short *pdata;
char errstr[32];
};
st_t st[16];
char *p = (char *)( st[2].errstr + 32 );
printf( "%d", ( p - (char *)(st) ) );
A. 32 B. 114 C. 120 D. 1112
9. STL 中的哪种结构是连续形式的存储：
A. map B. set C. list D. vector
10. 一个栈的入栈序列是 A，B，C，D，E，则栈的不可能的输出序列是：
A. EDCBA B. DECBA C. DCEAB D. ABCDE
二、简答题：20 分，共 2 题
1. （5 分）重复多次 fclose 一个打开过一次的 FILE *fp 指针会有什么结果，并请解释。
考察点：导致文件描述符结构中指针指向的内存被重复释放，进而导致一些不可预期的异常。
2. （15 分）下面一段代码，想在调用 f2(1) 时打印 err1，调用 f2(2) 时打印 err4，但是代码中有一些问题，请做尽可能少的修改使之正确。
1 static int f1( const char *errstr, unsigned int flag ) {
2 int copy, index, len;
3 const static char **__err = { "err1", "err2", "err3", "err4" };
4
5 if( flag & 0x10000 )
6 copy = 1;
7 index = ( flag & 0x300000 ) >> 20;
8
9 if( copy ) {
10 len = flag & 0xF;
11 errstr = malloc( len );
12 if( errstr = NULL )
13 return -1;
14 strncpy( errstr, __err[index], sizeof( errstr ) );
15 } else
16 errstr = __err + index;
17 }
18
19 void f2( int c ) {
20 char *err;
21
22 swtch( c ) {
23 case 1:
24 if( f1( err, 0x110004 ) != -1 )
25 printf( err );
26 case 2:
27 if( f2( err, 0x30000D ) != -1 )
28 printf( err );
29 }
30 }
三、编程题：30 分 共 1 题
注意：要求提供完整代码，如果可以编译运行酌情加分。
1. 求符合指定规则的数。
给定函数 d(n) = n + n 的各位之和，n 为正整数，如 d(78) = 78+7+8=93。 这样这个函数可以看成一个生成器，如 93 可以看成由 78 生成。
定义数 A：数 A 找不到一个数 B 可以由 d(B)=A，即 A 不能由其他数生成。现在要写程序，找出 1 至 10000 里的所有符合数 A 定义的数。
输出：
1
3
…
四、设计题：35 分 共 1 题
注意：请尽可能详细描述你的数据结构、系统架构、设计思路等。建议多写一些伪代码或者流程说明。
1. 假设一个 mp3 搜索引擎收录了 2^24 首歌曲，并记录了可收听这些歌曲的 2^30 条 URL，但每首歌的 URL 不超过 2^10 个。系统会定期检查这些 URL，如果一个 URL 不可用则不出现在搜索结果中。现在歌曲名和 URL 分别通过整型的 SONG_ID 和 URL_ID 唯一确定。对该系统有如下需求：
1) 通过 SONG_ID 搜索一首歌的 URL_ID，给出 URL_ID 计数和列表
2) 给定一个 SONG_ID，为其添加一个新的 URL_ID
3) 添加一个新的 SONG_ID
4) 给定一个 URL_ID，将其置为不可用
限制条件：内存占用不超过 1G，单个文件大小不超过 2G，一个目录下的文件数不超过 128 个。
为获得最佳性能，请说明设计的数据结构、搜索算法，以及资源消耗。如果系统数据量扩大，该如何多机分布处理？
百度第二套
一、选择题：15 分 共 10 题
1. 已知一个线性表(38,25,74,63,52,48)，采用的散列函数为 Hash($Key)=$Key mod 7，将元素散列到表长为7的哈希表中存储。请选择后面两种冲突解决方法分别应用在该散列表上进行等概率成功查找的平均查找长度，拉链法 ，线性探测法 .
A. 1.0 B. 1.5 C. 1.7 D. 2.0 E. 2.3
F. 7/6 G. 4/3 H. 3/2
2. 需要将OS缓冲区的数据刷新到硬盘，可以调用的函数有(多选)：
A.fflush() B. fsync() C. sync() D.writev()
3. 下面哪个shell语句不能打印出用户主目录的路径？
A. echo "$HOME" B. echo ~
C. echo `$HOME` D. echo $HOME
4. 最坏情况下，合并两个大小为n的已排序数组所需要的比较次数
A.2n B.2n-1 C.2n+1 D.2n-2
5. 一个B类网的子网掩码是255.255.240.0，这个子网能拥有的最大主机数是：
A. 240 B. 255 C.4094 D. 65534
6. 以下代码执行后，val的值是___:
unsigned long val = 0;
char a = 0x48;
char b = 0x52;
val = b << 8 | a;
A 20992 B 21064 C 72 D 0
7. 内存的速度远远高于磁盘速度，所以为了解决这个矛盾，可以采用：
A 并行技术 B 虚存技术 C 缓冲技术 D 通道技术
8. 以下代码打印的结果是（假设运行在i386系列计算机上）：
struct st_t
{
int status;
short* pdata;
char errstr[32];
};
st_t st[16];
char* p = (char*)(st[2].errstr + 32);
printf("%d", (p - (char*)(st)));
A 32 B 114
C 120 D 1112
9. 同一进程下的线程可以共享以下
A. stack B. data section
C. register set D. thread ID
10. 以下哪种操作最适合先进行排序处理？
A 找最大、最小值 B 计算算术平均值
C 找中间值 D 找出现次数最多的值
二、简答题：20分，共2题
1. （6分）下面是一个http请求：
GET /baidu/blog/item/6605d1b4eb6433738ad4b26d.html HTTP/1.1
Host: hi.baidu.com
User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; zh-CN; rv:1.8.0.6) Gecko/20060728 Firefox/1.5.0.6
Accept: text/xml,application/xml,application/xhtml+xml,text/html;q=0.9,text/plain;q=0.8,image/png,*/*;q=0.5
Accept-Language: zh-cn,zh;q=0.5
Accept-Encoding: gzip,deflate
Accept-Charset: gb2312,utf-8;q=0.7,*;q=0.7
Keep-Alive: 300
Connection: keep-alive
Referer: http://hi.baidu.com/baidu
Cookie: BAIDUID=AFB70E986AC48B336ABAB7505CDD1C76;
请解释以下各字段基本含义： Host、User-Agent、Accept-Charset、Connection、Referer、Cookie
2. （14分）函数A将字符串str1转成小写，并打印出转化前后的字符串。另外，改错时不能改变函数的接口和主要思路。改错时，请指出行号。
1 #include
2 #include
3
4
5 char* str1 = "ABDFLjlero我们都是saf";
6
7 char* ToLower(char s[])
8 {
9 static size_t i=sizeof(s);
10
11 for (i; i>=0; i--) {
12 if (s>"A" && s<"Z") {
13 s += 26;
14 }
15 }
16 return s;
17 }
18
19 int A()
20 {
21 printf("old str[%s] after lower[%s]n", str1, ToLower(str1));
22 }
三、编程题：30分 共1题
注意：要求提供完整代码，如果可以编译运行酌情加分。
1. 两个已排序的整型数组，求交集，最快算法
输入：两个已排序的整型数组（int a[m], b[n]）
输出：两个数组的交集
四、设计题：35分 共1题
注意：请尽可能详细描述你的数据结构、系统架构、设计思路等。建议多写一些伪代码或者流程说明。
1. 考虑一个字符串替换的过程，在一个文本文件中含有一些文本内容和一些需要替换的变量，变量的格式为“$Var$”，原来的“$”使用“$$”进行转义，原来的“$$”表示为“$$$”。我们将含有变量的文件称为模板(文件名为t)，文本文件的平均长度为100K。另外，还有一系列的变量文件，里面为变量名和变量值的对应关系(文件名为1.v , 2.v… n.v)，每个变量文件包含的变量数在百万数量级，且变量排列次序不定。现要求将，模板里的变量分别用变量文件里的变量替换，并将生成的文件写成 (1.r, 2.r… n.r)。
要求：从算法和实现上和实现技术上的细节对程序进行优化，尽量使程序高效。程序运行环境为2G内存，4CPU。阐明主要思路，给出伪码和说明，可以着重指出你使用的优化技术。
例子：模板文件为
This is an $FF$ $$. I like $FF$ and $FA$。
变量文件为
1.v
FF : banana
FA : apple
2.v
FA: 苹果
FF : 香蕉
则生成文件为
1.r
This is an banana $$. I like banana and apple。
2.r
This is an香蕉 $$. I like 香蕉and苹果。 1）此题10分
对任意输入的正整数N，编写C程序求N!的尾部连续0的个数，并指出计算复杂度。如：18！＝6402373705728000，尾部连续0的个数是3。
（不用考虑数值超出计算机整数界限的问题）
2）此题10分
编写一个C语言函数，要求输入一个url，输出该url是首页、目录页或者其他url
如下形式叫做首页：
militia.info/
www.apcnc.com.cn/
http://www.cyjzs.comwww.greena888.com/
www.800cool.net/
http://hgh-products.my-age.net/
如下形式叫做目录页：
thursdaythree.net/greenhouses--gas-global-green-house-warming/
http://www.mw.net.tw/user/tgk5ar1r/profile/
http://www.szeasy.com/food/yszt/chunjie/
www.fuckingjapanese.com/Reality/
请注意：
a） url有可能带http头也有可能不带
b）动态url（即含有"？"的url）的一律不算目录页，如：
www.buddhismcity.net/utility/mailit.php?l=/activity/details/3135/
www.buddhismcity.net/utility/mailit.php?l=/activity/details/2449/
另：如果你会linux，请用linux下的grep命令实现第2题的功能（附加5分）。
3）此题40分
如果必须从网页中区分出一部分"重要网页"（例如在10亿中选8亿），比其他网页更值得展现给用户，请提出一种方案。
4）此题40分
假设有10亿网页已经被我们存下来，并提供如下信息：网页全文（即网页的源码）、全文长度、网页正文（即网页中提取的主体文字）、
正文长度，以及其他网页提取物等，现在希望去掉其中的重复网页，请提出可行的方案，计算出每个网页对应的重复度，你可以自己
对网页重复下定义，也可以提出需要哪些更多的网页提取物来实现更好的去重复方案
百度面经：我是9月份跟百度联系的，当时连简历都没写，只是写了一下自己做过的一些东西，然后就通知我9月21日面试，第一次面试经过了3个小时，见了4位面试官，一个系统构建师，一个team leader，一个技术部经理，还有一个hrJJ，主要问的问题就是我曾经做过的信息检索项目，基本上照着简历（如果有的话）仔细地问，还会出点题目考你，建议大家多去看看《数据结构》，尤其是算法分析、查找、排序方面的东西。还有一些就看你的反应能力了，这里就不说了。
然后她会让你问一些问题，记得去之前到网上搜集点百度的资料看看，对百度有些认识，然后再问写关于公司发展和个人发展的问题，薪水的问题就别问题。
大约3个星期后，通知我去二面，又见了一个team leader和技术副总裁，这回还是围绕着简历提问，但自由交流的成份很多，就看你的亲和力和素质了，总之让他认为你这个人有创意，有想法，跟你一起合作会很愉快就是了。
当时那个副总裁邀请我到公司去做兼职，因为最近比较忙，就说下学期才能开始，可以说是整个面试中最大的败笔。
一个星期后打电话到HR那里问结果，被告知应届生招聘计划暂时推迟，感觉很faint，只好去找别的工作了。
百度的待遇一直不知道，工作时间大约是每天10小时以上，周六经常加班。
有股票期权，看你是不是喜欢了。
主要注意的是他让你问他问题的时候，一定问点有水平的问题，给他们点表现的机会，它表现的很爽，一高兴，对你也有好处。
百度网络笔试题目
1.假设Apache产生的日志文件名为access_log,在apache正在运行时,执行命令mv
access_log access_log.bak,执行完后,请问新的apache的日志会打印到哪里,为什么?
2.在Shell环境下,如何查看远程Linux系统运行了多少时间?
3.处理以下文件内容,将域名取出并进行计数排序,如处理:
http://www.baidu.com/index.html
http://www.baidu.com/1.html
http://post.baidu.com/index.html
http://mp3.baidu.com/index.html
http://www.baidu.com/3.html
http://post.baidu.com/2.html
得到如下结果:
域名的出现的次数 域名
3 www.baidu.com
2 post.baidu.com
1 mp3.baidu.com
可以使用bash/perl/php/c任意一种
4.如果得到随机的字串,长度和字串中出现的字符表可定义,并将字串倒序显示,如
把0123456789作为基准的字串字符表,产生一个6位的字串642031,打印出的字串为
130246,可使用bash/perl/php/c任意一种.
5.如何查看当前Linux系统的状态,如CPU使用,内存使用,负载情况等.
6.你在大学中做的最成功的一件事是什么(不必一定与计算机相关) 百度面试过程：
我的求职路程好像很是艰辛……到目前为止面试了很多家，简历更是投了几十份，只有Neusofe给了我一个offer。这个offer并不是对我能力的肯定，只是觉得我可能会留在东软。可惜东软我已经给拒了，基本上没有退路了。
说一下我的百度求职过程吧。
经过在线笔试、两轮电话面试，今天上午收到了百度的拒信，我的百度求职算是告一段落了……
从百度校园招聘开始，我就投了一份简历。在别人都有在线笔试机会的时候，我却没有任何消息。
听说师兄可以给推荐，我就又通过内部推荐的方式投递了一次，这次很快就有消息了——拒信。
那时基本上就放弃了百度。可是大概20多天以后，我投递的第一份简历有消息了——通知我在线笔试。经过精心准备，笔试题答得还凑合。过了几天给我来了封邮件告知我笔试通过，会找时间安排电话面试。又过了好几天，我正在剃头的时候接到百度电话，约了第二天下午三点电话面试。心情异常兴奋，回到寝室拼命复习数据结构并收集百度面试题型……临阵磨枪 呵呵。
百度的面试氛围很是轻松，让你很快就觉得是在聊天而不是面试。第一轮主要是在针对我的在线笔试的题目进行提问和分析，主要讲的是做题的思路和改进的方法。面试时间大概有半个小时，觉得应该有下一轮。
果然上个星期五晚上接到了百度技术经理的电话，自称姓刘。在前一天我同学也是这个时候接到百度第二面电话，看来是同一个人，后来的面试内容证实了是同一个人。面试过程大概如下：
1、介绍一下项目。
2、提了一个问题：上千万条记录，统计出重复记录最多的前N条。
3、一个概率题：54张扑克牌，除去两张大小王剩下52张扑克牌。问红桃A和黑桃A同时被一个人拿到的概率是多少？
4、多个线程访问共享内存时因该怎么办？
5、在写程序遇到问题的时候，通常采用什么调试方法？
6、一个client/server的协议问题
7、剩下就是随便聊聊，比如有缺点、期望工作的性质、职业规划等
总结一下教训：
1、介绍项目的时候不能一味的按照事前想好的模板说，应该根据所申请的工作的性质，多说一些和自己申请的工作内内容相近的东西说。我在介绍我的项目的时候，说了很多硬件的东西，而相关的Linux下的C编程却没有提到多少，一大失败之处。
2、对于他提的第二个问题，当时因为紧张没有想出来，挂了电话以后才有了思路。
3、这个概率题以前碰到过，而且和同学们讨论过，答案很早就知道了。但是遇到面试的时候，不能马上就说出答案，因为这样摆明了高诉人家你以前就见过这道题，这样就失去了作为考题的意义。所以，如果事前知道答案也不要马上说出来，装作考虑中，然后慢慢说出答案。我就是很快就说出了答案，失败！
4、在问项目的时候，他问我代码行大概有多少？我说大概有5.6K行左右。在回答第四个问题的时候，我几乎是将书上所讲过的东西背了一遍给他，虽然答案是正确的，但是我估计他一听就听出来是在背书了，所以这也会减分不少。，而且百度强调创新，其实就算你不知道答案也可以按照自己的思路说一下的，只要逻辑清晰、合理都会比我背书强……
5、我的回答是有时候用gdb，有时候用输出日志的形式。以我之前给他讲的项目经验是不大可能会涉及这么多的知识的，所以估计他又听出我是在背书了……继续减分
6、后来我发现这个问题其实他不是在考我问题的答案，是考我解决问题的能力和考虑问题的思路。这点是我比较差的地方，没办法……减分
我前面表现那么失败，基本上已经没有什么希望了，后面的谈话已经没有意义了，只不过是礼貌性的结束这次面试了。
上面的总结是我收到拒信以后才总结出来的，可悲的是电话面试结束以后，还以为能被录取呢……
面试官太和蔼了，而且气氛及其融洽，根本没有任何不好的征兆，面试官好厉害！
至此，我的百度求职过程到此告一段落……生活还在继续，工作还得继续努力去找，加油！ 百度电话面试题目： 1.谈谈你对数据库中索引的理解2.现在普通关系数据库用得数据结构是什么类型的数据结构3.索引的优点和缺点4.session和cache的区别是什么5.如果有几千个session，怎么提高效率6.session是存储在什么地方，以什么形式存储的。
