数据结构第二章线性表1习题

数据结构第二章课后答案数据结构第二章课后答案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. 链表的每个结点中都恰好包含一个指针。

链表中的结点可含多个指针域，分别存放多个指针。

例如，双向链表中的结点可以含有两个指针域，分别存放指向其直接前趋和直接后继结点的指针。

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

链表的存储结构特点是无序，而链表的示意图有序。

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

链表的结点不会移动，只是指针内容改变。

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

混淆了逻辑结构与物理结构，链表也是线性表！且即使是顺序表，也能存放记录型数据。

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

正好说反了。

顺序表才适合随机存取，链表恰恰适于“顺藤摸瓜”（×）6. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。

前一半正确，但后一半说法错误，那是链式存储的优点。

顺序存储方式插入、删除运算效率较低，在表长为n的顺序表中，插入和删除一个数据元素，平均需移动表长一半个数的数据元素。

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

线性表有两种存储方式，顺序存储和链式存储。

后者不要求连续存放。

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

线性表有两种存储方式，在顺序存储时，逻辑上相邻的元素在存储的物理位置次序上也相邻。

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

顺序存储方式不仅能用于存储线性结构，还可以用来存放非线性结构，例如完全二叉树是属于非线性结构，但其最佳存储方式是顺序存储方式。

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

理由同7。

链式存储就无需一致。

第二章线性表习题1 ．填空题(1) 链表中逻辑上相邻的元素的物理位置( ) 相连。

(2) 在单链表中除首结点外，任意结点的存储位置都由( ) 结点中的指针指示。

(3) 在单链表中，设置头结点的作用是在插入或删除首结点时不必对( ) 进行处理。

(4) 已带头结点的单链表L ，指针p 指向L 链表中的一个结点，指针q 是指向L 链表外的一个结点，则：在指针p 所指结点后插入q 所指结点的语句序列是( ) ；在指针p 所指结点前插入q 所指结点的语句序列是( ) ；将q 所指结点插入在链表首结点的语句序列是( ) ；将q 所指结点插入在链表尾结点的语句序列是( ) 。

(5) 已知带表头结点的单链表L ，指针p 指向L 链表中的一个结点（非首结点，非尾结点），则：删除指针p 所指结点的直接后继结点的语句是( ) 。

删除指针p 所指结点的直接前驱结点的语句序列是( ) 。

删除指针p 所指结点的语句序列是( ) 。

删除首结点的语句序列是( ) 。

⑤删除尾结点的语句序列是( ) 。

(6) 已知指针p 指向双向链表中的一个结点（非首结点，非尾结点），则：将结点s 插入在指针p 所指结点的直接后继位置的语句是( ) 。

将结点s 插入在指针p 所指结点的直接前驱位置的语句是( ) 。

删除指针p 所指结点的直接后继结点的语句序列是( ) 。

删除指针p 所指结点的直接前驱结点的语句序列是( ) 。

⑤删除指针p 所指结点的语句序列是( ) 。

(7) 线性表的存储结构有顺序存储和( ) 存储两种。

(8) 线性表的元素长度为4 ，在顺序存储结构下Loc(ai)=2000 ，则Loc(ai ＋1)=( ) 。

(9) 线性表a 的元素长度为L ，在顺序存储结构下Loc(ai)=Loc(a1)+( ) 。

(10) 在线性表的链式存储结构中，某结点的指针字段指向该结点的( ) 两种存储。

(11) 线性表的元素长度为4 ，Loc(ai ＋1)=1000 ，则Loc(a3)=( ) 。

《数据结构》第二版严蔚敏课后习题作业参考答案(1-7章)【第一章绪论】1. 数据结构是计算机科学中的重要基础知识，它研究的是如何组织和存储数据，以及如何通过高效的算法进行数据的操作和处理。

本章主要介绍了数据结构的基本概念和发展历程。

【第二章线性表】1. 线性表是由一组数据元素组成的数据结构，它的特点是元素之间存在着一对一的线性关系。

