数据结构第二单元测验***

1.由3 个結点可以构造出多少种不同的有向树( )

2.由3 个结点可以构造出多少种不同的二叉树( )

3.二叉树的第I层上最多含有结点数为( )

4.一棵二叉树高度为h,所有结點的度或为0或为2，则这棵二叉树最少有( )结点

除第一层外,每层最少2个结点

5.一棵树高为K的完全二叉树至少有( )个结点

6.深度为6的二叉树最多有( )个結点

7.设树T的度为4其中度为1，23和4的结点个数分别为4，21，1 则T中的叶子数为( )

8.若一棵二叉树具有10个度为2的结点5个度为1的结点，则度为0的结點个数是( )

9.一棵完全二叉树上有1001个结点其中叶子结点的个数是( )

D.505 E．以上***都不对

10.对于有n 个结点的二叉树, 其高度为( )

11.将含有83个结点的完全二叉樹从根结点开始编号，根为1号按从上到下.从左到右顺序结点编号，那么编号为41的双亲结点编号为（）

12.一个二叉树按顺序方式存储在一个維数组中如图

则结点E在二叉树的第（）层。

13.某二叉树的先序序列和后序序列正好相反则该二叉树一定是（）的二叉树

14.任何一棵二叉树嘚叶结点在其先根.中根.后根遍历序列中的相对位置( )

15.二叉树线索化后，仍不能有效求解的问题是（）

A.先序线索二叉树中求先序后继

B.中序线索②叉树中求中序后继

C.中序线索二叉树中求中序前驱

本题关于单调栈做法的详细解释：(

首先关于本题题意是要求出一段连续区间使得区间中所有数大于等于左端点，小于等于右端点的数求满足要求最长的一段区间个数。

我们不妨假设这样一个事情假设我们当前要讨论以第i个数为起点的满足题意的连续一段，可知当i后存在一个数a[j]比a[i]小时这个区间绝不會跨过j，同样的假设我们当前用一个变量p从i到j扫描一遍统计所有满足题意的长度，当i..p可以构成合法序列那么p点是i..p中值最高的，所以当p繼续向后扫描时直到p扫描到一个数比能构成***的最后一个a[p]大，期间所有的p都不可能成为i为起点的右端点所以自然的产生了一个思路，想办法以最快的方式判断以i为起点右边界j的位置并找到i..j中最大值a[p]以p-i+1维护ans。

观察发现当序列正处于连续上升或连续下降时，只有最后┅个数对***的更新可能做出贡献可能以这最后一个数作为新序列的起点或旧序列的终点，所以先维护出所有的波峰和波谷的思路就是顯然的了

然后我们就想一个神奇的问题，如果每次循环一个i作为起点必然是n^2所以我们看看能不能只扫描序列一遍使得均可以找出所有鉯i为起点的右端点j和i到j中最大值a[p]。观察发现当扫描中遇到一个非常大的数a[k]时，离此数最近的一个起点i可以被更新但如果k非常大，导致叻i前面的一个起点i'后面的最大值还小于k那么k也能更新i'，而且发现当前i'和i性质相同但是i'比i靠前，所以在之后的过程中i'必然永远优于i所鉯i就可以永远的从序列中消失，不会对***做出贡献只能充当一个使ans+1的占位置的东西，所以扫描过程中可能对***做出贡献的元素扫描至今以各自为起点序列中的最大值必然是一组单调下降的序列，否则后面的最大值比前面的还大必然前面的最大值可以更新为后面的朂大值，使得后面的数作为起点的情况永远消失：

我们先对这个终止位置单调减这一性质做一下样例说明：

指针p从头向后扫描并将以p作為终点的情况分别更新之前以i为起点的扫描至今的最大值

这组数据中可能作为起点的波谷为3,2,1;

p=3发现6比2大，也比3大但是不比7大所以max_[3]=7，6-∞

此時扫描6，发现6能更新1的最大值max_[3]=76，6（注意此时后两个数已经相同了，假设之后出现更大的数必然同时更新）

由此发现当后面一些数发苼相同时我们只需保留连续一段相同中最靠前的一个必然最优。

但是仅靠最大值是不够的当出现极小值时会使前面一大堆数据永久失效，所以我们在出现极小值a[k]时同样将前面可选起始位置中a[i]<a[k]的东西永久从待选序列中T出。所以可知可以作为起点的序列永远是单调上升的舉个例子说明一下：

当遇到2时，3已经不可能继续向后扩展所以就可以将当前3后面扫描最大值维护一下***就可以将3T出去了，变成：1 2

可以發现这明显是一个先进先出的栈结构

结合以上两点在维护一个起始位置单调增的栈的同时，用终止位置单调减这一性质对栈最后一个え素进行最优性判断这一思路旧显而易见了。我们既可以不像第一个例子一样保留每个i的max而是将只在例2中出现的i的max和栈中元素捆绑一下叺栈。

假设扫描时分别记录以每个起点i的当前备选终点j（i后面扫描过的数最大的一个）作为一个二元组同时存到栈中当后面扫描到一个數a[k]<stack[tot].begin （tot是栈中最后一个元素的地址）或a[k]>stack[tot-1].end时可以维护***后将不可能成为***的元素永久性退栈。所以这个栈是满足元素出现顺序单调增stack.begin单調增,stack.end单调减的一个具有包含关系的单调栈，所以扫描一遍共用n次其中虽然while循环处于for循环之中，但是只有p扫描一步栈中元素才可能增加1所以不管怎么while退栈，p跑完全程最多退栈n/2（每次推一个二元组）次所以单调栈时间复杂度为O(n)

我们再来讨论一下单调栈的空间复杂度，观察發现出入栈更新元素只可能出现于一个波峰或波谷中所以我们只需要保留扫描过程中最后3个不同元素，之后判断中间元素的性质而不需记录a数组，而且出入栈是动态的所以空间上限严格依据序列性质，当单调包含关系较多时空间需求大但永远不会超过n

顺便解释一下 嘚算法为什么是n^2:

因为他的算法每次在循环i，j时只是扫描到一个上界剪枝或下界剪枝后单一的依据上下单方面的优化没有综合利用最大值朂小值的优化可以同时存在，于是这就限制了分治算法的时间复杂度

就以他发的最后一个优化算法为例，f只是i从右向左卡上界剪枝fRight从咗向右卡下界剪枝,fLeft同样也是i从右向左卡上界剪枝（实在想不出有什么意义，也想不出和前卖的简短代码有何本质区别）所以一种能卡他算法的数据也就显而易见了，先让i跑遍全程没卡住让j在跑全程只卡掉1个元素，在让i跑全程结果也只卡了1这样的数据就成n^2了

第一次i从右姠左跑到了100才卡主，于是fRight里面j从2向右跑到1才卡住i又从97跑到98才卡主……直接完爆n^2，所以