发布于 2014-10-01 02:40:01 | 250 次阅读 | 评论: 0 | 来源: 网友投递
百度(Baidu)中文搜索引擎
百度（Nasdaq简称：BIDU）是全球最大的中文搜索引擎，2000年1月由李彦宏、徐勇两人创立于北京中关村，致力于向人们提供“简单，可依赖”的信息获取方式。“百度”二字源于中国宋朝词人辛弃疾的《青玉案·元夕》词句“众里寻他千百度”，象征着百度对中文信息检索技术的执著追求。
一、简答题(30分)
1．当前计算机系统一般会采用层次结构存储数据，请介绍下典型计算机存储系统一般分为哪几
个层次，为什么采用分层存储数据能有效提高程序的执行效率？
2．简述Unix/Linux系统中使用socket库编写服务器端程序的流程，请分别用对应的socket
通信函数表示
3、Unix/Linux系统中僵尸进程是如何产生的？有什么危害？如何避免？
二、算法与程序设计题
1，使用C/C++编写函数，实现字符串反转，要求不使用任何系统函数，且时间复杂度最小，
函数原型：char* reverse_str(char* str)。
获取首尾指针，然后将首尾指针指向的元素交换，将首指针指向下一个，将尾指针指向前一个，
交换指针指向的元素，然后重复执行，直到首尾指针相遇。
2，给定一个如下格式的字符串(1,(2,3),(4,(5,6),7))括号内的元素可以是数字，也可以是另一个
括号，请实现一个算法消除嵌套的括号，比如把上面的表达式变成：(1,2,3,4,5,6,7)，如果表达
式有误请报错。
3、相似度计算用于衡量对象之间的相似程度，在数据挖掘、自然语言处理中是一个基础性计算，
在广告检索服务中往往也会判断网民检索Query和广告Adword的主题相似度，假设Query或
者Adword的主题属性定义为一个长度为10000的浮点数组Pr（10000）（称之为主题概率数
组）。其中Pr[i]表示Query或者Adword属于主题Id为i的概率，而Query和Adword的相似
度简化定义为两者主题概率数组的内积，即
sim(Query,Adword)=sum(QueryPr[i]*AdwordPr[i])(0<=i<10000),在实际应用场景中，由于大多
数主题的概率都为0，所以主题概率数组往往比较稀疏，在实现时会以一个紧凑型数组
topic_info_t的方式保存，其中100<=数组大小<=1000,并按照topic_id递增顺序排列，
0<=topic_id<10000,0<topic_pr<1,
Struct topic_info_t{
int topic_id;
float topic_pr;
}
现在给出Query的topic_info_t数组和N（N>=5000）个Adwords的topic_info_t数组，现要
求出Query与Adwords的相似度最大值，即max(sim(Query,Adword[i]))(0<=i<N),
Float max_sim(const vector<topic<info_t)&query_topic_info;
Const vector<topic_info_t>adwords_topic_info[];
Int adwords_number);
编写代码求时间复杂度最低的算法，并给出时间复杂度分析。