题目内容
（请给出正确答案）
以查阅英文字典为例，单词“Data”应大致位于前1/5和1/4之间，而“Structure”则应大致位于后1/5和1/4之间。对元素的分布规律掌握得越准确，这种加速效果也就加可观。
此类方法的原理大同小异，无非是利用向量元素的分布规律，根据目标数值，通过插值估计出其大致所对应的秩，从而迅速缩小搜索范围，故称作插值查找(interpolation search)。
a)若有序向量中的元素均独立且等概率地取自某一数值区间，试证明它们应大致按线性规律分布;
b)针对此类有序向量，如何通过插值来估计待查找元素的秩？试给出具体的计算公式;
c)试证明：对于此类向量，每经一次插值和比较，待搜索区间的宽度大致以平方根的速度递减;
d)试证明：对于长度为n的此类向量，插值查找的期望运行时间为o(loglogn);
如果结果不匹配，请 联系老师 获取答案
更多“在实际应用中，有序向量内的元素不仅单调排列，而且往往还服从某…”相关的问题
a)试按照以上思路，实现一个排序算法：
b)你的这一算法，时间和空间复杂度各是多少？
c)改进你的算法，使之能够在O(n+M)时间内对来自[0，M)范围内的n个整数进行排序，且使用的辅助空间不超过O(M)。
令V是实数域R上一个三维向量空间，σ是V的一个线性变换。它关于V的某一个基的矩阵是
(i)求出σ的最小多项式p(x)，并把p(x)在R[x]内分解为两个最高次项系数是1的不可约多项式p1(x)与p2(x)的乘积;
(ii)令Wi={ξ∈V|pi(σ)ξ=0}，i=1，2。证明，Wi是σ的不变子空间，并且V=W1⊕W2;
(iii)在每一子空间Wi中选取一个基，凑成V的一个基，使得σ关于这个基的矩阵里只出现三个非零元素。
有序表时，为寻找插入位置，元素间需比较()次。(按升序排序)
A.所有实现都是有序集合，集合内元素不能重复
B.所有实现都是有序集合，集合内元素可以重复
C.所有实现都是无序集合，集合元素可以重复
D.所有实现都是无序集合，集合元素不能重复
A、数组元素个数必须小于100
B、数组元素个数必须大于10
C、数组中要查找的元素排列在数组的中间位置
D、数组元素是有序排列
已知如下所示长度为12的关键字有序的表:
(1)试按表中元索的顺序依次插入到一棵初始为空的二叉排序树，画出插入完成后的二叉排序树，并求其在等概宰的情况下查找成功的平均查找长度。
(2)若对表中元素先进行排序构成有序表，求在等概率的情况下查找成功的平均查找长度。
(3)按表中元素的顺序构造一棵平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。
已知如下所示长度为12的表：(Jan，Feb，Mar，Apr，May，June，July，Aug，Sep，Oct，Nov，Dec)
①试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成之后的二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。
②若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长度。
③按表中元素顺序构造一棵平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。
