数据结构练习 第二章 线性表资料

第二章线性表一、选择题1.一个线性表第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是( )（A）110 （B）108（C）100 （D）120参考答案：B2. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（）个元素。

（A）64（B）63 （C）63.5 （D）7参考答案：C3.线性表采用链式存储结构时，其地址（）。

(A) 必须是连续的 (B) 部分地址必须是连续的(C) 一定是不连续的 (D) 连续与否均可以参考答案：D4. 在一个单链表中，若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;参考答案：B5.在一个单链表中，若删除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;参考答案：A6.下列有关线性表的叙述中，正确的是（）（A）线性表中的元素之间隔是线性关系（B）线性表中至少有一个元素（C）线性表中任何一个元素有且仅有一个直接前趋（D）线性表中任何一个元素有且仅有一个直接后继参考答案：A7.线性表是具有n个（）的有限序列（n≠0)（A）表元素（B）字符（C）数据元素（D）数据项参考答案：C二、判断题1.线性表的链接存储，表中元素的逻辑顺序与物理顺序一定相同。

（）2.如果没有提供指针类型的语言，就无法构造链式结构。

（）3.线性结构的特点是只有一个结点没有前驱，只有一个结点没有后继，其余的结点只有一个前驱和后继。

第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．顺序表顺序存储的线性表称为顺序表。

其特点是：用一组地址连续的存储单元来依次存放线性表的数据元素，因此数据元素的逻辑顺序和物理次序一致（这是顺序存储的核心所在）。

一、选择题1、用单链表方式存储的线性表，存储每个结点需要两个域，一个是数据域，另一个是（）A、当前结点所在的地址域B、指针域C、空指针域D、空闲域2、不带头结点的单链表head为空的判断条件是（）A、head==NULLB、head->next==NULLC、head->data==NULLD、head!=NULL3、在一个单链表中，已知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)*mB、d1+i*mC、d1-i*mD、d1+(i+1)*m7、在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;C、q->prior=p->prior; q->next=p; p->prior->next=q; p->prior=q;D、以上都不对9、在循环双链表的p所指结点之后插入s所指结点的操作是（）A、p->next=s; s->prior=p; p->next->prior=s; s->next=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; p->next->prior=s; s->next=p->next; p->next=s;10、从具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较（）个结点。

第二章 线性表重 点：重点讨论单链表的表示，插入和删除操作的实现及其算法的时间和空间复杂性讨论。

掌握循环链表和双向链表的基本概念；掌握静态链表的基本概念及基本操作的实现。

了解一元多项式的表示及相加。

难 点：单链表的表示及基本操作的实现，静态链表的基本概念及基本操作的实现，算法时间复杂度的分析。

学习提要：1. 了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。

用前者表示的线性表简称为顺序表，用后者表示的线性表简称为链表。

