算法与数据结构第二章测试_智慧树知到答案2021年

第二章 线性表：数据结构分线性结构和非线性结构，线性表是一种典型的线性结构，也是一种非常基本的数据结构，是学习其他数据结构的基础。本章将介绍线性表的基本概念及其两种实现方法——顺序表和链表。2.1线性表:线性结构的特点是数据元素存放在非空有限集合中，并且满足如下几个条件：（1）存在唯一的“第一个”数据元素；（2）存在唯一的“最后一个”数据元素；（3）除第一个数据元素之外，集合中的每一个数据元素都只有一个前驱；（4）除最后一个数据元素之外，集合中的每一个数据元素都只有一个后继。本节我们将学习什么是线性表，线性表有哪些特点，如何定义线性表的抽象数据类型，以及如何用线性表的基本操作实现一些复杂的操作。学完本章，要求能够从时间和空间复杂度的角度，综合比较线性表两种存储结构的不同特点及其适用场合，会运用线性表解决实际问题。
2.2顺序表:顺序表是线性表顺序存储的实现，是最简单的数据组织方法，它使用方便，可以对数据元素进行高效的随机存取，但对插入、删除等操作效率较低。本节将介绍顺序表的定义，基本操作（建立、查找、插入和删除等）及程序实现，通过若干示例讲解顺序表的应用。要求能够编程实现相关内容，并掌握调试程序的方法。
2.3链表:链表是线性表链式存储的实现，是本章的重点和难点，要学好本节内容，需要具有扎实的指针操作和内存动态分配的编程技术。本节以单链表为例，介绍链表结构实现线性表操作的基本方法，在此基础上，引出循环链表、双链表等其他链表形式，并通过考研、面试经常遇到的问题讲解链表的各种应用。

[单选题]带头结点的单链表head为空的判定条件是（）
head= =NULL
head->next= =NULL
head->next= =head
head!=NULL
答案：head->next==NULL
[单选题]循环链表的主要优点是（ ）。
已知某结点位置后能容易找到其直接前驱
不再需要头指针
在进行插入、删除运算时能保证链表不断开
在表中任一结点出发都能扫描整个链表
答案：从表中任一结点出发都能遍历整个链表
[单选题]线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）
部分地址必须是连续的
一定是不连续的
连续或不连续都可以
必须是连续的
答案：连续或不连续都可以
[单选题]若一个线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（ ）存储方式最节省时间。
循环单链表
双链表
单链表
顺序表
答案：顺序表
[单选题]在一个长度为n的顺序表中，在第i个元素之前插入一个新元素时，需向后移动（ ）个元素
n-i
n-i+1
i
n-i-1
答案：n-i+1
[单选题]线性表的顺序存储结构是一种（ ）存储结构。
随机存取
顺序存取
索引存取
散列存取
答案：随机存取
[单选题]在双向循环链表中，在p指针所指的结点后插入一个指针q所指向的新结点，修改指针的操作是（ ）。
q->next=p->next;q->prior=p;p->next=q;p->next=q;
q->prior=p;q->next=p->next;p->next->prior=q;p->next=q;
p->next=q;q->prior=p;p->next->prior=q;q->next=q;
p->next=q;p->next->prior=q;q->prior=p;q->next=p->next;
答案：q->prior=p;q->next=p->next;p->next->prior=q;p->next=q;
[单选题]在下列对顺序表进行的操作中，算法时间复杂度为O(1)的是（ ）。（答案中的i均为合法输入）
删除第i个元素
对顺序表中元素进行排序
访问第i个元素的前驱
在第i个元素之后插入一个新元素
答案：访问第i个元素的前驱
[单选题]已知指针p和q分别指向某单链表中第一个结点和最后一个结点。假设指针s指向另一个单链表中某个结点，则在s所指结点之后插入上述链表应执行的语句为（ ）。
s->next=q；p->next=s->next；
q->next=s->next；s->next=p；
p->next=s->next；s->next=q；
s->next=p；q->next=s->next；
答案：q->next=s->next；s->next=p；
[单选题]在表长为n的顺序表中，当在任何位置删除一个元素的概率相同时，删除一个元素所需移动的平均个数为（ ）。
(n-1)/2
(n+1)/2
n/2
n
答案：(n-1)/2