设线性表有n个元素,以下操作中,( )在顺序表上实现比链表上实现效率更高。

admin2019-12-10  24

问题 设线性表有n个元素,以下操作中,(    )在顺序表上实现比链表上实现效率更高。

选项 A、输出第i(1≤i≤n)个元素值
B、交换第1个元素与第2个元素的值
C、顺序输出这n个元素的值
D、输出与给定值x相等的元素在线性表中的序号

答案A

解析  顺序表支持随机存储,链表不支持,因此顺序表输出第i个元素的值的时间复杂度为O(1),链表则为O(n),因此A正确。
   交换第1个与第2个元素的值,对于顺序表和链表,时间复杂度均为O(1),因此B不对。
    输出n个元素的值,两者时间复杂度均为O(n),因此C不对。
    输出与给定值x相等的元素在线性表中的序号,对于顺序表和链表,count需要搜索整个表,因此时问复杂度为O(n),因此D不对。
  【注】有的同学认为B也是正确的,其实严格来说B确实是对的,因为线性表交换要执行3次操作:
    temp=a[1];
    a[1]=a[2];
    a[2]=temp;
    而链表要执行5次:
    p=head->next;
    q=head->next->next;
    temp=p->data;
    p->data=q->data;
    q->data=temp,
    但本题是单选题的时候,考生需要选择更准确的一项,显然与B项相比,A项更准确。
转载请注明原文地址:https://kaotiyun.com/show/Lh3i777K
0

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