百度招聘笔试考试题.docx

百度招聘笔试考试题-附面试经验一、选择题：15 分 共 10 题# W! Z1 a+ g5 nm; E0 T1. 在排序方法中，关键码比较次数与记录地初始排列无关的是：, H% V0 H- C/ cA. Shell 排序 B. 归并排序 C. 直接插入排序 D. 选择排序$ o0 _, u h2 t0 ?# s( Q; p) H, a8 k$ , y& q6 8 O d . m d2. 以下多线程对 int 型变量x的操作，哪几个需要进行同步：/ : l# M. S, wn% QA. x=y; B. x+; C. +x; D. x=1; u; U- j- t+ iT7 c1 y; _ b: L 3 Q; C3. 代码3 t$ p# d0 C9 H! D( m8 m u* ?1 R% Evoid func()+ I$ v* F8 U* F * R0 v0 Q W0 E. w, u+ p gstatic int val;( ) K8 a$ j* v6 h& _; S9 A1 p. J6 v d/ k9 X N6 s# U$ Z. P- s4 P中，变量 val 的内存地址位于：( m/ c( P% b# i, Y- j5 kA. 已初始化数据段 B.未初始化数据段 C.堆 D.栈) n A3 ; r- H( |8 T2 H4 3 r3 d7 ya8 z3 B5 . e4. 同一进程下的线程可以共享以下：: R8 v: g3 I 0 rA. stack B. data section C. register set D. thread ID1 Z& n; . P+ 1 s( a( ?, O+ _. c# g, r8 u5. TCP 和 IP 分别对应了 OSI 中的哪几层？0 U. L% V) j1 Kk# s9 NA.Application layer B. Data link layer C. Presentation layer D. Physicallayer E. Transport layer F. Session layer G. Network layer3 s6 h7 c/ o Gg) j; k4 b, h+ L# G B J1 / # P+ 6. short a100，sizeof(a) 返回？6 u5 C% 6 H$ x5 2 nA. 2 B. 4 C. 100 D. 200 E. 400- U& C7 J+ l5 S3 V0 Y; ; C5 8 H9 a1 F4 B! Qf5 F& j: + m0 |7. 以下哪种不是基于组件的开发技术_。$ n1 e% N! C2 f5 9 AA. XPCOM B. XP C. COM D. CORBA U3 n! W4 N8 j2 E H A) J2 x9 Hl# m) R9 U8. 以下代码打印的结果是（假设运行在 i386 系列计算机上）：! V, ; $ K( Q 7 Ustruct st_t. D; c. o% ; _! m6 q+ O8 d$ / _! A; ( x( E5 Z2 8 g8 m$ w+ m9 h( j+ dint status;/ j/ M: I5 N- V1 D$ M$ s4 H- oshort *pdata;# R6 |* qq4 N+ K% Kchar errstr32;6 4 S9 U. K3 a- u;4 U$ Y9 s- l# Z6 K* u! H8 v r) P3 z j2 & P6 hst_t st16; Y! T0 + m% Tchar *p = (char *)( st2.errstr + 32 );+ X; k% U6 T( S/ o1 i3 mprintf( %d, ( p - (char *)(st) ) );6 p! E( U2 O8 i9 n) 4 U# _: B1 k: h% a z2 p0 IA. 32 B. 114 C. 120 D. 1112/ h; |- Y5 i# u* E) # J. p& 0 R& s% r9. STL 中的哪种结构是连续形式的存储：* O+ s$ t1 | Z. r+ D+ g DA. map B. set C. list D. vector7 N, % y9 K4 V, ?/ o* 3 Q, | 5 y3 K; R1 s10. 一个栈的入栈序列是 A，B，C，D，E，则栈的不可能的输出序列是：# Q4 E1 J4 a) - U( r+ iA. EDCBA B. DECBA C. DCEAB D. ABCDE+ V G, u3 u- E/ ?5 T# i v7 k9 O; Sh2 I5 E1 r二、简答题：20 分，共 2 题, F7 ; T2 3 1. （5 分）重复多次 fclose 一个打开过一次的 FILE *fp 指针会有什么结果，并请解释。( i: o5 Q1 x |* n考察点：导致文件描述符结构中指针指向的内存被重复释放，进而导致一些不可预期的异常。$ E3 c% S- c% E1 l. 8 hk6 s. P5 e2. （15 分）下面一段代码，想在调用 f2(1) 时打印 err1，调用 f2(2) 时打印 err4，但是代码中有一些问题，请做尽可能少的修改使之正确。/ 2 o$ r4 F& D) h# O- X# Q1 static int f1( const char *errstr, unsigned int flag ) * i* k& b2 lF2 2 int copy, index, len;9 t O+ C- c( u, B4 L: k3 const static char *_err = err1, err2, err3, err4 ;# rn) r7 u; ; q) w2 g4# G, k. r) v3 + c+ Z2 8 I, e& d5 if( flag & 0x10000 )! e0 i: e6 y: J- Jg u) b6 copy = 1;# P/ l3 P7 P7 U6 ?; 6 j7 index = ( flag & 0x300000 ) 20;9 M6 _1 G/ . l8 x) M$ m$ D8. m* z- F8 O$ i; E; P- b9 if( copy ) + A( l$ d1 8 s% v1 M3 |/ l10 len = flag & 0xF;7 1 q! E0 , e11 errstr = malloc( len );5 z D/ T8 b gK% M12 if( errstr = NULL )* Q5 S S. K7 H, k i/ ?R13 return -1;j/ . lA: QN14 strncpy( errstr, _errindex, sizeof( errstr ) ); b M# d/ l8 J7 O15 else! f2 u& b& J7 y# OE16 errstr = _err + index;- H- d9 ZB0 e( 4 i17 ; J/ * m& M( I. s18 h9 a7 L4 z; h/ S+ f: J19 void f2( int c ) * c& H( y& 2 + 5 l8 z4 v20 char *err;& w) T0 $ f) J3 f9 A0 B; O212 5 X, e+ % u# i# d7 B z& Q6 j22 swtch( c ) L$ ?3 A# 4 a P8 h23 case 1:0 8 d/ j5 I4 ) P) a& h2 h; N9 B24 if( f1( err, 0x110004 ) != -1 ). h! e5 F ! Y q% G: y: e: i25 printf( err );3 Z; q* X v6 t26 case 2:) h% w0 c9 |6 E6 4 X1 I+ _27 if( f2( err, 0x30000D ) != -1 ); e: z, E2 L! b/ g7 R; P* 2 z28 printf( err );* P$ C: O# T4 H- F6 h/ Q f3 l29 ! m. O* y( U: P3 r# C30 8 e& u& ( D2 K1 T. I2 T$ a; z! I$ * 0 I三、编程题：30 分 共 1 题$ j4 H _! |2 u% p注意：要求提供完整代码，如果可以编译运行酌情加分。5 c- h9 q& a Z; c( I. Y$ L2 l5 z% a+ l5 u3 m) : |1. 求符合指定规则的数。, W; I7 H# m7 C _给定函数 d(n) = n + n 的各位之和，n 为正整数，如 d(78) = 78+7+8=93。 这样这个函数可以看成一个生成器，如 93 可以看成由 78 生成。- P7 R2 _+ y, h0 2 Q定义数 A：数 A 找不到一个数 B 可以由 d(B)=A，即 A 不能由其他数生成。现在要写程序，找出 1 至 10000 里的所有符合数 A 定义的数。. P9 0 R5 Z1 P& o9 U+ e( I8 y8 o2 N) _ T3 h* W& m9 m$ Z: Y输出：) G* K3 & ; m0 j. m! H1: U- |% P7 1 E8 D( j e$ b37 W$ s! C2 2 S- j; x J& ?8 K o3 M3 b* G$ |. , U! 5 W/ D四、设计题：35 分 共 1 题 $ q R4 x9 J1 J, q- 注意：请尽可能详细描述你的数据结构、系统架构、设计思路等。建议多写一些伪代码或者流程说明。9 Y- _+ Z- T% C! G* j# X3 D! o1 M M# D: w1.假设一个 mp3 搜索引擎收录了 224 首歌曲，并记录了可收听这些歌曲的 230 条 URL，但每首歌的 URL 不超过 210个。系统会定期检查这些 URL，如果一个 URL 不可用则不出现在搜索结果中。现在歌曲名和 URL 分别通过整型的 SONG_ID 和URL_ID 唯一确定。对该系统有如下需求：1 u k& j7 _7 B9 S( H4 C6 n( _ h4 A1) 通过 SONG_ID 搜索一首歌的 URL_ID，给出 URL_ID 计数和列表* t/ h; V2 H( r! d2) 给定一个 SONG_ID，为其添加一个新的 URL_ID7 % w5 d0 A m; b3) 添加一个新的 SONG_ID3 a0 b6 5 0 d. D4) 给定一个 URL_ID，将其置为不可用% T+ 2 v8 X* D8 y* J+ C_1 x/ S/ D$ m% x: s7 V3 B4 t限制条件：内存占用不超过 1G，单个文件大小不超过 2G，一个目录下的文件数不超过 128 个。9 2 p c6 E& N 6 t% V8 f2 g2 y& ; g4 P为获得最佳性能，请说明设计的数据结构、搜索算法，以及资源消耗。如果系统数据量扩大，该如何多机分布处理？1 s8 k* ?1 zz6 F; e T8 H) F( R0 * S1 a0 x9 B百度第二套$ E. L. q6 e8 f: p8 F6 _! X# f! ) : R一、选择题：15 分 共 10 题4 % ! L7 4 V* $ K W9 U1.已知一个线性表(38,25,74,63,52,48)，采用的散列函数为 Hash($Key)=$Key mod7，将元素散列到表长为7的哈希表中存储。请选择后面两种冲突解决方法分别应用在该散列表上进行等概率成功查找的平均查找长度，拉链法 ，线性探测法 .* + m7 K U4 A. 1.0 B. 1.5 C. 1.7 D. 2.0 E. 2.3& M b# K2 o. oF. 7/6 G. 4/3 H. 3/2 W* i# e% + uC/ c 5 r U4 C# M7 v6 r2 M0 d# 2. 需要将OS缓冲区的数据刷新到硬盘，可以调用的函数有(多选)：- R9 Q/ C7 $ s! m, Y2 d8 hA.fflush() B. fsync() C. sync() D.writev() E+ m6 t3 % : e8 J1 r7 6 u r) r3. 下面哪个shell语句不能打印出用户主目录的路径？+ + J3 f, e) s$ x0 v, 7 GA. echo $HOME B. echo : j+ Sz- a5 M4 p% aC. echo $HOME D. echo $HOME5 HJ$ aJ0 Y7 ! m. T+ W; O4 L( |6 _! r/ _ v% 0 c& d+ |- q4. 最坏情况下，合并两个大小为n的已排序数组所需要的比较次数$ v4 q! J+ W* o. R E2 I/ aA.2n B.2n-1 C.2n+1 D.2n-2 y/ A9 M8 _! T. L$ w1 c) L* * k 0 e; E3 l3 G5. 一个B类网的子网掩码是，这个子网能拥有的最大主机数是：) A% J- E5 l) B* 4 QA. 240 B. 255 C.4094 D. 65534- q) xM% S2 0 b: H) |, v) Z( a% z* f$ B6. 以下代码执行后，val的值是_:, v Q% n7 g0 I8 kunsigned long val = 0;% T5 m* v4 a0 mchar a = 0x48;& P A3 U# B; |# P2 E2 # Hchar b = 0x52;2 t& nv! 2 j) Wval = b =0; i-) , q, D+ U8 Z; | S9 8 v12 if (sA & sZ) , b+ G% g5 ?7 M! Z; 2 R5 0 H13 s += 26;5 v8 a0 $ Y% V/ N! * U0 L+ t14 3 $ K! Q, u1 w% 7 K6 n: t15 & Y& s: 9 W. e 6 d16 return s; K: Z1 v+ d% Q5 U17 # % _ L( c m189 9 j) b + J+ G19 int A()7 & ! W( I3 G; y7 Y& R20 - $ v8 _8 S8 P. p7 j7 M9 _& K21 printf(old str%s after lower%sn, str1, ToLower(str1);3 Z, t( kp6 U8 q1 1 c2 |22 N7 P# q% / W, o+ f5 q$ . a) Y! c; U- ) x* c三、编程题：30分 共1题2 c. q& D) U7 K! I$ U6 注意：要求提供完整代码，如果可以编译运行酌情加分。& K! m1 1 |( K* 9 O2 E8 T7 J7 Y W! D w3 1 Y5 J# c, H# y6 E3 q! k4 M5 + K* M& I7 h7 B8 Q1. 两个已排序的整型数组，求交集，最快算法9 f, V a1 y* I% x. T0 ?输入：两个已排序的整型数组（int am, bn）) m( K9 e5 |1 d4 & 输出：两个数组的交集 # P5 $ b# J. H& s9 X) i8 U- q t四、设计题：35分 共1题, b: j: Z3 I( ?% h- Y& q注意：请尽可能详细描述你的数据结构、系统架构、设计思路等。建议多写一些伪代码或者流程说明。 u6 C v% Z) h; / s r! C9 I1.考虑一个字符串替换的过程，在一个文本文件中含有一些文本内容和一些需要替换的变量，变量的格式为“$Var$”，原来的“$”使用“$”进行转义，原来的“$”表示为“$”。我们将含有变量的文件称为模板(文件名为t)，文本文件的平均长度为100K。另外，还有一系列的变量文件，里面为变量名和变量值的对应关系(文件名为1.v , 2.vn.v)，每个变量文件包含的变量数在百万数量级，且变量排列次序不定。现要求将，模板里的变量分别用变量文件里的变量替换，并将生成的文件写成(1.r, 2.r n.r)。9 U& Q. w$ k8 要求：从算法和实现上和实现技术上的细节对程序进行优化，尽量使程序高效。程序运行环境为2G内存，4CPU。阐明主要思路，给出伪码和说明，可以着重指出你使用的优化技术。 b$ H# H6 |* ) T9 T. N例子：模板文件为& RS+ 9 1 M8 z* p$ IThis is an $FF$ $. I like $FF$ and $FA$。2 # + rc. p& l5 R- H3 n变量文件为( y8 ?/ * ! . r8 1.v4 g5 g* l9 h uA6 _5 4 AFF : banana0 N* g7 L% O: VFA : apple+ K5 x) X2 g+ m. F2.v4 f! Z; R: O- v- zFA: 苹果, K$ m$ Z8 w, k& _/ d& L) MFF : 香蕉8 X2 q* V- p! I9 P则生成文件为, C* P0 n: XM1.r s. p* l# : g mThis is an banana $. I like banana and apple。- g7 I8 M4 K, F- x: Q4 M7 f& b2.r m* Y1 A. U. AThis is an香蕉 $. I like 香蕉and苹果。5 Q/ z3 z1 ?! w! ; c8 ( l+ W# w) s) x2 V1）此题10分4 M; C8 _# ri; M/ U0 v对任意输入的正整数N，编写C程序求N!的尾部连续0的个数，并指出计算复杂度。如：18！6402373705728000，尾部连续0的个数是3。: E8 j O& Z% e v5 c（不用考虑数值超出计算机整数界限的问题）8 d9 u. 0 K9 |6 - A. F/ Z, m0 _, 7 a2）此题10分8 y2 F) N# X9 S( z编写一个C语言函数，要求输入一个url，输出该url是首页、目录页或者其他url4 . |5 X R+ m( i9 M7 a* A如下形式叫做首页：, c+ k; |3 7 |4 n$ , q0 h0 /9 Q6 B/ a: ?) S8 /! H$ O* R, b+ g! ; P/6 y3 f5 g d* O6 b/ 8 /9 B- x% N$ r1 O$ E0 p( s( j$ d/. K 2 ; c# KK0 r如下形式叫做目录页：* z! p: y: ?$ k# F. /greenhouses-gas-global-green-house-warming/N4 S. d$ i9 X$ g! y# P, u4 : P.tw/user/tgk5ar1r/profile/5 T. 7 w! s h! X/food/yszt/chunjie/3 F# Pk1 A /Reality/+ O5 d7 I7 i2 v. O5 G& % t, _1 w; 9 W, X( b1 A请注意：* U8 T2 7 , L, U: ma） url有可能带http头也有可能不带; m Q0 . V3 2 p/ i0 O4 2 Mb）动态url（即含有？的url）的一律不算目录页，如：% $ m: I4 t5 f) ?6 /utility/mailit.php?l=/activity/details/3135/3 u5 g z N) j6 e& /utility/mailit.php?l=/activity/details/2449/6 ) d ! c1 X( |4 yP7 s u/ k# X7 D4 另：如果你会linux，请用linux下的grep命令实现第2题的功能（附加5分）。- B, A& c & p, e: c, x( . H5 g1 n5 K4 Z+ t) s& ?3）此题40分3 o: b$ U0 n j1 Y/ o+ u5 : x如果必须从网页中区分出一部分重要网页（例如在10亿中选8亿），比其他网页更值得展现给用户，请提出一种方案。3 f! A* W1 f1 T, R6 G9 y: i5 W3 1 P- O2 x! F- P4）此题40分* F; v6 f9 h1 % c- E假设有10亿网页已经被我们存下来，并提供如下信息：网页全文（即网页的源码）、全文长度、网页正文（即网页中提取的主体文字）、5 C7 - I2 e/ w1 m0 a9 T/ o正文长度，以及其他网页提取物等，现在希望去掉其中的重复网页，请提出可行的方案，计算出每个网页对应的重复度，你可以自己/ o U2 e, z8 t$ y- j5 Q对网页重复下定义，也可以提出需要哪些更多