【正确答案】正确答案：假设在含有n(n≥1)个关键字的序列中，i个关键字小于或等于第一个关键字，n一i一1个关键字大于或等于第一个关键字，则由此构造的二叉排序树在各记录查找概率相同的前提下，其平均查找长度为P(n，i)=1/n[1+i*(P(i)+1)+(n—i一1)(P(n一i一1)+1)] (1)其中P(k)为含有k个结点的二叉排序树的平均查找长度，则P(i)+1为查找左子树每个关键字时比较次数的平均值，P(n一i一1)+1为查找右子树每个关键字时比较次数的平均值。又假设表中关键字的排列是“随机”的，即任一关键字在序列1到n各位置上的概率相同，则对(1)式从i等于0到n一1取平均值