百度2010年校园招聘笔试题
一、简答题
1. 简述树的深度优先遍历及广度优先遍历，及其非递归实现的特点。
2. 找出以下程序中的BUG：
#include <stdio.h>#include <stdlib.h>struct Record{ int a; int b;}int create(struct Record *p, int num){ p = new strcut Record[num]; if(!p) return -1; else return 0;}int Test(){ struct Record *p = NULL; int i; int num; prinf("0x%08x\n", p); scanf("Input record num: %d", &num); if(create(p, num) < 0) return -1; printf("0x%08x\n", p); for(i=0; i<num; i++) { p.a = 0; p.b = 0; } return 0;}int main(void){ test(); getchar(); return 0;}3. 有一台Mini计算机，内存大小为1K， CPU主频为1M（CPU状态每秒改变10的6次方次），问在这台计算机上可运行并且确定可以终止的程序的最长运行时间是多少？请给出思路及推理过程（可以做任何的假设）
分析：要使程序可以终止，则表明计算机的内存状态不能出现重复情况，否则永远不能终止。内存大小为1K，1K=1024byte=8*1024bit，而每1bit有0、1这2中状态，因此内存状态有2^(8*1024)中状态。而CPU状态每秒改变10的6次方次，因此最长运行时间t = (2^(8*1024)) / (10^6).（单位：秒）
二、算法设计
1. 某大型项目由n个组件N1, N2, ..., Nn构成，每个组件都可以独立编译，但是某些组件的编译依赖其他组件（即某些组件只能在其他组件编译完成后才能编译），设计算法实现快速编译，并写出其时间复杂度。（注：不考虑多线程）
2. 完成函数：int maxnumstr(char *inputstr, char *outputstr)
函数功能：找出inputstr中的最长连续数字串存储到outputstr里，并返回长度。如：调用maxnumstr("123abc1234a", outputstr)后返回4且outputstr的值为“1234”。
三、系统设计
URL（统一资源定位符）由site、path组成，并且有其他属性信息，如访问时间等。如：http://www.baidu.com/img/abc中site为http://www.baidu.com，path为/img/abc。
请设计一个系统，实现以下要求：
1. 设计系统存储100亿条URL信息
2. 说明如何完成URL信息的添加、删除和修改
3. 如何添加URL属性
4. 对URL实现快速的查找
（提示：采用分布式操作系统实现）