顺序表的插人和删除要求仍然保持各个元素原来的次序。设在等概率情形下，对有127个元素的顺序表进行插人，平均需要移动多少个元素？删除一个元素，又平均需要移动多少个元素？

率时的平均搜索长度是否相同？

(1)搜索失败;

(2)搜索成功，且表中只有一个关键码等于给定值k的元素;

(3)搜索成功，且表中有若千个关键码等于给定值k的元素，要求一次搜索找出所有元素。

已知如下所示长度为12的表：（Jan，Feb，Mar，Apr，May，June，July，Aug，Sep，Oct，Nov，Dec)①试按表中元

已知如下所示长度为12的表：(Jan，Feb，Mar，Apr，May，June，July，Aug，Sep，Oct，Nov，Dec)

①试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成之后的二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。

②若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长度。

③按表中元素顺序构造一棵平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。

线性表可用顺序表或链表存储。试问：（1) 两种存储表示各有哪此主要优缺点？（2) 如果有n个表同时并

线性表可用顺序表或链表存储。试问：

(1) 两种存储表示各有哪此主要优缺点？

(2) 如果有n个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总数也可能自动改变，在此情况下，应选用哪种存储表示？为什么？

(3) 若表的总数基本稳定，且很少进行插人和删除，但要求以最快的速度存取表中的元素，这时，应采用哪种存储表示？为什么？

已知如下所示长度为12的关键字有序的表: （1)试按表中元索的顺序依次插入到一棵初始为空的二

已知如下所示长度为12的关键字有序的表:

(1)试按表中元索的顺序依次插入到一棵初始为空的二叉排序树，画出插入完成后的二叉排序树，并求其在等概宰的情况下查找成功的平均查找长度。

(2)若对表中元素先进行排序构成有序表，求在等概率的情况下查找成功的平均查找长度。

(3)按表中元素的顺序构造一棵平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。

对长度为3的顺序表做顺序搜索，若搜索第1个元素的概率是1/2，搜索第2个元素的概率是1/3，搜索第3个元素的概率是1/6，则搜索任一元素的平均搜索长度为（)。

A、5/3

B、2

C、7/3

D、3

设在有序顺序表中搜索x的过程为：首先用x与表中的第4i（i=0，1，…)个元素做比较，如果相等，则搜索

成功;否则确定下一步搜索的区间为4(i-1)+1到4i-1.然后在此区间内与第4i-2个元素作比较，若相等则搜索成功，否则继续与第4i-3或4i-1个元索进行比较，直到搜索成功。

(1)给出实现算法。

(2)试面出当表长n=16时的判定树，并推导此搜索方法的平均搜索长度(考虑搜索元素等概率和n%4=0的情况)。

每次从无序表中取出一个元素，把它插人到有序表中的适当位置，此种排序方法讯做（①)排序;每次从无

序表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种排序方法叫做(②)排序。

设在一个带附加头结点的单链表中所有元素结点的数据值按递增顺序排,试编写一个函数,删除表中所有大丁min,小于max的元素（若存在) 。

对于顺序存储的线性表，其算法的时间复杂度为Q（1)的运算应是（)。

A、将n个元素从小到大排序

B、从线性表中删除第i个元素(1≤i≤n)

C、查找第i个元素(1≤i≤n)

D、在第i个元素(1≤i≤n)后插人一个新元素