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

第2章线性表

-选择题

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

A.线性表采用顺序存储，必须占用一片连续的存储单元。

B.线性表采用顺序存储，便于进行插入和删除操作。

C.线性表采用链接存储，不必占用一片连续的存储单元。

D.线性表采用链接存储，便于插入和删除操作。

2.线性表是具有n个（）的有限序列（n>0）。

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

3.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则

利用（）存储方式最节省时间。

A.顺序表B.双链表C.带头结点的双循环链表D.单循环链表

4.某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采

用（）存储方式最节省运算时间。

A.单链表B.仅有头指针的单循环链表C.双链表D.仅有尾指针的单循环

链表

5.设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用（）最节省时间。

A.单链表B.单循环链表C.带尾指针的单循环链表D.带头结点的双循环链表

6.链表不具有的特点是（）

A.插入、删除不需要移动元素B.可随机访问任一元素

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

7.下面的叙述不正确的是（）

A.线性表在链式存储时，查找第i个元素的时间同i的值成正比

B.线性表在链式存储时，查找第i个元素的时间同i的值无关

D.线性表在顺序存储时，查找第i个元素的时间同i的值无关

8.线性表的表元存储方式有（顺序）和链接两种。试指出下列各表中使用的是何种存储方式:

表1是（）存储方式；表2是（）存储方式；表3是（）存储方式；表4是（）存储

方式…

表元编数表元间联

货号

号量系

1618-402

220523

3103154

4501205

5781176

6901240

表1:头结点指向1

表元编数表元间联

货号

量系

1618-405

220521

3103154

4501202

5781176

6901243

表2：头结点指向1

表元编数表元间联

货号

号量系

1618-405

220521

3103156

4501200

5781174

6901242

表3：头结点指向3

表元间联

表元编数

货号系

号量

12

1618-4052

2205210

31031546

45012003

57811761

69012435

表4：头结点指向4

供选择的答案：

A.连续B.单向链接C.双向链接D,不连接E.循环链接

F.树状G.网状H.随机I.顺序J.顺序循环

9.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间

复杂度为()(l<=i<=n+l)。

A.0(0)B.0(1)C.0(n)D.0(n2)

10.对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为()。

A.O(n)O(n)B.O(n)0(1)C.0(1)0(n)D.0(1)0(1)

11.线性表(al,a2,...,an)以链接方式存储时，访问第i位置元素的时间复杂性为()

A.0(i)B.0(1)C.0(n)D.0(i-1)

12.循环链表H的尾结点P的特点是()。

A.P.NEXT=HB.P.NEXT=H.NEXTC.P=HD.P=H.NEXT

二、判断

1.顺序存储结构的主要缺点是不利于插入或删除操作。（）

2.线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。（）

3.顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。（）

4,对任何数据结构链式存储结构一定优于顺序存储结构。（）

5.顺序存储方式只能用于存储线性结构。（）

6.集合与线性表的区别在于是否按关键字排序。（）

7.线性表的特点是每个元素都有一个前驱和一个后继。（）

8.取线性表的第i个元素的时间同i的大小有关.（）

9.循环链表不是线性表.（）

10.线性表只能用顺序存储结构实现。（）

11.线性表就是顺序存储的表。（）

12.为了很方便的插入和删除数据，可以使用双向链表存放数据。（）

13.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。（）

14.链表是采用链式存储结构的线性表，进行插入、删除操作时，在链表中比在顺序存储结

构中效率高。（）

三、填空

1.当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取

线性表中的元素时，应采用存储结构。

2.线性表L=（al,a2,...,an）用数组表示，假定删除表中任一元素的概率相同，则删除一

个元素平均需要移动元素的个数是O

3.在一个长度为n的顺序表中第i个元素（l<=i<=n）之前插入一个元素时，需向后移

动个元素。

5.对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为

，在给定值为x的结点后插入一个新结点的时间复杂度为。

6.链接存储的特点是利用来表示数据元素之间的逻辑关系。

7.顺序存储结构是通过表示元素之间的关系的;链式存储结构是通过

表示元素之间的关系的。

8.对于双向链表，在两个结点之间插入一个新结点需修改的指针共个，单链表为

个。

9,循环单链表的最大优点是：