第2章线性表
线性表是一种最基本、最常用的数据结构，它有两种存储结构——顺序表和链表。本章主要介绍线性表的定义、表示和基本运算的实现。重点讨论了线性表的存储结构，以及在顺序、链式两种存储结构上基本运算的实现。
重点提示：
●线性表的逻辑结构特征
●线性表的顺序存储和链式存储两种存储结构的特点
●在两种存储结构下基本操作的实现
2-1 重点难点指导
2-1-1 相关术语
1．线性表
线性表是具有相同数据类型的n（n≥0）个数据元素的有限序列，通常记为：(a1,a2,…,a n)，其中n为表长，n=0时称为空表。
要点：一种逻辑结构，其数据元素属于相同数据类型，之间的关系是线性关系。
2．顺序表
顺序存储的线性表。
要点：按线性表中的元素的逻辑顺序依次存放在地址连续的存储单元里，其存储特点：用物理上的相邻实现逻辑上的相邻。
3．链表
用链表存储的线性表。
要点：链表是通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起的，对每个结点的地址是否连续没有要求。
4．单链表
每个结点除了数据域外还有一个指向其后继的指针域。
要点：通常将每个元素的值和其直接后继的地址作为一个结点，通过每个结点中指向后继结点的指针表示线性表的逻辑结构。
5．头指针
要点：头指针是一个指针变量，里面存放的是链表中首结点的地址，并以此来标识一个链表。如链表H，链表L等，表示链表中第一个结点的地址存放在指针变量H、L中。通常用头指针来惟一标识一个链表。
6．头结点
要点：附加在第一个元素结点之前的一个结点，头指针指向头结点。当该链表表示一个非空的线性表时，头结点的指针域指向第一个元素结点；为空表时，该指针域为空。
7．头结点的作用
要点：其作用有两个，一是使对空表和非空表的处理得到统一；二是在链表的第一个位置上的操作和在其他位置上的操作一致，无需特殊处理。
2-1-2 线性表的顺序存储
1．顺序表
顺序存储的线性表称为顺序表。其特点是：用一组地址连续的存储单元来依次存放线性表的数据元素，因此数据元素的逻辑顺序和物理次序一致（这是顺序存储的核心所在）。
具体实现：在程序设计语言中，一维数组在内存中占用的存储空间就是一组连续的存储区域，因此，用一维数组来表示顺序表的数据存储区域是再合适不过的。考虑到线性表的运算有插入、删除等，即表长是可变的，因此，数组的容量需设计得足够大，设用data[MaxSize]来表示，其中MaxSize是一个根据实际问题定义的足够大的整数，线性表中的数据从data[0] 开始依次顺序存放，但当前线性表中的实际元素个数可能未达到MaxSize个，因此需用一个变量 last 记录当前线性表中最后一个元素在数组中的位置，即 last 起一个指针的作用，始终指向线性表中最后一个元素，因此，表空时last=-1。
这种存储思想的具体实现可以是多样的。
方法一：可以用一个数组和表示长度的变量共同完成上述思想，如：
#define MaxSize ……//MaxSize为根据实际问题定义的足够大的整数
DataType data[MaxSize];
int last;
这样表示的顺序表如图2-1所示。数据元素分别存放在data[0]到data[last]中。
这样使用简单方便，但有时不便管理。
0 1 …i-1 i …n-1 n MaxSize-1
data
last
图2-1 线性表的顺序存储示意图
方法二：从结构上考虑，通常将data 和last 封装成一个结构作为顺序表的类型：
#define MaxSize ……//MaxSize为根据实际问题定义的足够大的整数
typedef struct{
DataType data[MaxSize];
int last; //表示线性表最后一个元素位置。
}SeqList;
定义一个顺序表变量：SeqList L ;
这样表示的线性表如图2-2（a）所示。表长为https://www.doczj.com/doc/0119479554.html,st+1，线性表中的数据元素a1~a n分别存储在L.data[0]~L.data[https://www.doczj.com/doc/0119479554.html,st]中。
方法三：由于教科书中的算法用Visual C++语言描述，根据Visual C++语言中的一些规则，有时定义一个指向SeqList 类型的指针更为方便：
SeqList *L ；
L是一个指针变量，线性表的存储空间通过L=new SeqList操作（Visual C++语句，
不同的语言版本可能有所不同）来获得。
L 中存放的是顺序表的地址，这样表示的线性表如图2-2（b ）所示。表长表示为（*L ）.last+1或L -＞last+1，线性表中数据元素的存储空间为：
L-＞data[0] ~ L-＞data[L-＞last]。
读者通过上述介绍的几种表示方式，进一步体会顺序存储的“理念”，做题时根据题意灵活掌握，在读写算法时注意相关数据结构的类型说明。
图2-2 线性表的顺序存储示意图
2．顺序表的优缺点
优点1：顺序表是由地址连续的向量实现的，因此具有按序号随机访问的特点。 设a １的存储地址为Loc(a １)，每个数据元素占d 个存储地址，则第i 个数据元素的地址为：
Loc(a i )=Loc(a １)+(i-1)*d 1≤i ≤n
这就是说只要知道顺序表首地址和每个数据元素所占地址单元的个数就可求出第i 个数据元素的地址来，这就是顺序表具有按数据元素的序号随机存取的特点。
优点2：存储密度高。
缺点1：在顺序表中做插入和删除运算时，平均需移动大约表中一半的元素；
缺点2：顺序表的存储空间是静态分配的，在程序执行之前必须明确规定它的存储规模，因此分配不足则会造成溢出；分配过大，又可能造成存储单元的浪费。
2-1-3 链表
1．单链表
链表是通过一组任意的存储单元来存储线性表中的数据元素的，为建立起数据元素之间的线性关系，对每个数据元素a i ，除了存放数据元素自身的信息 a i 之外，还需要和a i 一起存放其后继 a i+1 所在的存储单元的地址，这两部分信息组成一个“结点”，结点的结构如图2-3所示，每个元素都如此。因此n 个元素的线性表通过每个结点的指针域拉成了一个“链子”，称
之为链表。因为每个结点中只有一个指向后继的指针，所以称其
图2-3 单链表结点结构
L.data L ->data 0 1 2 3 4 5
https://www.doczj.com/doc/0119479554.html,st MaxSize -1
（a ）表长为https://www.doczj.com/doc/0119479554.html,st+1
（b ）表长为L->last+1
MaxSize -1
L ->length 6
4
3 2 1 0 a 1 a 2 a 3 a
4 a
5 a 6
…
…
a 1 a 2 a 3 a 4 a 5 a 6
L->last 5 6
6
为单链表。
链表是由一个个结点构成的，结点定义如下：
typedef struct Node{
DataType data;
struct Node *next;
}LNode,*LinkList;
LNode是结点的类型，*LinkList是指向LNode结点的指针类型。
作为线性表的一种存储结构，我们关心的是结点间的逻辑结构，而对每个结点的实际地址并不关心，所以通常的单链表用图2-4的形式表示。
图2-4 单链表
通常用“头指针”来标识一个单链表，如单链表L、单链表H等，是指某链表的第一个结点的地址放在了指针变量L、H中，头指针为“NULL”则表示一个空表。
2．单循环链表
对于单链表而言，最后一个结点的指针域是空指针，如果将该链表的头指针置入该指针域，则使得链表头尾结点相连，就构成了单循环链表。
对于单链表只能从头结点开始遍历整个链表，而对于单循环链表则可以从表中任意结点开始遍历整个链表，不仅如此，有时对链表常做的操作是在表尾、表头进行，此时可以改变一下链表的标识方法，不用头指针而用一个指向尾结点的指针R来标识，可以使操作效率得以提高。
3．双向循环链表
在单链表的结点中只有一个指向其后继结点的指针域next，因此若已知某结点的指针为p，其后继结点的指针则为p->next，而找其前驱结点则只能从该链表的头指针开始，顺着各结点的next域进行，也就是说找后继结点的时间性能是O(1)，找前Array驱的时间性能是O(n)，如果希望找前驱结点的时间性能也达到
O(1)，则只能付出空间的代价：每个结点再加一个指向前驱结点的
指针域，结点的结构如图2-5所示，用这种结点组成的链表称为双
图2-5 双向链表
向链表。
双向链表结点及指针类型定义如下：
typedef struct DLNode{
DataType data;
struct DLNnode *prior,*next;
}DLNode,*DLinkList;
和单链表类似，双向链表通常也是用头指针标识。
通过双向链表中某结点的指针p既可以直接得到它的后继结点的指针p->next，也可以直接得到它的前驱结点的指针p->prior。这样在有些操作中需要找前驱结点时，则勿需再用循环。
设p指向双向循环链表中的某一结点，即p中是该结点的指针，则p->prior->next表示的是p所指结点之前驱结点的后继结点的指针，即与p相等；类似，p->next->prior表示的
是p所指结点之后继结点的前驱结点的指针，也与p相等，所以有以下等式：p->prior->next = p = p->next->prior
4．静态链表
静态链表是指以数组方式存放链表的数据，数组的每个元素包含有数据域data和指针域next，这里的指针域next与链表中的指针域不同的是其存放的是该结点逻辑上的后继结点的相对地址（即在数组中的下标），也称之为静态指针。
在以静态链表方式存储链表时，数组中含有两个单链表，一个是数据元素的链表，一个是空结点的链表，故还需要设置两个整型变量，分别用于存放链表首元素（或头结点）在数组中的位置和空结点链表的首位置。
静态链表存储定义如下：
#define MAXSIZE ……//足够大的数
typedef struct {
DataType data;
int next;
}SNode; //结点类型
SNode sd[MAXSIZE]; //数组sd以静态链表方式存放链表数据
int SL,AV; //两个头指针变量
5．链式存储的优缺点
链式存储的优缺点与顺序存储互补：
优点1：对链表做插入和删除运算时，只需改变指针，不需移动数据。
优点2：不需要事先分配空间，便于表的扩充。
缺点1：存储密度降低，因为每个结点中除了存放数据元素的值还有一个指针域。
缺点2：不具有按序号随机访问第i个元素的特点，必须通过标识链表的头指针（或尾指针）“顺藤摸瓜”才能找到第i个结点。
2-1-4 线性表的基本运算
1．基于顺序表的运算
顺序表中常做的运算有插入、删除、合并、查找等，做这些运算时，要掌握一个原则：时刻体现顺序存储的思想，即元素之间物理相邻和逻辑相邻的一致性。
（1）在顺序表中插入元素：
①插入元素时，检查顺序表是否已满，已满则不能做插入操作。
②根据具体问题确定插入位置。
③移动有关元素，以便为待插入的元素让出位置来。
④将元素插入。
⑤修改表长。
（2）在顺序表中删除元素：
①检查顺序表是否已空，空则不能做删除运算。
②根据具体问题确定删除元素的位置。
③将其后面的有关元素移动，“挤掉”被删除的元素。
④修改表长。
结论：
顺序表中插入一个数据元素平均需要移动（n+1）/2个元素。具体某一次的插入中，移动数据元素的个数与表长和插入位置有关。
顺序表中删除一个数据元素需要平均移动n/2个元素。具体某一次的删除中，移动数据元素的个数与表长和删除元素的位置有关。
2．基于链表的运算
链表操作过程中，主要是指针的变化，因此必须清楚指针和动态结点的问题。
（1）头结点的使用
在对不带头结点的单链表进行操作时，对第一个结点的处理和其他结点是不同的。
头结点的加入完全是为了运算的方便，它的数据域无定义，指针域中存放的是第一个数据元素结点的地址，空表时为空。
（2）插入
①后插结点：设指针p指向单链表中某结点，s指向待插入的值为x 的新结点，将s 结点插入到p结点的后面，插入示意图如图2-6所示。
操作如下：
s->next=p->next;
p->next=s;
要点：两个指针的操作顺序不能交换。
②前插结点
设指针ｐ指向链表中某结点，s指向待插入的值为x的新结点，将s结点插入到p结点的前面，插入示意图如图2-7所示，与后插不同的是：首先要找到p结点的前驱结点q，然后再完成在q结点之后插入s结点的操作，设单链表头指针为L，操作如下：q=L;
while (q->next!=p)
q=q->next; //找p的直接前驱
s->next=q->next;
q->next=s;
图2-6 在p之后插入s 图2-7 在p之前插入s 后插操作的时间复杂性为O(1)，前插操作因为要找p 结点的前驱结点，时间性能为O(n)；其实我们更关心的是数据元素之间的逻辑关系，所以仍然可以将s 结点插入到p 结点的后面，然后将p->data与s->data交换即可，这样既满足了逻辑关系，也能使得时间复杂性为O(1)。
由此得知：在单链表中插入一个结点必须知道其前驱结点。
③在单链表第i 个元素之前插入元素x
ⅰ. 从头指针开始找到第i-1个元素结点，若存在继续步骤ⅱ，否则结束。
ⅱ. 申请、填装新结点。 ⅲ. 将新结点插入，结束。 （3）删除 ① 删除结点
ⅰ. 删除p 结点的后继结点（假设存在），则可以直接完成：
s=p->next;
p->next=s->next; delete s;
该操作的时间复杂性为O(1)。
ⅱ. 若要删除p 结点，即p 所指结点，通过示意图可见，要实现对结点p 的删除，首先要找到p 结点的前驱结点q ，然后完成指针的操作即可。
指针的操作由下列语句实现：
q->next=p->next; delete p;
显然找p 结点前驱结点的时间复杂性为O(n)。 操作示意图如图2-8所示。
当p 结点有后继结点时，对p 结点的删除可以这样处理：把结点p 后继结点的值存储到结点p 中，再删除结点p 的后继结点，这样逻辑上删除了p 结点，
而时间性能为O(1)。
② 删除单链表的第i 个结点
在单链表中删除第i 个结点，必须知道第i -1个结点的指针。算法思路： ⅰ. 找到第i -1个结点；若存在继续步骤ⅱ，否则结束。 ⅱ. 若存在第i 个结点则继续步骤ⅲ，否则结束。 ⅲ. 删除第i 个结点，结束。 （4）查找
在单链表中按值查找或按序号查找某个元素，需通过头指针从第一个元素结点开始，逐个与x 进行比较或记数，若查找成功，则返回指向该元素的指针，若查找失败，则返回NULL 。
（5）双向链表中结点的插入
设p 指向双向链表中某结点，s 指向待插入的值为x 的新结点，将*s 所指结点插入到*p 所指结点的前面，插入示意图如图2-9所示。
操作如下：
① s ->prior=p ->prior; ② p ->prior ->next=s;
③ s ->next=p; ④ p ->prior=s; 指针操作的顺序不是惟一的，但也不是任意的，操作①必须要放到操作④的前面完成，否则结点p
图2-8 删除p 结点
图2-9 双向链表中的结点插入
的前驱结点的指针就丢掉了。读者把每条指针操作的涵义搞清楚，就不难理解了。
（6）双向链表中结点的删除 设p 指向双向链表中某结点，删除指针p 所指结点。
操作示意图如图2-10所示。 操作如下：
① p ->prior ->next=p ->next;
② p ->next ->prior=p ->prior;
delete p;
2-2 典型例题解析
2-2-1 选择题
1．带头结点的单链表head 为空的判断条件是（ ）。 A ．head==NULL B ．head ->next==NULL C ．head ->next==head D ．head!=NULL
【分析】链表为空时，头结点的指针域为空。 【答案】B
2．若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。
A ．单链表
B ．仅有头指针的单循环链表
C ．双链表
D ．仅有尾指针的单循环链表
【分析】根据题意要求，该线性表的存储应能够很方便地找到线性表的第一个元素和最后一个元素，A 和B 都能很方便地通过头指针找到线性表的第一个元素，却要经过所有元素才能找到最后一个元素；选项C 双链表若存为双向循环链表，则能很方便地找到线性表的第一个元素和最后一个元素，但存储效率要低些，插入和删除操作也略微复杂；选项D 可通过尾指针直接找到线性表的最后一个元素，通过线性表的最后一个元素的循环指针就能很方便地找到第一个元素。
【答案】D
3．线性表的静态链表存储结构与顺序存储结构相比优点是（ ）。 A ．所有的操作算法简单 B ．便于插入和删除 C ．便于利用零散的存储器空间 D ．便于随机存取
【分析】静态链表采用的是链式方式存储线性表，因此其具有链式存储的特点。 【答案】B
4．若长度为n 的线性表采用顺序存储结构，在其第i 个位置插入一个新元素算法的时间复杂度为（ ）。
A ．O(log 2n)
B ．O(1)
C ．O(n)
D ．O(n 2)
【分析】在第i 个位置上插入新元素需要从最后一个元素开始后移直到第i 个元素后移
①
图2-10 双向链表中结点的删除
为止，后移元素的次数为n-i+1，即时间复杂度为O(n)。
【答案】C
5．将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是（）。
A．n B．2n-1 C．2n D．n-1
【分析】当一个表的最小元素大于另一个表的最大元素时比较次数为最少，共需n次。
【答案】A
6．在双循环链表p所指结点之后插入s所指结点的操作是（）。
A．p->next=s; s->prior=p; p->next->prior=s; s->prior=p->next;
B．p->next=s; p->next->prior=s; s->prior=p; s->next=p->next;
C．s->prior=p; s->next=p->next; p->next=s; p->next->prior=s;
D．s->prior=p; s->next=p->next; p->next->prior=s; p->next=s;
【分析】由于要将s所指结点插入到p所指结点之后，p结点为s结点的前驱，s结点为p结点的新后继，而结点p的原后继结点为结点s的后继结点，结点s为结点p的原后继结点的前驱结点。在选项A、B和C中均是先执行操作p->next=s，就是修改了结点p的后继结点为s结点，然后再执行操作p->next->prior=s，因此，无法使得结点s为结点p的原后继结点的前驱结点，这样的赋值会使s结点为其自身的前驱。应先执行操作p->next->prior=s，再执行操作p->next=s。
【答案】D
7．在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q结点和p结点之间插入s结点，则执行（）
A．s->next=p->next;p->next=s;
B．p->next=s->next;s->next=p;
C．q->next=s; s->next=p;
D．p->next=s; s->next=q;
【分析】由于是将s所指结点插入到q和p所指结点之间，即使其为q所指结点的后继结点，为p所指结点的前驱结点，因此s->next的取值应为p，p->next的取值无需改动，q->next 的取值应改为s，故A、B和D均是错误的。
【答案】C
2-2-2 判断题
1．顺序存储的线性表可以按序号随机存取。
【分析】因为顺序表在内存是用地址连续的空间存储的，设a１的存储地址为Loc(a１)，每个数据元素占d个存储地址，则第i个数据元素的地址为：
Loc(a i)=Loc(a１)+(i-1) *d 1<=i<=n
这就是说只要知道顺序表首地址和每个数据元素所占地址单元的个数就可求出第i个数据元素的地址来，这也是顺序表具有按数据元素的序号随机存取的特点。
【答案】正确
2．在单链表中和在顺序表中插入一个元素其时间复杂度均为O（n），因此说它们的执行时间是相等的。
【分析】大O 记法表示时间渐近复杂度，是指一个算法中的时间耗费，往往是问题规模n 的函数T(n)，当n 趋向于无穷大时，T(n)的数量级称为算法的时间渐近复杂度。虽然两种存储结构下的插入操作时间复杂度均为O （n ），但由于两者的基本操作不同，因此不能说它们的执行时间是相等的。
【答案】错误
3．静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i 个元素的时间与i 无关。
【分析】因为静态链表的存取特性与动态链表是一样的，只能顺序地找到第i 个元素，不能随机地存取第i 个元素，故其存取表中第i 个元素的时间与i 有关。
【答案】错误
2-2-3 简答题
1．如图所示的双向链表中，欲在结点p 前插入一个结点s ，请完成有关操作。
s->prior = p->prior; p->prior=s;
______________________ s->next=p;
【解答】
只能是：s ->prior ->next=s; 而不能为： p ->prior ->next=s;
因为在上面的第二条语句中已经改变了结点p 的前驱结点，结点p 的前驱结点已经为s 结点，而不是操作前的前驱结点了。在下面的语句顺序下，可有两个答案的选择。
s->prior = p->prior; ______________________ p->prior=s; s->next=p ；
读者做这种题时，最好予以图示，不易出错。
2．已知线性表非递减有序，存储于一个一维数组A[0..n-1] 中（表长为n ，设为全局量），下面算法的功能是什么？
void del(DataType A[ ]){ int i,j; i=1;
while(i<=n-1)
if (A[i]!=A[i+1]) i++;
else{
for (j=(i+2);j A[j-1]=A[j]; n--; } } 【解答】 由于一维数组中的元素按元素非递减有序排列，值相同的元素必为相邻的元素，因此依 次比较相邻两个元素，若值相等，则删除其中一个，否则继续向后查找。故算法功能是删除一维数组中多余的值相同的元素。 3．下述算法的功能是什么？ LinkList Demo(LinkList L){ // L是无头结点的单链表 LNode *q,*p; if (L && L->next){ q=L; L=L->next; p=L; while (p->next) p=p->next; p->next=Q; q->next=NULL; } return L; } 【解答】 算法的功能是把单链表的第一个结点从表头移到了链尾。返回的L指向原链表的第二个结点。若原链表表示的线性表是（a1, a2,…, a n），则操作后表示的线性表为（a2, a3,…, a n,a1）。 4．试描述头指针、头结点、开始结点的区别，并说明头指针和头结点的作用。 【解答】 头指针是一个指针变量，里面存放的是链表中首结点的地址，并以此来标识一个链表。如链表H，链表L等，表示链表中第一个结点的地址存放在H、L中。 头结点是附加在第一个元素结点之前的一个结点，头指针指向头结点。当该链表表示一个非空的线性表时，头结点的指针域指向第一个元素结点，为空表时，该指针域为空。 开始结点指第一个元素结点。 头指针的作用是用来惟一标识一个单链表。 头结点的作用有两个：一是使得对空表和非空表的处理得以统一。二是使得在链表的第一个位置上的操作和在其他位置上的操作一致，无需特殊处理。 5．在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，而不知道头指针，能否将结点p从相应的链表中删除？若可以，其时间复杂度各为多少？ 【解答】 单链表：若结点p有后继结点，则可以实现：将结点p的后继元素数据放入结点p中，再将后继结点删除。时间复杂度为O(1)。若结点p无后继结点，则不可以实现。 双链表：可以实现，时间复杂度为O(1)。 单循环链表：像单链表那样做，也可以从p开始，找结点p的直接前驱，然后再删除p 结点，时间复杂度为O(n)。 2-2-4 算法设计题 1．设线性表存放在一维数组A[arrsize]的前num个分量中，且递增有序。试写一算法，将x插入到线性表的适当位置上，以保持线性表的有序性。并且分析算法的时间复杂度。 【分析】直接用题目中所给定的数据结构（顺序存储的思想是用物理上的相邻表示逻辑上的相邻，不一定要将一维数组和表示线性表长度的变量封装成一个结构体），因为是顺序存储，分配的存储空间是固定大小的，所以首先确定是否还有存储空间，若有，则根据原线性表中元素的有序性，来确定插入元素的插入位置，后面的元素为它让出位置（也可以从高下标端开始一边比较，一边移位），然后插入x，最后修改表示表长的变量。 【算法】 InsertSeq(DataType A[],int *num,DataType x){ //设num为表的最大下标 int i; if (*num==arrsize-1) return 0; else{ i=*num; while (i>=0 && A[i]>x){ //边找位置边移动 A[i+1]=A[i]; i--; } A[i+1]=x; //找到的位置是插入位的下一位 (*num)++; return 1; } } 时间复杂度为O(n)。 2．假设在长度大于1的单循环链表中，既无头结点也无头指针。s为指向链表中某个结点的指针，试编写算法删除结点s的直接前驱结点。 【分析】利用循环单链表的特点，通过s指针可循环找到其前驱结点p及p的前驱结点q，然后可删除结点p。 【算法】 viod delepre(LNode *s){ LNode *p,*q; p=s; while (p->next==s){ q=p; p=p->next; } q->next=s; delete p; } 3．已知两个单链表A与B分别表示两个集合，其元素递增排列，编写一个函数求出A 和B的交集C，要求C同样以元素值递增的单链表形式存储。 【分析】交集指的是两个单链表的元素值相同的结点的集合，为了操作方便，先让单链表C带有一个头结点，最后将其删除掉。算法中指针p用来指向A中的当前结点，指针q 用来指向B中的当前结点，将其值进行比较，两者相等时，属于交集中的一个元素，两者不 等时，将其较小者跳过，继续后面的比较。 【算法】 LinkNode *inter(LinkList A,B){ LNode *q,*p,*r,*s,*C; C=new LNode; r=C; p=A; q=B; while (p && q ) if (p->data p=p->next; else if (p->data==q->data){ s=new LNode; s->data=p->data; r->next=s; r=s; p=p->next; q=q->next; } else q=q->next; r->next=NULL; r=C->next; delete C; return r; } 4．单链表L是一个递减有序表，试写一个高效算法，删除表中值大于min且小于max 的结点（若表中有这样的结点），同时释放被删结点的空间，这里min 和max 是两个给定的参数。请分析你的算法时间复杂度。 【分析】由于单链表L是一个递减有序表，即由大到小有序，故可从表头开始查找第一个比max小的结点，记住其位置，再接着向后查找第一个不大于min的结点，然后将它们之间的结点删除。 【算法】 LinkList delete(LinkList L,int min,int max){ // 设L为带头结点的循环链表 LNode *p,*q,*s,*k; if (L->next){ p=L->next; s=L; while (p->data>=max){ s=p; p=p->next; } //p 指向第一个值小于max的结点,s指向其前驱 while (p!=L && p->data>min) //p继续下移 p=p->next; //p 指向第一个值不大于min的结点 while (s->next!=p){ //删除*s 的后继至* p的前驱之间的结点 k=s->next; s->next=k->next; delete k; } } } 前两个while循环和起来最多循环n次，第三个while循环最多循环n次，即删除n个结点，故算法的时间复杂度为O(n)。 2-3 课后习题选解 1．设线性表存放在向量A[arrsize]的前num个分量中，且递增有序。试写一个算法，将x插入到线性表的适当位置上，以保持线性表的有序性。并且分析算法的时间复杂度。 （参考典型例题解析中的算法设计题1） 2．已知一顺序表A，其元素值非递减有序排列，编写一个算法删除顺序表中多余的值相同的元素。 【提示】对顺序表A，从第一个元素开始，查找其后与之值相同的所有元素，将它们删除；再对第二个元素做同样处理，依此类推。 typedef struct{ DataType data[maxsize]; int last; }seqlist; //定义顺序表类型seqlist void delete(seqlist *A){ int i,j,k,n; i=0; while (i //将第i个元素后与其值相同的元素删除 k=i+1; while (k<=A->last && A->data[i]==A->data[k]) k++; //使k指向第一个与A[i]不同的元素 n=k-i-1; //n表示要删除元素的个数 for (j=k;j<=A->last;j++) A->data[j-n]=A->data[j]; //删除多余元素 A->last=A->last-n; i++; } } 3．写一个算法，从给定的顺序表A中删除值在x～y（x<=y）之间的所有元素，要求以较高的效率来实现。 【提示】对顺序表A，从前向后依次判断当前元素A->data[i]是否介于x和y之间，若是，并不立即删除，而是用n记录删除时应前移元素的位移量；若不是，则将A->data[i]向前移动n位。n用来记录当前已删除元素的个数。 typedef struct{ int data[maxsize]; int last; }seqlist; void delete(seqlist *A,int x,int y){ //删除顺序表A中值在x~y之间的所有元素 int i,n; i=0; n=0; while (i if (A->data[i]>=x && A->data[i]<=y) n++; //若A->data[i] 介于x和y之间，n自增 else A->data[i-n]=A->data[i]; //否则向前移动A->data[i] i++; } A->last=A->last-n; } 4．线性表中有n个元素，每个元素是一个字符，现存于一维数组R[n]中，试写一算法，使R中的字符按字母字符、数字字符和其他字符的顺序排列。要求利用原来的存储空间，元素移动次数最小。 【提示】对线性表进行两次扫描，第一次将所有的字母放在前面，第二次将所有的数字放在字母之后、其他字符之前。 int fch(char c){ //判断c是否为字母 if (c>='a' && c<='z'||c>='A' && c<='Z') return 1; else return 0; } int fnum(char c){ //判断c是否为数字 if (c>='0' && c<='9') return 1; else return 0; } void process(char R[n]){ int low,high; char ch; low=0; high=n-1; while (low //将字母放在前面 while (low low++; while (low high--; if (low ch=R[low]; R[low]=R[high]; R[high]=ch; } } low=low+1; high=n-1; while (low //将数字放在字母后面、其他字符前面 while (low low++; while (low high--; if (low ch=R[low]; R[low]=R[high]; R[high]=ch; } } } 5．线性表用顺序存储，设计一个算法，用尽可能少的辅助存储空间将顺序表中前m个元素和后n个元素进行整体互换。即将线性表 (a1, a2, … , a m, b1, b2, … , b n)改变为：(b1, b2, … , b n , a1, a2, … , a m)。 【提示】比较m和n的大小，若m void process(seqlist *L,int m,int n){ //将顺序表中前m个元素和后n个元素进行整体互换 int i,k; DataType x; if (m<=n) for (i=1;i<=m;i++){ x=L->data[0]; for (k=1;k<=L->last;k++) L->data[k-1]=L->data[k]; L->data[L->last]=x; } else for (i=1;i<=n;i++){ x=L->data[L->last]; for (k=L->last-1;k>=0;k--) L->data[k+1]=L->data[k]; L->data[0]=x; } } 6．已知带头结点的单链表L中的结点是按整数值递增排列的，试写一个算法，将值为x 的结点插入到表L中，使得L仍然有序。并且分析算法的时间复杂度。 【提示】先在单链表中顺序比较，找到插入位置，再生成结点，插入。 typedef struct node{ int data; struct node *next; }Lnode,*Linklist; Linklist insert(Linklist L,int x){ //将值为x 的结点插入到有序的单链表L中 Lnode *p,*s; p=L; while (p->next && x>p->next->data) p=p->next; //找插入位置 s=new Lnode; s->data=x; //申请、填装结点 s->next=p->next; p->next=s; //插入到链表中去 return L; } 7．假设有两个已排序的单链表A和B，编写一个算法将它们合并成一个链表C而不改变其排序性。 【提示】同时从单链表A和单链表B的第一个结点开始进行比较，将值较小的结点插入到链表C的表尾。 typedef struct node{ DataType data; struct node *next; }Lnode,*Linklist; //定义单链表结点类型、指针类型 Linklist combine(Linklist A,Linklist B){ Linklist C; Lnode *pa,*pb,*rc; C=A; rc=C; pa=A->next; //pa指向A的第一个结点 pb=B->next; //pb指向B的第一个结点 delete B; //释放B的头结点 while (pa && pb) if (pa->data rc->next=pa; rc=pa; pa=pa->next; } else{ rc->next=pb; rc=pb; pb=pb->next; } //将pa、pb所指向结点中值较小的一个插入到链表C的表尾 if (pa) rc->next=pa; else rc->next=pb; //将链表A或B中剩余的部分链接到链表C的表尾 return C; } 8．假设在长度大于1的单循环链表中，既无头结点也无头指针。s为指向链表中某个结点的指针，试编写算法，删除结点s的直接前驱结点。 （参考典型例题解析中的算法设计题2） 9．已知两个单链表A与B分别表示两个集合，其元素递增排列，编写一个函数求出A 和B的交集C，要求C同样以元素值递增的单链表形式存储。 （参考典型例题解析中的算法设计题3） 10．设有一个双向链表，每个结点中除有prior、data和next域外，还有一个访问频度freq 域，在链表被起用之前，该域的值初始化为零。每当在链表进行一次Locate(L,x)运算后，令值为x的结点中的freq域增1，并调整表中结点的次序，使其按访问频度的递减序列排列，以便使频繁访问的结点总是靠近表头。试写一个满足上述要求的Locate(L,x)算法。 【提示】在定位操作的同时，需要调整链表中结点的次序：每次进行定位操作后，要查看所查找结点的freq域，将其同前面结点的freq域进行比较，同时进行结点次序的调整。 typedef struct dnode{ DataType data; int freq; struct dnode *prior,*next; }Dnode,*DLinklist; DLinklist locate(DLinklist L,DataType x){ Dnode *p; DataType Y; int k; p=L->next; while (p&&p->data!=x) p=p->next; //查找值为x的结点，使p指向它 if (!p) return NULL; //若查找失败，返回空指针 p->freq++; //修改p的freq域 while (p->prior!=L && p->prior->freq //调整结点的次序 Y=p->prior->data; p->prior->data=p->data; p->data=Y; k=p->prior->freq; p->prior->freq=p->freq; p->freq=k; p=p->prior; } return p; //返回找到的结点的地址} 第2章线性表 班级学号__________-姓名 一、判断正误 （×）1. 链表的每个结点中都恰好包含一个指针。 链表中的结点可含多个指针域，分别存放多个指针。例如，双向链表中的结点可以含有两个指针域，分别存放指向其直接前趋和直接后继结点的指针。 （×）2. 链表的物理存储结构具有同链表一样的顺序。 链表的存储结构特点是无序，而链表的示意图有序。 （×）3. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。 链表的结点不会移动，只是指针内容改变。 （×）4. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。 混淆了逻辑结构与物理结构，链表也是线性表！且即使是顺序表，也能存放记录型数据。 （×）5. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 正好说反了。顺序表才适合随机存取，链表恰恰适于“顺藤摸瓜” （×）6. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。 前一半正确，但后一半说法错误，那是链式存储的优点。顺序存储方式插入、删除运算效率较低，在表长为n的顺序表中，插入和删除一个数据元素，平均需移动表长一半个数的数据元素。 （×）7. 线性表在物理存储空间中也一定是连续的。 线性表有两种存储方式，顺序存储和链式存储。后者不要求连续存放。 （×）8. 线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。 线性表有两种存储方式，在顺序存储时，逻辑上相邻的元素在存储的物理位置次序上也相邻。 （×）9. 顺序存储方式只能用于存储线性结构。 顺序存储方式不仅能用于存储线性结构，还可以用来存放非线性结构，例如 完全二叉树是属于非线性结构，但其最佳存储方式是顺序存储方式。（后一节介绍） （×）10. 线性表的逻辑顺序与存储顺序总是一致的。 理由同7。链式存储就无需一致。 二、单项选择题 （C ）1．数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为：（A）存储结构（B）逻辑结构（C）顺序存储结构（D）链式存储结构（ B ）2. 一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（A）110 （B）108 （C）100 （D）120 （ A ）3. 在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是： （A）访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n） （B）在第i个结点后插入一个新结点（1≤i≤n） （C）删除第i个结点（1≤i≤n） （D）将n个结点从小到大排序 （ B ）4. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动个元素（A）8 （B）63.5 （C）63 （D）7 （ A ）5. 链式存储的存储结构所占存储空间： 第2章线性表 线性表是一种最基本、最常用的数据结构，它有两种存储结构——顺序表和链表。本章主要介绍线性表的定义、表示和基本运算的实现。重点讨论了线性表的存储结构，以及在顺序、链式两种存储结构上基本运算的实现。 重点提示： ●线性表的逻辑结构特征 ●线性表的顺序存储和链式存储两种存储结构的特点 ●在两种存储结构下基本操作的实现 2-1 重点难点指导 2-1-1 相关术语 1．线性表 线性表是具有相同数据类型的n（n≥0）个数据元素的有限序列，通常记为：(a1,a2,…,a n)，其中n为表长，n=0时称为空表。 要点：一种逻辑结构，其数据元素属于相同数据类型，之间的关系是线性关系。 2．顺序表 顺序存储的线性表。 要点：按线性表中的元素的逻辑顺序依次存放在地址连续的存储单元里，其存储特点：用物理上的相邻实现逻辑上的相邻。 3．链表 用链表存储的线性表。 要点：链表是通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起的，对每个结点的地址是否连续没有要求。 4．单链表 每个结点除了数据域外还有一个指向其后继的指针域。 要点：通常将每个元素的值和其直接后继的地址作为一个结点，通过每个结点中指向后继结点的指针表示线性表的逻辑结构。 5．头指针 要点：头指针是一个指针变量，里面存放的是链表中首结点的地址，并以此来标识一个链表。如链表H，链表L等，表示链表中第一个结点的地址存放在指针变量H、L中。通常用头指针来惟一标识一个链表。 6．头结点 要点：附加在第一个元素结点之前的一个结点，头指针指向头结点。当该链表表示一个非空的线性表时，头结点的指针域指向第一个元素结点；为空表时，该指针域为空。 7．若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（）存储方式最节省运算时间。【北京理工大学 2000 一、1（2分）】 A．单链表 B．双链表 C．单循环链表 D．带头结点的双循环链表 8. 静态链表中指针表示的是（）. 【北京理工大学 2001 六、2（2分）】 A．内存地址 B．数组下标 C．下一元素地址 D．左、右孩子地址 9. 链表不具有的特点是（）【福州大学 1998 一、8 (2分)】 A．插入、删除不需要移动元素 B．可随机访问任一元素 C．不必事先估计存储空间 D．所需空间与线性长度成正比 10. 下面的叙述不正确的是（）【南京理工大学 1996 一、10（2分）】 A．线性表在链式存储时，查找第i个元素的时间同i的值成正比 B. 线性表在链式存储时，查找第i个元素的时间同i的值无关 C. 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比 D. 线性表在顺序存储时，查找第i个元素的时间同i的值无关 11. 线性表的表元存储方式有(（1）)和链接两种。试指出下列各表中使用的是何种存储方式：表1是(（2）)存储方式；表2是(（3）)存储方式；表3是(（4）)存储方式；表4是(（5）)存储方式。表左的s指向起始表元。 供选择的答案： A.连续 B.单向链接 C.双向链接 D.不连接 E.循环链接 F.树状 G.网状 H.随机 I.顺序 J.顺序循环 【上海海运学院 1995 二、1（5分）】 12.(1) 静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关。 (2) 静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。 第2章线性表 1. 填空 ⑴在顺序表中，等概率情况下，插入和删除一个元素平均需移动（）个元素，具体移动元素的个数与（）和（）有关。 【解答】表长的一半，表长，该元素在表中的位置 ⑵顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的存储地址是（）。 【解答】108 【分析】第5个元素的存储地址=第1个元素的存储地址＋(5－1)×2=108 ⑶设单链表中指针p 指向结点A，若要删除A的后继结点（假设A存在后继结点），则需修改指针的操作为（）。 【解答】p->next=(p->next)->next ⑷单链表中设置头结点的作用是（）。 【解答】为了运算方便 【分析】例如在插入和删除操作时不必对表头的情况进行特殊处理。 ⑸非空的单循环链表由头指针head指示，则其尾结点（由指针p所指）满足（）。 【解答】p->next=head 【分析】如图2-8所示。 ⑹在由尾指针rear指示的单循环链表中，在表尾插入一个结点s的操作序列是（）；删除开始结点的操作序列为（）。 【解答】s->next =rear->next; rear->next =s; rear =s; q=rear->next->next; rear->next->next=q->next; delete q; 【分析】操作示意图如图2-9所示： ⑺一个具有n个结点的单链表，在指针p所指结点后插入一个新结点的时间复杂度为（）；在给定值为x的结点后插入一个新结点的时间复杂度为（）。 【解答】Ο(1)，Ο(n) 【分析】在p所指结点后插入一个新结点只需修改指针，所以时间复杂度为Ο(1)；而在给定值为x的结点后插入一个新结点需要先查找值为x的结点，所以时间复杂度为Ο(n)。 ⑻可由一个尾指针唯一确定的链表有（）、（）、（）。 【解答】循环链表，循环双向链表，双向链表 2. 选择题 第2章线性表 一、选择题 1.表长为N 的顺序表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均次数为（），删 除一个元素需要移动的元素个数为（）。【＊＊，★】 A. (N-1)/2 B. N C. N+1 D. N-1 E. N/2 F. (N+1)/2 G. (N-2)/2 2.线性表是具有N 个（）的有限序列。【＊】 A、表元素 B、字符 C、数据元素 D、数据项 E、信息 3.“线性表的逻辑顺序和物理顺序总是一致的。”这个结论是（）。【＊】 A、正确的 B、错误的 C、不一定，与具体结构有关。 4.线性表采用链式存储结构时，要求内存中可用存储单元的地址（）。【＊，★】 A、必须是连续的 B、部分地址必须是连续的 C、一定是不连续的 D、连续或不连续都可以。 5.带头结点的单链表为空的判定条件是（）。【＊】 A、head==NULL B、head->next==NULL C、head->next==head D、head!=NULL 6.不带头结点的单链表head 为空的判定条件是（）。【＊】 A、head==NULL B、head->next==NULL C、head->next==head D、head!=NULL 7.非空的循环单链表head 的尾结点P 满足（）。（注:带头结点）【＊】 A、P->NEXT=NULL B、p=NULL C、p->next==head D、p==head 8.在一个具有n 个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（）。【＊，★】 A、O(1) B、O(n) C、O(n2) D、O(nlog2n) 9.在一个单链表中，若删除P 所指结点的后继结点，则执行（）。【＊，★】 A、p->next=p->next->next B、p=p->next;p->next=p->next->next C、p->next=p->next; D、p=p->next->next; 10.在一个单链表中，若在Ｐ所指结点之后插入Ｓ所指结点，则执行（）。【＊，★】 《数据结构》 第二章线性表习题 一、单项选择题 1. 线性表是________。 A．一个有限序列，可以为空B．一个有限序列，不可以为空 C．一个无限序列，可以为空D．一个无限序列，不可以为空 2. 在一个长度为n的顺序表中删除第i个元素(0<=i<=n)时，需向前移动个元素。 A．n-i B．n-i+l C．n-i-1 D．i 3. 线性表采用链式存储时，其地址________。 A．必须是连续的B．一定是不连续的 C．部分地址必须是连续的D．连续与否均可以 4. 从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较________个元素结点。 A．n/2 B．n C．（n+1）/2 D．（n-1）/2 5. 在双向循环链表中，在p所指的结点之后插入s指针所指的结点，其操作是____。 A． p->next=s; s->prior=p; p->next->prior=s; s->next=p->next; B． s->prior=p; s->next=p->next; p->next=s; p->next->prior=s; C． p->next=s; p->next->prior=s; s->prior=p; s->next=p->next; D． s->prior=p; s->next=p->next; p->next->prior=s; p->next=s; 6. 设单链表中指针p指向结点m，若要删除m之后的结点（若存在），则需修改指针的操作为________。A．p->next=p->next->next; B．p=p->next; C．p=p->next->next; D．p->next=p; 7. 在一个长度为n的顺序表中向第i个元素(0< i 数据结构练习题 习题1 绪论 1.1 单项选择题 1. 数据结构是一门研究非数值计算的程序设计问题中,数据元素的①、数据信息在计算机中的②以及一组相关的运算等的课程。 ① A．操作对象Ｂ．计算方法Ｃ．逻辑结构Ｄ．数据映象 ② A．存储结构Ｂ．关系Ｃ．运算Ｄ．算法 2. 数据结构DS(Data Struct)可以被形式地定义为DS=（D，R），其中D是①的有限集合，R是D上的②有限集合。 ① A．算法Ｂ．数据元素Ｃ．数据操作Ｄ．数据对象 ② A．操作Ｂ．映象Ｃ．存储Ｄ．关系 3. 在数据结构中，从逻辑上可以把数据结构分成。 A．动态结构和静态结构Ｂ．紧凑结构和非紧凑结构 Ｃ．线性结构和非线性结构Ｄ．内部结构和外部结构 4. 算法分析的目的是①，算法分析的两个主要方面是②。 ① A. 找出数据结构的合理性 B. 研究算法中的输入和输出的关系 C. 分析算法的效率以求改进 D. 分析算法的易懂性和文档性 ② A. 空间复杂性和时间复杂性 B. 正确性和简明性 C. 可读性和文档性 D. 数据复杂性和程序复杂性 5. 计算机算法指的是①，它必具备输入、输出和②等五个特性。 ① A. 计算方法 B. 排序方法 C. 解决问题的有限运算序列 D. 调度方法 ② A. 可行性、可移植性和可扩充性 B. 可行性、确定性和有穷性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和安全性 1.2 填空题（将正确的答案填在相应的空中） 1. 数据逻辑结构包括、和三种类型，树形结构和图形结构合称为。 2. 在线性结构中，第一个结点前驱结点，其余每个结点有且只有个前驱结点；最后一个结点后续结点，其余每个结点有且只有个后续结点。 3. 在树形结构中，树根结点没有结点，其余每个结点有且只有个直接前驱结点，叶子结点没有结点，其余每个结点的直接后续结点可以。 4. 在图形结构中，每个结点的前驱结点数和后续结点数可以。 5. 线性结构中元素之间存在关系，树形结构中元素之间存在关系，图形结构中元素之间存在关系。 6. 算法的五个重要特性是__ __ , __ __ , ___ _ , __ __ , _ ___。 7. 分析下面算法（程序段），给出最大语句频度，该算法的时间复杂度是__ __。 for (i=0;i 第2章自测卷答案 一、填空 1. 【严题集 2.2①】在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与表长和该元素在表中的位置有关。 2. 线性表中结点的集合是有限的，结点间的关系是一对一的。 3. 向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动n-i+1 个元素。 4. 向一个长度为n的向量中删除第i个元素(1≤i≤n)时，需向前移动n-i 个元素。 5. 在顺序表中访问任意一结点的时间复杂度均为O(1)，因此，顺序表也称为随机存取的数据结构。 6. 【严题集2.2①】顺序表中逻辑上相邻的元素的物理位置必定相邻。单链表中逻辑上相邻的元素的物理位置不一定相邻。 7. 【严题集2.2①】在单链表中，除了首元结点外，任一结点的存储位置由其直接前驱结点的链域的值指示。 8．在n个结点的单链表中要删除已知结点*p，需找到它的前驱结点的地址，其时间复杂度为O（n）。二、判断正误（在正确的说法后面打勾，反之打叉） （×）1. 链表的每个结点中都恰好包含一个指针。 答：错误。链表中的结点可含多个指针域，分别存放多个指针。例如，双向链表中的结点可以含有两个指针 域，分别存放指向其直接前趋和直接后继结点的指针。 （×）2. 链表的物理存储结构具有同链表一样的顺序。错，链表的存储结构特点是无序，而链表的示意图有序。（×）3. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。错，链表的结点不会移动，只是指针内容改变。 （×）4. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。 错，混淆了逻辑结构与物理结构，链表也是线性表！且即使是顺序表，也能存放记录型数据。 （×）5. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 错，正好说反了。顺序表才适合随机存取，链表恰恰适于“顺藤摸瓜” （×）6. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。 错，前一半正确，但后一半说法错误，那是链式存储的优点。顺序存储方式插入、删除运算效率较低， 在表长为n的顺序表中，插入和删除一个数据元素，平均需移动表长一半个数的数据元素。 （×）7. 线性表在物理存储空间中也一定是连续的。 错，线性表有两种存储方式，顺序存储和链式存储。后者不要求连续存放。 （×）8. 线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。 错误。线性表有两种存储方式，在顺序存储时，逻辑上相邻的元素在存储的物理位置次序上也相邻。（×）9. 顺序存储方式只能用于存储线性结构。 错误。顺序存储方式不仅能用于存储线性结构，还可以用来存放非线性结构，例如完全二叉树是属于 非线性结构，但其最佳存储方式是顺序存储方式。（后一节介绍） （×）10. 线性表的逻辑顺序与存储顺序总是一致的。 错，理由同7。链式存储就无需一致。 三、单项选择题 （C）1．数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为：（A）存储结构（B）逻辑结构（C）顺序存储结构（D）链式存储结构（ B ）2.一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（A）110 （B）108 （C）100 （D）120 （ A ）3. 在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是： （A）访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n） （B）在第i个结点后插入一个新结点（1≤i≤n） 数据结构练习题第二章线性表习题及答案 第二章线性表 一．名词解释 1. 线性结构 2.数据结构的顺序实现 3.顺序表 4.链表 5.数据结构的链接实现 6. 建表 7.字符串 8.串 9.顺序串 10.链串 二、填空题 1.为了便于讨论，有时将含n(n>=0)个结点的线性结构表示成(a1， a2,……an)，其中每 个ai代表一个______。a1称为______结点，an称为______结点，i称为ai在线性表中的________ 或______。对任意一对相邻结点ai、ai┼1(1<=i 9.顺序表的类型定义可经编译转换为机器级。假定每个datatype类型的变量占用k(k>=1)个内存单元，其中，b是顺序表的第一个存储结点的第一个单元的内存地址，那么，第i个结点ai的存储地址为______。 10.以下为顺序表的插入运算，分析算法，请在______处填上正确的语句。 Void insert_sqlist(sqlist L，datatype x，int i) /*将X插入到顺序表L的第i-1个位置*/ { if( https://www.doczj.com/doc/0119479554.html,st == maxsize) error(“表满”)； if((i<1)||(i>https://www.doczj.com/doc/0119479554.html,st+1))error(“非法位置”); for(j=https://www.doczj.com/doc/0119479554.html,st;j>=i;j--)______; L.data[i-1]=x; https://www.doczj.com/doc/0119479554.html,st=https://www.doczj.com/doc/0119479554.html,st+1; } 11.对于顺序表的插入算法insert_sqlist来说，若以结点移动为标准操作，则插入算法的最坏时间复杂性为________，量级是________。插入算法的平均时间复杂性为________，平均时间复杂性量级是________。 12.以下为顺序表的删除运算，分析算法，请在________处填上正确的语句。 void delete_sqlist(sqlist L,int i) /*删除顺序表L中的第i-1个位置上的结点*/ {if((i<1)||(i>https://www.doczj.com/doc/0119479554.html,st))e rror(“非法位置”)； for(j=i+1;j=https://www.doczj.com/doc/0119479554.html,st;j++)________; https://www.doczj.com/doc/0119479554.html,st=https://www.doczj.com/doc/0119479554.html,st-1; } 2.7 习题 2.7.1知识点：线性表的逻辑结构 一、选择题 1①线性表L=（a 1, a 2 ,…,a n ）,下列说法正确的是（D ）。 A．每个元素都有一个直接前驱和一个直接后继。 B．线性表中至少要有一个元素。 C．表中诸元素的排列顺序必须是由小到大或由大到小。 D．除第一个和最后一个元素外,其余每个元素都有一个且仅有一个直接前驱和直接后继。 2①在线性表的下列运算中，不改变数据元素之间结构关系的运算是（D ）。 A．插入B．删除 C．排序D．定位 3①线性表是具有n 个（C ）的有限序列（n>0）。【清华大学1998】 A．表元素B．字符C．数据元素D．数据项E．信息项 二、判断题 （T ）1①线性表中的每个结点最多只有一个前驱和一个后继。 （ F ）2①线性表中的每个结点都至少有一个前驱结点和后继结点。 （ F ）3①线性表是N个数的有限序列。 （F）4①同一线性表的数据元素可以具有不同的特性。 （T ）5①线性表的长度n就是表中数据元素的个数，当n=0时，称为空表。 （T ）6①线性表是一个相当灵活的数据结构，它的长度可根据需要增长或缩短。 （ F ）7①对线性表中的数据元素只能进行访问，不能进行插入和删除操作。 2.7.2知识点：线性表的顺序存储结构 一、选择题 1①在一个长度为n的顺序表中，在第i个元素（1 <= i <=n+1）之前插入一个新元素时需向后移动（ B ）个元素． A．n-1 B．n-i+1 C．n-i-1 D．i 2①若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（D ）存储方式最节省时间。 A．单链表B．双链表C．单向循环D．顺序表 3②一个数组第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（B ） A．110 B．108 C．100 D．120 4①下述哪一条是顺序存储结构的优点（ A ）。【北方交通大学2001】 A．存储密度大B．插入运算方便 一、选择题 1、用单链表方式存储的线性表，存储每个结点需要两个域，一个是数据域，另一个是（） A、当前结点所在的地址域 B、指针域 C、空指针域 D、空闲域 2、不带头结点的单链表head为空的判断条件是（） A、head==NULL B、head->next==NULL C、head->data==NULL D、head!=NULL 3、在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在p和q之间插入s结点，则执行（） A、s->next=p; q->next=s; B、p->next=s->next; s->next=p; C、q->next=s->next; s->next=p; D、p->next=s; s->next=q; 4、在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（） A、O（1） B、O（n） C、O（n2） D、O（nlog2n） 5、一个单链表中，若删除p所指结点的后续结点，则执行（） A、p->next=p->next->next; B、p=p->next; p->next=p->next->next; C、p->next=p; D、p=p->next->next; 6、已知一个顺序存储的基本线性表，设每个结点需占m个存储单元，若第一个结点的地址为d1，则第i个结点的地址为（） A、d1+(i-1)*m B、d1+i*m C、d1-i*m D、d1+(i+1)*m 7、在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是（） A、访问第i个结点(1<=i<=n)和求第i个结点的直接前驱(2<=i<=n) B、在第i个结点后插入一个新结点(1<=i<=n) C、删除第i个结点(1<=i<=n) D、将n个结点从小到大排序 8、下面给出的算法段是要把一个q所指新结点作为非空双向链表中的p所指结点的前驱结点插入到该双向链表中，能正确完成要求的算法段是（） A、q->next=p; q->prior=p->prior; p->prior=q; p->prior->next=q; B、p->prior=q; q->next=p; p->prior->next=q; q->prior=p->prior; 第二章线性表 一、选择题 1.一个线性表第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是( ) （A）110 （B）108（C）100 （D）120 参考答案：B 2. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（）个元素。 （A）64（B）63 （C）63.5 （D）7 参考答案：C 3.线性表采用链式存储结构时，其地址（）。 (A) 必须是连续的 (B) 部分地址必须是连续的 (C) 一定是不连续的 (D) 连续与否均可以 参考答案：D 4. 在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行（） （A）s->next=p;p->next=s; （B） s->next=p->next;p->next=s; （C）s->next=p->next;p=s; （D）p->next=s;s->next=p; 参考答案：B 5.在一个单链表中，若删除p所指结点的后续结点，则执行（） （A）p->next=p->next->next; （B）p=p->next; p->next=p->next->next; （C）p->next=p->next; （D）p =p->next->next; 参考答案：A 6.下列有关线性表的叙述中，正确的是（） （A）线性表中的元素之间隔是线性关系 （B）线性表中至少有一个元素 （C）线性表中任何一个元素有且仅有一个直接前趋 （D）线性表中任何一个元素有且仅有一个直接后继 参考答案：A 7.线性表是具有n个（）的有限序列（n≠0) （A）表元素（B）字符（C）数据元素（D）数据项 参考答案：C 二、判断题 1.线性表的链接存储，表中元素的逻辑顺序与物理顺序一定相同。（） 2.如果没有提供指针类型的语言，就无法构造链式结构。（） 3.线性结构的特点是只有一个结点没有前驱，只有一个结点没有后继，其余的结点只有一个前驱和后继。（） 4.语句p=p->next完成了指针赋值并使p指针得到了p指针所指后继结点的数据域值。（） 5.要想删除p指针的后继结点，我们应该执行q=p->next ； p->next=q->next；free(q)。（） 参考答案：1、×2、√3、×4、×5、√ 三、填空题 1.已知P为单链表中的非首尾结点，在P结点后插入S结点的语句为： _______________________ 。 s->next=p->next; p->next=s; 2.顺序表中逻辑上相邻的元素物理位置( )相邻，单链表中逻辑上相邻的元素物理位置_________相邻。 一定；不一定 3.线性表L＝（a1，a2，...，an）采用顺序存储，假定在不同的n＋1个位置上插入的概率相同，则插入一个新元素平均需要移动的元素个数是________________________ n/2 4.在非空双向循环链表中，在结点q的前面插入结点p的过程如下： p->prior=q->prior; q->prior->next=p; p->next=q; ______________________; q->prior=p; 第 2 章线性表 课后习题讲解 1. 填空 ⑴在顺序表中，等概率情况下，插入和删除一个元素平均需移动（）个元素，具体移动元素的个数与（）和（）有关。 【解答】表长的一半，表长，该元素在表中的位置 ⑵顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的存储地址是（）。【解答】108 【分析】第5个元素的存储地址=第1个元素的存储地址＋(5－1)×2=108 ⑶设单链表中指针p 指向结点A，若要删除A的后继结点（假设A存在后继结点），则需修改指针的操作为（）。 【解答】p->next=(p->next)->next ⑷单链表中设置头结点的作用是（）。 【解答】为了运算方便 【分析】例如在插入和删除操作时不必对表头的情况进行特殊处理。 ⑸非空的单循环链表由头指针head指示，则其尾结点（由指针p所指）满足（）。 【解答】p->next=head 【分析】如图2-8所示。 ⑹在由尾指针rear指示的单循环链表中，在表尾插入一个结点s的操作序列是（）；删除开始结点的操作序列为（）。 【解答】s->next =rear->next; rear->next =s; rear =s; q=rear->next->next; rear->next->next=q->next; delete q; 【分析】操作示意图如图2-9所示： ⑺一个具有n个结点的单链表，在指针p所指结点后插入一个新结点的时间复杂度为（）；在给定值为x的结点后插入一个新结点的时间复杂度为（）。 【解答】Ο(1)，Ο(n) 【分析】在p所指结点后插入一个新结点只需修改指针，所以时间复杂度为Ο(1)；而在给定值为x的结点后插入一个新结点需要先查找值为x的结点，所以时间复杂度为Ο(n)。 ⑻可由一个尾指针唯一确定的链表有（）、（）、（）。 【解答】循环链表，循环双链表，双链表 2. 选择题 ⑴线性表的顺序存储结构是一种（）的存储结构，线性表的链接存储结构是一种（）的存储结构。 A 随机存取 B 顺序存取 C 索引存取 D 散列存取 【解答】A，B 【分析】参见2.2.1。 ⑵线性表采用链接存储时，其地址（）。 A 必须是连续的 B 部分地址必须是连续的 C 一定是不连续的 D 连续与否均可以 【解答】D 【分析】线性表的链接存储是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以连续，也可以不连续，甚至可以零散分布在内存中任意位置。 ⑶单循环链表的主要优点是（）。 A 不再需要头指针了 B 从表中任一结点出发都能扫描到整个链表； C 已知某个结点的位置后，能够容易找到它的直接前趋； D 在进行插入、删除操作时，能更好地保证链表不断开。 【解答】B ⑷链表不具有的特点是（）。 A 可随机访问任一元素 B 插入、删除不需要移动元素 C 不必事先估计存储空间 D 所需空间与线性表长度成正比 【解答】A ⑸若某线性表中最常用的操作是取第i 个元素和找第i个元素的前趋，则采用（）存储方法最节省时间。 A 顺序表 B 单链表 C 双链表 D 单循环链表 【解答】A 【分析】线性表中最常用的操作是取第i 个元素，所以，应选择随机存取结构即顺序表，同时在顺序表中查找第i个元素的前趋也很方便。单链表和单循环链表既不能实现随机存取，查找第i个元素的前趋也不方便，双链表虽然能快速查找第i个元素的前趋，但不能实现随机存取。 ⑹若链表中最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点，则采用（）存储方法最节省时间。 A 单链表 B 带头指针的单循环链表 C 双链表 D 带尾指针的单循环链表 数据结构第二章习题解答 一、单选题 1．在一个长度为n的顺序存储线性表中，向第i个元素(1≤i≤n+1)之前插入一个新元素时，需要从后向前依次后移（B）个元素。 A、n-i B、n-i+1 C、n-i-1 D、i 2．在一个长度为n的顺序存储线性表中，删除第i个元素(1≤i≤n+1)时，需要从前向后依次前移（A）个元素。 A、n-i B、n-i+1 C、n-i-1 D、i 3. 在一个长度为n的线性表中顺序查找值为x的元素时，在等概率情况下，查找成功时的平均查找长度（即需要比较的元素个数）为( C )。 A. n B. n/2 C. (n+1)/2 D. (n-1)/2 4．在一个长度为n的线性表中，删除值为x的元素时需要比较元素和移动元素的总次数为(C )。 A. (n+1)/2 B. n/2 C. n D. n+1 5. 在一个顺序表的表尾插入一个元素的时间复杂度为(B )。 A. O(n) B. O(1) C. O(n*n) D. O(log2n) 6.若一个结点的引用为p，它的前驱结点的引用为q，则删除p的后继结点的操作为(B )。 A. p=p.next.next B. p.next=p.next.next C. q.next=p.next D. q.next=q.next.next 8. 假定一个多项式中x的最高次幂为n，则在保存所有系数项的线性表表示中，其线性表长度为(A )。 A. n+1 B. n C. n-1 D. n+2 二、填空题 1．对于当前长度为n的线性表，共包含有________多个插入元素的位置，共包含有________多个删除元素的位置。（答案n+1 n） 2．若经常需要对线性表进行表尾插入和删除运算，则最好采用________存储结构，若经 常需要对线性表进行表头插入和删除运算，则最好采用________存储结构。（答案：顺序链式） 3．由n个元素生成一个顺序表，若每次都调用插入算法把一个元素插入到表头，则整个算法的时间复杂度为________，若每次都调用插入算法把一个元素插入到表尾，则整个算法的时间复杂度为________。（答案：O（n）O（n）） 4．由n个元素生成一个单链表，若每次都调用插入算法把一个元素插入到表头，则整个算法的时间复杂度为________，若每次都调用插入算法把一个元素插入到表尾，则整个算法的时间复杂度为________。（答案：O（1）O（1）） 5. 对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为________， 在表尾插入元素的时间复杂度为________。（答案：O（n），O（1）） 6. 对于一个单链接存储的线性表，在表头插入结点的时间复杂度为________，在表尾插 入结点的时间复杂度为________。（答案：O（1），O（1）） 7. 从一个顺序表和单链表中访问任一个给定位置序号的元素（结点）的时间复杂度分别 为________和_______。（答案：O（1），O（n）） 三、算法设计题 1. 修改从顺序存储的集合中删除元素的算法，要求当删除一个元素后检查数组空间的大小，若空间利用率小于40%同时数组长度大于maxSize时则释放数组的一半存储空间。public void remove(int i) throws Exception{ 习题 2.1选择题 1、线性表的顺序存储结构是一种（A）的存储结构，线性表的链式存储结构是一种（B）的存储结构。 A、随机存取 B、顺序存取 C、索引存取 D、散列存取 2、对于一个线性，既要求能够进行较快的插入和删除，又要求存储结构能够反映数据元素之间的逻辑关系，则应该选择（B）。 A、顺序存储方式 B、链式存储方式 C、散列存储方式 D、索引存储方式 3、已知，L是一个不带头结点的单链表，p指向其中的一个结点，选择合适的语句实现在p结点的后面插入s结点的操作（B）。 A、p->next=s ; s->next=p->next ; B、s->next=p->next ; p->next=s ; C、p->next=s ; s->next=p ; D、s->next=p ; p->next=s ; 4、单链表中各结点之间的地址（ C D）。 A、必须连续 B、部分地址必须连续 C、不一定连续 D、连续与否都可以 5、在一个长度为n的顺序表中向第i个元素（0 精品文档 第二章线性表 一．名词解释 1.线性结构 2.数据结构的顺序实现 3.顺序表 4.链表 5.数据结构的链接实现 6. 建表 7.字符串 8.串 9.顺序串 10.链串 二、填空题 1.为了便于讨论，有时将含n(n>=0)个结点的线性结构表示成(a，a,……a)，其中每n12个a代表一个______。a称为______结点，a称为______结点，i称为a在线性表中的________ii1n或______。对任意一对相邻结点a、a(1<=i数据结构第2章作业 线性表(答案)
数据结构习题及答案与实验指导(线性表)2
数据结构第2章习题及答案
数据结构第2章习题兼解答
《数据结构》习题及答案：第2章 线性表(第1次更新3)
《数据结构》第二章线性表习题及参考答案
数据结构练习题(含答案)
数据结构第2章线性表习题及答案
数据结构练习题 第二章 线性表 习题及答案
数据结构第2章习题参考答案
数据结构第二章 线性表练习及答案
数据结构习题及答案 (2)
数据结构(C++版)课后答案 (王红梅)第2章 线性表
《数据结构》吕云翔编著第2章线性表习题解答
数据结构(C语言版)习题及答案第二章
数据结构练习题线性表习题及答案
相关主题
文本预览