2. 熟练掌握这两类存储结构的描述方法，如一维数组中一个区域]..[j i 的上、下界和长度之间的变换公式(1,1,1-+=+-=+-=L i j L j i i j L )，链表中指针p 和结点p *的对应关系(结点)(next p >-*是结点p *的后继等)，链表中的头结点、头指针和首元结点的区别及循环链表、双向链表的特点等。

链表是本章的重点和难点。

扎实的指针操作和内存动态分配的编程技术是学好本章的基本要求。

3. 熟练掌握线性表在顺序存储结构上实现基本操作：查找、插入和删除的算法。

4. 熟练掌握在各种链表结构中实现线性表操作的基本方法，能在实际应用中选用适当的链表结构。

5. 能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。

2.1 线性表的逻辑结构一．线性表及基本运算1. 线性表（逻辑结构）（1）定义（2）特性（3）举例（略）2.线性表的基本运算（即常规操作）例2-1、2-2见书20P 。

2.2 线性表的顺序存储结构线性表按存储方式分为⎩⎨⎧链表顺序表1.顺序存储顺序存储结构（或顺序映象sequential mapping ）的特点：* 线性表的顺序存储结构是一种“随机存取”存储结构。

2.顺序表的具体实现3.顺序表的基本操作的实现(1) 顺序表的插入操作),,(x i l insert着重在于分析及用函数来表示算法的一般格式。

第2章线性表班级学号__________-姓名一、判断正误（）1. 链表的每个结点中都恰好包含一个指针。

（）2. 链表的物理存储结构具有同链表一样的顺序。

（）3. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动将后续各个单元向前移动。

（）4. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。

（）5. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。

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

（）7. 线性表在物理存储空间中也一定是连续的。

（）8. 线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。

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

（）10. 线性表的逻辑顺序与存储顺序总是一致的。

二、单项选择题（）1．数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为：（A）存储结构（B）逻辑结构（C）顺序存储结构（D）链式存储结构（）2. 一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（A）110 （B）108 （C）100 （D）120（）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个结点从小到大排序（）4. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动个元素（A）8 （B）63.5 （C）63 （D）7（）5. 链接存储的存储结构所占存储空间：（A）分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针（B）只有一部分，存放结点值（C）只有一部分，存储表示结点间关系的指针（D）分两部分，一部分存放结点值，另一部分存放结点所占单元数（）6. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址:（A）必须是连续的（B）部分地址必须是连续的（C）一定是不连续的（D）连续或不连续都可以（）7．线性表Ｌ在情况下适用于使用链式结构实现。

第二章线性表一、选择题1.一个线性表第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是( )（A）110 （B）108（C）100 （D）120参考答案：B2. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（）个元素。

（A）64（B）63 （C）63.5 （D）7参考答案：C3.线性表采用链式存储结构时，其地址（）。

(A) 必须是连续的 (B) 部分地址必须是连续的(C) 一定是不连续的 (D) 连续与否均可以参考答案：D4. 在一个单链表中，若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;参考答案：B5.在一个单链表中，若删除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;参考答案：A6.下列有关线性表的叙述中，正确的是（）（A）线性表中的元素之间隔是线性关系（B）线性表中至少有一个元素（C）线性表中任何一个元素有且仅有一个直接前趋（D）线性表中任何一个元素有且仅有一个直接后继参考答案：A7.线性表是具有n个（）的有限序列（n≠0)（A）表元素（B）字符（C）数据元素（D）数据项参考答案：C二、判断题1.线性表的链接存储，表中元素的逻辑顺序与物理顺序一定相同。

（）2.如果没有提供指针类型的语言，就无法构造链式结构。

（）3.线性结构的特点是只有一个结点没有前驱，只有一个结点没有后继，其余的结点只有一个前驱和后继。

《数据结构》吕云翔编著第2章线性表习题解答数据结构第2章线性表习题解答一、习题解答1. 假设有一个线性表L={a1, a2, ..., an}，设计一种算法，将线性表的所有元素逆置。

解答：可以使用两个指针i和j，分别指向线性表的第一个元素和最后一个元素，然后交换这两个指针所指向的元素，接着i向后移动一个单位，j向前移动一个单位，再次交换他们所指向的元素。

依次类推，直到i和j指针相遇为止。

这样就完成了线性表的逆置。

2. 设线性表L={a1, a2, ..., an}，设计一个算法，删除其中所有值为x 的元素。

解答：可以使用一个指针i遍历线性表，当遇到一个元素值等于x 时，将该元素删除，同时将后面的元素依次前移一位。

直到整个线性表遍历完毕。

3. 设有两个线性表LA={a1, a2, ..., am}和LB={b1, b2, ..., bn}，其中元素递增有序排列。

设计一个算法，将LA和LB合并成一个新的线性表LC，且元素递增有序排列。

解答：可以使用两个指针i和j分别指向LA和LB的第一个元素，并且使用一个指针k指向LC的最后一个元素。

比较LA[i]和LB[j]的大小，将较小的元素插入到LC的末尾，然后相应指针后移一位，直到其中一个指针到达对应线性表的末尾。

最后，将剩余的元素插入到LC的末尾，即可得到合并后的线性表LC。

4. 设线性表L={a1, a2, ..., an}，设计一个算法，找出其中最大的元素以及最大元素的位置。

解答：可以使用一个变量max记录当前遍历到的最大元素，初始化为L[0]，同时使用变量position记录最大元素的位置，初始值也为0。

然后遍历整个线性表，若遇到L[i]大于max，则更新max为L[i]，同时更新position为i。

遍历完毕后，max就是最大元素，position就是最大元素的位置。