本章主要介绍了线性表的顺序存储结构和链式存储结构，以及它们的操作和应用。

【第三章栈与队列】1. 栈是一种特殊的线性表，它的特点是只能在表的一端进行插入和删除操作。

本章主要介绍了栈的顺序存储结构和链式存储结构，以及栈的应用场景。

2. 队列也是一种特殊的线性表，它的特点是只能在表的一端进行插入操作，而在另一端进行删除操作。

本章主要介绍了队列的顺序存储结构和链式存储结构，以及队列的应用场景。

【第四章串】1. 串是由零个或多个字符组成的有限序列，它是一种线性表的特例。

本章主要介绍了串的存储结构和基本操作，以及串的模式匹配算法。

【第五章数组与广义表】1. 数组是一种线性表的顺序存储结构，它的特点是所有元素都具有相同数据类型。

本章主要介绍了一维数组和多维数组的存储结构和基本操作，以及广义表的概念和表示方法。

【第六章树与二叉树】1. 树是一种非线性的数据结构，它的特点是一个节点可以有多个子节点。

本章主要介绍了树的基本概念和属性，以及树的存储结构和遍历算法。

2. 二叉树是一种特殊的树，它的每个节点最多只有两个子节点。

本章主要介绍了二叉树的存储结构和遍历算法，以及一些特殊的二叉树。

【第七章图】1. 图是一种非线性的数据结构，它由顶点集合和边集合组成。

本章主要介绍了图的基本概念和属性，以及图的存储结构和遍历算法。

【总结】1. 数据结构是计算机科学中非常重要的一门基础课程，它关注的是如何高效地组织和存储数据，以及如何通过算法进行数据的操作和处理。

本文对《数据结构》第二版严蔚敏的课后习题作业提供了参考答案，涵盖了第1-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章线性表一、选择题1.表长为N 的顺序表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均次数为（），删除一个元素需要移动的元素个数为（）。

【＊＊，★】A. (N-1)/2B. NC. N+1D. N-1E. N/2F. (N+1)/2G. (N-2)/22.线性表是具有N 个（）的有限序列。

【＊】A、表元素B、字符C、数据元素D、数据项E、信息3.“线性表的逻辑顺序和物理顺序总是一致的。

”这个结论是（）。

【＊】A、正确的B、错误的C、不一定，与具体结构有关。

4.线性表采用链式存储结构时，要求内存中可用存储单元的地址（）。

【＊，★】A、必须是连续的B、部分地址必须是连续的C、一定是不连续的D、连续或不连续都可以。

5.带头结点的单链表为空的判定条件是（）。

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

【＊】A、head==NULLB、head->next==NULLC、head->next==headD、head!=NULL7.非空的循环单链表head 的尾结点P 满足（）。

（注:带头结点）【＊】A、P->NEXT=NULLB、p=NULLC、p->next==headD、p==head8.在一个具有n 个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（）。

【＊，★】A、O(1)B、O(n)C、O(n2)D、O(nlog2n)9.在一个单链表中，若删除P 所指结点的后继结点，则执行（）。

【＊，★】A、p->next=p->next->nextB、p=p->next;p->next=p->next->nextC、p->next=p->next;D、p=p->next->next;10.在一个单链表中，若在Ｐ所指结点之后插入Ｓ所指结点，则执行（）。

第一章绪论1.有如下程序段：for(i=1;i<=n;i++)for(j=1;j<=n;j++){++t;}他的算法时间复杂度为：n n第二章线性表1.若有100个学生，每个学生有学号，姓名，平均成绩，采用什么样的数据结构最方便，写出这些结构？2.线性表有两种存储结构：一是顺序表，二是链表。

试问：（1）如果有 n个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。

在此情况下，应选用哪种存储结构？为什么？链表（2）若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构？为什么？顺序表3.在顺序表中，逻辑上相邻的元素，其物理位臵相邻。

在单链表中，逻辑上相邻的元素，其物理位臵相邻。

