百度笔试题HWT整理(含答案)

1编程：用C语言实现一个revert函数，它的功能是将输入的字符串在原串上倒序后返回。（程序运行通过）char*Revert(char*string){If(NULL==string)ReturnNULL;Intlen=strlen(string);For(intI=0,intj=len-1;ij;i++,j--){String[I]=string[i]^string[j];String[j]=string[i]^string[j];String[i]=string[i]^string[j];}Returnstring;}2编程：用C语言实现函数void*memmove(void*dest,constvoid*src,size_tn)。memmove函数的功能是拷贝src所指的内存内容前n个字节到dest所指的地址上。（程序运行通过）Void*memmove(void*dest,constvoid*src,size_tn)(此时假设dest和src的有效内存都大于n，不会出现非法越界情况){If(NULL==dest||NULL==src||n=0)ReturnNULL;Char*temp=(char*)dest;Char*srouce=(char*)src;IntI=0;While(In){Temp[i]=src[i];I++;}Returntemp;}3英文拼写纠错：在用户输入英文单词时，经常发生错误，我们需要对其进行纠错。假设已经有一个包含了正确英文单词的词典，请你设计一个拼写纠错的程序。（1）请描述你解决这个问题的思路；（2）请给出主要的处理流程，算法，以及算法的复杂度；（3）请描述可能的改进（改进的方向如效果，性能等等，这是一个开放问题）。(1)思路:字典以字母键树组织，在用户输入同时匹配(2)流程:每输入一个字母：沿字典树向下一层，a）若可以顺利下行，则继续至结束，给出结果；b)若该处不能匹配，纠错处理，给出拼写建议,继续至a）；算法:1.在字典中查找单词字典采用27叉树组织,每个节点对应一个字母,查找就是一个字母一个字母匹配.算法时间就是单词的长度k.2.纠错算法情况:当输入的最后一个字母不能匹配时就提示出错,简化出错处理，动态提示可能处理方法:(a)当前字母前缺少了一个字母：搜索树上两层到当前的匹配作为建议；(b)当前字母拼写错误：当前字母的键盘相邻作为提示；（只是简单的描述，可以有更多的）根据分析字典特征和用户单词已输入部分选择(a),(b)处理复杂性分析：影响算法的效率主要是字典的实现与纠错处理(a）字典的实现已有成熟的算法，改进不大，也不会成为瓶颈；(b)纠错策略要简单有效,如前述情况，是线性复杂度；4寻找热门查询：（未解决）搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。假设目前有一千万个记录，这些查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就是越热门。请你统计最热门的10个查询串，要求使用的内存不能超过1G。（1）请描述你解决这个问题的思路；（2）请给出主要的处理流程，算法，以及算法的复杂度。答：（1）将查询串映射成哈希值，然后将查询串读入，统计频度。取出频度最高的的10个。（2）如何设计哈希表呢？5集合合并：给定一个字符串的集合，格式如：{aaabbbccc}，{bbbddd}，{eeefff}，{ggg}，{dddhhh}要求将其中交集不为空的集合合并，要求合并完成后的集合之间无交集，例如上例应输出{aaabbbcccdddhhh}，{eeefff}，{ggg}（1）请描述你解决这个问题的思路；（2）请给出主要的处理流程，算法，以及算法的复杂度（3）请描述可能的改进（改进的方向如效果，性能等等，这是一个开放问题）。（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)可能的改进：首先可以实现将每个集合里面的字符串按照字典序进行排列，这样就可以将查找以及合并的效率增高。另外，可能采取恰当的数据结构也可以将查找以及合并等操作的效率得到提高。6.编程对任意输入的正整数N，编写C程序求N!的尾部连续0的个数，并指出计算复杂度。如：18！＝6402373705728000，尾部连续0的个数是3。（不用考虑数值超出计算机整数界限的问题）7.编程编写一个C语言函数，要求输入一个url，输出该url是首页、目录页或者其他url如下形式叫做首页：militia.info/://://hgh-products.my-age.net/如下形式叫做目录页：thursdaythree.net/greenhouses--gas-global-green-house-warming/://请注意：a）url有可能带http头也有可能不带b）动态url（即含有？的url）的一律不算目录页，如：=/activity/details/3135/=/activity/details/2449/8.系统设计（未解决）如果必须从网页中区分出一部分重要网页（例如在10亿中选8亿），比其他网页更值得展现给用户，请提出一种方案。9.系统设计（未解决）假设有10亿网页已经被我们存下来，并提供如下信息：网页全文（即网页的源码）、全文长度、网页正文（即网页中提取的主体文字）、正文长度，以及其他网页提取物等，现在希望去掉其中的重复网页，请提出可行的方案，计算出每个网页对应的重复度，你可以自己对网页重复下定义，也可以提出需要哪些更多的网页提取物来实现更好的去重复方案。答：我的思路：首先我认为网页重复度应该包含的应该是网页主体的的相似度，如果网页主体的相似度非常高的话，便可以认为这两个网页时非常相似的。计算网页重复度方法：首先将网页主题长度titlelen和网页正文长度textlen计算出来，然后将主题和正文按照一定算法进行哈希，将所得的哈希值分别与各自长度进行相乘，得到两个数值title，text然后各自模100，保存下来，每次得到网页后做相关计算，然后再比较。10简答题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；11.编程题1、从文件中读取字符串数据，反序显示并大小写转换。3．intReplace(Stringtype&S,StringtypeT,StringtypeV);//将串S中所有子串T替换为V,并返回置换次数(该程序运行成功，同时加入了对替换后字符串长度的判断)12编程题1.实现voiddelete_char(char*str,charch);把str中所有的ch删掉13选择题1.一个含有n个顶点和e条边的简单无向图，在其邻接矩阵存储结构中共有____个零元素。A．eB．2eC．n2-eD．n2-2e2.____是面向对象程序设计语言中的一种机制。这种机制实现了方法的定义与具体的对象无关，而对方法的调用则可以关联于具体的对象。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.10245.下面结构体（看不懂）