第2章线性表自测卷答案

习题二参考答案

一、选择题

1. 链式存储结构的最大优点是（ D ）。

A.便于随机存取 B.存储密度高

C.无需预分配空间 D.便于进行插入和删除操作

2. 假设在顺序表{a0,a1,……,an－1}中，每一个数据元素所占的存储单元的数目为4，且第0个数据元素的存储地

址为100，则第7个数据元素的存储地址是（ D ）。 A. 106 B. 107 C.124 D.128 3. 在线性表中若经常要存取第i个数据元素及其前趋，则宜采用（ A ）存储方式。

A.顺序表 B. 带头结点的单链表

C.不带头结点的单链表 D. 循环单链表

4. 在链表中若经常要删除表中最后一个结点或在最后一个结点之后插入一个新结点，则宜采用（ C ）存储方

式。

A. 顺序表 C. 用尾指针标识的循环单链表

B. 用头指针标识的循环单链表 D. 双向链表

5. 在一个单链表中的p和q两个结点之间插入一个新结点，假设新结点为S,则修改链的java语句序列是（ D ）。

A. s.setNext(p); q.setNext(s); B. p.setNext(s.getNext()); s.setN

习题二参考答案

一、选择题

1. 链式存储结构的最大优点是（ D ）。

A.便于随机存取 B.存储密度高 C.无需预分配空间 D.便于进行插入和删除操作

2. 假设在顺序表{a0,a1,……,an－1}中，每一个数据元素所占的存储单元的数目为4，且第0

个数据元素的存储地址为100，则第7个数据元素的存储地址是（ D ）。 A. 106 B. 107 C.124 D.128

3. 在线性表中若经常要存取第i个数据元素及其前趋，则宜采用（ A ）存储方式。

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

4. 在链表中若经常要删除表中最后一个结点或在最后一个结点之后插入一个新结点，则宜

采用（ C ）存储方式。

A. 顺序表 B. 用头指针标识的循环单链表 C. 用尾指针标识的循环单链表 D. 双向链表

5. 在一个单链表中的p和q两个结点之间插入一个新结点，假设新结点为S,则修改链的

java语句序列是（ D ）。 A. s.setNext(p); q.setNext(s); B. p.setNext(s.getNext()); s.setN

习题二参考答案

一、选择题

1. 链式存储结构的最大优点是（ D ）。

A.便于随机存取 B.存储密度高

C.无需预分配空间 D.便于进行插入和删除操作

2. 假设在顺序表{a0,a1,……,an－1}中，每一个数据元素所占的存储单元的数目为4，且第0个数据元素的存储地

址为100，则第7个数据元素的存储地址是（ D ）。 A. 106 B. 107 C.124 D.128 3. 在线性表中若经常要存取第i个数据元素及其前趋，则宜采用（ A ）存储方式。

A.顺序表 B. 带头结点的单链表

C.不带头结点的单链表 D. 循环单链表

4. 在链表中若经常要删除表中最后一个结点或在最后一个结点之后插入一个新结点，则宜采用（ C ）存储方

式。

A. 顺序表 C. 用尾指针标识的循环单链表

B. 用头指针标识的循环单链表 D. 双向链表

5. 在一个单链表中的p和q两个结点之间插入一个新结点，假设新结点为S,则修改链的java语句序列是（ D ）。

A. s.setNext(p); q.setNext(s); B. p.setNext(s.getNext()); s.setN

第2章习题 ............................................................................................................................... 1

第2章习题

2.1若将顺序表中记录其长度的分量listlen改为指向最后一个元素的位置last，在实现各基本运算时需要做那些修改？

【解】

//用线性表最后一个元素的下标last代替listLen实现顺序表 #define MAXLEN 100 typedef int elementType;

typedef struct sllLast { elementType data[MAXLEN]; int last; }seqList;

//初始化

void initialList(seqList &S) { S.last=-1; }

//求表长度

int listLength(seqList S) { return S.last+1; }

//按序号取元素

