百度面试题
stone54321277
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个。
为获得最佳性能，请说明设计的数据结构、搜索算法，以及资源消耗。如果系统数据量扩大，该如何多机分布处理？
stone54321277
access_log access_log.bak,执行完后,请问新的apache的日志会打印到哪里,为什么?
1、新的日志会打印在access_log.bak中，因为apache启动时会找到access_log文件，随时准备向文件中加入日志信息，
虽然此时文件被改名，但是由于服务正在运行，因为它的inode节点的位置没有变，程序打开的fd仍然会指向原来那个inode，
不会因为文件名的改变而改变。apache会继续向已改名的文件中追加日志，但是若重启apache服务，系统会检查access_log
文件是否存在，若不存在则创建。
2.在Shell环境下,如何查看远程Linux系统运行了多少时间?
2、监控主机执行： ssh user@被监控主机ip "uptime"
这样得到了被监控主机的uptime
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任意一种
3、[root@localhost shell]# cat file | sed -e ' s/http:\/\///' -e ' s/
\/.*//' | sort | uniq -c | sort -rn
3 www.baidu.com
2 post.baidu.com
1 mp3.baidu.com
[root@codfei4 shell]# awk -F/ '{print $3}' file |sort -r|uniq -c|awk
'{print $1"\t",$2}'
3 www.baidu.com
2 post.baidu.com
1 mp3.baidu.com
4.如果得到随机的字串,长度和字串中出现的字符表可定义,并将字串倒序显示,如
把0123456789作为基准的字串字符表,产生一个6位的字串642031,打印出的字串为
130246,可使用bash/perl/php/c任意一种.
4、 [root@localhost ~]# awk -v count=6 'BEGIN {srand
();str="0123456789";len=length(str);for(i=count;i>0;i--) marry=substr
(str,int(rand()*len),1);for(i=count;i>0;i--) printf("%c",marry);printf
("\n");for
(i=0;i<=count;i++) printf("%c",marry);printf("\n")}'
838705
507838
5.如何查看当前Linux系统的状态,如CPU使用,内存使用,负载情况等.
5、Linux系统中“/proc”是个伪文件目录,不占用系统空间，及时的反应出内存现在使用的进程情况......其中许多文件都保存系统运行状态
和相关信息
对于“/proc”中文件可使用文件查看命令浏览其内容，文件中包含系统特定信息：
cpuinfo 主机CPU信息
filesystems 文件系统信息
meninfo 主机内存信息
version Linux内存版本信息
diskstatus 磁盘负载情况
另外top命令可以动态的显示当前系统进程用户的使用情况,而且是动态的显示出来，尤其是在该命令显示出来的对上方对系统的情况进行汇总.
free命令呢可以查看真实使用的内存 一般用free -m
使用lsof 、ps -aux 可以查看详细的每个进程的使用状况
dmesg 也是常用来查看系统性能的命令
#######################################################################################################################################################################
#题目：有10台被监控主机、一台监控机，在监控机上编写脚本，一旦某台被监控机器/分区适用率大于80%， 就发邮件报警放到crontab里面，
每10分钟检查一次
#测试机器：虚拟机Linux as 4
#1.首先建立服务器间的信任关系。拿两台机器做测试
本机ip:192.168.1.6
[root@codfei ~]# ssh-keygen -t rsa
Generating public/private rsa key pair.
Enter file in which to save the key (/root/.ssh/id_rsa):
/root/.ssh/id_rsa already exists.
Overwrite (y/n)? y (以为我是第2次建立关系所以此处覆盖原来的文件)
Enter passphrase (empty for no passphrase):(直接回车无须输入密钥)
Enter same passphrase again:
Your identification has been saved in /root/.ssh/id_rsa.
Your public key has been saved in /root/.ssh/id_rsa.pub.
The key fingerprint is:
04:37:13:2a:4b:10:af:c1:2b:03:3f:6b:27:ce:b9:62 root@codfei
[root@codfei ~]# cd .ssh/
[root@codfei .ssh]# ll
-rw------- 1 root root 883 Apr 25 17:51 id_rsa
-rw-r--r-- 1 root root 221 Apr 25 17:51 id_rsa.pub
-rw-r--r-- 1 root root 442 Apr 25 17:37 known_hosts
id_rsa是密钥文件，id_rsa.pub是公钥文件。
[root@codfei .ssh]# scp id_rsa.pub192.168.1.4:/root/.ssh/192.168.1.6
ro...@192.168.1.4's password:
id_rsa.pub 100% 221 0.2KB/s
00:00
这里把公钥文件取名为本机的ip地址就是为了以后和更多的机器建立信任关系不发生混淆。
现在登陆到192.168.1.4机器
[root@codfei ~]# cd .ssh/
[root@codfei .ssh]# cat 192.168.1.6 >> authorized_keys
然后回到192.168.1.6机器直接
[root@codfei .ssh]# ssh 192.168.1.4
Last login: Wed Aug 8 12:14:42 2007 from 192.168.1.6
这样就可以了，里面偶尔涉及到权限问题。一般./ssh文件夹是755 authorized_keys为600或者644
####脚本如下#######################
#!/bin/bash
#SCRIPT:df_check.sh
#Writeen by codfei Mon Sep 3 07:25:28 CST 2007
#PURPOSE:This script is used to monitor for full filesystems.
#######################Begining########################################
FSMAX="80"
remote_user='root' #####完全可以不用root
remote_ip=(192.168.1.5 192.168.1.6 192.168.1.7 192.168.1.8 192.168.1.9
192.168.1.10 192.168.1.11 192.168.1.12 192.168.1.13 192.168.1.14 )
###这里填写你要监控的主机ip
ip_num='0'
while [ "$ip_num" -le "$(expr ${#remote_ip[@]} - 1)" ]
do
read_num='1'
ssh "$remote_user"@"${remote_ip[$ip_num]}" df -h > /tmp/diskcheck_tmp
grep '^/dev/*' /tmp/diskcheck_tmp|awk '{print $5}'|sed 's/\%//g' > /
tmp/diskcheck_num_tmp
while [ "$read_num" -le $(wc -l < /tmp/
diskcheck_num_tmp) ]
do
size=$(sed -n "$read_num"'p' /tmp/diskcheck_num_tmp)
if [ "$size" -gt "$FSMAX" ]
then
$(grep '^/dev/*' /tmp/diskcheck_tmp|sed -n $read_num'p' > /tmp/
disk_check_mail)
$(echo ${remote_ip[$ip_num]} >> /tmp/
disk_check_mail)
$(mail -s "diskcheck_alert" admin < /tmp/
disk_check_mail)
fi
read_num=$(expr $read_num + 1)
done
ip_num=$(expr $ip_num + 1)
done
#############over################################
################让脚本每十分钟执行一次#############
在cron表中加入
0/10 * * * * /home/codfei/diskcheck.sh 2>&1
##########################################################################
比如， ext2文件系统， 如果异常死机，开机如何修复文件系统？
如果异常关机，比如断电，通知机房的人开机之后，
我们需要远程修复、检查文件系统
除了/分区之外， 其他的分区：
umount /home
fsck -y /home
/ 分区需要开机之后， 由机房的人来扫描
随后我们再登录并扫描/home等其他分区
如何查看一个进程所使用的文件句柄？
看这里面 /proc/进程号/fd/
的个数就行了
简单的比如如何查看apache进程数
[root@localhost fd]# ps -ef|grep httpd|wc -l
1
如何统计apache的每秒访问数？
tail access_log | awk '{print $1,$4}'
[root@localhost logs]# grep -c `date -d '3 second ago' +%T` access_log
0
#######################################################################################################################
#######################################################################################################################
1、/proc/sys 子目录的作用
该子目录的作用是报告各种不同的内核参数，并让您能交互地更改其中的某些。与 /proc 中所有其他文件不同，该目录中的某些文件可以写入，不过这仅
针对 root。
其中的目录以及文件的详细列表将占据过多的篇幅，而且该目录的内容是依赖于系统的，而大部分的文件也仅仅对某些特殊的应用程序有用。然而，以下是该子目
录的两个最常见的用途：
允许路由：即便是 Mandrakelinux 默认的内核也是允许路由的，您必需显式允许它这么做。为此，您只要以 root 身份键入以下命令：
$ echo 1 >/proc/sys/net/ipv4/ip_forward
如果您要禁用路由，请将上述命令中的 1 改为 0。
阻止 IP 欺骗：IP 欺骗会让人认为某个来自于外部的某个数据包是来自于它到达的那个接口。这一技术常被骇客(cracker)所使用。您可以让内
核阻止这种入侵。请键入：
$ echo 1 >/proc/sys/net/ipv4/conf/all/rp_filter
这样，这种攻击就不再可能了。
这些改变仅当系统运行时有效。在系统重新启动之后，它们会改会它们的默认值。要在启动时就改动这些值，您可以将您在 shell 提示符后键入的命令添
加到 /etc/rc.d/rc.local 中以免每次都键入它们。另一个方法是修改
/etc/sysctl.conf
2、将一个文本的奇数行和偶数行合并，第2行和第3行合并
[root@localhost bin]# cat 1
48 Oct 3bc1997 lpas 68.00 lvx2a 138
484 Jan 380sdf1 usp 78.00 deiv 344
483 nov 7pl1998 usp 37.00 kvm9d 644
320 aug der9393 psh 83.00 wiel 293
231 jul sdf9dsf sdfs 99.00 werl 223
230 nov 19dfd9d abd 87.00 sdiv 230
219 sept 5ap1996 usp 65.00 lvx2c 189
216 Sept 3zl1998 usp 86.00 kvm9e 234
[root@localhost bin]# sed '$!N;s/\n/ /g' 1
48 Oct 3bc1997 lpas 68.00 lvx2a 138 484 Jan
380sdf1 usp 78.00 deiv 344
483 nov 7pl1998 usp 37.00 kvm9d 644 320 aug
der9393 psh 83.00 wiel 293
231 jul sdf9dsf sdfs 99.00 werl 223 230 nov
19dfd9d abd 87.00 sdiv 230
219 sept 5ap1996 usp 65.00 lvx2c 189 216 Sept
3zl1998 usp 86.00 kvm9e 234
[root@localhost bin]# sed -n -e 2p -e 3p 1|sed '$!N;s/\n/ /'
484 Jan 380sdf1 usp 78.00 deiv 344 483 nov
7pl1998 usp 37.00 kvm9d 644
3、read 命令5秒后自动退出
[root@localhost bin]# read -t 5
4、自动ftp上传
#!/bin/sh
ftp -n<<END_FTP
open 192.168.1.4
user codfei duibuqi //用户名codfei 密码duibuqi
binary
prompt off //关闭提示
mput test //上传test
close
bye
END_FTP
自动ssh登陆 从A到B然后再到c
#!/usr/bin/expect -f
set timeout 30
spawn ssh codfei@B
expect "password:"
send "pppppp\r"
expect "]*"
send "ssh codfei@C\r"
expect "password:"
send "pppppp\r"
interact
5、#打印第一个域
[root@localhost bin]# cat 3
eqeqedadasdD
eqeqdadfdfDD
fdsfdsfQWEDD
DSADASDSADSA
[root@localhost bin]#
[root@localhost bin]#
[root@localhost bin]# awk -F "" '{print $1}' 3
e
e
f
D
6、实现字符串翻转
[root@localhost bin]# cat 8
qweqewqedadaddas
[root@localhost bin]# rev 8
saddadadeqweqewq
########################################第2次电面
7、sed awk grep哪个最好
我答的是 哪个掌握的精通，都很好，但是还是问我哪个最好，我只能说awk了，对于行操作和列操作都可以操作的很好。
8、grep -E -P 是什么意思
我说的是-E, --extended-regexp 采用规则表示式去解释样式。 -P不太清楚
9、还问了我对运维这个工作的理解，和应该具备的素质。
…………
后记：百度面试的这些日子，很刻苦的学习了一个阶段。脚本编写能力有了很大的提高。但是还是很遗憾，没有去到那。打算在大连找个运维的工作，继续我的理
想。工作几年之后，我还会继续努力的。
3年前，我是个连电脑开机关机都不会的农村孩子，现在我感觉自己已经对于Linux入门了，我很有成就感，但是我还是被百度通知，我没有发展潜力。我是
东软的学生，我总是认为计算机这个行业不看
出身，只要有实力就可以了。但是第一次电面我没有被提前通知会电面，突然打来的电话，当时正在睡觉，头脑一片空白……进入到第2次面试的时候，没有慌张
准备的很充分，但是还是没有最终被录取。
面试的考官问我，你最失落的事是什么，我说我最失落的事是我高考前意外受伤休学了，我现在才意识到，我当时应该回答他，我最失落的时刻应该是我得知被百
度拒绝的那一刻。
已经付出了努力，即使失败也很坦然。
stone54321277
a) 文件名不包括域名、路径和URL参数，例如http://www.rs.com/n.op/q/rs?id=1中的文件名是rs。
b) 部分URL可能没有文件名，例如http://www.abc.com/，这类统计为“空文件名”。
c) 出现在不同URL中的相同文件名视为同一文件名，例如http://www.ceshi.com/hi.php和ftp://
ftp.cdef.com/hi.php为同一文件名
文件内容示例如下：
http://www.test.com/abc/de/fg.php?id=1&url=http://www.test.com/index.html
http://www.hello.com/cw/hi.jsp?k=8
http://www.hi.com/jk/l.html?id=1&s=a.html
http://www.rs.com/n.op/q/rs?id=1
http://www.abc.com/
C++代码
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
void UrlFileName(char* fileName, char* p[], int nLen);
void GetUrlFileName(const char* fileName);
char* StringTrim(char* pFile);
char* GetFileName(const char* pstrUrl,int nStrLen);
void UrlFileName(char* fileName, char* p[], int nLen)
{
int nCount = 0;
for(int i = 0 ;i < nLen;++i)
{
if(!strcmp(p[i], fileName))
{
++nCount;
}
}
printf("文件名%s出现的次数为%d\n", fileName, nCount);
free(p[i]);
}
void GetUrlFileName(const char* fileName)
{
FILE* fRead = fopen(fileName, "r");
FILE* fWrite = fopen("d:\\write.txt", "w");
char szFile[1000] = {0};
char* p[100] = {NULL};
char* p1[100] = {NULL};
int index = 0;
int nflag = 0;
int index1 = 0;
while(1)
{
memset(szFile, 0, 1000);
fgets(szFile, 1000, fRead);
strcpy(szFile, StringTrim(szFile));
int nStr = strlen(szFile);
if(nStr == 1 || nStr == 0) continue;
fputs(szFile, fWrite);
p[index] = GetFileName(szFile, nStr);
for(int i = 0;i < index1;++i)
{
if(!strcmp(p1[i], p[index]))
{
++nflag;
break;
}
}
if(nflag == 0)
{
p1[index1] = p[index];
++index1;
}else
{
nflag = 0;
}
++index;
if(feof(fRead)) break;
}
for(int i = 0;i < index1;++i)
{
UrlFileName(p1[i], p, index);
}
fclose(fRead);
fclose(fWrite);
}
/*
去除前后空格
abcdefg
*/
char* StringTrim(char* pFile)
{
char* pStr = pFile;
while(*pFile != 0)
{
if(*pFile != ' ')
{
break;
}else
{
++pStr;
}
++pFile;
}
int i = strlen(pFile) - 1;
do
{
if(*(pFile+i) != ' ')
{
break;
}else
{
*(pStr+i) = '\0';
}
--i;
} while (i >= 0);
return pStr;
}
/*
截取最后一个反斜的杠的位置和"?"号的位置
*/
char* GetFileName(const char* pstrUrl,int nStrLen)
{
char* pUrlName = (char*)malloc(20);
memset(pUrlName, 0, 20);
int i = 0;
int nCount1 = 0;
int nCount2 = 0;
do
{
if('/' == *(pstrUrl+i))
{
if(nCount1 != 0)
{
nCount1 = 0;
}
nCount1 += i;
}
if('?' == *(pstrUrl+i))
{
nCount2 += i;
break;
}
++i;
}while(i < nStrLen);
if(!nCount2)
{
nCount2 = i-1;
}
i = nCount1 + 1;
int urlIndex = 0;
if(i == nCount2)
{
pUrlName = "空文件";
}else
{
for(;i < nCount2;++i)
{
*(pUrlName+urlIndex) = *(pstrUrl+i);
++urlIndex;
}
}
return pUrlName;
}
stone54321277
数据结构为：
typedef struct_TreeNode{
char c;
TreeNode *leftchild;
TreeNode *rightchild;
}TreeNode;
函数接口为：int CompTree(TreeNode* tree1,TreeNode* tree2);
注：A、B两棵树相等当且仅当Root->c==RootB-->c,而且A和B的左右子树相等或者左右互换相等。
2、写一段程序，找出数组中第k大小的数，输出数所在的位置。例如{2，4，3，4，7}中，第一大的数是7，位置在4。第二大、第三大的数都是4，位
置在1、3随便输出哪一个均可。
函数接口为：int find_orderk(const int* narry,const int n,const int k)
2'、已知一个字串由GBK汉字和ansi编码的数字字母混合组成，编写c语言函数实现从中去掉所有ansi编码的字母和数字(包括大小写),要求在原
字串上返回结果。
函数接口为：int filter_ansi(char* gbk_string)
注：汉字的GBK编码范围是0x8140-0xFEFE
百度笔试题（感谢网友lihan提供）
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亿网页已经被我们存下来，并提供如下信息：网页全文（即网页的源码）、全文长度、网页正文（即网页中提取的主体文字）、
正文长度，以及其他网页提取物等，现在希望去掉其中的重复网页，请提出可行的方案，计算出每个网页对应的重复度，你可以自己
对网页重复下定义，也可以提出需要哪些更多的网页提取物来实现更好的去重复方案