百度笔试题

1.简述深度优先及广度优先遍历算法，并说明非递归实现的特点 

2. 程序找错，一大段。 

3. 假设有一台迷你计算机，1KB的内存，1MHZ的cpu，已知该计算机执行的程序可出现确定性终止（非死循环），问如何求得这台计算机上程序运行的最长时间，可以做出任何大胆的假设。 

4. 大型软件有很多组件，编译时存在复杂的依赖关系，比如N1和N2存在依赖关系，要编译N1必须先编译N2,假设存在N<1000个组件，之间存在复杂的依赖关系，但不存在依赖环，问采用怎样的算法来构建编译规则，说明算法的复杂度。 

5.写一个函数 int MaxContinuNum(const char *inputstr,char *outputstr) 

找出一个字符串中最长的连续数字串，返回最长数字串的长度，并将最长字符串存入Outputstr指定的地址， 

如， abcd1234abd123abcd123456789, 最长连续字符串为123456789，长度为9 

6.有100亿个url，要求设计一个系统，能实现url的添加、删除、更新，并能查看url的内容 

//ougaoyan 2009-7-11

#include

#include

#include

#include

#include

#define MaxVNum 7

#define NIL (-1)

typedef struct _Graph

{

char Vertex[MaxVNum]; //顶点集合

int Edge[MaxVNum][MaxVNum];//邻接矩阵表示边

int Vn;//顶点个数

int En;//边的个数

}Gragh;

//VColor VCOLOR;

int colorV[MaxVNum]; //0：白色；1：灰色；2：黑色

int Father[MaxVNum];

int time = 0;

int D[MaxVNum];

int F[MaxVNum];

char Result[MaxVNum];

//创建图的方法

void CreateGraph(Gragh* G,char *V, int E[][MaxVNum])

{

int numE = 0;

G->Vn = strlen(V);//顶点数

for(int i = 0; i < G->Vn;i++)

{

   G->Vertex[i] = V[i];

   for(int j = 0; j < G->Vn;j++)

   {

    G->Edge[i][j] = E[i][j];

    if(E[i][j] == 1)

    {

     numE++;

    }

   }

}

G->En = numE;//边数

  

}

void DFS_Visit(int u,Gragh G)

{

colorV[u] = 1; //发现该顶点时将其置为灰色

    time = time +1;//时间加1

D[u] = time; //设置该顶点的发现时间

//对每一个与u连接的顶点，如果其还未被发现，对其进行深度优先搜索

for(int i = 0; i < G.Vn;i++)

{

   if(G.Edge[u][i] == 1 && colorV[i] == 0)

   {

    Father[i] = u;

    DFS_Visit(i,G);

   }

}

colorV[u] = 2;

time = time + 1;

F[u] = time;

}

void DFS(Gragh G)

{

time = 0;

for(int i = 0; i < G.Vn;i++)

{

   colorV[i] = 0;

   Father[i] = NIL;

   D[i] = 0;

   F[0] = 0;

}

for(int j = 0; j < G.Vn;j++)

{

   if(colorV[j] == 0)

   {

    DFS_Visit(j, G);

   

   }

}

}

int main()

{

Gragh G;

char *V = "1234567";

int E[7][7] = { {0,1,1,1,0,0,0}, 

      {0,0,0,1,1,0,0},

      {0,0,0,0,0,1,0},

      {0,0,1,0,0,1,1},

      {0,0,0,1,0,0,1},

      {0,0,0,0,0,0,0}, 

      {0,0,0,0,0,1,0}};

CreateGraph(&G, V, E);

    DFS(G);

for(int i = 0; i < G.Vn;i++)

{

   printf("%c开始时间：%d 结束时间：%d\n",G.Vertex[i],D[i],F[i]);

}

return 0;

}

int GetMaxSubStr(const unsigned char *str) 

{ 

    int maxLen = 0; 

    if (NULL == str) 

    { 

        return 0; 

    } 

    int lastPos[256]; 

    for (int i = 0; i < 256; ++i) 

    { 

        lastPos[i] = -1; 

    }     

    for (int pos = 0; str[pos] != '\0'; ++pos) 

    { 

        unsigned char c = str[pos]; 

        if (lastPos[c] > -1) 

        { 

            int len = pos - lastPos[c] + 1; 

            if (len > maxLen) 

            { 

                maxLen = len; 

            } 

        } 

        lastPos[c] = pos; 

    } 

    return maxLen; 

}