高分求教百度笔试题答案！

1、   简答题。请说出树的深度优先、广度优先遍历算法，及非递归实现的特点。

2、   找错

struct complex_t

{

   int real;

   int imag;

}

int create(complex_t*p,unsigned int n)

{

   p=new complex_t[n];

   if(p==NULL){

return -1;

}

return 0;

}

     int compute()

{

   //implement

   complex_t*comps;

   unsigned int num=0;

   cin>>num;

   if(create(comps,num)=0){

       cerr<<”create comps failes!”<

     return n-1;

}

long long int sum=0;

unsigned int pos=0;

cin>>pos;

while(pos<

cin>>comps[pos].real>>comps[pos].imag;

sum+=comps[pos].real*comps[pos+1].real+comps[pos].imag*comps[pos+1].imag;

pos+=2;

}

cout<<”sum is”<

return 0;

}

第二部分程序与算法

1、   一个典型的大型项目，通常由众多组件构成，这些组件之间复杂的编译依赖于在构建整个系统时，是最让人头疼的地方之一。现在就有这样的一个大型项目，由N（N>1000）个组件构成，每个组件都是可以编译的，但组件之间存在着编译依赖，如组件N1依赖N2，即编译N1时N2必须已经先编译完成，否则N1不能完成编译，但组件之间没有循环依赖的问题。请设计一种快速算法，能完成整个项目的编译构建过程，并给出算法的时间复杂度。

2、   实现一个函数的完整代码。

int maxContinuNum(const char*inputstr.char*outputstr)

功能：

在以‘\0’结尾的字符串中找出连续最长的数字串，并把这个串的长度返回，并把这个最长数字串付给其中一个函数参数outputstr所指内存。不能用strlen之类的库函数。

现在有一组共计N个固定的集合（N为万量级），每个集合有个从0开始递增的集合ID，每个
集合包含1－M个
term(M为o-100的量级),希望设计一个程序，能够持续对外服务，输入是一个term数组，输
出其中任意一个集
合ID（如果该term数组包含该集合的所有term)，如果找不到，输出－1。要求：
1、时间复杂度最优，能够在短时间内对大量输入逐个输出。
2、实现具体的代码（可以是伪代码），其中常用的数据结构可以采用标准库
3、给出时间复杂度和空间复杂度
　TERM_1 空格 TERM_2
TERM_1 空格 TERM_3
TERM_1 空格 TERM_3 TERM_4
输入的为TERM数组。
　　　（说明:TERM为一个词，可能是中文，用字符串表示)

8 个解决方案

#1

我也想知道啊

#2

这里的int create(complex_t*p,unsigned int n)有问题，无法得到分配的空间。正确的写法应该是：
int create(complex_t**p,unsigned int n)
{

  *p=new complex_t[n];

  if(p==NULL)
  {
     return -1;
  }
  return 0;
}

#3

complex_t*comps;应该初始化
long long int sum=0;在vc6.0中错误如下：error C2632: 'long' followed by 'long' is illegal
应该修改成long int sum=0;

#4

1、一个典型的大型项目，通常由众多组件构成，这些组件之间复杂的编译依赖于在构建整个系统时，是最让人头疼的地方之一。现在就有这样的一个大型项目，由N（N>1000）个组件构成，每个组件都是可以编译的，但组件之间存在着编译依赖，如组件N1依赖N2，即编译N1时N2必须已经先编译完成，否则N1不能完成编译，但组件之间没有循环依赖的问题。请设计一种快速算法，能完成整个项目的编译构建过程，并给出算法的时间复杂度。

典型的图中的拓补排序。

#5

2、实现一个函数的完整代码。

int maxContinuNum(const char*inputstr.char*outputstr)

功能：

在以‘\0’结尾的字符串中找出连续最长的数字串，并把这个串的长度返回，并把这个最长数字串付给其中一个函数参数outputstr所指内存。不能用strlen之类的库函数。

找两个下标，数字开始且连续到非数字字符

#6

1、简答题。请说出树的深度优先、广度优先遍历算法，及非递归实现的特点。
深度：从一个子结点直到叶子结点，回溯。
广度：一层一层的找，把上一层放入队列，用于下一层的查找。

一般非递归理论上更快，因为少了函数的递归调用，但也是借助于栈来处理，但是现在的编译器对递归优化得很好。但有的非递归实现可以使用叶结点的空指针来指向其它结点，帮助搜索，而不用栈。

#7

去百度，就是考算法，数据量超大时，算法直接关系系统性能的优劣

#8

该回复于2010-12-07 09:18:11被版主删除

#1