首页 > 试题广场 > 对于长度为n的线性表,建立其对应的单链表的时间复杂度为()。
[单选题]

对于长度为n的线性表,建立其对应的单链表的时间复杂度为()。

  • O(1)
  • O(log2n)
  • O(n)
  • O(n^2)

7个回答

添加回答
推荐
本题答案为C。
[解析] 本题主要考查的知识点是单链表的建立。
[要点透析] 无论采用什么方式建立单链表,都需要扫描这n个元素,边扫描边创建单链表中的结点并链接起来,其时间复杂度为O(n)。
编辑于 2019-02-25 14:18:22 回复(0)
C
我们使用头插式尾插式创建链表都只需要一次循环遍历就可实现,所以时间复杂度为O(n)。


线性表是最基本、最简单、也是最常用的一种数据结构。线性表中数据元素之间的关系是一对一的关系,即除了第一个和最后一个数据元素之外,其它数据元素都是首尾相接的(注意,这句话只适用大部分线性表,而不是全部。比如,循环链表逻辑层次上也是一种线性表(存储层次上属于链式存储),但是把最后一个数据元素的尾指针指向了首位结点)。

链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构,链表比较方便插入和删除操作



编辑于 2019-02-22 15:23:11 回复(0)
选C。遍历一遍线性表,同时插入单链表中。
发表于 2019-02-22 22:16:21 回复(0)
C.一遍遍历线性表,同时插入单链表。
发表于 2019-02-22 21:41:01 回复(0)
选择C,建立单链表的方法是遍历整个线性表,因为线性表的n个元素都要遍历,所以时间复杂度是O(n)
发表于 2019-02-22 18:21:25 回复(0)
链接:https://www.nowcoder.com/questionTerminal/357fb0073b6044c2b68c99ff6c05724c?toCommentId=2565680
来源:牛客网
C
我们使用头插式尾插式创建链表都只需要一次循环遍历就可实现,所以时间复杂度为O(n)。


线性表是最基本、最简单、也是最常用的一种数据结构。线性表中数据元素之间的关系是一对一的关系,即除了第一个和最后一个数据元素之外,其它数据元素都是首尾相接的(注意,这句话只适用大部分线性表,而不是全部。比如,循环链表逻辑层次上也是一种线性表(存储层次上属于链式存储),但是把最后一个数据元素的尾指针指向了首位结点)。

链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构,链表比较方便插入和删除操作
编辑于 2019-02-22 18:39:12 回复(0)
C 建立对应的单链表,先构造一个头结点,然后重复插入动作就行,
发表于 2019-02-22 14:42:18 回复(0)

扫一扫,把题目装进口袋

牛客网,程序员必备求职神器

扫描二维码,进入QQ群

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

  • 公司地址:北京市朝阳区大屯路东金泉时代3-2708北京牛客科技有限公司
  • 联系方式:010-60728802(电话) admin@nowcoder.com
  • 牛客科技©2018 All rights reserved
  • 京ICP备14055008号-4
  • 京公网安备 11010502036488号