在具有n个元素的顺序存储结构的线性表任意一个位置中删除一个元素,

题目

在具有n个元素的顺序存储结构的线性表任意一个位置中删除一个元素,在等概率条件下,平均需要移动()个元素。

如果没有搜索结果或未解决您的问题,请直接 联系老师 获取答案。
相似问题和答案

第1题:

将长度为n的顺序存储在线性表中删除一个元素,最坏情况下需要移动表中的元素个数为()。


正确答案:

n-1在顺序表中删除一个元素,最坏情况是删除第一个元素,后面的(n-1)个元素均要向前移动,所以此处填n-1。

第2题:

顺序存储的线性表中有N个元素,若向线性表中任意位置插入一个元素的概率相同,则插入一个元素平均需要移动的元素的个数是,(38)。

A.N/2

B.1og2N

C.N

D.N(N-1)/2


正确答案:A
解析:本题考查线性表的插入。线性表是最简单和最常用的一种数据结构,是由相同类型的结点组成的有限序列。线性表常用的存储方式有顺序存储和链接存储。线性表的顺序存储是将线性表的结点依次存储在数组中,用数组元素的顺序存储来体现线性表中结点的先后次序关系。在对顺序存储的线性表进行插入时,完成插入主要有以下步骤:(1)检测插入要求的有关参数的合理性;(2)把原来的第n-1个结点至第i个结点依次往后移一个数组元素位置;(3)把新结点放在第i个位置上,修改线性表的结点个数。在具有N个结点的线性表上插入新结点时,其时间主要花费在移动结点的循环上。若插入任一位置的概率相等,从后往前依次需要移动的次数为0,1,2,…,n,所以,平均移动次数为n/2。

第3题:

给定一个有n个元素的有序线性表。若采用顺序存储结构,则在等概率前提下,删除其中的一个元素平均需要移动(54)个元素。

A.

B.

C.

D.1


正确答案:C
解析:本题考查线性表在顺序存储结构下的特点。在表长为n的线性表中,共有n个可删除的元素,删除第一个元素a1时需要将后面的n-1个元素依次前移,删除最后一个元素an时不需要移动元素。因此,等概率下删除元素时平均需要移动的元素个数为:(1+2+…+n-1)/n=(n-1)/2

第4题:

对于长度为n的顺序存储的线性表,当随机插入和删除一个元素时,需平均移动【 】个元素。


正确答案:n/2
n/2

第5题:

在长度为n的顺序存储的线性表中删除一个元素,最坏情况下需要移动表中的元素个数为【 1 】。


正确答案:
【答案】:n-1
【知识点】:线性表中元素的删除
【解析】:在顺序存储线性表中删除一个元素,实际就是让后面的元素向前移动,在长度为n的顺序存储线性表中删除一个元素,最坏情况下需要移动表中n-1个元素。

第6题:

在一个长度为n的顺序存储结构的线性表中,向第i个元素(1≤i≤n+1)位置插入一个元素时,需要从后向前依次后移()个元素。

A、n-i

B、n-i+l

C、n-i-l

D、i


参考答案:B

第7题:

给定一个有n个元素的有序线性表。若采用顺序存储结构,则在等概率的前提下,删除其中的一个元素平均需要移动(38)个元素。

A.

B.

C.

D.


正确答案:D
解析:在表长为n的线性表中,共有n个可删除的元素。若删除第一个元素a1时,则需要将后面的n-1个元素依次前移:若删除最后一个元素an,不需要移动元素。因此,在等概率的前提下删除元素,平均需要移动的元素个数为:。

第8题:

在长度为n的顺序存储结构的线性表中,插入(或删除)一个元素,在平均情况下需要移动表中的________个元素,在最坏情况下需要移动表中的________个元素。


正确答案:
n/2 n

第9题:

以下关于线性表存储结构的叙述,正确的是(57)。

A.线性表采用顺序存储结构时,访问表中任意一个指定序号元素的时间复杂度为常量级

B.线性表采用顺序存储结构时,在表中任意位置插入新元素的运算时间复杂度为常量级

C.线性表采用链式存储结构时,访问表中任意一个指定序号元素的时间复杂度为常量级

D.线性表采用链式存储结构时,在表中任意位置插入新元素的运算时间复杂度为常量级


正确答案:A
线性表采用顺序存储结构时,访问表中任意一个指定序号元素的时间复杂度为常量级,因为顺序存储结构访问元素时,能直接定位元素,这样,操作的时间复杂度为O(1)。

第10题:

对具有n个元素的顺序表(采用顺序存储的线性表)进行( ) 操作,其耗时与n的大小无关。

A.在第i(1≤i≤n)个元素之后插入一个新元素

B.删除第i(1≤i≤n)个元素

C.对顺序表中的元素进行排序

D.访问第i(1≤i≤n)个元素的前驱和后继


正确答案:D
解析:线性表是随机读取的,所以参看某个元素与n无关。【总结与扩展】顺序表是在计算机内存中以数组的形式保存的线性表,是指用一组地址连续的存储单元依次存储数据元素的线性结构。线性表采用顺序存储的方式存储就称之为顺序表。顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。将表中元素一个接一个地存入一组连续的存储单元中,这种存储结构是顺序结构。采用顺序存储结构的线性表简称为“顺序表”。顺序表的存储特点是:只要确定了起始位置,表中任一元素的地址都通过下列公式得到:L0c(ai)=LOC(ai)+(i-1)*L(1≤i≤n),其中,L是元素占用存储单元的长度。

更多相关问题