数据结构（宁夏大学） 第二章_智慧树知到答案2021年

第二章 线性表：线性表是最简单且最常用的一种数据结构。线性结构的特点是，在数据元素的非空有限集合中，除第一元素无直接前驱、最后一个元素无直接后继外，其余每个数据元素均有唯一的直接前驱和唯一的直接后继。本章将介绍线性表的概念，给出线性表顺序存储结构与链式存储结构两种存储结构，并进一步讨论在相应存储结构上实现线性表的基本运算。2.1线性表的基本概念及运算:本节中介绍了线性表的概念，线性表中所有元素的排列呈线性关系，除了唯一的开始和结束结点之外，每个结点都有唯一的前趋和后继结点。线性表有初始化、求长度、插入、删除、按序号查找、按值查找6个基本运算。
2.2线性表的顺序存储:顺序表的插入首先要考虑空间上溢的问题，如果有空间允许插入，必须保证插入新元素后依然是一个顺序表。顺序表的删除，必须保证删除元素后依然是一个顺序表，所以如何实现批量移动是本节重点讲述的内容。
2.3线性表:由于顺序表的插入和删除都需要批量移动元素，所以链表存储的插入和删除更为高效，本节重点讲解。单链表有头插法和尾插法两种创建的方式，本节将分别介绍这两种方法，并进行了时间复杂度的分析。单链表虽然实现了空间申请的自由，无须进行预分配，但是由于地址不连续，所以查找只能是从头开始的顺序比对查找。顺序表的插入和删除都需要批量移动表中近一半的元素，本节通过对单链表多个算法的分析、改进，实现了链表的插入和删除的时间复杂度为O(1)，提高了程序效率。链表的设计比较灵活，可以根据应用的需要，设计出合适的数据存储结构，以提高程序的运行效率，本节所讨论的循环链表和双链表就是这样的结构。
2.4顺序表和链表的比较:计算机中数据存储本质就是地址连续与否，所以存储结构对应就有顺序存储和链式存储这两大类，本节针对线性表的这两种存储进行了对比分析。

[判断题]

对链表进行插入和删除操作时不必移动链表中结点。

选项:[对, 错]
[判断题]

已知指针P指向键表L中的某结点，执行语句P=P->next不会删除该链表中的结点。

选项:[对, 错]
[判断题]线性表的唯一存储形式是链表。

选项:[对, 错]
[单选题]线性表采用链式存储时，结点的存储地址（  ）。

选项:[连续与否均可 , 必须是连续的 , 和头结点的存储地址相连续, 必须是不连续的]
[单选题]设带有头结点的单向循环链表的头指针变量为head，则其判空条件是（  ）。

选项:[head->next==head, head->next== NULL, head==NULL, head!= NULL]
[单选题]在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q所指结点和p所指结点之间插入s结点，则执行（  ）。

选项:[p->link=s->link;s->link=p, s->link=p->link;p->link=s, q->link=s;s->link=p, p->link=s;s->link=q]
[单选题]顺序查找不论在顺序线性表中还是在链式线性表中的时间复杂度为（  ）。

选项:[O(n²), O(n), O(n^1/2), O(1og₂n)]
[单选题]下面关于线性表的叙述错误的是（   ）。

选项:[线性表采用链式存储不必占用一片连续的存储空间, 线性表采用顺序存储必须占用一片连续的存储空间, 线性表采用链式存储便于插入和删除操作的实现, 线性表采用顺序存储便于插入和删除操作的实现]
[单选题]设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（  ）。

选项:[O(nlog₂n), O(n²), O(1), O(n)]
[单选题]若某链表最常用的操作是在最后一个结点之后插入一个结点删除最后一个结点，则采用（  ）存储方式最节省时间。

选项:[单循环链表, 带头结点的双循环链表, 单链表, 双链表]
[单选题]线性表是具有n个（  ）的有限序列（n≠0）。

选项:[数据项, 表元素, 数据元素　, 字符]
[单选题]在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行（  ）。

选项:[p->next=s;s->next=p, s->next=p->next;p->next=s, s->next=p;p->next=s, s->next=p->next;p=s]
[单选题]顺序存储的线性表（a₀,a₁,…,a_n-1）,在任一结点前插入一个新结点时所需移动结点的平均次数为（  ）。

选项:[n, n+1, n/2, (n+1)/2]
[单选题]若线性表最常用的操作是存取第i个元素及其前趋的值，则采用（  ）存储方式节省时间。

选项:[单循环链表, 顺序表, 单链表, 双链表  ]
[单选题]在一个单链表中，若删除p所指结点的后续结点，则执行（  ）。

选项:[p =p->next->next;, p->next=p->next->next, p->next=p->next, p=p->next; p->next=p->next->next]