2. 计算机
  3. 以下关于线性表存储结构的叙述，正确的是(57)。

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

admin2017-09-14  50
问题 以下关于线性表存储结构的叙述，正确的是(57)。
选项 A、线性表采用顺序存储结构时，访问表中任意一个指定序号元素的时间复杂度为常量级
B、线性表采用顺序存储结构时，在表中任意位置插入新元素的运算时间复杂度为常量级
C、线性表采用链式存储结构时，访问表中任意一个指定序号元素的时间复杂度为常量级
D、线性表采用链式存储结构时，在表中任意位置插入新元素的运算时间复杂度为常量级
答案A
解析 本题考查数据结构基础知识。线性表进行顺序存储时，逻辑上相邻的元素，其物理位置也相邻，因此在已知第一个元素存储位置和元素序号的情况下，可计算出表中任意指定序号元素的存储位置，即按照序号访问元素时随机的，该运算的时间复杂度为O(1)，也就是常量级。而插入元素时就需要移动一些元素了，在最坏情况下要移动表中的所有元素，因此该运算的时间复杂度为O(n)，其中n为线性表的长度。线性表进行链式存储时，逻辑上相邻的元素，其物理位置不要求相邻，因此需要额外的存储空间表示元素之间的顺序关系。在链表上查找元素和插入元素的运算时间复杂度都为O(n)。
转载请注明原文地址:https://kaotiyun.com/show/iARZ777K
本试题收录于： 软件设计师上午基础知识考试题库软考中级分类
0

软件设计师上午基础知识考试

软考中级

相关试题推荐
随机试题
最新回复(0)