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

第2章线性表

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

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

2. 线性表是具有n个（
）的有限序列（n>0） o
A.表元素 B.字符
A.表元素 B.字符

A.表元素 B.字符
C.数据元素 D.数据项
E.信息项

3. 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则 利用（）存储方式最节省时间。
A.顺序表 B.双链表
C.带头结点的双循环链表D,单循环链表
某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采 用（）存储方式最节省运算时间。
A.单链表 B.仅有头指针的单循环链表C.双链表 D.仅有尾指针的单循环链表设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用（）最节省时间。
A,单链表 B.单循环链表C.带尾指针的单循环链表D.带头结点的双循环链表链表不具有的特点是（）A.插入、删除不需要移动元素B.可随机访问任一元素不必事先估计存储空间D.所需空间与线性长度成正比
6, 下面的叙述不正确的是（）A.线性表在链式存储时，查找第i个元素的时间同i的值成正比
B,线性表在链式存储时，查找第i个元素的时间同i的值无关线性表在顺序存储时，查找第i个元素的时间同i的值无关线性表的表元存储方式有（顺序）和链接两种。试指出下列各表中使用的是何种存储方式: 表1是（）存储方式；表2是（）存储方式；表3是（ ）存储方式；表4是（）存储 方式。。
表元编

货号
数
量
表元间联
1
618-
40

2
205
2
3
3
103
15
4
4
501
20
5
5
781
17
6
6
901
24
0
表1:头结点指向1表2：头结点指向1
表元编

货号
数
量
表元间联
冬
1
618-
40
5
2
205
2

3
103
15
4
4
501
2。
2
5
781

6
6
901
24
3
6901 242
表元编
号
货号
数
量
表元间联
系
1
618-
40

2
205
2

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