5. 在线性表L={a1, a2, ..., an}中，设计一个算法，找出倒数第k个位置上的元素。

数据结构课后习题答案第二章线性表线性表是数据结构中最基本、最常用的一种数据结构，它按照线性的顺序存储数据元素，具有访问方便、插入和删除操作简单等特点。

第二章的习题主要涉及线性表的基本概念、顺序表、链表以及线性表的应用等内容。

以下是对第二章习题的详细解答。

1. 题目：给定一个具有n（1≤n≤10）个整数的一个线性表，设计一个时间复杂度为O(n)的算法，判断其中是否存在相同的元素。

解答：我们可以基于哈希表实现该算法。

首先创建一个哈希表，用于存储每个整数对应的出现次数。

然后遍历线性表中的每个元素，将其作为键，出现次数作为值存入哈希表中。

在遍历的同时，判断当前元素是否已经在哈希表中存在，若存在则说明存在相同的元素，算法结束；若不存在，则继续遍历下一个元素。

最终，如果遍历完所有元素都没有找到相同的元素，则可以得出结论线性表中不存在相同的元素。

2. 题目：设计一个算法，将一个线性表L（已知长度为n）中所有元素逆置。

解答：我们可以使用两个指针，一个指向线性表的首元素，另一个指向线性表的尾元素，然后交换两个指针所指向的元素，然后将指针向中间移动，继续进行交换操作，直到两个指针相遇为止。

通过这样的操作，就可以将线性表中所有元素逆置。

3. 题目：设计一个算法，将一个顺序表L的所有元素逆置，并将逆置后的顺序表存放到一个新的顺序表中。

解答：首先创建一个新的顺序表R，将L中的元素逆序遍历并依次插入到R中即可实现逆置。

具体过程为，遍历L中的每个元素，依次将其插入到R的首位置。

经过遍历后，R中的元素顺序和L中的元素顺序完全相反，即实现了逆置操作。

4. 题目：设计一个算法，删除一个单链表中所有值为x的节点。

解答：我们可以使用两个指针，一个指向当前节点，另一个指向当前节点的前一个节点。

遍历链表时，判断当前节点的值是否为x，若是，则将当前节点的前一个节点的指针指向当前节点的下一个节点，然后删除当前节点。

若不是，则继续遍历下一个节点。

数据结构与算法习题：第二章线性表在计算机科学中，数据结构和算法是至关重要的基础知识。

而线性表作为其中的一个重要概念，在很多实际应用中都有着广泛的用途。

线性表是一种最简单、最基本的数据结构。

它是由一组相同类型的数据元素组成的有限序列。

这些数据元素之间存在着线性的逻辑关系，也就是说，除了第一个元素和最后一个元素，每个元素都有且仅有一个直接前驱和一个直接后继。

线性表有两种常见的存储结构：顺序存储结构和链式存储结构。

顺序存储结构，简单来说，就是把线性表中的元素依次存放在一组连续的存储单元中。

这种存储方式就好像我们把一系列物品整齐地摆放在一排柜子里。

通过这种方式，我们可以直接通过元素的位置来访问和操作元素，时间复杂度为 O(1)。

但它也有一些缺点，比如插入和删除操作可能会比较麻烦，因为需要移动大量的元素，时间复杂度为O(n)。

相比之下，链式存储结构则更加灵活。

每个元素由两部分组成：数据域和指针域。

数据域用于存储元素本身的数据，而指针域则用于指向链表中的下一个元素。

这种结构就像是一个链条，每个环节都连接着下一个环节。

在链式存储结构中，插入和删除操作相对简单，只需要修改相关的指针即可，时间复杂度为 O(1)。

但是，要访问某个特定的元素，就需要从链表的头节点开始逐个遍历，时间复杂度为 O(n)。

接下来，让我们通过一些具体的习题来加深对线性表的理解。

假设有一个顺序存储的线性表，长度为 n，现在要在第 i 个位置插入一个新元素。

首先，我们需要判断插入位置是否合法，如果 i ＜ 1 或者 i ＞ n ＋ 1 ，那么就是非法插入。

如果插入位置合法，我们就需要从最后一个元素开始，依次向后移动一位，为新元素腾出位置，然后将新元素插入到指定位置。

