百度试题.docx
《百度试题.docx》由会员分享，可在线阅读，更多相关《百度试题.docx（21页珍藏版）》请在冰点文库上搜索。
XX试题
1编程：
用C语言实现一个revert函数，它的功能是将输入的字符串在原串上倒序后返回。
用栈
2编程：
用C语言实现函数void*memmove（void*dest,constvoid*src,size_tn）。
memmove函数的功能是拷贝src所指的内存内容前n个字节到dest所指的地址上。
3英文拼写纠错：
在用户输入英文单词时，经常发生错误，我们需要对其进行纠错。
假设已经有一个包含了正确英文单词的词典，请你设计一个拼写纠错的程序。
（1）请描述你解决这个问题的思路；
（2）请给出主要的处理流程，算法，以及算法的复杂度；
（3）请描述可能的改进（改进的方向如效果，性能等等，这是一个开放问题）。
4寻找热门查询：
搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。
假设目前有一千万个记录，这些查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个。
一个查询串的重复度越高，说明查询它的用户越多，也就是越热门。
请你统计最热门的10个查询串，要求使用的内存不能超过1G。
（1）请描述你解决这个问题的思路；
（2）请给出主要的处理流程，算法，以及算法的复杂度。
5集合合并：
给定一个字符串的集合，格式如：
{aaabbbccc}，{bbbddd}，{eeefff}，{ggg}，{dddhhh}要求将其中交集不为空的集合合并，要求合并完成后的集合之间无交集，例如上例应输出{aaabbbcccdddhhh}，{eeefff}，{ggg}
（1）请描述你解决这个问题的思路；
（2）请给出主要的处理流程，算法，以及算法的复杂度
（3）请描述可能的改进（改进的方向如效果，性能等等，这是一个开放问题）。
////////////////////////////////
1题
char*revert（char*str）
{
intn=strlen（str）;
inti=0;
charc;
for（i=0;i{
c=str;
str=str[n-i];
str[n-i]=c;
}
returnstr;
}
///////////////////////////////////
2题
void*memmove（void*dest,constvoid*src,size_tn）
{
assert（（dest!
=0）&&（src!
=0））;
char*temp=（char*）dest;
char*ss=（char*）src;
inti=0;
for（;i{
*temp=*ss ;
}
returntemp;
}
/////////////////////////////////////////////////
3题
（1）思路:
字典以字母键树组织，在用户输入同时匹配
（2）流程:
每输入一个字母：
沿字典树向下一层，
a）若可以顺利下行，则继续至结束，给出结果；
b）若该处不能匹配，纠错处理，给出拼写建议,继续至a）；
算法:
1.在字典中查找单词
字典采用27叉树组织,每个节点对应一个字母,查找就是一个字母
一个字母匹配.算法时间就是单词的长度k.
2.纠错算法
情况:
当输入的最后一个字母不能匹配时就提示出错,简化出错处理，动态提示可能处理方法:
（a）当前字母前缺少了一个字母：
搜索树上两层到当前的匹配作为建议；
（b）当前字母拼写错误：
当前字母的键盘相邻作为提示；（只是简单的描述，可以有更多的）
根据分析字典特征和用户单词已输入部分选择（a）,（b）处理
复杂性分析：
影响算法的效率主要是字典的实现与纠错处理
（a）字典的实现已有成熟的算法，改进不大，也不会成为瓶颈；
（b）纠错策略要简单有效,如前述情况，是线性复杂度；
（3）改进
策略选择最是重要，可以采用统计学习的方法改进。
//////////////////////////////////////////////
4题
（1）思路：
用哈希做
（2）首先逐次读入查询串，算哈希值，保存在内存数组中，同时统计频度（注意值与日志项对应关系）选出前十的频度，取出对应的日志串，简单不过了。
哈希的设计是关键。
//////////////////////////////////////////////////
5题
（1）思路：
先将集合按照大小排列后,优先考虑小的集合是否与大的集合有交集。
有就合并，如果小集合与所有其他集合都没有交集，则独立。
独立的集合在下一轮的比较中不用考虑。
这样就可以尽量减少字符串的比较次数。
当所有集合都独立的时候，就终止。
（2）处理流程：
1.将集合按照大小排序，组成集合合并待处理列表
2.选择最小的集合，找出与之有交集的集合，如果有，合并之；如果无，则与其它集合是独立集合，从待处理列表中删除。
3.重复直到待处理列表为空
算法：
1。
将集合按照大小从小到大排序,组成待处理的集合列表。
2。
取出待处理集合列表中最小的集合，对于集合的每个元素，依次在其他集合中搜索是否有此元素存在：
1>若存在，则将此小集合与大集合合并，并根据大小插入对应的位置。
转3。
2>若不存在，则在该集合中取下一个元素。
如果无下一个元素，即所有元素都不存在于其他集合。
则表明此集合独立，从待处理集合列表中删除。
并加入结果集合列表。
转3。
3。
如果待处理集合列表不为空，转2。
如果待处理集合列表为空，成功退出，则结果集合列表就是最终的输出。
算法复杂度分析：
假设集合的个数为n，最大的集合元素为m排序的时间复杂度可以达到n*log（n）然后对于元素在其他集合中查找，最坏情况下为（n-1）*m查找一个集合是否与其他集合有交集的最坏情况是m*m*（n-1）合并的时间复杂度不会超过查找集合有交集的最坏情况。
所以最终最坏时间复杂度为O（m*m*n*n）
需要说明的是：
此算法的平均时间复杂度会很低，因为无论是查找还是合并，都是处于最坏情况的概率很小，而且排序后优先用最小集合作为判断是否独立的对象，优先与最大的集合进行比较，这些都最大的回避了最坏情况。
（3）可能的改进：
首先可以实现将每个集合里面的字符串按照字典序进行排列，这样就可以将查找以及合并的效率增高。
另外，可能采取恰当的数据结构也可以将查找以及合并等操作的效率得到提高。
取自"
、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、
1）此题10分
对任意输入的正整数N，编写C程序求N!
的尾部连续0的个数，并指出计算复杂度。
如：
18！
＝6402373705728000，尾部连续0的个数是3。
（不用考虑数值超出计算机整数界限的问题）
2）此题10分 编写一个C语言函数，要求输入一个url，输出该url是首页、目录页或者其他url
如下形式叫做首页：
militia.info/
http:
//hgh-products.my-
如下形式叫做目录页：
.tw/user/tgk5ar1r/profile/
请注意：
a）url有可能带http头也有可能不带
b）动态url（即含有"？
"的url）的一律不算目录页，如：
另：
如果你会linux，请用linux下的grep命令实现第2题的功能（附加5分）。
3）此题40分
如果必须从网页中区分出一部分"重要网页"（例如在10亿中选8亿），比其他网页更值得展现给用户，请提出一种方案。
4）此题40分
假设有10亿网页已经被我们存下来，并提供如下信息：
网页全文（即网页的源码）、全文长度、网页正文（即网页中提取的主体文字）、正文长度，以及其他网页提取物等，现在希望去掉其中的重复网页，请提出可行的方案，计算出每个网页对应的重复度，你可以自己对网页重复下定义，也可以提出需要哪些更多的网页提取物来实现更好的去重复方案。
取自"
、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、
好久没来了。
发生了一些事情，其间的心情已不是几行文字所能表述的了。
终于明白有些事情，并不是自己努力就一定能圆满的；有些事情，是我控制不了的。
唉，不提也罢！
说说今天去XX笔试的经历吧
部门：
XX搜索应用技术部。
地点：
海淀南路银科大厦（海淀图书城西临）18层。
时间：
2005/6/1510：
00-11：
20am
九点从实验室出发，725到知春路，转735，到海淀桥下车，9：
50到达XX。
在725的车上碰到一男士索要手机号，说自己认识信息产业部的部长杨泽民先生，以居高临下的姿态把手机号给了他-__-!
在XX前台见到了一直帮我安排笔试的杨韫敏jj，不是想象中的HR形象，而是一副干练的女IT的样子跳跃的灵魂很快，给我找了一间小会议室，只有一张桌子，两把椅子，还帮我开了灯，关门，走人，我开始看题。
冷汗也开始流。
翻了一下三页纸的笔试题，只有很少的传说中的Linux题目，其他的全是C、数据结构、算法编程的题。
第一反应：
走人！
但又觉得对不起陈jj，关键的是我已经在笔试题上写了姓名和学校了，sign，总的为自己的名字和学校负责吧，他们是无辜的。
如此斗争良久，决定坚持下来。
题目大致是这样的：
第一部分选择题：
有几道网络相关的题目，巨简单，比如第一题是TCP、RIP、IP、FTP中哪个协议是传输层的......。
有一道linux的chown使用题目。
其他的全是数据结构的题目！
什么链，表，码的，不知所云跳跃的灵魂唉，我可以没有学过数据结构的人呐！
真残忍！
这一部分迅速猜完！
第二部分简答题：
1、在linux中如何编译C程序，使之成为可执行文件？
如何调试？
答案：
1）检查程序中.h文件所在的目录，将其加入系统PATH中；
2）执行C编译：
#gcc[源文件名]-o[目标文件名]
执行C++编译：
#g++[源文件名]-o[目标文件名]
3）改变目标文件为可执行文件：
#chmod+x[目标文件名]
4）如需将多个可执行文件连续执行，可生成批处理文件：
#vi[批处理文件名]
可执行文件1
可执行文件2
.........
最后将该批处理文件属性该位可执行。
调试：
在编译时使用-g参数，就可以使用gdb进行调试。
2、写出内存分配和释放的函数，并指出区别。
答案：
C语言的标准内存分配函数：
malloc，calloc，realloc，free等。
malloc与calloc的区别为1块与n块的区别：
malloc调用形式为（类型*）malloc（size）：
在内存的动态存储区中分配一块长度为“size”字节的连续区域，返回该区域的首地址。
calloc调用形式为（类型*）calloc（n，size）：
在内存的动态存储区中分配n块长度为“size”字节的连续区域，返回首地址。
realloc调用形式为（类型*）realloc（*ptr，size）：
将ptr内存大小增大到size。
free的调用形式为free（void*ptr）：
释放ptr所指向的一块内存空间。
C++中为new/delete函数。
3、写出socket函数，并指出其功能。
socket（）:
建立socket通信描述符；
bind（）：
将套接字和机器上的一定的端口关联；
connect（）：
连接到远程主机；
listen（）：
使套接字做好连接的准备，规定等待服务请求队列的长度；
accept（）：
接受连接，一旦有客户端发出连接，accept返回客户地址信息和一个新的sock；
有了这个新的sock，双方就可以开始收发数据：
send（）和recv（）：
用于流式套接字或者数据套接字的通讯；
sendto（）和recvfrom（）：
用于无连接的数据报套接字；
close（）：
关闭套接字；
shutdown（）：
选择性的关闭套接字，可以只允许某一方向的通讯关闭；
getpeername（）：
返回流式套接字时对端peer信息；
gethostname（）：
返回程序所运行的机器的主机名字；
gethostbyname（）：
返回本机IP；
第三部分编程题：
1、从文件中读取字符串数据，反序显示并大小写转换。
2、给定26字母表以及对应的密码表，编程实现加密及解密功能。
第四部分思考题（正是传说中的字典纠错题）：
用户在输入英文单词时经常出错，现对其进行就错。
给定一个正确的英文词典，考虑纠错实现。
1）指出思路。
2）流程、算法难易程度及可能的改进策略。
不过陈jj没有给我答题纸，只好拿试题的背面做了答题纸兼草稿纸-___-!
说实话有些题目是很基础的，就是没背过。
不知怎么搞得，巨潦草。
实验室参加过笔试的通同学都是憋着劲做了两个多小时才答完，而我只一个小时就完了，唉，正好说明肚子里只有别人一半的东西~~看着潦草而不着边际的答题，决定在最后给陈jj写段话，大意就是感谢她帮我挽回了一次笔试的机会，但我的表现很遗憾等等......然后交卷走人~~
没想到交了试卷没让我走，等了大约30分钟的样子，有个很深沉的gg来看我的卷子跳跃的灵魂-___-!
我颤颤的跟他说我很长时间没有接触C了，当时脖子都红了，真觉得丢人。
gg看了一下，没有很鄙视的样子，问我有没有带简历。
当然木有啦~~答应回来给他发个电子版的，然后赶紧跑人了！
、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、
题目大致是这样的：
第一部分选择题：
有几道网络相关的题目，巨简单，比如第一题是TCP、RIP、IP、FTP中哪个协议是传输层的......。
有一道linux的chown使用题目。
其他的全是数据结构的题目！
什么链，表，码的，不知所云．唉，我可以没有学过数据结构的人呐！
真残忍！
这一部分迅速猜完！
第二部分简答题：
1、在linux中如何编译C程序，使之成为可执行文件？
如何调试？
答案：
1）检查程序中.h文件所在的目录，将其加入系统PATH中；
2）执行C编译：
#gcc[源文件名]-o[目标文件名]
执行C++编译：
#g++[源文件名]-o[目标文件名]
3）改变目标文件为可执行文件：
#chmod+x[目标文件名]
4）如需将多个可执行文件连续执行，可生成批处理文件：
#vi[批处理文件名]
可执行文件1
可执行文件2
.........
最后将该批处理文件属性该位可执行。
调试：
在编译时使用-g参数，就可以使用gdb进行调试。
2、写出内存分配和释放的函数，并指出区别。
答案：
C语言的标准内存分配函数：
malloc，calloc，realloc，free等。
malloc与calloc的区别为1块与n块的区别：
malloc调用形式为（类型*）malloc（size）：
在内存的动态存储区中分配一块长度为“size”字节的连续区域，返回该区域的首地址。
calloc调用形式为（类型*）calloc（n，size）：
在内存的动态存储区中分配n块长度为“size”字节的连续区域，返回首地址。
realloc调用形式为（类型*）realloc（*ptr，size）：
将ptr内存大小增大到size。
free的调用形式为free（void*ptr）：
释放ptr所指向的一块内存空间。
C++中为new/delete函数。
3、写出socket函数，并指出其功能。
socket（）:
建立socket通信描述符；
bind（）：
将套接字和机器上的一定的端口关联；
connect（）：
连接到远程主机；
listen（）：
使套接字做好连接的准备，规定等待服务请求队列的长度；
accept（）：
接受连接，一旦有客户端发出连接，accept返回客户地址信息和一个新的sock；
有了这个新的sock，双方就可以开始收发数据：
send（）和recv（）：
用于流式套接字或者数据套接字的通讯；
sendto（）和recvfrom（）：
用于无连接的数据报套接字；
close（）：
关闭套接字；
shutdown（）：
选择性的关闭套接字，可以只允许某一方向的通讯关闭；
getpeername（）：
返回流式套接字时对端peer信息；
gethostname（）：
返回程序所运行的机器的主机名字；
gethostbyname（）：
返回本机IP；
第三部分编程题：
1、从文件中读取字符串数据，反序显示并大小写转换。
2、给定26字母表以及对应的密码表，编程实现加密及解密功能。
第四部分思考题（正是传说中的字典纠错题）：
用户在输入英文单词时经常出错，现对其进行就错。
给定一个正确的英文词典，考虑纠错实现。
1）指出思路。
2）流程、算法难易程度及可能的改进策略。
一道算法题目答案
intReplace（Stringtype&S,StringtypeT,StringtypeV）;//将串S中所有子串T替换为V,并返回置换次数
{
for（n=0,i=1;i〈=Strlen（S）-Strlen（T）+1;i++）//注意i的取值范围
if（!
StrCompare（SubString（S,i,Strlen（T））,T））//找到了与T匹配的子串
{//分别把T的前面和后面部分保存为head和tail
StrAssign（head,SubString（S,1,i-1））;
StrAssign（tail,SubString（S,i+Strlen（T）,Strlen（S）-i-Strlen（T）+1））;
StrAssign（S,Concat（head,V））;
StrAssign（S,Concat（S,tail））;//把head,V,tail连接为新串
i+=Strlen（V）;//当前指针跳到插入串以后
n++;
}//if
returnn;
}//Replace
分析:
i+=Strlen（V）;这一句是必需的,也是容易忽略的.如省掉这一句,则在某些情况下,会引起不希望的后果,虽然在大多数情况下没有影响.请思考:
设S='place',T='ace',V='face',则省掉i+=Strlen（V）;运行时会出现什么结果?
（无限递归face）
XX2005年的笔试题
1.实现voiddelete_char（char*str,charch）;
把str中所有的ch删掉
2.把字符串S中所有A子串换成B,这个没给函数原型
3.搜索引擎的日志要记录所有查询串,有一千万条查询,不重复的不超过三百万
要统计最热门的10条查询串.内存<1G.字符串长0-255
（1）主要解决思路//具体用词和原题不大一样
（2）算法及其复杂度分析
4.有字典,设计一个英文拼写纠正算法
（1）思想
（2）算法及复杂度（3）改进
5.{aaa,bb,ccc,dd},{bbb,ff},{gg}等一些字符串的集合
要求把交集不为空的集合并起来,如上例会得到{aaa,bb,ccc,dd,ff},{gg}
（1）思想
（2）算法及复杂度（3）改进
取自"
、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、
一、选择题：
15分共10题
1.一个含有n个顶点和e条边的简单无向图，在其邻接矩阵存储结构中共有____个零元素。
A．e B．2e C．n2-e D．n2-2e
2.____是面向对象程序设计语言中的一种机制。
这种机制实现了方法的定义与具体的对象无关，而对方法的调用则可以关联于具体的对象。
A．继承（Inhertance）B．模板（Template）
C．对象的自身引用（Self-Reference）D．动态绑定（DynamicBinding）
3.应用层DNS协议主要用于实现网络服务功能.
A.IP地址到网络设备名字的映射B.IP地址到网络硬件地址的映射
C.网络设备名字到IP地址的映射D.网络硬件地址到IP地址的映射
4.linux默认情况下，一个进程最多能打开多少文件？
A.64B.128C.512D.1024
5.下面结构体
structs1{
charch,*ptr;
union{
shorta,b;
unsignedintc:
2,d:
1;
}
structs1*next;
};
的大小是_____：
A.12字节B.16字节C.20字节D.24字节
6.任何一个基于"比较"的内部排序的算法，若对6个元素进行排序，则在最坏情况下所需的比较次数至少为____。
A．10B．11C．21D．36
7.以下不是进程间通
升级会员 