数据结构第2章 链表 练习题

数据结构练习题第二章答案一、选择题1. 在数据结构中，线性结构的特点是什么？A. 元素之间存在一对一的关系B. 元素之间存在一对多的关系C. 元素之间存在多对多的关系D. 元素之间存在一对一或一对多的关系答案：D2. 栈（Stack）是一种特殊的线性表，其特点是：A. 允许在表的一端进行插入和删除操作B. 允许在表的两端进行插入和删除操作C. 只能在表的两端进行插入和删除操作D. 只能在表的中间进行插入和删除操作答案：A3. 队列（Queue）与栈的主要区别在于：A. 队列是先进先出（FIFO），栈是先进后出（LIFO）B. 栈是先进先出（FIFO），队列是先进后出（LIFO）C. 队列和栈都是先进先出（FIFO）D. 队列和栈都是先进后出（LIFO）答案：A二、简答题1. 什么是链表？链表有哪些基本操作？答案：链表是一种由一系列节点组成的线性数据结构，每个节点包含数据部分和指向下一个节点的指针。

链表的基本操作包括插入节点、删除节点、查找节点和遍历链表。

2. 线性表的顺序存储结构和链式存储结构有何区别？答案：顺序存储结构使用连续的存储单元来存储数据元素，如数组。

链式存储结构不要求数据元素在存储空间中连续，每个元素包含指向下一个元素的指针，如链表。

三、编程题1. 编写一个函数，实现在单链表中插入一个新节点到指定位置。

```c#include <stdio.h>#include <stdlib.h>typedef struct Node {int data;struct Node *next;} Node;Node* createNode(int data) {Node *newNode = (Node*)malloc(sizeof(Node));newNode->data = data;newNode->next = NULL;return newNode;}void insertNode(Node head, int position, int data) {Node *newNode = createNode(data);if (position == 0) {newNode->next = *head;*head = newNode;} else {Node *current = *head;for (int i = 0; current != NULL && i < position - 1; i++) {current = current->next;}if (current == NULL) return; // Position is greater than the number of nodesnewNode->next = current->next;current->next = newNode;}}int main() {Node *head = NULL;insertNode(&head, 0, 10);insertNode(&head, 1, 20);// Print the list to verify the insertionNode *current = head;while (current != NULL) {printf("%d ", current->data);current = current->next;}return 0;}```四、分析题1. 分析栈的后进先出（LIFO）特性在实际应用中的优势和局限性。

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) 静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。

(3) 静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。

