数据结构第二章线性表

数据结构第二章课后答案数据结构第二章课后答案1. 线性表1.1 数组实现线性表Q1. 请说明线性表的定义，并结合数组实现线性表的特点进行解释。

线性表是由n(n≥0)个数据元素构成的有序序列，其中n表示线性表的长度。

数组实现线性表的特点是使用一组具有相同数据类型的连续存储空间存储线性表中的元素，通过下标访问和操作元素。

A1. 线性表的定义指出，线性表是由若干个数据元素组成的有序序列。

具体地，在数组实现线性表中，我们将元素存储在一组连续的内存空间中，通过下标访问和操作元素。

由于数组的存储空间具有连续性，这样的实现方式可以在O(1)的时间复杂度下进行元素的访问和修改操作。

1.2 链表实现线性表Q2. 请说明链表实现线性表的特点，并与数组实现进行比较。

链表实现线性表的特点是通过指针将线性表中的元素按照节点的形式连接起来，每个节点包含了存储的元素和指向下一个节点的指针。

与数组实现相比，链表的插入和删除操作更为高效，但是访问某个位置的元素需要从头开始遍历，时间复杂度较大。

A2. 链表实现线性表的特点是通过使用节点和指针将线性表中的元素连接起来。

每个节点中包含了一个存储的元素和指向下一个节点的指针。

链表的插入和删除操作的时间复杂度为O(1)，因为只需要改变指针的指向即可。

但是，访问某个位置的元素需要从头开始遍历链表，所以时间复杂度为O(n)。

2. 栈和队列2.1 栈的定义和基本操作Q3. 请给出栈的定义和基本操作。

栈是一种特殊的线性表，它只能在表的一端进行插入和删除操作，该端称为栈顶。

栈的基本操作包括入栈(push)和出栈(pop)，分别用于将元素压入栈和将栈顶元素弹出。

A3. 栈是一种特殊的线性表，它只能在表的一端进行插入和删除操作。

这个特定的一端称为栈顶，而另一端称为栈底。

栈的基本操作包括入栈(push)和出栈(pop)。

入栈操作将一个元素压入栈顶，出栈操作将栈顶元素弹出。

2.2 队列的定义和基本操作Q4. 请给出队列的定义和基本操作。

第 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、线性结构反映结点间的逻辑关系是一对一的。

2、线性结构的特点：1）只有一个首结点和尾结点2）除首尾结点外，其他结点只有一个直接前驱和一个直接后继3、线性表的顺序表示又称为顺序存储结构。

4、结点只有一个指针域的链表，称为单链表。

5、首尾相接的链表称为循环链表。

6、线性表的链式表示又称为非顺序映像。

7、指向链表中第一个结点的指针称为头指针。

8、链表中存储第一个数据元素的结点称为首元结点。

二、判断题1、线性表的逻辑顺序与存储顺序总是一致的。

（╳）2、顺序存储的线性表可以按序号随机存取。

（√）3、顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。

（╳）4、线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此属于同一数据对象。

（√）5、在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定相邻。

（╳）6、在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。

（√）7、线性表的链式存储结构优于顺序存储结构。

（╳）8、在线性表的顺序存储结构中，插入和删除时移动元素的个数与该元素的位置有关。

（√）9、线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。

（√）10、在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。

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

（╳）三、单项选择题1、顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（B）。

A．110 B．108 C．100 D．120解释：顺序表中的数据连续存储，所以第5个元素的地址为：100+2*4=108。

2、在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是（A）。

A．访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）B．在第i个结点后插入一个新结点（1≤i≤n）C．删除第i个结点（1≤i≤n）D．将n个结点从小到大排序解释：在顺序表中插入一个结点的时间复杂度都是O(n2)，排序的时间复杂度为O(n2)或O(nlog2n)。