4.线性结构包括哪几种？5.已知L是无表头结点的单链表，且P结点既不是首元素结点，也不是尾元素结点。

按要求从下列语句中选择合适的语句序列。

a. 在P结点后插入S结点的语句序列是：。

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

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

d. 在表尾插入S结点的语句序列是：。

供选择的语句有：（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= P;第三章栈和队列1.有5 个元素，其入栈次序为：A，B，C，D，E，在各种可能的出栈次序中，以元素C，D最先出栈（即C第一个且D第二个出栈）的次序有哪几个？2.栈S和队列Q的初始状态皆为空,元素a1,a2,a3,a4,a5和a6依次通过S栈，一个元素出栈后即进入队列Q，若6个元素出队列的顺序是a3,a5,a6,a4,a2,a1，则栈S至少应该容纳个元素。

第二章线性表一、选择题1．下述哪一条是顺序存储结构的优点？（ A ）A．存储密度大 B．插入运算方便C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示2．下面关于线性表的叙述中，错误的是哪一个？（ B ）A．线性表采用顺序存储，必须占用一片连续的存储单元。

B．线性表采用顺序存储，便于进行插入和删除操作。

C．线性表采用链接存储，不必占用一片连续的存储单元。

D．线性表采用链接存储，便于插入和删除操作。

3．线性表是具有n个（ C ）的有限序列（n>0）。

A．表元素 B．字符 C．数据元素 D．数据项 E．信息项4．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ A ）存储方式最节省时间。

A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表5．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。

A．单链表 B．仅有头指针的单循环链表C．双链表 D．仅有尾指针的单循环链表6．设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( C )最节省时间。

A. 单链表B.单循环链表C. 带尾指针的单循环链表D.带头结点的双循环链表7. 链表不具有的特点是（ B ）A．插入、删除不需要移动元素 B．可随机访问任一元素C．不必事先估计存储空间 D．所需空间与线性长度成正比8. 下面的叙述不正确的是（ B C ）A．线性表在链式存储时，查找第i个元素的时间同i的值成正比B. 线性表在链式存储时，查找第i个元素的时间同i的值无关C. 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比D. 线性表在顺序存储时，查找第i个元素的时间同i的值无关10. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（）(1<=i<=n+1)。

A. O(0)B. O(1)C. O(n)D. O(n2)11. 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（ C ）。