以上错误的是（）【南京理工大学 2000 一、3（1.5分）】A．（1），（2） B．（1） C．（1），（2）,(3) D.（2）13. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（）(1Rlink=p;p->Llink->Rlink=q;q->Llink=q；B. p->Llink=q;p->Llink->Rlink=q;q->Rlink=p;q->Llink=p->Llink;C. q->Rlink=p;q->Llink=p->Llink;p->Llink->Rlink=q;p->Llink=q;D. q->Llink=p->Llink;q->Rlink=q;p->Llink=q;p->Llink=q;24．在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（）。

单元练习2一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳）（×）（1）线性表的链式存储结构优于顺序存储。

（×）（2）链表的每个结点都恰好包含一个指针域。

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

（×）（4）顺序存储方式的优点是存储密度大，插入、删除效率高。

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

（×）（6）顺序表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。

（√）（7）线性表链式存储的特点是可以用一组任意的存储单元存储表中的数据元素。

（√）（8）线性表采用顺序存储，必须占用一片连续的存储单元。

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

（ㄨ）（10）插入和删除操作是数据结构中最基本的两种操作，所以这两种操作在数组中也经常使用。

二．填空题（1）顺序表中逻辑上相邻的元素在物理位置上必须相连。

（2）线性表中结点的集合是有限的，结点间的关系是一对一关系。

（3）顺序表相对于链表的优点是：节省存储和随机存取。

（4）链表相对于顺序表的优点是：插入、删除方便。

（5）采用顺序存储结构的线性表叫顺序表。

（6）顺序表中访问任意一个结点的时间复杂度均为O(1)。

（7）链表相对于顺序表的优点是插入、删除方便；缺点是存储密度小。

（8）在双链表中要删除已知结点*P，其时间复杂度为O(1)。

（9）在单链表中要在已知结点*P之前插入一个新结点，需找到*P的直接前趋结点的地址，其查找的时间复杂度为 O(n) 。

（10）单链表中需知道头指针才能遍历整个链表。

（11）线性表中第一个结点没有直接前趋，称为开始结点。

（12）在一个长度为n的顺序表中删除第i个元素，要移动n-i 个元素。

（13）在一个长度为n的顺序表中，如果要在第i个元素前插入一个元素，要后移n- i +1 个元素。

数据结构第2章习题参考答案2.7习题2.7.1知识点：线性表的逻辑结构一、选择题1①线性表L=（a1, a2,…,an）,下列说法正确的是（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-1B．n-i+1C．n-i-1D．i2①若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（D）存储方式最节省时间。

A．单链表B．双链表C．单向循环D．顺序表3②一个数组第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（B）A．110B．108C．100D．1204①下述哪一条是顺序存储结构的优点（A）。

【北方交通大学2001】A．存储密度大B．插入运算方便C．删除运算方便D．可方便地用于各种逻辑结构的存储表示5③若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（C）（1<=i<=n+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. 插入操作：在链表的指定位置插入一个新的节点。

3. 删除操作：删除链表中的指定节点。

4. 遍历操作：从头节点开始，依次访问链表中的每个节点。

问题二：二叉树的遍历二叉树是一种特殊的树形数据结构，其中每个节点最多有两个子节点。

二叉树的遍历方式有：1. 前序遍历：首先访问根节点，然后递归地遍历左子树，最后递归地遍历右子树。

2. 中序遍历：首先递归地遍历左子树，然后访问根节点，最后递归地遍历右子树。

3. 后序遍历：首先递归地遍历左子树，然后递归地遍历右子树，最后访问根节点。

问题三：图的表示图是一种复杂的非线性数据结构，由顶点和边组成。

图的表示方法有：1. 邻接矩阵：使用一个二维数组来表示图，其中矩阵的元素表示两个顶点之间的边是否存在。

2. 邻接表：使用链表来表示每个顶点的邻接顶点。

问题四：排序算法排序算法是将一组数据按照特定顺序重新排列的过程。

常见的排序算法包括：1. 冒泡排序：通过重复遍历待排序的数列，比较每对相邻元素的大小，并在必要时交换它们的位置。

2. 选择排序：从未排序序列中找到最小（或最大）的元素，存放到排序序列的起始位置，然后从剩余未排序元素中继续寻找最小（或最大）元素，以此类推。

3. 快速排序：选择一个元素作为“基准”，通过一趟排序将待排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据都要小，然后再递归地对这两部分数据分别进行快速排序。

总结数据结构习题二涵盖了链表、二叉树、图和排序算法等基本概念和操作。

掌握这些基础知识对于深入理解计算机科学和进行高效的程序设计至关重要。

希望以上答案能够帮助你更好地理解和应用这些概念。

请注意，这只是一个示例答案，具体的习题答案需要根据实际的习题内容来编写。

一、名词解释1.线性表2.顺序表3.单链表4.循环单链表5.循环双向链表二、选择题1.用单链表方式存储的线性表，存储每个结点需要两个域，一个是数据域，另一个是_________A.当前结点的所在地址B.后继结点的所在地址C.空指针域D.空闲域2.不带头结点的单链表head为空的判定条件是__________A.head==NULLB.head→next==NULLC.head→next==headD.head!=NULL3.带头结点的单链表head为空的判定条件是__________A.head==NULLB.head→next==NULLC.head→next==headD.head!=NULL4.一个顺序表的第一个元素的存储地址是100，每个元素的长度为5，则第7个元素的地址是____________A. 130B. 125C. 120D. 1355.非空的循环单链表head的尾结点（由p所指向）满足____________A.p→next==NULLB.p==NULLC.p→next==headD.p==head6.设线性链表中结点的结构为(data, next)，已知指针q所指结点是指针结点p的直接前驱，若在q与p之间插入结点s，则应执行_________操作A.s→next=p→next; p→next=s;B.q→next=s; s→next=p;C.p→next=s→next; s→next=p;D.p→next=s; s→next=q;7.设线性链表中结点的结构为(data, next)，已知指针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;8.设线性链表中结点的结构为(data, next)，若想删除结点p的直接后继，则应执行______A.p→next=p→next→next;B.p=p→next; p→next= p→next→nextC.p→next=p→next;D.p=p→next→next;9.p指向线性链表中L的某一个结点，则在线性链表的表尾插入结点s的语句序列是_________A.while(p→next != NULL) p=p→next; p→next=s; s→next=NULL;B.while(p != NULL) p=p—next; p→next=s; s→next=NULL;C.while(p→next != NULL) p=p→next; s→next=p; p→next=NULL;D.while(p!=NULL) p=p→next→next; p→next=s; s→next=p→next;三、填空题1.按顺序存储方法存储的线性表称为________，按链式存储方法存储的线性表称为________。

1.1. 一元稀疏多项式的求导算法写出一元稀疏多项式的求导算法，用带表头结点的单链表存储该一元稀疏多项式，Lb为头指针，用类C语言描述该求导算法，不另行开辟存储空间，删除无用结点，并分析算法的时间复杂度。

该链表的数据结构如下：typedef struct LNode{float coe; //系数int exp; //指数struct LNode *next; //指针} LNode , *LinkList ;求导算法如下：void Differential(LinkList &Lb){ //求导算法pre=Lb; p=pre->next;while ( p ){if ( p->exp != 0 )//指数不等于零{p->coe = p->coe * p->exp ;p->exp = p->exp – 1 ;pre = pre->next ;}else//指数等于零{pre->next = p->next ;free ( p );}p = pre->next ;}}时间复杂度为: O(n)1.2. 单链表存储结构的排序算法排序算法：将一组整数排序成非递减有序序列。

用带头结点的单链表存储，L为头指针，用类C语言写出该排序算法，不另行开辟存储空间，并分析算法的时间复杂度。

该单链表的数据结构如下：typedef struct LNode{int data; //数据域struct LNode *next; //指针域} LNode , *LinkList ;void Sort(LinkList &L){ //排序算法如下：将L排序成非递减单链表q=L; p=q->next->next; q->next->next=NULL;while(p){While(q->next && p->data >= q->next->data)q=q->next;s=p->next;p->next=q->next;q->next=p;p=s;q=L;}}//sort1.3. 设H为具有n(n>0，n很大且未知)个数据元素的单链表的头结点指针，试采用C语言编写一个程序，完成将单链表中第n/2个数据元素之后的全部数据元素倒置的功能。

1.已知L是无表头结点的单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。

a.在P结点后插入S结点的语句序列是__4,1_______。

b.在P结点前插入S结点的语句序列是___711841________。

c.在表首插入S结点的语句序列是__5 12_______。

d.在表尾插入S结点的语句序列是____9 1 6______。

(1) P->next=S;(2) P->next=P->next->next;(3) P->next=S->next;(4) S->next=P->next;(5) S->next=L;(6) S->next=NULL;(7) Q=P;(8) while(P->next!=Q) P=P->next;(9) while(P->next!=NULL) P=P->next;(10) P=Q;(11) P=L;(12) L=S;(13) L=P2.已知L是带表头结点的非空单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。

b.删除P结点的直接前驱结点的语句序列是_10,12,8,11,3,14__________。

c.删除P结点的语句序列是___10,12,7,3,14________。

d.删除首元结点的语句序列是__12,11,3,14_________。

e.删除尾元结点的语句序列是__9,11,3,14________。

(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)3.已知P结点是某双向链表的中间结点，试从下列提供的答案中选择合适的语句序列。

第2章线性表一、选择题1.链表不具备的特点是（）。

A．可随机访问任意结点B.插入删除不需要移动元素C.不必事先估计存储空间D.所需空间与其长度成正比2.不带头结点的单链表head为空的判定条件是（）。

==NULLB. head->next==NULL >next==head!=NULL3.带头结点的单链表head为空的判定条件是（）。

==NULLB. head->next==NULL >next==head!=NULL4．带头结点的双循环链表L为空表的条件是（）。

A．L==NULL B．L->next->==NULL C．L->prior==NULL >next==L5.非空的循环链表head的尾结点（由P所指向）满足（）。

A．p->next==NULL B．p==NULL C．p->next==head ==head6.在循环双链表的p所指结点之前插入s所指结点的操作是（）。

A．p->prior=s;s->next=p;p->prior->next=s;s->prior=p->prior;B．p->prior=s;p->prior->next=s;s->next=p;s->prior=p->prior;C．s->next=p;s->prior=p->prior;p->prior=s;p->right->next=s;D. s->next=p;s->prior=p->prior;p->prior->next=s;p->prior=s;7.若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用（）存储方式最节省运算时间。

A．单链表B．给出表头指针的单循环链表C．双链表D.带头结点的双循环链表8.某线性表最常用的操作是在最后一个结点之后插入一个节点或删除第一个结点，故采用（）存储方式最节省运算时间。

第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．线性表Ｌ在情况下适用于使用链式结构实现。

数据结构第二章参考答案习题21. 填空题（1）在一个单链表中，已知每个结点包含data和next两个域，q所指结点是p所指结点的直接前驱，若在q和p之间插入s所指结点，则执行（___________）和（___________）操作。

答案：q->next = s; s->next = p; 或 s->next=q->next; q->next = s; （2）表长为n的顺序表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均个数为（___________），删除一个元素需要移动元素的平均个数为（___________）。

答案：n/2 (n-1)/2（3）表长为0的线性表称为（___________）。

答案：空表（4）动态内存管理是操作系统的基本功能之一，其作用是响应用户程序对内存的（___________）和（___________）请求。

答案：申请释放（5）顺序表多采用（___________）实现的，是一种随机存取结构，对表中任意结点存取操作的时间复杂度为（___________）。

而查找链表中的结节，需要从头指针起顺着链扫描才能得到，平均时间复杂度为（___________）。

因此，若线性表的操作主要是进行查找，很少进行插入或删除操作时，采用（___________）表比较合适。

答案：数组 O(1) O(n) 顺序（6）在链表某个位置上进行插入和删除操作，只需要修改（___________）即可，而无须移动大量元素，操作的时间复杂度为（___________）。

而在顺序表中进行插入和删除操作，往往要移动大量元素，平均移动元素的数目为（___________），平均时间复杂度为（___________）。

因此，若对线性表进行频繁的插入和删除操作时，采用（___________）表相对合适。

若插入和删除主要发生在表头和表尾，则采用（___________）表更为合适。

第二章线性表一、单项选择题1.顺序存储结构的特点是（ B ）。

A. 只能实现顺序存取元素的操作B. 逻辑上相邻的数据元素在存储地址上也一定相邻C. 逻辑上相邻的数据元素在存储地址上一定不相邻D. 逻辑上相邻的数据元素在存储地址上不一定相邻2.若某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用（ C ）最节省时间。

A. 单链表B. 双链表C. 带头结点的双循环链表D. 单循环链表3.与线性表的顺序存储不相符的特性是（ A ）。

A. 插入和删除操作灵活B. 需要连续存储空间C. 便于随机访问D. 存储密度大4.与线性表的链接存储不相符合的特性是（ C）。

A. 便于插入、删除运算B. 存储空间动态分配C. 需要连续的存储空间D. 只能顺序查找5.链表不具有的特点是（ B）。

A. 插入、删除不需要移动元素B. 可随机访问任一元素C. 不必事先估计存储空间D. 所需空间与线性长度成正比6.循环链表h的尾结点p的特点是（ D ）。

A.p==h->nextB. p->next== h->nextC.p==hD. p->next==h7.在一个单链表中，已知q所指向的结点是p所指向结点的前驱结点，若在q和p 之间插入s所指向的结点，则执行（ C ）。

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;8.设一个有序的顺序表中有n个结点，现要求插入一个新结点后使得顺序表仍然保持有序，则该操作的平均时间复杂度为（D ）。

A. O(log2n)B. O(1)C. O(n2)D. O(n)9.对于一个线性表，若要求既能够进行较快地插入和删除，又能够反映出数据元素之间的关系，则应该（ A）。

数据结构第二章试题第2章线性表一、选择题1. 链表不具备的特点是（）。

A．可随机访问任意结点 B. 插入删除不需要移动元素C. 不必事先估计存储空间D. 所需空间与其长度成正比2. 不带头结点的单链表head为空的判定条件是（）。

A.head==NULLB. head->next==NULLC.head->next==headD.head!=NULL3.带头结点的单链表head为空的判定条件是（）。

A.head==NULLB. head->next==NULLC.head->next==headD.head!=NULL4．带头结点的双循环链表L为空表的条件是（）。

A．L==NULL B．L->next->==NULL C．L->prior==NULLD.L->next==L5.非空的循环链表head的尾结点（由P所指向）满足（）。

A．p->next==NULL B．p==NULL C．p->next==headD.p==head6.在循环双链表的p所指结点之前插入s所指结点的操作是（）。

A．p->prior=s;s->next=p;p->prior->next=s;s->prior=p->p rior;B．p->prior=s;p->prior->next=s;s->next=p;s->prior=p->pr ior;C．s->next=p;s->prior=p->prior;p->prior=s;p->right->next=s;D.s->next=p;s->prior=p->prior;p->prior->next=s;p->prior=s;7.若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用（）存储方式最节省运算时间。

《数据结构》第二章线性表习题一、单项选择题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．求单链表中当前结点的后继和前驱的时间复杂度分别是（）A．O（n）和O（1）B．O（1）和O（1）C．O（1）和O（n）D．O(n)和O（n）2．非空的单循环链表的头指针为head,尾指针为rear，则下列条件成立的是（）A．rear->next= =head B．rear->next->next= =headC．head->next= =rear D．head->next->next= =rear3．在带头结点的循环链表L中，结点的数据元素为整型，且按值递增有序存放。

给定两个整数a和b，且a<b，编写算法删除链表L中元素值大于a且小于b的所有结点。

4．在线性表的下列运算中，不．改变数据元素之间结构关系的运算是（）A．插入B．删除C．排序D．定位5.已知指针p和q分别指向某单链表中第一个结点和最后一个结点。

假设指针s指向另一个单链表中某个结点，则在s所指结点之后插入上述链表应执行的语句为( ) A.q->next=s->next；s->next=p； B.s->next=p；q->next=s->next；C.p->next=s->next；s->next=q；D.s->next=q；p->next=s->next；6．若线性表的插入和删除操作频繁地在表头或表尾位置进行，则更适宜采用的存储结构为（）A．无头结点的双向链表B．带尾指针的循环链表C．无头结点的单链表D．带头指针的循环链表7.在下列对顺序表进行的操作中，算法时间复杂度为O(1)的是（）A.访问第i个元素的前驱（1<ni≤）B.在第i个元素之后插入一个新元素(n1≤≤)iC.删除第i个元素(n≤)i1≤D.对顺序表中元素进行排序8.在链表的结点中，数据元素所占的存储量和整个结点所占的存储量之比称作________。