我要招人

去企业版

首页 > 试题广场 >

有序顺序表含有127个元素,向其插入一个新元素并保持原来顺序

[单选题]

有序顺序表含有127个元素，向其插入一个新元素并保持原来顺序不变，平均要移动（）个元素。

```
63.5
```
```
8
```
```
32
```
```
7
```

查看答案及解析

菜鸟葫芦娃

平均要移动63.5次；如果插在第一个位置那就要移动127个元素（即127次）；如果插在第二个位置那就要移动126个元素（即126次）；

.……

如果插在最后一个位置那不用移动移动次数为0；

就是从0~127的一个递增数列（想倒过来递减也行）；

所以平均要移动的次数N=(0+127)/2=63.5；

发表于 2015-11-27 16:58:55 回复(1)

冲鸭！冲鸭！冲鸭！

线性表按照存储方式可分为顺序表和链表。

（1）顺序表。将数据元素放到一块连续的内存空间，相邻数据元素存储地址也相邻。

1）优点：通过下标就可访问元素，因此存取效率高。

2）缺点：需预分配空间，分配多了会造成浪费，分配少了会造成“溢出”，因此空间利用率低；插入和删除元素需移动元素，因此插入删除慢。

3）时间复杂度：访问元素是O（1），插入删除元素是O（n）。

（2）链表。相邻数据元素的地址可能不相邻。每个数据元素所占存储空间分成两部分，一部分存放元素值，一部分存放元素之间的关系。

1）优点：存储空间是动态分配的，因此没有空间限制；插入和删除元素只需要改变指针指向，因此插入删除快。

2）缺点：访问元素需要从开始元素一个一个去查找访问，因此存取效率低。

3）时间复杂度：访问元素是O（n），插入元素是O（1）。

--------------------------------------------------------------------------------------------------------------------

本题解题思路：

有127个元素，插入一个新元素，插入的位置有127+1（在顺序表尾部插）=128方式

1）如果在第0个位置插入，需移动127个元素。

2）如果在第1个位置插入，需移动126个元素。

3）如果在第2个位置插入，需移动125个元素。

127）如果在第126个位置插入，需移动1个元素。

128）如果在表尾部插入，需移动0个元素。

因此平均需要移动：(0+1+2+...+127)/128 = (127*128)/2*1/128 = 63.5个元素。

发表于 2019-07-29 18:47:04 回复(1)

はくけつ

题意要保持原顺序不变的话，就只有两种情况，第一，插入在第一个位置，其余的向后移，总共127次；第二，插入到最后一个位置，其余的数不需要移动，总共0次；故而，平均移动次数为，(127+0)/2=63.5

发表于 2016-08-11 13:39:14 回复(0)

色影师จุ๊บ

发表于 2022-01-28 00:28:22 回复(0)

牛客193954号

按照一楼的思想，放在最前面需要移动127次，，，，放在最后需要移动0次，那么总的移动次数是1+2+...+127=128*127/2，总的插入的位置个数是128，所以平均移动次数为（128*127/（128*2））=63.5

发表于 2016-07-31 09:28:27 回复(0)

想做樱木的圆寸少年

我个人觉得，我们可以根据插入的位置来选择移动插入位置的左边元素或是右边，这样的话，最坏情况是在中间插入，移动64次，最好情况是两端插入。因此我觉得平均移动次数是32

发表于 2016-03-03 10:55:36 回复(4)

真的不秃

我能想到的就是：如果插在顺序表的开头，那么要移动127次，这是最多的情况；如果插在顺序表的末尾，那么不需要移动，即最少为0次。而在中间位置时，是1-126次。综上所述，可能的情况是0-127，所以平均次数63.5。

编辑于 2017-05-25 00:54:34 回复(0)

xxxxxxxxxxxxxxxa

以前算过这个127+........0/128 公式化就是(n+1)(n+0)/2n 答案是63.5 就算你公式有出入，但是算到63-64是没有问题的，答案只能选A

发表于 2018-06-14 14:26:50 回复(0)

深眸暖光

失策了，除了127

发表于 2023-05-08 15:40:34 回复(0)

不敲代码的菜鸡

插入第一个位置移动127次，插入第二个位置移动126次...依此类推，插入最后一个位置移动1次，插入到整体的后面移动0次

所以，结果为(127+126+....+1)/128 = 63.5

发表于 2021-09-04 19:20:59 回复(0)

bingjilin

所有移动的情况就是：移动 127次，126次，。。。，0次共128种情况。

平均移动的次数就是：（128*（0+127）/2）/128 = 63.5 次

发表于 2017-09-25 17:11:08 回复(0)

希望拥抱变化的西瓜

话说次数有小数？

发表于 2016-08-03 13:04:14 回复(0)

炒更

到底选哪个啊牛妹呢

发表于 2016-03-22 17:58:19 回复(0)

tonny

C 相近的一端移动数据，最大64，最小0，平均32

发表于 2015-11-26 21:51:21 回复(1)

提交观点

问题信息

复杂度

来自：迅雷2016研发工程师笔试题

上传者：SunburstRun

难度：

14条回答 159收藏 15986浏览

有序顺序表含有127个元素,向其插入一个新元素并保持原来顺序

问题信息

热门推荐

相关试题