第一章绪论一. 选择题1．BD 2．CA 3．B 4．C 5．A 6．D 7．A 8．A 9．A 10．C 二. 解答题第二章线性表一. 选择题1．A 2．B 3．A 4．D 5．A 6．C 7．A 8．B 9．A二.填空题1．.物理位置相邻指针2．.直接前驱直接后继3．顺序链式三. 算法设计题1．①int count(Linklist h,int x){int num=0;Linknode *p;p=h->next;while(p&&p->data<=x)//p指针向后移动，直至p指向第一个值大于x的结点p=p->next;while(p)if(p->next&&p->data==p->next->data)//若p没有指向链表中同一数值的最后一个结点，则向后移动p=p->next;else//若p指向数值相同的结点中的最后一个，则num加1，p指针后移，继续执行while循环{num++;p=p->next;}return num;}②void delevenl(Linklist &h,int x){Linknode *p,*r;p=h->next;r=h;while(p&&p->data<x){if(p->data%2==0){r->next=p->next;free(p);p=r->next;}else{r=p;p=p->next;}}}2．void converse(Linklist &h){Linknode *p,*q;p=h->next;h->next=NULL;while(p){q=p->next;p->next=h->next;h->next=p;p=q;}}3．void decompose(Linklist La,Linklist &Lb,Linklist &Lc) {Linknode *p;Lc=(Linknode *)malloc(sizeof(Linknode));Lc->next=NULL;p=La->next;Lb=La;Lb->next=NULL;while(p){La=p->next;if(p->data>0){p->next=Lc->next;Lc->next=p;}else{p->next=Lb->next;Lb->next=p;}p=La;}}4．int subset(LinkList la, LinkList lb){ LinkNode * pa,*pb;pa=la->next;while(pa){ pb=lb->next;while(pb&&(pb->data!=pa->data)) pb=pb->next;if(!pb) return 0;pa=pa->next;}return 1;}算法时间复杂度O（A.Length*B.Length）5．void priorset(DuLinkList &la){ p=la;q=la->next;while(q!=la){q->prior=p; p=q;q=q->next;} q->prior=p;}第三章栈和队列一. 选择题1．C C 2．C 3．B 4．D 5．C 6．A 7．C 8．D二. 解答题1栈底栈底2//双向栈类型定义#define STACK_SIZE 100;Typedef struct {SElemType * base_one, * base_two;//栈底指针SElemType * top_one, * top_two;//栈顶指针int stacksize;} SqStack;Status InitStack ( SqStack &S) {//初始化双向栈S.base_one=S.top_one=( SElemType *)malloc(STACK_SIZE * sizeof(SElemType));//第一个栈底和栈顶指向数组起点S.base_two=S.top_two=S.base_one +STACK_SIZE-1;// 第二个栈底和栈顶指向数组终点S.stacksize= STACK_SIZE ;return OK;}//InitStackStatus Push ( SqStack &S, int i, SElemType e){//入栈操作，i=0时将e存入前栈，i=1时将e存入后栈if( S.top_two < S.top_one) return OVERFLOW;//栈满，不考虑追加空间if( i = = 0 )*S.top_one++ = e;else*S.top_two-- = e;return OK;}//PushSElemType Pop ( SqStack &S, int i){//出栈操作，i=0出前栈，i=1出后栈if( i==0 ) {if ( S.top_one==S.base_one) return ERROR;S.top_one--; e=*S.top_one;}else {if ( S.top_two==S.base_two) return ERROR;S.top_two++; e=*S.top_two;}return e;}//Pop2．#define M 3struct Stack{Qelemtype data[M];int top;};struct Queue{Stack s1;Stack s2;};void InitQueue(Queue &Q)//初始化队列{Q.s1.top=0;Q.s2.top=0;}int IsEmpty(Queue &Q)//判断队列是否为空{if(Q.s1.top==0&&Q.s2.top==0)return 1;if(Q.s2.top==0&&Q.s1.top!=0){while(Q.s1.top!=0)Q.s2.data[Q.s2.top++]=Q.s1.data[--Q.s1.top];}return 0;}int IsFull(Queue &Q){if(Q.s1.top==M&&Q.s2.top!=0)return 1;if(Q.s1.top==M&&Q.s2.top==0){while(Q.s1.top!=0)Q.s2.data[Q.s2.top++]=Q.s1.data[--Q.s1.top];return 0;}if(Q.s1.top!=M)return 0;}void InQueue(Queue &Q,Qelemtype e) {if(IsFull(Q)){cout<<"OVERFLOW"<<endl;return;}Q.s1.data[Q.s1.top++]=e;}void DeQueue(Queue &Q,Qelemtype &e) {if(IsEmpty(Q)){cout<<"UNDERFLOW"<<endl;return;}e=Q.s2.data[--Q.s2.top];}3．(1)不能（2）可以原因略4．struct QueueNode{Qelemtype data;QueueNode *next;};struct LinkQueue{QueueNode *rear;};void InitQueue(LinkQueue &Q) //置空队{Q.rear=new QueueNode;Q.rear->next=Q.rear;}int EmptyQueue(LinkQueue Q) //判队空{return Q.rear==Q.rear->next;}void EnQueue(LinkQueue &Q, Qelemtype e)//元素入队{QueueNode *p;//新建一个结点，并置其值为ep=new QueueNode;p->data=e;//将结点插入队列末尾p->next=Q.rear->next;Q.rear->next=p;//修改队尾指针Q.rear=p;}void DeQueue(LinkQueue &Q,Qelemtype &e) //元素出队{QueueNode *p;if (EmptyQueue(Q)) //若队中无元素，则无法执行出队操作{cout<<"error"<<endl;return;}p=Q.rear->next->next; //让p指向队头元素e=p->data;if(p==Q.rear)//如队中只有一个元素，则要rear指向头结点，头结点的next指针指向自身{Q.rear=Q.rear->next;Q.rear->next=Q.rear;}else //若队中不只一个元素，则删除p所指向的结点。

数据结构第二章线性表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）。

第二章线性表一、选择题1.线性表是（）A．一个有限序列，可以为空B．一个有限序列，不可以为空C．一个无限序列，可以为空D．一个无限序列，不可以为空2.一维数组与线性表的特征是（）。

A．前者长度固定，后者长度可变B．两者长度均固定C．后者长度固定，前者长度可变D．两者长度均可变3.用单链表方式存储的线性表，存储每个结点需要两个域，一个数据域，另一个是( ).A．当前结点所在地址域B．指针域C．空指针域D．空闲域4.用链表表示线性表的优点是（）。

A．便于随机存取B．便于进行插入和删除操作C．占用的存储空间较顺序表少D．元素的物理顺序与逻辑顺序相同5.在具有 n 个结点的单链表中，实现___的操作，其算法的时间复杂度都是O（n）。

A．遍历链表和求链表的第i个结点D．删除地址为P的结点的后继结点B．在地址为P的结点之后插入一个结点 C．删除开始结点6.下面关于线性表的叙述中，错误的是（）。

A．线性表采用顺序存储必须占用一片连续的存储单元B．线性表采用顺序存储便于进行插入和删除操作C．线性表采用链式存储不必占用一片连续的存储单元D．线性表采用链式存储便于进行插入和删除操作7.已知单链表的每个结点包括一个指针域next，它指向该结点的后继结点。

现要将指针 q 指向的新结点插入到指针 p 指向的结点之后，下面的操作序列中正确的是（）。

A . q = p->next; p->next = q->next ;B . p->next = q->next; q = p->next ;C . q->next = p->next; p->next = q ;D . p->next = q; q->next = p->next ;8.设 a l，a2， a3为三个结点； p , 10 , 20 代表地址，则如下的链表存储结构称为（）。

A．链表B．单链表C．双向循环链表D．双向链表9.单链表的存储密度（）。

数据结构(第二版)课后习题答案第一章：数据结构概述数据结构是计算机科学中非常重要的一个概念，它用于组织和管理计算机内部存储的数据。

数据结构的设计直接影响到程序的运行效率和对真实世界问题的建模能力。

第二版的《数据结构》教材旨在帮助读者更好地理解和应用数据结构。

为了提高学习效果，每章节后都附有一系列习题。

本文将为第二版《数据结构》教材中的部分习题提供详细的答案和解析。

第二章：线性表2.1 顺序表习题1：请问如何判断顺序表是否为空表？答案：当顺序表的长度为0时，即为空表。

解析：顺序表是用一块连续的内存空间存储数据元素的线性结构。

当顺序表中没有元素时，长度为0，即为空表。

习题2：如何求顺序表中第i个元素的值？答案：可以通过访问顺序表的第i-1个位置来获取第i个元素的值。

解析：顺序表中的元素在内存中是连续存储的，通过下标访问元素时，需要将下标减1，因为数组是从0开始编号的。

2.2 链表习题1：请问链表中的结点包含哪些信息？答案：链表的结点一般包含两部分信息：数据域和指针域。

解析：数据域用于存储数据元素的值，指针域用于存储指向下一个结点的指针。

习题2：如何删除链表中的一个结点？答案：删除链表中的一个结点需要将其前一个结点的指针指向其后一个结点，然后释放被删除结点的内存空间。

解析：链表的删除操作相对简单，只需要通过修改指针的指向即可。

但需要注意释放被删除结点的内存空间，防止内存泄漏。

第三章：栈和队列3.1 栈习题1：如何判断栈是否为空？答案：当栈中没有任何元素时，即为空栈。

解析：栈是一种先进后出（Last In First Out，LIFO）的数据结构，栈顶指针指向栈顶元素。

当栈中没有元素时，栈顶指针为空。

习题2：请问入栈和出栈操作的时间复杂度是多少？答案：入栈和出栈操作的时间复杂度均为O(1)。

解析：栈的入栈和出栈操作只涉及栈顶指针的改变，不受栈中元素数量的影响，因此时间复杂度为O(1)。

3.2 队列习题1：请问队列可以用哪些方式实现？答案：队列可以用数组或链表来实现。

数据结构部分习题一、问答题1、简述下列术语：线性表，顺序表，链表。

2、何时选用顺序表，何时选用链表作为线性表的存储结构合适?各自的主要优缺点是什么?3、在顺序表中插入和删除一个结点平均需要移动多少个结点?具体的移动次数取决于哪两个因素?4、链表所表示的元素是否有序?如有序，则有序性体现于何处?链表所表示的元素是否一定要在物理上是相邻的?二、单选题1、在表长为n的单链表中,算法时间复杂度为O(n)的操作是( )。

A. 查找单链表中第i个结点B. 在p结点之后插入一个结点C. 删除表中第一个结点D. 删除p结点的直接后继结点2、在下列链表中不能从当前结点出发访问到其余各结点的是( )。

A. 单链表B. 单循环链表C. 双向链表D. 双向循环链表3、线性表采用顺序存储时，其地址( )A．必须是连续的B．部分地址必须是连续的C．一定是不连续的D．连续与否均可以4、线性表采用链式存储结构时，其地址( )A．必须是连续的B．部分地址必须是连续的C.一定是不连续的D．连续与否均可以5、在长度为n的顺序表的第i个数据元素(1≤i≤n)之前插入一个数据元素,元素的移动次数为( )。

A. n-i+1B. n-iC. iD. i-16、对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为( )。

A. 顺序表B. 用头指针表示的单循环链表C. 用尾指针表示的单循环链表D. 单链表7、在需要经常查找结点的前驱与后继的场合中，使用( )比较合适。

A．单链表B．双向链表C．单循环链表D．循环链表8、在一个单链表h中，若要删除由指针q所指向结点的直接后继结点，则执行（）。

A．p = q->next ; p->next = q->next;B．p = q->next ; q->next = p;C．p = q->next ; q->next = p->next;D．q->next = q->next->next; q->next = q;9、9、链表不具有的特点是（）。

数据结构第二章习题第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（指向尾结点），执行_________操作与链表的长度有关。

第二章线性表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 的顺序表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均次数为（E ），删除一个元素需要移动的元素个数为（A ）。

A. (N-1)/2B. NC. N+1D. N-1E. N/2F. (N+1)/2G. (N-2)/22.线性表是具有N 个（C ）的有限序列。

A、表元素B、字符C、数据元素D、数据项E、信息3.“线性表的逻辑顺序和物理顺序总是一致的。

”这个结论是（B ）。

A、正确的B、错误的C、不一定，与具体结构有关。

4.线性表采用链式存储结构时，要求内存中可用存储单元的地址（D ）。

A、必须是连续的B、部分地址必须是连续的C、一定是不连续的D、连续或不连续都可以。

5.带头结点的单链表为空的判定条件是（B ）。

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

A、head==NULLB、head->next==NULLC、head->next==headD、head!=NULL7.非空的循环单链表head 的尾结点P 满足（ C ）。

A、P->NEXT=NULLB、p=NULLC、p->next==headD、p==head8.在一个具有n 个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（B ）。

A、O(1)B、O(n)C、O(n2)D、O(nlog2n)9.在一个单链表中，若删除P 所指结点的后继结点，则执行（ A ）。

A、p->next=p->next->nextB、p=p->next;p->next=p->next->nextC、p->next=p->next;D、p=p->next->next;10.在一个单链表中，若在Ｐ所指结点之后插入Ｓ所指结点，则执行（B ）。

第二章作业题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.在链表的结点中，数据元素所占的存储量和整个结点所占的存储量之比称作________。