数据结构第二章线性表1答案第二部分线性表一、选择题1．关于顺序存储的叙述中,哪一条是不正确的( B )A.存储密度大B.逻辑上相邻的结点物理上不必邻接C.可以通过计算直接确定第i个结点的位置D.插入、删除操作不方便2．长度为n的单链表连接在长度为m的单链表后的算法的时间复杂度为( C )A O(n)B O(1)C O(m)D O(m+n)3．在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是：( A )A 访问第i个结点（1<=i<=n）和求第i个结点的直接前趋（2<=i<=n）B 在第i个结点（1<=i<=n）后插入一个新结点C 删除第i个结点（1<=i<=n）D 将n个结点从小到大排序4．一个向量第一个元素的存储地址是100 ，每个元素的长度为2 ，则第5 个元素的地址是：( B )（A ）110 （ B ）108 （C ）100 （D ）1205．已知一个顺序存储的线性表，设每个结点需要占m个存储单元，若第一个结点的地址为da，则第i个结点的地址为：( A ) A）da+(i-1)*m B) da+i*m C) da-i*m D) da+(i+1)*m6．在具有n个结点的单链表中，实现（A ）的操作，其算法的时间复杂度为O(n)。

A）遍历链表和求链表的第i个结点B）在地址为p的结点之后插入一个结点C）删除开始结点D）删除地址为p的结点的后继结点7．链表是一种采用（B ）存储结构存储的线性表。

（A ）顺序（B ）链式（ C ）星式（D ）网状8．线性表若采用链式存储结构时，要求内存中可用存储单元的地址：（D ）（A ）必须是连续的（ B ）部分地址必须是连续的（C ）一定是不连续的（ D ）连续或不连续都可以9．线性表Ｌ在（B ）情况下适用于使用链式结构实现。

（Ａ）需经常修改Ｌ中的结点值（Ｂ）需不断对Ｌ进行删除插入（Ｃ）Ｌ中含有大量的结点（Ｄ）Ｌ中结点结构复杂10．在长度为n 的顺序表的第i (1≤i≤n+1) 个位置上插入一个元素，元素的移动次数为( A )A.n-i+1B.n-iC.iD.i-111．线性表是（A）。

第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. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。

第二章线性表2.1描述以下三个概念的区别：头指针，头结点，首元结点（第一个元素结点）。

并说明头指针和头结点的作用。

答：头指针是一个指针变量，里面存放的是链表中首结点的地址，并以此来标识一个链表。

如链表H，链表L等，表示链表中第一个结点的地址存放在H、L中。

头结点是附加在第一个元素结点之前的一个结点，头指针指向头结点。

当该链表表示一个非空的线性表时，头结点的指针域指向第一个元素结点，为空表时，该指针域为空。

开始结点指第一个元素结点。

头指针的作用是用来惟一标识一个单链表。

头结点的作用有两个：一是使得对空表和非空表的处理得以统一。

二是使得在链表的第一个位置上的操作和在其他位置上的操作一致，无需特殊处理。

2.2填空题1、在顺序表中插入或删除一个元素，需要平均移动（表中一半）元素，具体移动的元素个数与（表长和该元素在表中的位置）有关。

2、顺序表中逻辑上相邻的元素的物理位置（必定）相邻。

单链表中逻辑上相邻的元素的物理位置（不一定）相邻。

3、在单链表中，除了首元结点外，任一结点的存储位置由（其直接前驱结点的链域的值）指示。

4、在单链表中设置头结点的作用是（插入和删除元素不必进行特殊处理）。

2.3何时选用顺序表、何时选用链表作为线性表的存储结构为宜?答：在实际应用中，应根据具体问题的要求和性质来选择顺序表或链表作为线性表的存储结构，通常有以下几方面的考虑：1.基于空间的考虑。

当要求存储的线性表长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表；反之，当线性表长度变化大，难以估计其存储规模时，采用动态链表作为存储结构为好。

2.基于时间的考虑。

