当前位置：文档之家› 数据结构第二章线性表

数据结构第二章线性表

基本信息：[矩阵文本题] *

1. 在长度为n的顺序表的第i（1≤i≤n+1）个位置上插入一个元素，元素的移动次数为 [单选题] *

A．n-i+1(正确答案)

B．n-i

C．i

D．i-1

2. 若一个顺序表中第一个元素的存储地址为1000，每个元素占4个地址单元，那么，第6个元素的存储地址应是 [单选题] *

A．1020(正确答案)

B．1010

C．1016

D．1024

3. 带头结点的单链表（以head为头指针）为空的判断条件是 [单选题] *

A．head!=NULL

B．head->next==head

C．head->next==NULL(正确答案)

D．head ==NULL

4. 将长度为n的单链表连接在长度为m的单链表之后，其算法的时间复杂度为 [单选题] *

A．O(1)

B．O(m)(正确答案)

C．O(n)

D．O(m+n)

5. 在一个单链表中，若删除p指向结点的后继结点，则执行的操作为 [单选题] * A．q=p->next；p->next=p->next->next；free(q)；(正确答案)

B．p=p->next；q=p->next；p=q->next；free(q)；

C．q=p->next->next；p=p->next；free(q)；

D．p=p->next->next；q=p->next；free(q)；

6. 线性表是一个有限序列，组成线性表的基本单位是 [单选题] *

A．数据项

B．数据元素(正确答案)

C．数据域

D．字符

7. 顺序表便于 [单选题] *

A．插入结点

B．删除结点

C．按值查找结点

D．按序号查找结点(正确答案)

8. 对需要频繁插入和删除结点的线性表，适合的存储方式是 [单选题] *

A．顺序储存

B．链式存储(正确答案)

C．索引存储

D．散列存储

9. 设带头结点的单循环链表的头指针为head，指针变量p指向尾结点的条件是 [单选题] *

A．p->next->next==head

B．p->next==head(正确答案)

C．p->next->next==NULL

D．p->next==NULL

10. 针对线性表逻辑上相邻的两个元素，下列叙述中，正确的是 [单选题] *

A．采用顺序存储时一定相邻，采用链式存储时也一定相邻

B．采用顺序存储时一定相邻，采用链式存储时不一定相邻(正确答案)

C．采用顺序存储时不一定相邻，采用链式存储时一定相邻

D．采用顺序存储时不一定相邻，采用链式存储时也不一定相邻

11. 线性表的逻辑顺序和存储顺序总是一致的。 [判断题] *

对

错(正确答案)

12. 线性表采用链式存储时，结点和结点内部的存储空间可以是不连续的。 [判断题] *

对(正确答案)

错

13. 对任何数据结构，链式存储结构一定优于顺序存储结构。 [判断题] *

对

错(正确答案)

14. 线性表的特点是每个元素都有一个前驱和一个后继。 [判断题] *

对

错(正确答案)

15. 在线性表中，结点的类型都是一样的，即每个结点占据的存储空间是一样的。[判断题] *

对(正确答案)

错

16. 顺序存储的插入和删除效率低。 [判断题] *

对(正确答案)

错

17. 在线性链表中删除结点时，只需要将被删结点释放，不需要修改任何指针。[判断题] *

对

错(正确答案)

18. 顺序存储的线性表可以实现随机存取。 [判断题] *

对(正确答案)

错

19. 循环链表不是线性表。 [判断题] *

对

错(正确答案)

20. 在带头结点的单循环链表中，任一结点的后继指针均不为空。 [判断题] *

对(正确答案)

错

数据结构整理完整版

第二章线性表一、顺序表和链表的优缺点 1.顺序表定义：用一组连续的存储单元（地址连续）依次存放线性表的各个数据元素。即：在顺序表中逻辑结构上相邻的数据元素，其物理位置也是相邻的。优点逻辑相邻，物理相邻可随机存取任一元素存储空间使用紧凑缺点插入、删除操作需要移动大量的元素（平均约需移动一半结点，当n很大时，算法的效率较低）预先分配空间需按最大空间分配，利用不充分表容量难以扩充 2.链式存储结构定义：由分别表示a1,a2,…,a i-1,a i,…,a n的N 个结点依次相链构成的链表，称为线性表的链式存储表示优势： (1)能有效利用存储空间；动态存储分配的结构，不需预先为线性表分配足够大的空间，而是向系统“随用随取”，在删除元素时可同时释放空间。 (2)用“指针”指示数据元素之间的后继关系，便于进行“插入”、“删除”等操作；插入或删除时只需要修改指针，而不需要元素移动。劣势： (1)不能随机存取数据元素； (2)丢失了一些顺序表的长处，如线性表的“表长”和数据元素在线性表中的 “位序”，在单链表中都看不见了。如，不便于在表尾插入元素，需遍历整个表才能找到插入的位置。二、单链表中删除一个节点和插入一个节点的语句操作，p29 1.插入元素操作算法基本思想：首先找到相应结点，然后修改相应指针。假定在a，b之间插入结点X，s指向X, p指向a，指针修改语句为： s->next=p->next; p->next =s;

