湖南大学计算机与通信学院2007年保研能力测试(机试题目+部分解题报告)

green_guitar

我觉得xnby的二叉树遍历的程序不严谨，有问题。
例如，我输入
* 2 3
- 4 5
y 0 0
x 0 0
z 0 0
这是对的，然而如果我输成
* 4 5
x 0 0
- 2 5
y 0 0
z 0 0
结果就是错的了，但是这两种输入输进去的是同一棵数。

green_guitar

我写了一个关于二叉树的，希望大家指教
#include <iostream.h>
#include <stdio.h>

struct node
{
char val;
int l;
int r;
};

node * Nodes ;

void RLR(int i)
{
if (i == -1)
{
return;
}
printf("%c",Nodes.val);
RLR(Nodes.l-1);
RLR(Nodes.r-1);
}


void LRR(int i)
{
if (i == -1)
{
return;
}

LRR(Nodes.l - 1);
printf("%c",Nodes.val);
LRR(Nodes.r - 1);
}

void LRRoot(int i)
{
if (i == -1)
{
return;
}

LRRoot(Nodes.l - 1);
LRRoot(Nodes.r - 1);
printf("%c",Nodes.val);
}


int main()
{

int n;
cin >> n;
int j = n;

while(n--)
{
int m;
cin >> m;
Nodes = new node[m];//动态分配数组

for(int i = 0;i < m;i++)
{
cin >> Nodes.val;
cin>> Nodes.l;
cin>> Nodes.r;
}

printf("Case%d:\n",j - n);
RLR(0);
printf("\n");
LRR(0);
printf("\n");
LRRoot(0);
printf("\n");
delete[] Nodes;
}
return 0;
}

xnby

引用第36楼green_guitar于2008-09-26 08:02发表的:
我觉得xnby的二叉树遍历的程序不严谨，有问题。
例如，我输入
* 2 3
- 4 5
y 0 0
.......

再看了下题..题目节点是按顺序给出的吧..
不然你知道x,y,z对应3，4，5号节点？怎么对应？

xnby

我的程序是很暴力的..用了快500ms，
别人的程序0ms的。就是在建树上效率不好。
但是程序通过了测试。结果是AC的

你的程序还有12个编译错误...
你声明一个数组
Nodes = new node[m];//动态分配数组
还这样使用？
Nodes.l - 1
GNUC++/VC++都是通不过编译的

green_guitar

我在vc++6.0上通过编译了的。我不是用的标准c++
对，节点的顺序是每一个依次下来的，但是我举得那个例子你可以去看看，用你那个用指针建树的过程是错误的。
但是那两组数据的确也代表了同一棵树啊，题目确实也没怎么说清楚。
呵呵，我可不是和大家争吵的，希望大家别那么介意啊。探讨交流啊，我是菜鸟嘛。
我想问下啊，复试要做出来几个题目才可能被录取啊，一般来说，复试的时候录取率高不啊，今天我接到复试通知了。

green_guitar

其实那个Nodes = new node[m];//动态分配数组是通过指针来开辟你想要得到的数组，你只需要m（m<100）个大小的空间，你就没必要开100个大小的空间，我确实不是用最标准的c++写的，也许你的编译器和我的不一样，如果还是有错的话，你可以把动态分配改成静态的嘛，你就开100个，结果也是对的。

xnby

动态数组我没见过这么用的...　Nodes既然是个数组..直接使用就是首地址了..你这里语句实在不明白..
for(int i = 0;i < m;i++)
{
cin >> Nodes.val;
cin>> Nodes.l;
cin>> Nodes.r;
}
还有你说的那个例子第二种输入就是违法的，看题目说明（依次描述每个节点）
也就是说第一行是根节点...接下来依次类推...
然后你数据本来就是错的，可能是你打错- 2 5，
最后复试的问题各个学校都不同，好的学校１２０％的比率，一些学校去了都能要．

蓝白黑

呵呵，我可不是和大家争吵的，希望大家别那么介意啊。探讨交流啊，我是菜鸟嘛。
===================================================================
当然不会介意，来者皆是客

而且xnby兄亲自看了你的代码，不容易勒……看别人的代码很累的说……特别是有“个性”的代码，呵呵

还有，程序对不对，OJ说了算

green_guitar

呵呵，那谢谢xnby兄亲关心，呵呵，那几条语句就是输入数据的意思。呵呵，别讨论我的程序，我甘拜下风了，还是谢谢各位了。那我们学校的复试通过率高吗，还是希望自己能留在湖大读研呢。

upctanker

[s:333][s:333][s:333]

zhoujay1987

[s:326][s:325][s:330][s:329][s:328][s:331][s:332][s:333][s:354] 灌水...

treey

不错～～支持一下～