2.5 KiB
线性表习题
基本概念
例题 以下()是一个线性表。
$A.$由$n$个实数组成的集合
$B.$由$100$个字符组成的序列
$C.$所有整数组成的序列
$D.$邻接表
解：$B$。线性表定义的要求为：相同数据类型、有限序列。选项$C$的元素个数是无穷个，错误；选项$A$集合中的元素没有前后驱关系，错误；选项$D$属于存储结构，线性表是一种逻辑结构，不要将二者混为一谈。只有选项$B$符合线性表定义的要求。
顺序表
例题 设线性表有$n$个元素，严格说来，以下操作中，()在顺序表上实现要比在链表上实现的效率高。
Ⅰ.输出第$i$（$1\leqslant i\leqslant n$）个元素值。
Ⅱ.交换第$3$个元素与第$4$个元素的值
Ⅲ.顺序输出这$n$个元素的值
$A.$Ⅰ
$B.$Ⅰ、Ⅲ
$C.$Ⅰ、Ⅱ
$D.$Ⅱ、Ⅲ
解：$C$。对于Ⅱ，顺序表仅需$3$次交换操作；链表则需要分别找到两个结点前驱，第$4$个结点断链后再插入到第$2$个结点后，效率较低。对于Ⅲ，需依次顺序访问每个元素，时间复杂度相同。
链表
结构选择
例题 一个链表最常用的操作是在末尾插入结点和删除结点，则选用()最节省时间。
$A.$带头结点的双循环链表
$B.$单循环链表
$C.$带尾指针的单循环链表
$D.$单链表
解：$A$。首先分析要求。末尾删除和插入结点，则需要对尾部操作。$B$是循环链表，但是方向是头结点到尾部，如果操作尾部需要$O(n)$的时间。$C$带了尾指针，所以可以对尾指针直接插入元素，但是不能删除尾指针所指向的最后一个元素，因为是单链表，所以不能找到尾指针的前驱。$D$单链表只能从头开始找，所以不合适。对于$A$。虽然它是带头结点，但是是循环链表，所以头节点的前驱就是尾结点，且是双链表，所以可以向前。若是删除尾结点直接删除头节点的前驱，同理插入尾节点，直接对头节点的前驱操作。
链表逻辑
例题 某线性表用带头结点的循环单链表存储，头指针为head，当 head->next->next=head成立时，线性表长度可能是()。
A.0
B.1
C.2
$D.$可能为$0$或1
解：$D$。这个题目很容易就会选择$B$。对于$B$，若是有一个元素，则$head->next$就指向该元素，该元素后面没有了，就指向头节点从而head->next->next=head。若元素有$0$个，则head->next=head，则head->next->next=head->next=head，所以也成立。