2. 从业资格
  3. 采用顺序表和单链表存储长度为n的线性序列，根据序号查找元素，其时间复杂度分别为（

采用顺序表和单链表存储长度为n的线性序列，根据序号查找元素，其时间复杂度分别为（

考试题库2022-08-02  72
问题 采用顺序表和单链表存储长度为n的线性序列，根据序号查找元素，其时间复杂度分别为（　　）。A.O（1）O（1）B.O（1）O（N）C.O（N）O（1）D.O（N）O（N）
选项 A.O（1）O（1）
B.O（1）O（N）
C.O（N）O（1）
D.O（N）O（N）
答案 B
解析 顺序表是在计算机内存中以数组的形式保存的线性表，是指用一组地址连续的存储单元依次存储数据元素的线性结构。顺序存储结构的主要优点是节省存储空间，因为分配给数据的存储单元全用来存放结点的数据，结点之间的逻辑关系没有占用额外的存储空间。采用这种方法时，可实现对结点的随机存取，即每一个结点对应一个序号，由该序号可以直接计算出来结点的存储地址。
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。
链表（Linkedlist）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针（Pointer）。由于不必按顺序存储，链表在插入的时候可以达到O⑴的复杂度，比另一种线性表：顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O（n）的时间，而顺序表相应的时间复杂度分别是O（n）和O⑴。
转载请注明原文地址:https://tihaiku.com/congyezige/2410085.html
本试题收录于： 中级 软件设计师题库软件水平考试初中高级分类

中级 软件设计师

软件水平考试初中高级

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