百度2010年校园招聘笔试题

一、简答题

1. 简述树的深度优先遍历及广度优先遍历，及其非递归实现的特点。

分析：

1）深度优先遍历：假设给定图G的初态是所有定点均未访问过，在G中任选一顶点v为初始出发点（源点），则蛇毒优先遍历可以定义如下：首先访问出发点v，并将其标记为已访问过，然后依次才能够v促发搜索v的每一个邻接点w。若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至途中所有和源点v有路径相通的顶点均已被访问为止。若此时途中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至途中所有顶点均被访问到为止。

2）广度优先遍历：设图G的初态是所有顶点均未访问过。在G中任选一顶点v为源点，则广度优先遍历可以定义为：首先访问出发点v，接着依次访问v的所有邻接点w1，w2，…，wt，然后再依次访问与wl，w2，…，wt邻接的所有未曾访问过的顶点。依此类推，直至图中所有和源点v有路径相通的顶点都已访问到为止。此时从v开始的搜索过程结束。若G是连通图，则遍历完成；否则，在图C中另选一个尚未访问的顶点作为新源点继续上述的搜索过程，直至G中所有顶点均已被访问为止。

3）非递归的实现：深度优先遍历采用压栈算法，而广度优先遍历采用队列算法！

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;
}

分析：此题是一道基础测试题，其大概有如下BUG：

①、将scanf("Input record num: %d", &num)改为：

printf("Input record num:");

scanf(" %d", &num);

②、使用create（）为空指针分配空间，需使用双指针或返回空间地址：

将int create(struct record *p, int num)改为int create(struct record **p, int num)或struct record *create(int num)

③、C语言代码中不能使用new来分配空间应使用malloc（）

将p = new struct Record[num]改为*p = (struct record *)malloc(num * sizeof(struct record))

④、代码段

    for(i=0; i<num; i++) 
    {
        p.a = 0; 
        p.b = 0; 
    } 

改为：

    struct record *current = NULL;
    ...
    current = p;
    for(i=0; i<num; i++, current++)
    {
        current->a = 0;
        current->b = 0;
    }

⑤、存在内存泄露：没有释放动态申请的内存空间

应在Test（）最后加上free(p), p = NULL;

综合以上五点，可将代码改为：

int create(struct record **p, int num)
{
    *p = (struct record*)malloc(num*sizeof(struct record));
    if(NULL == *p)
    {
        return -1;
    }
    return 0;
}

int test()
{
    struct record *p = NULL, *current = NULL;
    int i = 0;
    int num = 0;

    prinf("0x%08x\n", p);
    printf(""Input record num: "");
    scanf(" %d", &num);

    if(create(p, num) < 0) return -1;
    printf("0x%08x\n", p);

    current = p;
    for(i=0; i<num; i++, current++)
    {
        current->a = 0;
        current->b = 0;
    }

    current = NULL;
    free(p), p = NULL;

     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”。

参考代码：

int maxnumstr(const char *inputstr, char *outputstr)
{
    char *pstr = inputstr,
         *maxstart = NULL;
    int len = 0, maxlen = 0;

    if(NULL == pstr) return 0;

    while('\0' != *pstr)
    {
        if(isdigital(*pstr))
        {
            len++;
            pstr++;
            continue;
        }

        if(len > maxlen)
        {
            maxstart = pstr - len;
            maxlen = len;
        }
        len = 0;
        pstr++;
    }

    if(len > maxlen)
    {
        maxstart = pstr - len;
        maxlen = len;
    }

    memcpy(outputstr, maxstart, maxlen);
    return maxlen;
}

三、系统设计

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实现快速的查找

（提示：采用分布式操作系统实现）

分析：使用哈希表，冲突时使用链表方式或二次哈希等方式处理。有了此思路，其添加、修改、删除、查找等问题都已不再是问题了！