在一棵表示有序集S的二又搜索树中，任意一条从根到叶结点的路径将S分为3部分：在该路径左边结点

中搜索一个元素X，返回的结果有两种情形，(1)在二叉搜索树的内结点中找到X=Xi，其概率为bi。(2)在二叉搜索树的叶结点中确定X∈(Xi，Xi+1)，其概率为ai。在表示S的二叉搜索树T中，设存储元素Xi的结点深度为Ci;叶结点(Xi，Xi+1)的结点深度为di，则二叉搜索树T的平均路长p为多少？假设二叉搜索树T[i][j]={Xi，Xi+1，···，Xj｝最优值为m[i][j]，W[i][j]= ai-1+bi+···+bj+aj，则m[i][j](1＜=i＜=j＜=n)递归关系表达式为什么？

一棵二又树第六层(根结点为第-层)的结点数最多为________个。

以下关于二叉排序树(或二叉查找树、二叉搜索树)的叙述中，正确的是()

A.对二叉排序树进行先序、中序和后序遍历，都得到结点关键字的有序序列

B.含有N个结点的二叉排序树高度为【log2n】+1

C.从根到任意二个叶子结点的路径上，结点的关键字呈现有序排列的特点

D.从左到右排列同层次的结点，’其关键字呈现有序排列的特点

由分别带权为9，2，5，7的4个叶结点构造一棵哈夫曼树，该树的带权路径长度为(44)。

A．32

B．36

C．44

D．50

编写一个递归算法，在一棵有n个结点的随机建立起来的二叉搜索树上搜索第k（1≤k≤n)小的元素，并返

回指向该结点的指针。要求算法的平均时间复杂度为O(log2n)。二叉搜索树的每个结点中除data、ieftChild、rightChild等数据成员外、增加一个count成员，保存以该结点为根的子树上的结点个数。

利用3、6、8、12这4个值作为叶结点的权值生成一棵Huffman树，该树的带权路径长度为(50)。

A．55

B．29

C．58

D．38

树插入一个元素时，若树中已存在与该元素的关键码柑同的结点，则就使该结点的count域增1，否则就由该元素生成一个新结点而插入到树中，并使其count域置为1，试按照这种插入要求编写一个算法。

最优二叉树（IIuffman树)和最优二叉搜索树均为平均搜索路径长度为最小的树，其中对最优二叉树。n

最优二叉树(IIuffman树)和最优二叉搜索树均为平均搜索路径长度为最小的树，其中对最优二叉树。n表示(①)，对最优二叉搜索树，n表示(②)，构造这两种树均(③)，

A、结点数

B、叶结点数

C、非叶结点数

D、度为2的结点数