首页 > 试题广场 >

在包含1000个元素的线性表中实现如下各运算,所需执行时间最

[单选题]
在包含1000个元素的线性表中实现如下各运算,所需执行时间最长的是( ) 
  • 线性表按顺序方式存储，删除线性表的第900个结点
  • 线性表按链式方式存储，删除指针P所指向的结点
  • 线性表按顺序方式存储，在线性表的第100个结点后面插入一个新结点
  • 线性表按链式方式存储，在线性表的第100个结点后面插入一个新结点
添加回答
白驹之过隙头像 白驹之过隙
选C。
含有有限的数据序列，我们就称之为线性表。
线性表的两种表现形式：
  • 顺序存储，用一组连续的存储单元依次存储数据元素，适用于随机存取的操作。
  • 链表存储，用一组任意存储单元通过数据域和指针域来存储元素，适用于对线性表的增删操作。
根据选项中的增删操作排除BD选项，因为顺序存储方式的增删操作更耗时。
  • A选项删除第900个结点，需要后100个节点依次向前移动
  • C选项第100个结点后面插入一个新结点，需要后900个节点依次向后移动（更耗时）
发表于 2019-12-13 19:19:33 回复(1)
更多回答
推荐
Jino.头像 Jino.
选C。
先看A和C项：
由于线性表采用的是顺序存储方式，用存储单元的邻接性体现线性表元素间的一维顺序关系，因此对线性表进行插入和删除运算时，可能需要移动大量的结点，以保持这种物理和逻辑的一致性。
对于选项A,删除线性表的第900个结点,后面的100个结点都要往前移动;
对于选项C,第100个结点后面插入一个新结点,后面的900个结点都要往后移动。
再看B和D项：
对于线性表按链接方式存储，当进行插入与删除操作时，只改变相应的指针即可。比顺序存储方式速度更快。
即B和D选项的执行时间较少。
所以比较4个选项的操作可易知，选项C所需要的执行时间最长。
编辑于 2019-12-16 14:15:57 回复(0)
努力的牛牛头像 努力的牛牛
答案：选C
解析：
A：需要将线性表的最后100个结点向前移动一个结点。
B：删除p指向的结点，只需做下面几步：
  • 1：p->val = p->next->val
  • 2：p->next = p->next->next
C：需要将线性表的最后900个结点向后移动一个结点
D：需要先循环遍历找到第100个结点，再将结点插入
综上所述：所用时间C>D>A>B
发表于 2019-12-14 19:04:05 回复(0)
安苒_头像 安苒_
查找的时间和删除的时间并不一样
发表于 2022-11-14 16:10:27 回复(0)
你的offer对我打了烊头像 你的offer对我打了烊
既然都是增加和删除元素，首先排除链表，因为它不用移动后面的每个元素，然后A选项删除第900个，只需要移动后面的100个元素，但是D选项需要移动900个元素，肯定更加耗时
发表于 2020-04-03 10:29:22 回复(1)
提交观点

问题信息

链表
上传者：zsw3
难度：
5条回答 2911浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号