数据结构作业：第2章-线性表作业答案.docx

第2章线性表

选择题下面关于线性表的叙述中，错误的是哪一个？ （ B ）A.

A.
线性表采用顺序存储,
必须占用一片连续的存储单元。
B.
线性表采用顺序存储,
便于进行插入和删除操作。
C.
线性表采用链接存储,
不必占用一片连续的存储单元。
D.
线性表采用链接存储,
便于插入和删除操作。

1. 线性表是具有n个（C ）的有限序列（n>0）。
A.表元素 B.字符 C.数据元素 D.数据项
巳信息项

2. 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则 利用（A ）存储方式最节省时间。
A.顺序表 B.双链表
C.带头结点的双循环链表D.单循环链表

3. 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采 用（D ）存储方式最节省运算时间。
A.单链表 B.仅有头指针的单循环链表 C.双链表 D.仅有尾指针的单循环 链表5.

5.
A.
设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用（D ）最节省时间。
单链表 B.单循环链表C.带尾指针的单循环链表 D.带头结点的双循环链表6.

6.
链表不具有的特点是（B ）
A.
插入、删除不需要移动元素B.可随机访问任一元素

C.不必事先估计存储空间D.所需空间与线性长度成正比7.

7.
下面的叙述不正确的是（B ）
A.
线性表在链式存储时，查找第i个元素的时间同i的值成正比
B.线性表在链式存储时，查找第i个元素的时间同i的值无关
D.
线性表在顺序存储时，查找第i个元素的时间同i的值无关
线性表的表元存储方式有（顺序）和链接两种。试指出下列各表中使用的是何种存储方式: 表1是（I ）存储方式；表2是（E ）存储方式；表3是（B ）存储方式；表4是（C ）存储 方式。表左的s指向起始表元。
8.

表元编
号
货号
数
量
表元间联
系
1
618-
40
2
2
205
2
3
3
103
15
4
4
501
20
5
5
781
17
6
6
901
24
0
表1表2
表元编
号
货号
数
量
表元间联
系
1
618-
40
5
2
205
2
1
3
103
15
4
4
501
20
2
5
781
17
6
6
901
24
3
6901 242
表元编
号
货号
数
量
表元间联
系
1
618-
40
5
2
205
2
1
3
103
15
6
4
501
20
0
5
781
17
4
表3
s—>
表元编 号
货号
数
量
表元间联
系
1
2
1
618-
40
5
2
2
205
2
1
0
3
103
15
4
6
4
501
20
0
3
5
781
17
6
1
6
901
24
3
5
表4供选择的答案：
A.连续B.单向链接C.双向链接 D.不连接E.循环链接F.树状 G.网状 H.随机I.顺序J.顺序循环若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间 复杂度为(C ) (lv = iv = n+l)。
A. 0(0) B. 0(1) C. O(n) D. O(n2)对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为(C )。
A. O(n) O(n) B. O(n) 0(1) C. 0(1) 0(n) D. 0(1) 0(1)线性表(al,a2,...,an)以链接方式存储时，访问第i位置元素的时间复杂性为(C )A. 0 (i) B. 0 (1) C. O (n) D. 0 (i-1)循环链表H的尾结点P的特点是(A )。
A. P.NEXT=H
B. P.NEXT= H.NEXT
C. P=H
D. P=H.NEXT
二、判断顺序存储结构的主要缺点是不利于插入或删除操作。（V）线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的V ）
1. 顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。（x ）对任何数据结构链式存储结构一定优于顺序存储结构。（x ）顺序存储方式只能用于存储线性结构。（x ）集合与线性表的区别在于是否按关键字排序。（x ）
2. 线性表的特点是每个元素都有一个前驱和一个后继。（x ）取线性表的第i个元素的时间同i的大小有关.（ x ）循环链表不是线性表.（x ）线性表只能用顺序存储结构实现。（x ）
3. 线性表就是顺序存储的表。（x ）为了很方便的插入和删除数据，可以使用双向链表存放数据。（V ）顺序存储方式的优点是存储密度大，旦插入、删除运算效率高。（x ）链表是采用链式存储结构的线性表，进行插入、删除操作时，在链表中比在顺序存储结 构中效率高。（V ）
三、填空当线性表的元素总数基本稳定，旦很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用顺序存储结构。
1. 线性表L= （al,a2,...,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是n-1/2。
2. 在一个长度为n的顺序表中第i个元素（lv=iv=n）之前插入一个元素时，需向后移动 n-i+1个元素。
3. 在单链表中设置头结点的作用是一主要是使插入和删除等操作统…，在第•个元素之 前插入元素和删除第一个结点不必另作判断。另外，不论链表是否为空，链表指针不变。
4. 对于一个具有n个结点的单链表，在己知的结点*p后插入一个新结点的时间复杂度为
0(1)，在给定值为x的结点后插入一个新结点的时间复杂度为0(n)。
5. 链接存储的特点是利用 指针来表示数据元素之间的逻辑关系。
6. 顺序存储结构是通过一物理上相邻表示元素之间的关系的:链式存储结构是通过
一指针一表示元素之间的关系的。
7. 对于双向链表，在两个结点之间插入一个新结点需修改的指针共 —4—个，单链表为 2_个。
8. 循环单链表的最大优点是：从任•结点出发都可访问到链表中每，个元素 °已知指针p指向单链表L中的某结点，则删除其后继结点的语句是：a = D->next;D->next=a->next;free(a);在单链表L中，指针p所指结点有后继结点的条件是：D・>next!=null
9. 在单链表p结点之后插入s结点的操作是：
_ s・>next=D->next；D・>next=s。