一、简答题
1. 简述树的深度优先遍历及广度优先遍历及其非递归实现的特点;
2. 找出以下程序中的bug:
#include <stdio.h>
#include <stdlib.h>
struct Record{
int a;
int b;
};
int create(struct Record *p, int num)
{
p = new struct Record[num];
if (!p)
return -1;
else
return 0;
}
int Test()
{
struct Record *p = NULL;
int i;
int num;
printf("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[i].a = 0;
p[i].b = 0;
}
return 0;
}
int main(void)
{
Test();
getchar();
return 0;
}
3. 有一台Mini计算机,内存大小为1K,CPU主频为1M(CPU状态每秒改变10的6次方次),问在这台计算机上可运行并且确定可以终止的程序的最长运行时间是多少?
给出思路及推理过程(可以做任何假设)。
二、算法设计
1. 某大型项目由n个组件N1, N2……Nn构成,每个组件都可以独立编译,但是某些组件的编译依赖于其它组件(即某些组件只能在其它组件编译完成后才能编译),设计算法给出统计过程。
2. 完成函数: