下载文档原格式
数据结构第二章参考答案1. 线性表线性表是数据结构中最基本的一种结构，在实际应用中广泛使用。
它是一个有序的数据元素序列，其中每个元素都有唯一的前驱和后继，除了第一个元素没有前驱，最后一个元素没有后继。
2. 顺序存储结构顺序存储结构是线性表最简单的一种实现方式。
它利用一段连续的存储空间依次存储线性表的元素，存储位置是连续的。
在顺序存储结构中，插入和删除操作需要移动大量元素，因此效率较低。
3. 链式存储结构链式存储结构通过指针将线性表的各个元素链接起来。
每个元素都包含一个数据域和一个指针域，数据域用于存储数据元素，指针域用于存储下一个元素的地址。
在链式存储结构中，插入和删除操作只需要修改指针，效率较高。
4. 栈栈是一种特殊的线性表，它只允许在表的一端进行插入和删除操作，这一端称为栈顶。
栈的特点是后进先出，即最后插入的元素最先被删除。
栈的应用场景包括函数调用、表达式求值等。
5. 队列队列也是一种特殊的线性表，它允许在表的一端（队尾）插入元素，在另一端（队首）删除元素。
队列的特点是先进先出，即最先插入的元素最先被删除。
队列的应用场景包括进程调度、打印队列等。
6. 递归递归是一种解决问题的方法，通过调用自身来解决规模较小的子问题。
在数据结构中，递归广泛应用于树和图的操作中。
递归需要注意递归的边界条件和递归的停止条件，以避免无限递归的问题。
7. 树树是一种非线性的数据结构，它由n个节点组成，这些节点通过边连接起来。
树的特点是每个节点最多有一个父节点，但可以有多个子节点。
树的应用场景包括文件系统、组织结构等。
8. 二叉树二叉树是一种特殊的树结构，每个节点最多有两个子节点。
二叉树的遍历有三种方式：前序遍历（根-左-右）、中序遍历（左-根-右）和后序遍历（左-右-根）。
二叉树的应用场景包括查找、排序等。
9. 查找算法查找算法是在数据集合中寻找特定元素的过程。
常用的查找算法有顺序查找、二分查找、哈希查找等。
不同的查找算法有不同的时间复杂度和空间复杂度，对于不同规模的数据集合有不同的效率。
第二章线性表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、头结点并不“仅起”标识作用，并且使操作统一。
另外，头结点数据域可写入链表长度，或作监视哨。
4．两种存储结构各有优缺点，应根据实际情况选用，不能笼统说哪一个好。
7．集合中元素无逻辑关系。
9．非空线性表第一个元素无前驱，最后一个元素无后继。
13．线性表是逻辑结构，可以顺序存储，也可链式存储。
三．填空题1．顺序 2．（n-1）/2 3．py->next=px->next; px->next=py4 ．n-i+15．主要是使插入和删除等操作统一，在第一个元素之前插入元素和删除第一个结点不必另作判断。
另外，不论链表是否为空，链表指针不变。
6．O(1)，O(n) 7．单链表，多重链表，（动态）链表，静态链表8．f->next=p->next; f->prior=p; p->next->prior=f; p->next=f;9．p^.prior s^.prior^.next10．指针 11．物理上相邻指针 12．4 213．从任一结点出发都可访问到链表中每一个元素。
14．u=p->next; p->next=u->next; free(u); 15．L->next->next==L 16．p->next!=null17．L->next==L && L->prior==L 18．s->next=p->next;p->next=s; 19．(1) IF pa=NIL THEN return(true);(2) pb<>NIL AND pa^.data>=pb^.data(3) return(inclusion(pa,pb));(4) pb:=pb^.next;(5) return(false);非递归算法：(1)pre:=pb; (2) pa<>NIL AND pb<>NIL AND pb^.data>=pa^.data (3)pa:=pa^.next; pb:=pb->next;(4)pb:=pre^.next;pre:=pb;pa:=pa^.next;(5)IF pa=NIL THEN return(true) ELSE return(false);[注]：本题是在链表上求模式匹配问题。
一、选择题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.1 什么是数据结构？数据结构是指相互之间存在一种或多种特定关系的数据元素的集合，包括数据的逻辑结构、物理结构和数据元素之间的运算。
1.2 数据的逻辑结构有哪些？数据的逻辑结构包括线性结构、树形结构和图状结构。
1.3 数据的物理结构有哪些？数据的物理结构包括顺序存储结构和链式存储结构。
1.4 数据结构的主要目标是什么？数据结构的主要目标是提高数据的存储效率和运算效率。
第二章：线性表2.1 线性表的定义线性表是由n(≥0)个数据元素组成的有限序列。
线性表是一种常见的数据结构，常用的实现方式包括数组和链表。
2.2 线性表的顺序存储结构线性表的顺序存储结构是将线性表中的元素存储在连续的存储空间中，通过元素在内存中的物理位置来表示元素之间的关系。
2.3 线性表的链式存储结构线性表的链式存储结构是通过指针将线性表中的元素连接在一起，每个元素包括数据域和指针域。
2.4 线性表的基本操作包括初始化线性表、插入元素、删除元素、查找元素等。
第三章：栈与队列3.1 栈的定义与特性栈是一种具有后进先出特性的线性表，只允许在一端进行插入和删除操作，被称为栈顶。
3.2 栈的顺序存储结构和链式存储结构栈的顺序存储结构和链式存储结构与线性表的存储结构类似，不同之处在于栈只允许在一端进行插入和删除操作。
3.3 栈的应用栈在表达式求值、函数调用和递归等场景中有广泛应用。
3.4 队列的定义与特性队列是一种具有先进先出特性的线性表，允许在一端插入元素，在另一端删除元素。
3.5 队列的顺序存储结构和链式存储结构队列的顺序存储结构和链式存储结构与线性表的存储结构类似，不同之处在于队列允许在一端插入元素，在另一端删除元素。
3.6 队列的应用队列在模拟排队系统、操作系统进程调度等场景中有广泛应用。
第四章：树与二叉树4.1 树的基本概念树是由n(≥0)个节点组成的有限集合，其中有一个称为根节点，除了根节点之外的其余节点被分为m(m≥0)个互不相交的集合，每个集合本身又是一棵树。
数据结构第二章习题解答一、单选题1．在一个长度为n的顺序存储线性表中，向第i个元素(1≤i≤n+1)之前插入一个新元素时，需要从后向前依次后移（B）个元素。
A、n-iB、n-i+1C、n-i-1D、i2．在一个长度为n的顺序存储线性表中，删除第i个元素(1≤i≤n+1)时，需要从前向后依次前移（A）个元素。
A、n-iB、n-i+1C、n-i-1D、i3. 在一个长度为n的线性表中顺序查找值为x的元素时，在等概率情况下，查找成功时的平均查找长度（即需要比较的元素个数）为( C )。
A. nB. n/2C. (n+1)/2D. (n-1)/24．在一个长度为n的线性表中，删除值为x的元素时需要比较元素和移动元素的总次数为(C )。
A. (n+1)/2B. n/2C. nD. n+15. 在一个顺序表的表尾插入一个元素的时间复杂度为(B )。
A. O(n)B. O(1)C. O(n*n)D. O(log2n)6.若一个结点的引用为p，它的前驱结点的引用为q，则删除p的后继结点的操作为(B )。
A. p=p.next.nextB. p.next=p.next.nextC. q.next=p.nextD. q.next=q.next.next8. 假定一个多项式中x的最高次幂为n，则在保存所有系数项的线性表表示中，其线性表长度为(A )。
A. n+1B. nC. n-1D. n+2二、填空题1．对于当前长度为n的线性表，共包含有________多个插入元素的位置，共包含有________多个删除元素的位置。
（答案n+1 n）2．若经常需要对线性表进行表尾插入和删除运算，则最好采用________存储结构，若经常需要对线性表进行表头插入和删除运算，则最好采用________存储结构。
（答案：顺序链式）3．由n个元素生成一个顺序表，若每次都调用插入算法把一个元素插入到表头，则整个算法的时间复杂度为________，若每次都调用插入算法把一个元素插入到表尾，则整个算法的时间复杂度为________。
第二章线性表一、选择题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个位置上的元素。
第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.在一个单链表中，若在Ｐ所指结点之后插入Ｓ所指结点，则执行（）。
