采用递归调用的算法编写一个计算x的n次方的函数（不用写主函数调用)。

编写一个递归算法，从大到小输出二叉搜索树中所有值不小于x的关键码。要求算法的时间复杂度为O（log₂n+m)，n为树中结点数，m为输出的关键码个数。

计算多项式Pn（x) –a₀xⁿ十a₁x^n-1+a₂x^n-2+…+a_n-1x十an⊕

计算多项式Pn(x) –a₀xⁿ十a₁x^n-1+a₂x^n-2+…+a_n-1x十aⁿ的值， 通常使用的方法是一种嵌套的方法。它可以描述为如下迭代形式：bv=av,b_i+1=x×b_i+a_i+1， i=0， 1，…，n-l。若设b_n=P_n(x) ， 则问题可以写为如下形式：Pn(x) =x×P_n-1(x)+a_n， 此处， Pn-i(x) =a_vx^n-1+a₁x^n-2+…+a_n-2x+a_n-1， 这是问题的递归形式。试编写一个函数， 计算这样的多项式的值。

A.递归是将一个规模较大的问题分解为若干个规模较小的子问题

B.递归算法中拆分出来的子问题可以与原问题不同

C.递归函数至少要有一个出口，也就是判断结束调用的条件来结束递归体

D.递归算法按照先递推再回归的过程执行

有中序线索树T，结点形式为：(LL，LT, D，RT,RL)，试编写非递归算法找到数据域为A的结点，并在其左子树中插入值为Q的已知新结点X：

注意：可能A有左孩子或无左孩子，插入后考虑线索的状态应作何修改。【上海大学1998六(1 7分)】

设一棵二叉树以二叉链表表示，试以成员函数形式编写有关二叉树的递归算法：（1)统计二叉树中度为

1的结点个数。

(2)统计二叉树中度为2的结点个数。

(3)统计二叉树中度为0(叶结点)的结点个数。

(4)统计二叉树的深度。

(5)统计二叉树的宽度，即在二叉树的各层上，具有结点数最多的那一层上结点总数。

(6)从二叉树中删去所有叶结点。

(7)计算二叉树中指定结点*p所在层次。

(8)计算二叉树中各结点中的最大元素的值。

(9)以前序次序输出一棵二叉树所有结点的数据值及结点所在的层次。