bool getElement(seqList S,int i,elementType &x) {

第2章习题 ............................................................................................................................... 1

第2章习题

2.1若将顺序表中记录其长度的分量listlen改为指向最后一个元素的位置last，在实现各基本运算时需要做那些修改？

【解】

//用线性表最后一个元素的下标last代替listLen实现顺序表 #define MAXLEN 100 typedef int elementType;

typedef struct sllLast { elementType data[MAXLEN]; int last; }seqList;

//初始化

void initialList(seqList &S) { S.last=-1; }

//求表长度

int listLength(seqList S) { return S.last+1; }

//按序号取元素

bool getElement(seqList S,int i,elementType &x) {

第2章 线性表及其应用

第2章 线性表及其应用

本章学习要点

◆掌握线性表的逻辑结构及相关概念。

◆掌握线性表的两种基本存储结构，即线性顺序表（顺序表）和线性链表（链表）的存储结构。体会线性表在各种存储方式之间的差异及其各自的优缺点。 ◆熟练掌握顺序表和链表上各种基本操作的实现过程。 ◆灵活运用顺序表和链表的特点解决实际应用问题。

线性表（Linear List）是一种最基本、最常用的数据结构。线性表有两种基本存储表示方法，即顺序存储表示和链表表示。线性表的基本操作主要有插入、删除和查找等。本章将具体给出线性表的定义、存储结构、基本操作及其算法实现，最后给出线性表的应用实例。

2.1线性表的定义和基本运算

2.1.1线性表的定义

线性表是n(n≥0)个同类型数据元素（记录或结点）的有限序列：a0,a1,a2,…,an-1。 记为：Ln=(a0,a1,a2,…,an-1)。

其中：a0是开始结点，an-1是终端结点，ak是ak+1的直接前驱结点，而ak+1是ak的直接后继结点(k=0,1,2,?,n-2)；终端结点an-1没有后继结点，开始结点a0没有前驱结点；元素ai(i=0,1,2?,n-1)在表中的位置为i+1；元素的个数n称为线性表L的

第2章 线性表及其应用

第2章 线性表及其应用

本章学习要点

◆掌握线性表的逻辑结构及相关概念。

◆掌握线性表的两种基本存储结构，即线性顺序表（顺序表）和线性链表（链表）的存储结构。体会线性表在各种存储方式之间的差异及其各自的优缺点。 ◆熟练掌握顺序表和链表上各种基本操作的实现过程。 ◆灵活运用顺序表和链表的特点解决实际应用问题。

线性表（Linear List）是一种最基本、最常用的数据结构。线性表有两种基本存储表示方法，即顺序存储表示和链表表示。线性表的基本操作主要有插入、删除和查找等。本章将具体给出线性表的定义、存储结构、基本操作及其算法实现，最后给出线性表的应用实例。

2.1线性表的定义和基本运算

2.1.1线性表的定义

线性表是n(n≥0)个同类型数据元素（记录或结点）的有限序列：a0,a1,a2,…,an-1。 记为：Ln=(a0,a1,a2,…,an-1)。

其中：a0是开始结点，an-1是终端结点，ak是ak+1的直接前驱结点，而ak+1是ak的直接后继结点(k=0,1,2,?,n-2)；终端结点an-1没有后继结点，开始结点a0没有前驱结点；元素ai(i=0,1,2?,n-1)在表中的位置为i+1；元素的个数n称为线性表L的

第二章 线性表 一、选择题

1. 下面关于线性表的叙述错误的是（ ）。

A.线性表采用顺序存储必须占用一片连续的存储空间 B. 线性表采用链式存储不必占用一片连续的存储空间 C. 线性表采用链式存储便于插入和删除操作的实现 D. 线性表采用顺序存储便于插入和删除操作的实现 2. 设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为（ ）。

A.q=p->next；p->data=q->data；p->next=q->next；free(q)； B. q=p->next；q->data=p->data；p->next=q->next；free(q)； C. q=p->next；p->next=q->next；free(q)； D. q=p->next；p->data=q->data；free(q)；

3. 设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（ ）。

A. O(n) B. O(nlog2n) C. O(1) D. O(n2)

4．设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为（ ）。

第二章 线性表

一、选择题

1．线性表是具有n个__C___的有限序列（n>0）。

A．表元素 B．字符 C．数据元素 D．数据项 2．一个顺序表所占用的存储空间大小与___B___无关。 A．表的长度 C．元素的类型

B．元素的存放顺序

D．元素中各字段的类型

3．线性表的顺序存储结构是一种__A___。 A．随机存取的存储方式 C．索引存取的存储方式

B．顺序存取的存储方式 D．Hash存取的存储方式

4. 若线性表采用顺序存储结构，每个元素占用 4 个存储单元，第一个元素的存储地址为 100,则第 12 个元素的存储地址是__B____。 A．112 B.144 C.148 D.412 5. 线性表是__A____。

A．一个有限序列，可以为空 B．一个有限序列，不能为空 C．一个无限序列，可以为空 D．一个无限序列，不能为空

6．对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为__C____。 A．O（n）O（n） B．O（n）O（1） C．O（1）O（n） D．O（1）O(1) 7．若长度为n的非空线性表采用顺序存储结构

第二章 线性表

一、选择题

1．线性表是具有n个__C___的有限序列（n>0）。

A．表元素 B．字符 C．数据元素 D．数据项 2．一个顺序表所占用的存储空间大小与___B___无关。 A．表的长度 C．元素的类型

B．元素的存放顺序

D．元素中各字段的类型

3．线性表的顺序存储结构是一种__A___。 A．随机存取的存储方式 C．索引存取的存储方式

B．顺序存取的存储方式 D．Hash存取的存储方式

4. 若线性表采用顺序存储结构，每个元素占用 4 个存储单元，第一个元素的存储地址为 100,则第 12 个元素的存储地址是__B____。 A．112 B.144 C.148 D.412 5. 线性表是__A____。

A．一个有限序列，可以为空 B．一个有限序列，不能为空 C．一个无限序列，可以为空 D．一个无限序列，不能为空

6．对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为__C____。 A．O（n）O（n） B．O（n）O（1） C．O（1）O（n） D．O（1）O(1) 7．若长度为n的非空线性表采用顺序存储结构