再来看一个关于链式存储的习题。

给定一个单链表，现在要删除第i 个节点。

我们首先要找到第 i 1 个节点，然后修改它的指针，使其指向第 i ＋ 1 个节点，从而实现删除第 i 个节点的操作。

数据结构--线性表习题及答案第⼆章线性表⼀、选择题1、若长度为n的线性表采⽤顺序存储结构，在其第i个位置插⼊⼀个新元素算法的时间复杂度（）。

A. O(log2n)B.O(1)C. O(n)D.O(n2)2、若⼀个线性表中最常⽤的操作是取第i个元素和找第i个元素的前趋元素，则采⽤（）存储⽅式最节省时间。

A. 顺序表B. 单链表C. 双链表D. 单循环链表3、具有线性结构的数据结构是（）。

A. 图B. 树C. ⼴义表D.栈4、在⼀个长度为n的顺序表中，在第i个元素之前插⼊⼀个新元素时，需向后移动（）个元素。

A. n-iB. n-i+1C. n-i-1D. i5、⾮空的循环单链表head的尾结点p满⾜（）。

A. p->next==headB. p->next==NULLC. p==NULLD. p==head6、链表不具有的特点是（）。

A. 可随机访问任⼀元素B. 插⼊删除不需要移动元素C. 不必事先估计存储空间D. 所需空间与线性表长度成正⽐7、在双向循环链表中，在p指针所指的结点后插⼊⼀个指针q所指向的新结点，修改指针的操作是（）。

A. p->next=q;q->prior=p;p->next->prior=q;q->next=q;B. p->next=q;p->next->prior=q;q->prior=p;q->next=p->next;C. q->prior=p;q->next=p->next;p->next->prior=q;p->next=q;D. q->next=p->next;q->prior=p;p->next=q;p->next=q;8、线性表采⽤链式存储时，结点的存储地址（）。

A. 必须是连续的B. 必须是不连续的C. 连续与否均可D. 和头结点的存储地址相连续9、在⼀个长度为n的顺序表中删除第i个元素，需要向前移动（）个元素。

第二章线性表：习题习题一、选择题1．L是线性表，已知Length(L)的值是5，经运算？Delete(L，2)后，length(L)的值是( c)。

A.5B.0C.4D.62．线性表中，只有一个直接前驱和一个直接后继的是( )。

A．首元素 B.尾元素C．中间的元素 D.所有的元素+3．带头结点的单链表为空的判定条件是( )。

A. head= =NULLB. head->next= =NULLC. head->next=headD. head!=NULL4．不带头结点的单链表head为空的判定条件是( )。

A. head=NULLB. head->next =NULLC.head->next=headD. head!=NULL5．非空的循环单链表head的尾结点P满足()。

A. p->next = =NULLB. p=NULLC. p->next==headD. p= =head6．线性表中各元素之间的关系是( c )关系。

A.层次B.网状 C．有序 D.集合7.在循环链表的一个结点中有（）个指针。

A．1 B．2 C. 0 D. 38.在单链表的一个结点中有（）个指针。

A．1 B．2 C. 0 D. 39.在双链表的一个结点中有（）个指针。

A．1 B．2 C. 0 D. 310.在一个单链表中，若删除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;11.指针P指向循环链表L的首元素的条件是（）。

A．P= =L B. P->next= =L C. L->next=P D. P-> next= =NULL12. 在一个单链表中，若在p所指结点之后插入s所指结点，则执行（）。

第二章线性表一．名词解释1.线性结构2。

数据结构的顺序实现 3.顺序表4。

链表5。

数据结构的链接实现6。

建表7.字符串8.串9.顺序串10。

链串二、填空题1。

