1、1 编程： 用 C 语言实现一个 revert 函数，它的功能是将输入的字符串在原串上倒序后返回。 2 编程： 用 C 语言实现函数 void * memmove(void *dest,const void *src,size_t n)。memmove 函数的功能是拷贝 src 所指的内存内容前 n 个字节到 dest 所指的地址上。 3 英文拼写纠错： 在用户输入英文单词时，经常发生错误，我们需要对其进行纠错。假设已经有一个包含了正确英文单词的词典，请你设计一个拼写纠错的程序。 （1）请描述你解决这个问题的思路；（2）请给出主要的处理流程，算法，以及算法的复杂度；（3）请描述可能的改进（改进
2、的方向如效果，性能等等，这是一个开放问题）。4 寻找热门查询 ： 搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为 1-255 字节。假设目前有一千万个记录，这些查询串的重复度比较高，虽然总数是 1 千万，但如果除去重复后，不超过 3 百万个。一个查询串的重复度越高，说明查询它的用户越多，也就是越热门。请你统计最热门的 10 个查询串，要求使用的内存不能超过 1G。 （1）请描述你解决这个问题的思路；（2）请给出主要的处理流程，算法，以及算法的复杂度。5 集合合并： 给定一个字符串的集合，格式如： aaa bbb ccc， bbb ddd，eee fff，gg
3、g， ddd hhh 要求将其中交集不为空的集合合并，要求合并完成后的集合之间无交集，例如上例应输出 aaa bbb ccc ddd hhh，eee fff， ggg （1）请描述你解决这个问题的思路；（2）请给出主要的处理流程，算法，以及算法的复杂度（3）请描述可能的改进（改进的方向如效果，性能等等，这是一个开放问题）。/ 1 题 char *revert(char * str)int n=strlen(str);int i=0;char c;for(i=0;i c=str;str=strn-i;strn-i=c;return str;/ 2 题 void * memmove(void *d
4、est,const void *src,size_t n)assert(dest!=0)char * temp=(char * )dest;char * ss=(char * )src;int i=0;for(;i *temp =*ss ;return temp;/ 3 题 (1)思路: 字典以字母键树组织，在用户输入同时匹配 (2) 流程:每输入一个字母： 沿字典树向下一层，a）若可以顺利下行，则继续至结束，给出结果；b)若该处不能匹配，纠错处理，给出拼写建议, 继续至 a）；算法:1.在字典中查找单词字典采用 27 叉树组织,每个节点对应一个字母,查找就是一个字母一个字母匹配.算法时间就是
5、单词的长度 k.2.纠错算法 情况:当输入的最后一个字母不能匹配时就提示出错, 简化出错处理，动态提示可能 处理方法: (a)当前字母前缺少了一个字母：搜索树上两层到当前的匹配作为建议；(b)当前字母拼写错误：当前字母的键盘相邻作为提示；（只是简单的描述，可 以有更多的）根据分析字典特征和用户单词已输入部分选择(a),(b)处理 复杂性分析：影响算法的效率主要是字典的实现与纠错处理 (a）字典的实现已有成熟的算法，改进不大，也不会成为瓶颈；(b)纠错策略要简单有效 ,如前述情况，是线性复杂度；(3)改进 策略选择最是重要，可以采用统计学习的方法改进。 / 4 题 (1)思路：用哈希做 (2)
6、首先逐次读入查询串，算哈希值，保存在内存数组中，同时统计频度（注意值与日志项对应关系） 选出前十的频度，取出对应的日志串，简单不过了。哈希的设计是关键。 / 5 题 （1）思路：先将集合按照大小排列后,优先考虑小的集合是否与大的集合有交集。有就合并，如果小集合与所有其他集合都没有交集，则独立。独立的集合在下一轮的比较中不用考虑。这样就可以尽量减少字符串的比较次数。当所有集合都独立的时候，就终止。 （2）处理流程： 1.将集合按照大小排序，组成集合合并待处理列表2.选择最小的集合，找出与之有交集的集合，如果有，合并之；如果无，则与其它集合是独立集合，从待处理列表 中删除。3.重复直到待处理列表
7、为空 算法： 1。将集合按照大小从小到大排序,组成待处理的集合列表。 2。取出待处理集合列表中最小的集合，对于集合的每个元素，依次在其他集合中搜索是否有此元素存在： 1若存在，则将此小集合与大集合合并，并根据大小插入对应的位置 。转3。 2若不存在，则在该集合中取下一个元素。如果无下一个元素，即所有元素都不存在于其他集合。则表明此集合独立，从待处理集合列表中删除。并加入结果集合列表。转 3。 3。如果待处理集合列表不为空，转 2。 如果待处理集合列表为空，成功退出，则结果集合列表就是最终的输出。 算法复杂度分析： 假设集合的个数为 n，最大的集合元素为 m 排序的时间复杂度可以达到 n*log
8、(n) 然后对于元素在其他集合中查找，最坏情况下为（n-1）*m 查找一个集合是否与其他集合有交集的最坏情况是 m*m*(n-1) 合并的时间复杂度不会超过查找集合有交集的最坏情况。所以最终最坏时间复杂度为O(m*m*n*n) 需要说明的是：此算法的平均时间复杂度会很低，因为无论是查找还是合并，都是处于最坏情况的概率很小，而且排序后优先用最小集合作为判断是否独立的对象，优先与最大的集合进行比较，这些都最大的回避了最坏情况。 (3)可能的改进： 首先可以实现将每个集合里面的字符串按照字典序进行排列，这样就可以将查找以及合并的效率增高。另外，可能采取恰当的数据结构也可以将查找以及合并等操作的效率得
9、到提高。 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、1）此题 10 分 对任意输入的正整数 N，编写 C 程序求 N!的尾部连续 0 的个数，并指出计算复杂度。如：18！ 6402373705728000，尾部连续 0 的个数是 3。 （不用考虑数值超出计算机整数界限的问题） 2）此题 10 分 编写一个 C 语言函数，要求输入一个 url，输出该 url 是首页、目录页或者其他 url 如下形式叫做首页： militia.info/ http:/ http:/hgh-products.my
10、- 如下形式叫做目录页： http:/.tw/user/tgk5ar1r/profile/ http:/ 请注意： a） url 有可能带 http 头也有可能不带 b）动态 url（即含有“？“的 url）的一律不算目录页，如： 另：如果你会 linux，请用 linux 下的 grep 命令实现第 2 题的功能（附加5 分）。 3）此题 40 分 如果必须从网页中区分出一部分“重要网页“（例如在 10 亿中选 8 亿），比其他网页更值得展现给用户，请提出一种方案。 4）此题 40 分 假设有 10 亿网页已经被我们存下来，并提供如下信息：网页全文（即网页的源码）、全文长度、网页正文
11、（即网页中提取的主体文字）、正文长度，以及其他网页提取物等，现在希望去掉其中的重复网页，请提出可行的方案，计算出每个网页对应的重复度，你可以自己对网页重复下定义，也可以提出需要哪些更多的网页提取物来实现更好的去重复方案。 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、好久没来了。 发生了一些事情，其间的心情已不是几行文字所能表述的了。 终于明白有些事情，并不是自己努力就一定能圆满的；有些事情，是我控制不了的。 唉，不提也罢！ 说说今天去百度笔试的经历吧 部门：百度搜索应用技术部。 地点：海淀南路银科大厦（海淀图书城西临）1
12、8 层。 时间：2005/6/15 10：00-11：20 am 九点从实验室出发，725 到知春路，转 735，到海淀桥下车，9：50 到达百度。在 725 的车上碰到一男士索要手机号，说自己认识信息产业部的部长杨泽民先生，以居高临下的姿态把手机号给了他-_-! 在百度前台见到了一直帮我安排笔试的杨韫敏 jj，不是想象中的 HR 形象，而是一副干练的女 IT 的样子跳跃的灵魂很快，给我找了一间小会议室，只有一张桌子，两把椅子，还帮我开了灯，关门，走人，我开始看题。冷汗也开始流。翻了一下三页纸的笔试题，只有很少的传说中的 Linux 题目，其他的全是 C、数据结构、算法编程的题。第一反应：走人
13、！但又觉得对不起陈 jj，关键的是我已经在笔试题上写了姓名和学校了， sign，总的为自己的名字和学校负责吧，他们是无辜的。如此斗争良久，决定坚持下来。 题目大致是这样的： 第一部分选择题：有几道网络相关的题目，巨简单，比如第一题是TCP、RIP 、 IP、FTP 中哪个协议是传输层的.。有一道 linux 的 chown使用题目。其他的全是数据结构的题目！什么链，表，码的，不知所云跳跃的灵魂唉，我可以没有学过数据结构的人呐！真残忍！这一部分迅速猜完！ 第二部分简答题： 1、在 linux 中如何编译 C 程序，使之成为可执行文件？如何调试？ 答案： 1)检查程序中.h 文件所在的目录，将其加
14、入系统 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 块
15、与 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()：用于无连接的数据报套接字；
