数据结构与算法（仲恺农业工程学院）第二章测试_智慧树知到答案2021年

第二章 线性表：一、线性表的逻辑结构和线性表的基本概念 二、顺序表、链式表及静态链表的描述方法、特点及其相关概念 三、顺序表和链式表的基本操作的算法实现 四、从时间和空间的角度综合比较顺序表和链式表的不同特点及其使用场合 线性表是最简单也是最基本的一种线性数据结构。它有两种存储表示方法：顺序表和链式表，其基本操作是插入、删除和查找。2.1线性表的类型定义:线性表的定义与抽象数据类型描述
2.2线性表的顺序存储结构:线性表的顺序存储表示、基本运算及其实现
2.3线性表的链式存储结构:线性表的链式存储表示、基本运算及其在单链表中的实现，循环链表、双向链表、静态链表的概念、运算及其实现。

[单选题]线性表是（）。
一个有限序列，不可以为空
一个无限序列，可以为空
一个有限序列，可以为空
一个元限序列，不可以为空
答案：一个有限序列，可以为空
[单选题]在一个长度为n的顺序表中于第i个元素(1≤i≤n+1)之前插入一个新元素，需要向后移动（）个元素。
n-i
n-i+1
i
n-i-1
答案：n-i+1
[单选题]链表不具有的特点是（）。
插入删除不需要移动元素
所需空间与线性表长度成正比
不必事先估计存储空间
可随机访问任一元素
答案：链表不具有的特点是（）。
[单选题]线性表采用链式存储结构时，各节点之间的地址（）。
连续与否均可以
必须是连续的
一定是不连续的
答案：连续与否均可以
[单选题]若线性表最常用的运算是存取第i个元素及其前驱的值，则采用（）存储方式最节省时间。
循环单链表
单链表
双链表
顺序表
答案：顺序表
[单选题]对于用一维数组d[0..n-1]顺序存储的线性表，其算法的时间复杂度为O(1)的操作是（）。
在线性表中第i个元素之后插入一个元素
将n个元素从小到大排序
查找第i个元素(1≤i≤n)
从线性表中删除第i个元素(1≤i≤n)
答案：查找第i个元素(1≤i≤n)
[单选题]在单链表中，若*p节点不是尾节点，在其后插入*s节点的操作是（）。
s->next=p->next;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->next = s;
[单选题]在一个单链表中，删除*p节点(非尾节点)之后的一个节点的操作是（）。
p->next->next=p
p->next =p
p->next->next=p->next
p->next=p->next->next
答案：p->next = p->next->next
[单选题]在一个双链表中，在*p节点(非尾节点)之后插入一个节点*s的操作是（）。
s->prior=p;p->next=s; p->next->prior=s;s->next=p->next;
p->next=s;s->prior=p;s->next=p->next; p->next->prior=s;
s->next=p->next;p->next->prior=s;p->next=s;s->prior=p;
p->prior=s; s->next=p; s->next->prior=p; p->next=s->next;
答案：s->next = p->next; p->next->prior = s; p->next = s; s->prior = p;
[单选题]在一个双链表中，删除*p节点(非尾节点)之后的一个节点的操作是（）。
p->next->next=p->next; p->next->prior=p;
p->next=p->next->next; p->next->prior=p;
p->next=p->next->next; p->next->next->prior=p;
p->next->prior=p; p->next=p->next->next;
答案：p->next = p->next->next; p->next->prior = p;