为了便于讨论,有时将含n（n>=0)个结点的线性结构表示成(a1,a2，……a n），其中每个a i代表一个______。

a1称为______结点，a n称为______结点,i称为a i在线性表中的________或______。

对任意一对相邻结点a i、a i┼1(1<=i<n)，a i称为a i┼1的直接______a i┼1称为a i的直接______。

2.为了满足运算的封闭性,通常允许一种逻辑结构出现不含任何结点的情况.不含任何结点的线性结构记为______或______。

3.线性结构的基本特征是:若至少含有一个结点,则除起始结点没有直接______外,其他结点有且仅有一个直接______；除终端结点没有直接______外，其它结点有且仅有一个直接______。

4.所有结点按1对1的邻接关系构成的整体就是______结构.5.线性表的逻辑结构是______结构。

其所含结点的个数称为线性表的______，简称______。

6.表长为O的线性表称为______7.线性表典型的基本运算包括:______、______、______、______、______、______等六种。

8.顺序表的特点是______.9.顺序表的类型定义可经编译转换为机器级。

假定每个datatype类型的变量占用k（k〉=1)个内存单元,其中，b是顺序表的第一个存储结点的第一个单元的内存地址，那么,第i个结点a i的存储地址为______。

10.以下为顺序表的插入运算,分析算法，请在______处填上正确的语句.Void insert_sqlist(sqlist L，datatype x,int i)/＊将X插入到顺序表L的第i—1个位置＊/{ if（st == maxsize) error(“表满"）；if((i〈1）|｜(i〉st+1））error（“非法位置"）;for（j=st;j〉=i;j—-)______；L.data［i—1]=x;L。

第二章（线性表）作业（参见《数据结构题集》第2章部分P13）一、在什么情况下用顺序表比链表好？（题集2.3）二、单选题：1、线性表的顺序存储是通过何种方式表示元素之间的逻辑关系。

①后继元素的地址②元素的存储顺序③左右孩子地址④后继元素的数组下标2、在线性表顺序存储结构中，在第I个元素之前插入新元素一般需要。

①移动元素②修改头指针③修改指针④申请新的结点空间3、在长度为n的顺序表的第I个元素之前插入一新元素的算法的时间复杂度为。

①O(n) ②O(1)③O(n2) ④O(Log2n)三、编写顺序表的判空操作算法。

四、编写顺序表求表长操作的算法。

五、已知L是带表头结点的非空单链表，且P结点既不是首元结点，也不是尾元结点，试从下列(1) ~ (14)提供的答案中选择合适的语句序列填空。

（题集2.7）a.删除P结点的直接后继结点的语句序列是_______ __________。

b.删除P结点的直接前驱结点的语句序列是_______________ __。

c.删除P结点的语句序列是_____________________________ _ _。

d.删除首元结点的语句序列是___________________________ __。

e.删除尾元结点的语句序列是____ _________________________。

(1)p = p->next;(2)p->next = p;(3)p->next = p->next->next;(4)p = p->next->next;(5)while ( p!=NULL ) p=p->next;(6)while ( q->next!=NULL ) { p=q; q=q->next; }(7)while ( p->next!=q ) p=p->next;(8)while ( p->next->next!=q ) p=p->next;(9)while ( p->next->next!=NULL ) p=p->next;(10)q=p;(11)q=p->next;(12)p=l;(13)l=l->next;(14)free(q);六、算法设计。

数据结构第二章习题第2章线性表一、单选题1．线性表是具有n个_________的有限序列。

a、表元素B.字符C.数据元素D.数据项2。

线性表格是。

a．一个有限序列，可以为空b．一个有限序列，不可以为空c．一个无限序列，可以为空d．一个无限序列，不可以为空3．线性表采用链表存储时，其地址_________。

a、 U4。

列表中不连续的部分必须是U4。

a．可随机访问任一结点b．插入删除不需要移动元素c．不必事先估计存储空间d．所需空间与其长度成正比5．设线性表有n个元素，以下操作中，_________在顺序表上实现比在链表上实现效率更高。

a、输出I（1≤ 我≤ n） th元素值b．交换第1个元素与第2个元素的值c．顺序输出这n个元素的值d、输出与线性表中给定值x相等的元素序列号6．设线性表中有2n个元素，以下操作中，_________在单链表上实现要比在顺序表上实现效率更高。

a．删除指定的元素b、在最后一个元素后插入新元素。

C.按顺序输出前k个元素d．交换第i个元素和第2n-i-1个元素的值(i=0,1…,n-1)7.如果最常见的操作是获取第i个节点及其前体，请使用___________________。

a．单链表b．双链表c、与单链表相比，双链表的优点之一是。

a．插入和删除操作更简单b．可以进行随机访问c．可以省略表头指针或表尾指针d．访问前后相邻结点更灵活9．带头结点的单链表l为空的判定条件是_________。