若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜；反之，若需要对线性表进行频繁地插入或删除等的操作时，宜采用链表做存储结构。

并且，若链表的插入和删除主要发生在表的首尾两端，则采用尾指针表示的单循环链表为宜。

2.10 Status DeleteK(SqList &a,int i,int k)//删除线性表a中第i个元素起的k个元素{if(i<1||k<0||i+k-1>a.length) return INFEASIBLE;for(count=1;i+count-1<=a.length-k;count++) //注意循环结束的条件a.elem[i+count-1]=a.elem[i+count+k-1];a.length-=k;return OK;}//DeleteK2.11设顺序表中的数据元素递增有序，试写一算法，将X插入到顺序表的适当位置上，以保持该表的有序性。

数据结构与算法华东师范大学计算机系杨沛第二章线性表2.1 线性表的基本概念线性表是具有相同数据类型的数据元素的有限序列。

由n（n≥0）个数据元素k0,k1,…,kn-1组成的线性表记为（k0 ,k1 ,…,kn-1），线性表中包含的数据元素的个数n称为线性表的长度（length），称长度为零的线性表为空的线性表（简称为空表）。

相关概念：表头、表尾、前驱、后继有序线性表：数据元素的相对位置与它们的值有联系。

无序线性表：数据元素的相对位置与它们的值没有联系。

第二章线性表例小于20的质数组成的线性表(2,3,5,7,11,13, 17,19)；英文字母表也是线性表，表中每个字母是一个数据元素：(A,B,C,……,Z)；2.2 顺序表2.2.1 线性表顺序表（sequential list）就是顺序存贮的线性表，即用一组连续的存贮单元依次、连续地存贮线性表中的结点。

如果每个结点占用s个存贮单元，并假设存放结点ki（0≤i≤n-1）的开始地址为loc(k0)，则结点ki的地址loc(ki)可表示成Loc(ki) =loc(k0) + i*s。

2.2 顺序表在C 语言中，可用数组表示线性表：#define MAXN 100int list[MAXN];int n;线性表的结点k 0,k 1,…,k n-1依次存放在数组单元list[0]，list[1]，…，list[n-1]。

2.2.1 线性表最大表长实际表长线性表2.2 顺序表2.2.1 线性表假设s=sizeof(int)，则可得到计算ki的地址的公式，因loc(ki)=&list[i]，而&list[i]=&list[0]+i·s，故loc(ki)=&list[0]+i·s。

2.2 顺序表2.2.2 顺序表的操作（1）初始化：初始长度置为0即可（n=0;），数组空间在编译时分配。

（2)顺序表的插入：插入算法的C函数SqListInsert()：若插入位置i不在可以插入的位置上，即i＜0或i>n，则返回0；若n=MAXN，即线性表已满，此时数组list[]没有多余的存贮单元可以存放新结点，则返回-1；若插入成功，则返回12.2 顺序表实际表长（2）顺序表的插入：int SqListInsert(int list[],int*p_n,int i,int x) {int j;if(i<0||i>*p_n）return(0);//i不是合法的插入位置if(*p_len==MAXN)return(-1);//线性表已满2.2 顺序表for(j=*p_n;j>i;j--)list[j]=list[j-1];//结点右移list[i]=x;(*p_n)++;//表长加1return(1);｝2.2 顺序表（2）顺序表的插入：对于存放在数组list[]中的、具有n个结点的顺序表，为了把值为x的结点插在表的位置i（0≤i≤n）上，可调用如下的语句：k=SqListInsert(list, &n, i, x);注：结点移动是本算法的关键操作2.2 顺序表（3）顺序表的删除：删除算法的C函数SqListDelete()：在具有n个结点的顺序表中，删除第i（0≤i≤n-1）个位置上的结点，使线性表长度减1，若删除位置不合法，即i＜0或i≥n，则返回0；若删除位置合法，即0≤i≤n-1，则删除成功，返回1。