2.删除元素操作算法基本思想:首先找到第i-1 个结点，然后修改相应指针。删除b结点，其中，P指向a，指针修改语句为：p->next=p->next->next；三、单链表的就地逆置习题集2.22 算法的基本思想：以单链表作存储结构进行就地逆置的正确做法应该是：将原链表的头结点和第一个元素结点断开（令其指针域为空），先构成一个新的空表，然后将原链表中各结点，从第一个结点起，依次插入这个新表的头部（即令每个插入的结点成为新的第一个元素结点）。算法思路：依次取原链表中的每个结点，将其作为第一个结点插入到新链表中去，指针p用来指向当前结点，p为空时结束。 void reverse (Linklist H){ LNode *p; p=H->next; /*p指向第一个数据结点*/ H->next=NULL; /*将原链表置为空表H*/ while (p){ q=p; p=p->next; q->next=H->next; /*将当前结点插到头结点的后面*/ H->next=q; } } 第三章栈和队列一、栈和队列的特性 1.特点栈必须按“后进先出”（LIFO）的规则进行操作，仅限在表尾进行插入和删除的操作。队列（FIFO）必须按“先进先出”的规则进行操作，队尾插入，队头删除。二、循环队列为空和满的判定方法，p63 队空条件：front == rear; 队满条件：(rear + 1) % maxSize == front

数据结构第2章作业线性表(答案)

第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章线性表线性表是一种最基本、最常用的数据结构，它有两种存储结构——顺序表和链表。本章主要介绍线性表的定义、表示和基本运算的实现。重点讨论了线性表的存储结构，以及在顺序、链式两种存储结构上基本运算的实现。重点提示： ●线性表的逻辑结构特征 ●线性表的顺序存储和链式存储两种存储结构的特点 ●在两种存储结构下基本操作的实现 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．头结点要点：附加在第一个元素结点之前的一个结点，头指针指向头结点。当该链表表示一个非空的线性表时，头结点的指针域指向第一个元素结点；为空表时，该指针域为空。

数据结构线性表

第1讲线性表本章主要掌握如下内容：线性表的定义和基本操作，线性表的实现,线性表的顺序存储结构及链式存储结构，线性表的应用。知识点分析（一）线性表的定义和基本操作 1．线性表基本概念 1）定义：是由相同类型的结点组成的有限序列。如：由n个结点组成的线性表（a1, a2, …, a n） a1是最前结点，a n是最后结点。结点也称为数据元素或者记录。 2）线性表的长度：线性表中结点的个数称为其长度。长度为0的线性表称为空表。 3）结点之间的关系：设线性表记为（a1,a2,…a i-1 , a i, a i+1 ,…a n），称a i-1是a i的直接前驱结点．．．．（简称前驱）， a i+1是a i的直接后继结点．．．．（简称后继）。 4）线性表的性质： ①线性表结点间的相对位置是固定．．的，结点间的关系由结点在表中的位置确定。 ②如果两个线性表有相同的数据结点，但它们的结点顺序不一致，该两个线性表也是不相等的。注意：线性表中结点的类型可以是任何数据（包括简单类型和复杂类型），即结点可以有多个成分，其中能唯一标识表元的成分称为关键字（key），或简称键。以后的讨论都只考虑键，而忽略其它成分，这样有利于把握主要问题，便于理解。『经典例题解析』线性表的特点是每个元素都有一个前驱和一个后继。( ) 【答案】错误。【解析】线性表的第一个数据元素没有前驱，最后一个元素没有后继。其余的所有元素都有一个前驱和后继。 2．线性表的抽象数据类型线性表是一个相当灵活的数据结构，其长度可以根据需要增加或减少。从操作上讲，用户不仅可以对线性表的数据元素进行访问操作，还可以进行插入、删除、定位等操作。 1）线性表的基本操作假设线性表L有数据对象 D＝{a i | a i ∈ElemSet，i=1,2,3,…,n，n>=0}, 数据元素之间的关系R＝{|a i-1 ,a i ∈D,i=1,2,…,n}, 则线性表L的基本操作如下所示： ●InitList(&L)：其作用是构造一个长度为0的线性表（空线性表）； ●DestoryList(&L)：其作用是销毁当前的线性表L； ●ClearList(&L)：清空线性表L，使之成为空表； ●ListLength(L)：返回线性表L的长度，即线性表中数据元素的个数； ●ListEmpty(L) ：判断线性表L是否为空表，是则返回True，否则返回False； ●GetElem(L,i,&e)：将线性表L中第i个数据元素的值返回到变量e中；