a、 l==nullb.l->next==nullc.l->next==ld.l！=无效的10．在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是_________。

a、 o（1）b.o（n）c.o（n2）d.o（nlog2n）11．在一个长度为n(n>1)的带头结点的单链表h上，另设有尾指针r（指向尾结点），执行_________操作与链表的长度有关。

数据结构第二章线性表习题含答案说明：顺序存储的线性表称为向量。

一,单项选择题一个向量第一个元素的地址是100，每个元素的长度为2，则第5个元素的地址是__①_B__。

A) 110 B) 108 C) 100 D) 120线性结构通常采用的两种存储结构是__①A___。

A) 顺序存储结构和链式存储结构B) 散列方式和索引方式C) 链表存储结构和数组D) 线性存储结构和非线性存储结构不带头结点的单链表head为空的判定条件是__①__A_.A) head==NULL B) head->next==NULLC) head->next==head D) head!=NULL带头结点的单链表head为空的判定条件是__①B___。

A) head==NULL B) head->next==NULLC) head->next==head D) head!=NULL非空的循环链表head的尾结点（由p所指向）满足__①_C__。

A) p->next==NULL B) p==NULLC) P->next==head D) p==head在循环双链表的p所指结点之后插入s所指结点的操作是___①_C_。

A) p->right=s; s->left=p; p->right->left=s; s->right=p->right;B) p->right=s; p->right->left=s; s->left=p; s->right=p->right;C) s->left=p; s->right=p->right; p->right=s; p->right->left=s;D) s->left=p; s->right=p->right; p->right->left=s; p->right=s;在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点, 则执行__①c___。

《数据结构》第二章线性表习题一、单项选择题1. 线性表是________。

A．一个有限序列，可以为空B．一个有限序列，不可以为空C．一个无限序列，可以为空D．一个无限序列，不可以为空2. 在一个长度为n的顺序表中删除第i个元素(0<=i<=n)时，需向前移动个元素。

A．n-i B．n-i+l C．n-i-1 D．i3. 线性表采用链式存储时，其地址________。

A．必须是连续的B．一定是不连续的C．部分地址必须是连续的D．连续与否均可以4. 从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较________个元素结点。

A．n/2 B．n C．（n+1）/2 D．（n-1）/25. 在双向循环链表中，在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<n+l )之前插入一个新元素时，需向后移动______个元素。

数据结构第二章——线性表基本信息：[矩阵文本题] *1. 顺序表的第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的存储地址是（） [单选题] *A. 110B. 108(正确答案)C. 100D. 1202. 在 n 个结点的顺序表中,算法的时间复杂度是 O(1)的操作是（）: [单选题] *A. 访问第 i 个结点(1≤i≤n)和求第 i 个结点的直接前驱(2≤i≤n)(正确答案)B. 在第 i 个结点后插入一个新结点(1≤i≤n)C. 删除第 i 个结点(1≤i≤n)D. 将 n 个结点从小到大排序3. 向一个有 127 个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动的元素个数为（）。

[单选题] *A. 8B. 63.5(正确答案)C. 63D. 74. 链接存储的存储结构所占存储空间（）。

[单选题] *A. 分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针(正确答案)B. 只有一部分，存放结点值C. 只有一部分，存储表示结点间关系的指针D. 分两部分，一部分存放结点值，另一部分存放结点所占单元数5. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）。

[单选题] *A. 必须是连续的B. 部分地址必须是连续的C. 一定是不连续的D. 连续不连续都可以(正确答案)6. 线性表L在（）情况下适用于使用链式结构实现。

[单选题] *A. 需经常修改L中的结点值B. 需不断对L进行删除插入(正确答案)C. L中含有大量的结点D. L中结点结构复杂7. 单链表的存储密度（）。

[单选题] *A. 大于1B. 等于1C. 小于1(正确答案)D. 不确定8. 将两个各有 n 个元素的有序表归并成一个有序表，其最少的比较次数是（）。

[单选题] *A. n(正确答案)B. 2n-1C. 2nD. n-19. 在一个长度为n的顺序表中向第i个元素(1≤i≤n+l )之前插入一个新元素时，需向后移动（）个元素。