软件水平考试
含有n个元素的线性表采用顺序存储，等概率删除其中任一个元素，平均需要移动( )个元素。A.n B.logn C.(n-1)/2 D.(n+2)/2
题目
B.logn
C.(n-1)/2
D.(n+2)/2
参考答案和解析
在表长为n的线性表中删除一个元素时，共有n个可删除的元素。删除a1时需要移动n-1个元素，删除an时不需要移动元素，因此，等概率下删除一个元素时平均的移动元素个数Edelete为
其中，qi表示删除第i个元素(ai)的概率。
相似问题和答案
第1题：
在长度为n的顺序存储结构的线性表中，插入(或删除)一个元素，在平均情况下需要移动表中的________个元素，在最坏情况下需要移动表中的________个元素。
第2题：
给定一个有n个元素的有序线性表。若采用顺序存储结构，则在等概率的前提下，删除其中的一个元素平均需要移动(38)个元素。
A．
B．
C．
D．
解析：在表长为n的线性表中，共有n个可删除的元素。若删除第一个元素a1时，则需要将后面的n-1个元素依次前移：若删除最后一个元素an，不需要移动元素。因此，在等概率的前提下删除元素，平均需要移动的元素个数为：。
第3题：
给定一个有n个元素的有序线性表。若采用顺序存储结构，则在等概率前提下，删除其中的一个元素平均需要移动(54)个元素。
A．
B．
C．
D．1
解析：本题考查线性表在顺序存储结构下的特点。在表长为n的线性表中，共有n个可删除的元素，删除第一个元素a1时需要将后面的n-1个元素依次前移，删除最后一个元素an时不需要移动元素。因此，等概率下删除元素时平均需要移动的元素个数为：(1+2+…+n-1)/n=(n-1)/2
第4题：
对于长度为n的线性表（即n个元素构成的序列），若采用顺序存储结构（数组存储），则在等概率下，删除一个元素平均需要移动的元素数为（ ）。
A.nB.（n-1）/2C. N/2D.Log n
第5题：
给定—个有n个元素的有序线性表。若采用顺序存储结构＇则在等概率前提下，删除其中的一个元素平均需要移动 （58） 个元素。
A.A
B.B
C.C
D.D
本题考查线性表在顺序存储结构下的特点。在表长为n的线性表中，共有n个可删除的元素，删除第一个元素a，时需要将后面的n-1个元素依次前移，删除最后一个元素a。时不需要移动元素。因此，等概率下删除元素时平均需要移动的元素个数为：（1+2+…+n-1）/n=（n-1）/2。
第6题：
在等概率前提下，向一个采用顺序存储结构的n个元素线性表插入一个元素需要移动的元素个数平均为(102)。
A．n+1
B．n/2
C．(n+1)/2
D．n
解析：平均移动次数可以这样计算；n个元素的线性表共有n+1个插入的位置，从右到左依次需要移动0，1，2，3，……n次。平均移动次数=(n+1)×(n+0)/2(n+1)=n/2。
第7题：
给定一个有n个元素的线性表。若采用顺序存储结构，则在等概率前提下，向其插入一个元素需要移动的元素个数平均为(43)。
A．n+1
B．n/2
C．
D．
解析：线性表n个元素共有n+1个可能插入的位置，从左到右分别需要移动n，n-1，n-2，n-3，……，0。所以平均移动次数为(n+1)×(n+0)/2(n+1)=n/2。
第8题：
线性表L=(a1，a2,...，an)用数组表示，假定删除表中任一个元素的概率相同，则删除一个元素平均需要移动的元素个数是
A．n
B．n/2
C．log2n
D．n log2n
第9题：
对于长度为n的顺序存储的线性表，当随机插入和删除一个元素时，需平均移动【 】个元素。
n/2
第10题：
含有 n 个元素的线性表采用顺序存储 ，等概率删除其中任一个元素，平均需要移动（ ） 个元素 。
A. n B. logn C. (n-1)/2 D. (n 2)/2