数据结构相关的问题

Question

1.已知一个二叉树的中的叶子数为50，仅有一个孩子的结点数为30
求总结点数是129
2.若一个叶子结点是某子树的中序遍历的最后的一个结点，则它必须是该子树的先序遍历的最后一个结点（×）
3.图的生成树的边数要小于顶点数（×）
4.已知某算法的的执行时间为(n+n^2)*log2(n+2)，n代表时间规模，则算法的时间复杂度是 O(n^2*log2 n) （ 其中log2 n是以2为底n的对数）

ps:以上给出的是参考答案，
第一题，我觉得有问题，不能做，
第二题和第三题，我觉得都是对的
第四题，我的答案是O(n^2)
请各位牛人帮我看看是不是我的答案错了，如果是我的错了
请写出正确的答案以及过程...本人很少感激

Answer 1

题目中的答案都没错：
第一题：由分枝数，有2D+30+1（树根）=N；D为双分枝结点，N为总结点数
由数结点数有，50+30+D=N。解上面两个方程可得N=129
第二题，当树只有左子树时
第三题，小于等于
第四题，n+n^2约等于n^2。后面的乘不能忽略.本回答被网友采纳

Answer 2

第一题没问题 是你不会做

Answer 3

数据结构问题!
悬赏分：5 - 解决时间：2009-6-4 16:48
数据结构问题！
实验三：开关盒布线
一．实验目的
深入了解栈的特点及操作，以便在实际问题背景下灵活使用。
二．实验内容
1、开关盒布线问题描述
给定一个矩形布线区域，其外围有若干针脚。两个针脚之间通过布设一条金属线路而实现互连。这条线路被称为电线，被限制在矩形区域内。如果两条电线发生交叉，则会发生电流短路。所以，不允许电线间的交叉。每对互连的针脚称为网组。现要求设计一个算法来确定：对于给定的网组，能否合理地布设电线以使其不发生交叉。
2、实例及操作思路
图a 给出了一个布线的例子，其中有八个针脚和四个网组。四个网组分别是( 1 , 4 , )，( 2 , 3 )，( 5 , 6 )和( 7 , 8 )。图b 给出的布线方案有交叉现象发生（ (1,4) 和(2,3) 之间），而图c 则没有交叉现象发生。由于四个网组可以通过合理安排而不发生交叉，因此可称其为可布线开关盒。（在具体实现时，还需要在两个相邻的电线间留出一定的间隔，为使问题简化，本应用中忽略这个额外的要求）。我们要解决的问题是，给定一个开关盒布线实例，确定它是不是一个可布线的。

为了解决开关盒布线问题，我们注意到，当两个针脚互连时，其电线把布线区分成两个分区。例如，当( 1 , 4 )互连时，就得到了两个分区，一个分区包含针脚2和3，另一个分区包含针脚5~8。现在如果有一个网组，其两个针脚分别位于这两个不同的分区，那么这个网组是不可以布线的，因而整个电路也是不可布线的。如果没有这样的网组，则可以继续判断每个独立的分区是不是可布线的。为此，可以从一个分区中取出一个网组，利用该网组把这个分区又分成两个子分区，如果任一个网组的两个针脚都分布在同一个子分区之中（即不会出现两个针脚分别位于两个子分区的情形），那么这个分区就是可布线的。
为了实现上述策略，可以按顺时针或反时针方向沿着开关盒的外围进行遍历，可从任意一个针脚开始。例如，如果按顺时针方向从针脚1开始遍历图a 中的针脚，那么将依次检查针脚1, 2, ..., 8。针脚1和4属于同一个网组，那么在针脚1至针脚4之间出现的所有针脚构成了第一个分区，而在针脚4至针脚1之间出现的所有针脚构成了第二个分区。把针脚1放入堆栈，然后继续处理，直至遇到针脚4。这个过程使我们仅在处理完一个分区之后才能进入下一个分区。
下一个针脚是针脚2，它与针脚3同属一个网组，它们又把当前分区分成两个子分区。与前面的做法一样，把针脚2放入堆栈，然后继续处理直至遇到针脚3。由于针脚3与针脚2属同一个网组，而针脚2正处在栈顶，这表明已经处理完一个子分区，因此可将针脚2从栈顶删除。接下来将遇到针脚4，由于与之互连的针脚1正处在栈顶，因此当前的分区已经处理完毕，可从栈顶删除针脚1。按照这种方法继续进行下去，直至检查完八个针脚，堆栈变空，所创建的分区都已处理完毕为止。
三．实验环境
Microsoft Visual C++ 6.0
四． 测试数据
自行编写测试数据，要求两种情况（可布线和不可布线）都要进行测试。
五．实验报告要求（手写）
（1）实验目的
（2）实验内容
（3）程序代码（可打印）
（4）程序测试结果
（5）实验中遇到的问题及解决方法
（6）实验体会