数据结构C语言版第一二章习题答案

数据结构习题集答案(C语言版严蔚敏)第2章线性表2.1 描述以下三个概念的区别：头指针，头结点，首元结点（第一个元素结点）。

解：头指针是指向链表中第一个结点的指针。

首元结点是指链表中存储第一个数据元素的结点。

头结点是在首元结点之前附设的一个结点，该结点不存储数据元素，其指针域指向首元结点，其作用主要是为了方便对链表的操作。

它可以对空表、非空表以及首元结点的操作进行统一处理。

2.2 填空题。

解：(1) 在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与元素在表中的位置有关。

(2) 顺序表中逻辑上相邻的元素的物理位置必定紧邻。

单链表中逻辑上相邻的元素的物理位置不一定紧邻。

(3) 在单链表中，除了首元结点外，任一结点的存储位置由其前驱结点的链域的值指示。

(4) 在单链表中设置头结点的作用是插入和删除首元结点时不用进行特殊处理。

2.3 在什么情况下用顺序表比链表好解：当线性表的数据元素在物理位置上是连续存储的时候，用顺序表比用链表好，其特点是可以进行随机存取。

2.4 对以下单链表分别执行下列各程序段，并画出结果示意图。

解：2.5 画出执行下列各行语句后各指针及链表的示意图。

L=(LinkList)malloc(sizeof(LNode)); P=L;for(i=1;i<=4;i++){P->next=(LinkList)malloc(sizeof(LNode));P=P->next; P->data=i*2-1;}P->next=NULL;for(i=4;i>=1;i--) Ins_LinkList(L,i+1,i*2);for(i=1;i<=3;i++) Del_LinkList(L,i);解：2.6 已知L是无表头结点的单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。

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

一、单选题1、______ 是数据的最小单位。

A、数据项B、表元素C、信息项D、数据元素2、以下说法不正确的是______。

A、数据可由若干个数据元素构成B、数据项可由若干个数据元素构成C、数据项是不可分割的最小标识单位D、数据元素是数据的基本单位3、数据结构是指 ______ 的集合以及它们之间的关系。

A、数据B、结构C、数据元素D、计算方法4、计算机所处理的数据一般具备某种内在联系，这是指 ______。

A、数据和数据之间存在某种关系B、元素和元素之间存在某种关系C、元素内部具有某种结构D、数据项和数据项之间存在某种关系5、在数据结构中，与所使用的计算机无关的是数据的 ______ 结构。

A、逻辑B、存储C、逻辑和存储D、物理6、数据的逻辑结构可以分为 ______ 两类。

A、紧凑结构和非紧凑结构B、动态结构和静态结构C、线性结构和非线性结构D、内部结构和外部结构7、数据的逻辑结构是指 ______ 关系的整体。

A、数据项之间逻辑B、数据元素之间逻辑C、数据类型之间D、存储结构之间8、以下是数据结构中 ______ 属非线性结构。

A、串B、栈C、队列D、平衡二叉树9、以下属于逻辑结构是 ______。

A、双链表B、单链表C、顺序表D、有序表10、以下不属于存储结构是______。

A、顺序表B、线性表C、邻接表D、单链表11、在计算机中存储数据时，通常不仅要存储各数据元素的值，而且还有存储 ______。

A、数据元素之间的关系B、数据元素的类型C、数据的处理方法D、数据的存储方法12、数据结构在计算机内存中的表示是指 ______。

A、数据的逻辑结构B、数据结构C、数据元素之间的关系D、数据的存储结构13、在数据的存储中，一个节点通常存储一个 ______。

A、数据结构B、数据元素C、数据项D、数据类型14、在决定选取任何类型的存储结构时，一般不多考虑 ______。

A、各节点的值如何B、节点个数的多少C、对数据有哪些运算D、所用编程语言实现这种结构是否方便15、数据在计算机的存储器中表示时，逻辑上相邻的两个元素对应的物理地址也是相邻的，这种存储结构称之为 ______。

第1、2章练习题1．以下叙述正确的是（）。

BA）C语言程序是由过程和函数组成的B）C语言函数可以嵌套调用，例如fun(fun(x)) C）C语言函数不可以单独编译D）C语言除了main函数外，其他函数不可以作为单独文件形式存在2．以下叙述正确的是（）。

CA）C程序的基本组成单位是语句B）C程序中的每一行只能写一条语句C）简单的C语句必须以分号结束D）C语句必须在一行内写完3．以下叙述中正确的是（）。

CA）C程序中的注释只能出现在程序的开始位置和语句的后面B）C程序书写格式严格，要求一行内只能写一条语句C）C程序书写格式自由，一条语句可以写在多行上D）用C语言编写的程序只能放在一个程序文件中4．下列叙述中错误的是（）。

AA）一个C语言程序只能实现一种算法B）C语言程序可以由多个程序文件组成C）C语言程序可以由一个或多个函数组成D）一个C函数可以单独作为一个C程序文件存在5．以下叙述中正确的是（）。

C页脚内容1A）C语言程序将从源程序中的第一个函数开始执行B）可以在程序中由用户指定任意一个函数作为主函数，程序将从此开始执行C）C语言规定必须用main作为主函数名，程序从此开始执行，在此结束D）main可作为用户标识符，用以命名任意一个函数作为主函数6．对于一个正常运行的C程序，以下叙述正确的是（）。

AA）程序的执行总是从main函数开始，在main函数中结束B）程序的执行总是从程序的第一个函数开始，在main函数结束C）程序的执行总是从main函数开始，在程序的最后一个函数中结束D）程序的执行总是从程序的第一个函数开始，在程序的最后一个函数中结束7．下列叙述正确的是（）。

DA）每个C语言程序文件中都必须有一个main( )函数B）在C语言程序中main( )函数的位置是固定的C）C语言程序中所有函数之间都可以相互调用，与函数所在的位置无关D）在C语言程序的函数中不能定义另一个函数8．下列叙述中错误的是（）。

数据结构（C语言版）1800道题及答案[完整版]数据结构(C语言版)1800道题及答案[完整版]数据结构1800例题与答案第一章绪论一、选择题（每小题2分）1．算法的计算量的大小称为计算的（B ）。

【北京邮电大学2000 二、3 （20/8分）】A．效率 B．复杂性 C．现实性 D．难度2．算法的时间复杂度取决于（C）。

【中科院计算所 1998 二、1 （2分）】A．问题的规模 B．待处理数据的初态 C．A和B D．都不是3．计算机算法指的是（① C ），它必须具备（② B ）这三个特性。

① A．计算方法B．排序方法C．解决问题的步骤序列 D．调度方法② A．可执行性、可移植性、可扩充性B．可执行性、确定性、有穷性C．确定性、有穷性、稳定性 D．易读性、稳定性、安全性【南京理工大学1999 一、1（2分）【武汉交通科技大学1996 一、1（4分）】4．一个算法应该是（ B ）。

【中山大学 1998 二、1（2分）】A．程序 B．问题求解步骤的描述C．要满足五个基本特性 D．A和C.5．下面关于算法说法错误的是（ D ）【南京理工大学 2000 一、1（1.5分）】A．算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性D. 以上几个都是错误的6. 下面说法错误的是（C ）【南京理工大学2000 一、2 （1.5分）】(1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低A．(1) B.(1),(2) C.(1),(4) D.(3)7．从逻辑上可以把数据结构分为（ C ）两大类。

【武汉交通科技大学 1996 一、4（2分）】A．动态结构、静态结构 B．顺序结构、链式结构C．线性结构、非线性结构 D．初等结构、构造型结构8．以下与数据的存储结构无关的术语是（D ）。

数据结构(C语言版本)课后练习答案的完整版本第一章引言5。

选择题:CCBDCA 6。

尝试分析以下程序段的时间复杂性。

(1)o(1)(2)o(m * n)(3)o(N2)(4)o(log3n)(5)因为x已执行n-1n-2.1=n (n-1)/2，执行时间为O(n2)(6)O()第2章线性表1。

多项选择babadbcbdcddac 2。

算法设计问题(6)设计一种算法，通过一次遍历来确定单个链表中具有最大值的节点。

元素类型最大值(链表L ){如果(下一个==空)返回空；pmax=1-下一个；//假设第一个节点中的数据具有最大值p=L-下一个-下一个；同时(p！=NULL ){//如果在下一个节点处存在if(p-数据pmax-数据)pmax=p；p=p-下一个；}返回pmax-数据；(7)设计一种算法，通过遍历一次来反转链表中所有节点的链接方向，并且仍然使用原表的存储空间。

空逆(链表L) {//逆单个链表L p=L-头节点的下一个；下一个=空；而(p){ q=p-next；//q指向*p=l-next 的下一个p-next；l-next=p；//*p插入在头节点p=q之后；}}(10)已知长度n的线性表A采用顺序存储结构。

请编写一个时间复杂度为0(n)和空间复杂度为0(1)的算法，删除线性表中所有有值项的数据元素。

[主题分析]删除线性表中按顺序存储的元素通常涉及一系列元素的移动(删除第I个元素，并按顺序向前移动第I到第N个元素)。

本主题要求删除线性表中项目值为的所有数据元素，并且不要求元素之间的相对位置保持不变。

因此，可以考虑设置两个指针(i=1，j=n)从两端移到中间。

当遇到带有值项的数据元素时，右端元素将直接移动到带有值项的数据元素的位置。

虚删除(元素类型A[)，整数n)A是一个有n个元素的一维数组。

此算法删除值为项的中的所有元素。

{ I=1；j=n。

∑设置数组的低端和高端指针(下标)。

同时(不精确；r=p；//让r 作为指针，而(q！=null){ if(q-data data)r=q；q:=q-next。

数据结构c 版第二版课后习题答案数据结构是计算机科学中的重要概念，它研究如何组织和存储数据，以便能够高效地进行操作和检索。

C语言是一种广泛应用于软件开发的编程语言，而数据结构C版第二版是一本经典的教材，它介绍了C语言中常用的数据结构和算法。

在学习这本教材时，课后习题是检验自己理解和掌握程度的重要方式。

下面我将为大家提供一些课后习题的答案，希望对大家的学习有所帮助。

1. 第一章：引论习题1：数据结构是什么？它的作用是什么？答案：数据结构是一种组织和存储数据的方式，它可以帮助我们更高效地进行数据操作和检索。

它的作用是提供一种合理的数据组织方式，使得我们可以快速地找到和处理需要的数据。

习题2：请举例说明数据结构的应用场景。

答案：数据结构可以应用于各个领域，比如在图像处理中，我们可以使用二维数组来表示图像的像素点；在网络通信中，我们可以使用链表来存储和管理网络节点之间的连接关系；在数据库中，我们可以使用树结构来组织数据的层次关系等等。

2. 第二章：算法分析习题1：什么是时间复杂度和空间复杂度？它们分别表示什么？答案：时间复杂度是衡量算法执行时间的度量，它表示随着输入规模的增加，算法执行时间的增长趋势。

空间复杂度是衡量算法所需内存空间的度量，它表示随着输入规模的增加，算法所需内存空间的增长趋势。

习题2：请解释最坏情况时间复杂度和平均情况时间复杂度的区别。

答案：最坏情况时间复杂度是指在最不利的情况下，算法执行的时间复杂度。

平均情况时间复杂度是指在所有可能输入情况下，算法执行的平均时间复杂度。

最坏情况时间复杂度是对算法性能的保证，而平均情况时间复杂度更能反映算法的平均性能。

3. 第三章：线性表习题1：请实现一个线性表的顺序存储结构。

答案：可以使用数组来实现线性表的顺序存储结构。

定义一个固定大小的数组，然后使用一个变量来记录线性表中元素的个数，通过数组下标来访问和操作元素。

习题2：请实现一个线性表的链式存储结构。

国家计算机等级考试二级C语言公共基础知识总结第一章数据结构与算法1.1 算法算法：是指解题方案的准确而完整的描述。

算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。

算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。

特征包括：（1）可行性；（2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性；（3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义；（4）拥有足够的情报。

算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。

指令系统：一个计算机系统能执行的所有指令的集合。

基本运算包括：算术运算、逻辑运算、关系运算、数据传输。

算法的控制结构：顺序结构、选择结构、循环结构。

算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。

算法复杂度：算法时间复杂度和算法空间复杂度。

算法时间复杂度是指执行算法所需要的计算工作量。

算法空间复杂度是指执行这个算法所需要的内存空间。

1.2 数据结构的基本基本概念数据结构研究的三个方面：（1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；（2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。

数据结构是指相互有关联的数据元素的集合。

数据的逻辑结构包含：（1）表示数据元素的信息；（2）表示各数据元素之间的前后件关系。

数据的存储结构有顺序、链接、索引等。

线性结构条件：（1）有且只有一个根结点；（2）每一个结点最多有一个前件，也最多有一个后件。

非线性结构：不满足线性结构条件的数据结构。

1．3 线性表及其顺序存储结构线性表是由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。

在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件。

抽出时间去学习，凡事从小做起，不怕单调和重复，长期的积累坚持，想不成功，也难。

第1章绪论习题1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型2．试举一个数据结构的例子叙述其逻辑结构和存储结构两方面的含义和相互关系3．简述逻辑结构的四种基本关系并画出它们的关系图4．存储结构由哪两种基本的存储方法实现？5．选择题（1）在数据结构中从逻辑上可以把数据结构分成（）A．动态结构和静态结构 B．紧凑结构和非紧凑结构C．线性结构和非线性结构 D．内部结构和外部结构（2）与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）A．存储结构 B．存储实现C．逻辑结构 D．运算实现（3）通常要求同一逻辑结构中的所有数据元素具有相同的特性这意味着（）A．数据具有同一特点B．不仅数据元素所包含的数据项的个数要相同而且对应数据项的类型要一致C．每个数据元素都一样D．数据元素所包含的数据项的个数要相等（4）以下说法正确的是（）A．数据元素是数据的最小单位B．数据项是数据的基本单位C．数据结构是带有结构的各数据项的集合D．一些表面上很不相同的数据可以有相同的逻辑结构（5）以下与数据的存储结构无关的术语是（）A．顺序队列 B. 链表 C. 有序表 D. 链栈（6）以下数据结构中（）是非线性数据结构A．树 B．字符串 C．队 D．栈6．试分析下面各程序段的时间复杂度（1）x=90; y=100;while(y>0)if(x>100){x=x-10;y--;}else x++;（2）for (i=0; i<n; i++)for (j=0; j<m; j++)a[i][j]=0;（3）s=0;for i=0; i<n; i++)for(j=0; j<n; j++)s+=B[i][j];sum=s;（4）i=1;while(i<=n)i=i*3;（5）x=0;for(i=1; i<n; i++)for (j=1; j<=n-i; j++)x++;（6）x=n; //n>1y=0;while(x≥(y+1)* (y+1))y++;（1）O（1）（2）O（m*n）（3）O（n2）（4）O（log3n）（5）因为x++共执行了n-1+n-2+......＋1= n(n-1)/2所以执行时间为O（n2）（6）O()第2章线性表1．选择题（1）一个向量第一个元素的存储地址是100每个元素的长度为2则第5个元素的地址是（）A．110 B．108 C．100 D．120 （2）在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．8 B．63.5 C．63 D．7（4）链接存储的存储结构所占存储空间（）A．分两部分一部分存放结点值另一部分存放表示结点间关系的指针B．只有一部分存放结点值C．只有一部分存储表示结点间关系的指针D．分两部分一部分存放结点值另一部分存放结点所占单元数（5）线性表若采用链式存储结构时要求内存中可用存储单元的地址（）A．必须是连续的 B．部分地址必须是连续的C．一定是不连续的 D．连续或不连续都可以（6）线性表Ｌ在（）情况下适用于使用链式结构实现A．需经常修改Ｌ中的结点值Ｂ．需不断对Ｌ进行删除插入C．Ｌ中含有大量的结点Ｄ．Ｌ中结点结构复杂（7）单链表的存储密度（）A．大于1 B．等于1 C．小于1 D．不能确定（8）将两个各有n个元素的有序表归并成一个有序表其最少的比较次数是（）A．n B．2n-1 C．2n D．n-1（9）在一个长度为n的顺序表中在第i个元素（1≤i≤n+1）之前插入一个新元素时须向后移动（）个元素A．n-i B．n-i+1 C．n-i-1 D．i(10) 线性表L=(a1a2......an)下列说法正确的是（）A．每个元素都有一个直接前驱和一个直接后继B．线性表中至少有一个元素C．表中诸元素的排列必须是由小到大或由大到小D．除第一个和最后一个元素外其余每个元素都有一个且仅有一个直接前驱和直接后继(11) 若指定有n个元素的向量则建立一个有序单链表的时间复杂性的量级是（）A．O(1) B．O(n) C．O(n2) D．O(nlog2n)(12) 以下说法错误的是（）A．求表长、定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低B．顺序存储的线性表可以随机存取C．由于顺序存储要求连续的存储区域所以在存储管理上不够灵活D．线性表的链式存储结构优于顺序存储结构(13) 在单链表中要将s所指结点插入到p所指结点之后其语句应为（）A．s->next=p+1; p->next=s;B．(*p).next=s; (*s).next=(*p).next;C．s->next=p->next; p->next=s->next;D．s->next=p->next; p->next=s;(14) 在双向链表存储结构中删除p所指的结点时须修改指针（）A．p->next->prior=p->prior; p->prior->next=p->next;B．p->next=p->next->next; p->next->prior=p;C．p->prior->next=p; p->prior=p->prior->prior;D．p->prior=p->next->next; p->next=p->prior->prior;(15) 在双向循环链表中在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->prior=p; q->next=p->next; p->next=q; p->next->prior=q;2．算法设计题（1）将两个递增的有序链表合并为一个递增的有序链表要求结果链表仍使用原来两个链表的存储空间不另外占用其它的存储空间表中不允许有重复的数据void MergeList_L(LinkList &LaLinkList &LbLinkList &Lc){pa=La->next; pb=Lb->next;Lc=pc=La; //用La的头结点作为Lc的头结点while(pa && pb){if(pa->data<pb->data){ pc->next=pa;pc=pa;pa=pa->next;}else if(pa->data>pb->data) {pc->next=pb; pc=pb; pb=pb->next;} else {// 相等时取La的元素删除Lb的元素pc->next=pa;pc=pa;pa=pa->next;q=pb->next;delete pb ;pb =q;}}pc->next=pa?pa:pb; //插入剩余段delete Lb; //释放Lb的头结点}（2）将两个非递减的有序链表合并为一个非递增的有序链表要求结果链表仍使用原来两个链表的存储空间不另外占用其它的存储空间表中允许有重复的数据void union(LinkList& LaLinkList& LbLinkList& Lc) {pa = La->next; pb = Lb->next; // 初始化Lc=pc=La; //用La的头结点作为Lc的头结点Lc->next = NULL;while ( pa || pb ) {if ( !pa ) { q = pb; pb = pb->next; }else if ( !pb ) { q = pa; pa = pa->next; }else if (pa->data <= pb->data ) { q = pa; pa = pa->next; } else { q = pb; pb = pb->next; }q->next = Lc->next; Lc->next = q; // 插入}delete Lb; //释放Lb的头结点}（3）已知两个链表A和B分别表示两个集合其元素递增排列请设计算法求出A与B的交集并存放于A链表中void Mix(LinkList& LaLinkList& LbLinkList& Lc) {pa=la->next;pb=lb->next;∥设工作指针pa和pb；Lc=pc=La; //用La的头结点作为Lc的头结点while(pa&&pb)if(pa->data==pb->data)∥交集并入结果表中{ pc->next=pa;pc=pa;pa=pa->next;u=pb;pb=pb->next; delete u;}else if(pa->data<pb->data) {u=pa;pa=pa->next; delete u;} else {u=pb; pb=pb->next; delete u;}while(pa){ u=pa; pa=pa->next; delete u;}∥释放结点空间while(pb) {u=pb; pb=pb->next; delete u;}∥释放结点空间pc->next=null;∥置链表尾标记delete Lb; ∥注：本算法中也可对B表不作释放空间的处理（4）已知两个链表A和B分别表示两个集合其元素递增排列请设计算法求出两个集合A和B 的差集（即仅由在A中出现而不在B中出现的元素所构成的集合）并以同样的形式存储同时返回该集合的元素个数void Difference（LinkedList AB*n）∥A和B均是带头结点的递增有序的单链表分别存储了一个集合本算法求两集合的差集存储于单链表A中*n是结果集合中元素个数调用时为0{p=A->next；∥p和q分别是链表A和B的工作指针q=B->next； pre=A；∥pre为A中p所指结点的前驱结点的指针while（p!=null && q!=null）if（p->data<q->data）{pre=p；p=p->next；*n++；} ∥ A链表中当前结点指针后移else if（p->data>q->data）q=q->next；∥B链表中当前结点指针后移else {pre->next=p->next；∥处理AB中元素值相同的结点应删除u=p； p=p->next； delete u；} ∥删除结点（5）设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B、C其中B表的结点为A表中值小于零的结点而C表的结点为A表中值大于零的结点（链表A的元素类型为整型要求B、C表利用A表的结点）（6）设计一个算法通过一趟遍历在单链表中确定值最大的结点ElemType Max (LinkList L ){if(L->next==NULL) return NULL;pmax=L->next; //假定第一个结点中数据具有最大值p=L->next->next;while(p != NULL ){//如果下一个结点存在if(p->data > pmax->data) pmax=p;p=p->next;}return pmax->data;（7）设计一个算法通过遍历一趟将链表中所有结点的链接方向逆转仍利用原表的存储空间void inverse(LinkList &L) {// 逆置带头结点的单链表 Lp=L->next; L->next=NULL;while ( p) {q=p->next; // q指向*p的后继p->next=L->next;L->next=p; // *p插入在头结点之后p = q;}}（8）设计一个算法删除递增有序链表中值大于mink且小于maxk的所有元素（mink和maxk是给定的两个参数其值可以和表中的元素相同也可以不同）void delete(LinkList &Lint minkint maxk) {p=L->next; //首元结点while (p && p->data<=mink){ pre=p; p=p->next; } //查找第一个值>mink的结点 if (p) {while (p && p->data<maxk) p=p->next;// 查找第一个值≥maxk 的结点q=pre->next; pre->next=p; // 修改指针while (q!=p){ s=q->next; delete q; q=s; } // 释放结点空间 }//if}（9）已知p指向双向循环链表中的一个结点其结点结构为data、prior、next三个域写出算法change(p)交换p所指向的结点和它的前缀结点的顺序知道双向循环链表中的一个结点与前驱交换涉及到四个结点（p结点前驱结点前驱的前驱结点后继结点）六条链void Exchange（LinkedList p）∥p是双向循环链表中的一个结点本算法将p所指结点与其前驱结点交换{q=p->llink；q->llink->rlink=p；∥p的前驱的前驱之后继为pp->llink=q->llink；∥p的前驱指向其前驱的前驱q->rlink=p->rlink；∥p的前驱的后继为p的后继q->llink=p；∥p与其前驱交换p->rlink->llink=q；∥p的后继的前驱指向原p的前驱p->rlink=q；∥p的后继指向其原来的前驱}∥算法exchange结束（10）已知长度为n的线性表A采用顺序存储结构请写一时间复杂度为O(n)、空间复杂度为O(1)的算法该算法删除线性表中所有值为item的数据元素[题目分析] 在顺序存储的线性表上删除元素通常要涉及到一系列元素的移动（删第i个元素第i+1至第n个元素要依次前移）本题要求删除线性表中所有值为item的数据元素并未要求元素间的相对位置不变因此可以考虑设头尾两个指针（i=1j=n）从两端向中间移动凡遇到值item的数据元素时直接将右端元素左移至值为item的数据元素位置void Delete（ElemType A[ ]int n）∥A是有n个元素的一维数组本算法删除A中所有值为item的元素{i=1；j=n；∥设置数组低、高端指针（下标）while（i<j）{while（i<j && A[i]!=item）i++；∥若值不为item左移指针if（i<j）while（i<j && A[j]==item）j--；∥若右端元素值为item 指针左移if（i<j）A[i++]=A[j--]；}[算法讨论] 因元素只扫描一趟算法时间复杂度为O（n）删除元素未使用其它辅助空间最后线性表中的元素个数是j。

第1 章绪论5．选择题：C CBDCA6．试分析下面各程序段的时间复杂度。

（1）O（1）（2）O（m*n）（3）O（n2）（4）O（log3n）O（n （5）因为x++ 共执行了n-1+n-2+⋯⋯＋1= n(n-1)/2 ，所以执行时间为2）（6）O( n )第2 章线性表1．选择题babadbcabdcddac2．算法设计题（6）设计一个算法，通过一趟遍历在单链表中确定值最大的结点。

ElemType Max (LinkList L ){if(L->next==NULL) return NULL;pmax=L->next; // 假定第一个结点中数据具有最大值p=L->next->next;while(p != NULL ){// 如果下一个结点存在if(p->data > pmax->data) pmax=p;p=p->next;}return pmax->data;原表（7）设计一个算法，通过遍历一趟，将链表中所有结点的链接方向逆转，仍利用的存储空间。

void inverse(LinkList &L) {// 逆置带头结点的单链表Lp=L->next; L->next=NULL;while ( p) {q=p->next; // q 指向*p 的后继p->next=L->next;L->next=p; // *p 插入在头结点之后p = q;}}（10）已知长度为n 的线性表 A 采用顺序存储结构，请写一时间复杂度为O (n) 、空间复杂度为O (1) 的算法，该算法删除线性表中所有值为item 的数据元素。

[ 题目分析] 在顺序存储的线性表上删除元素，通常要涉及到一系列元素的移动（删第i 个元素，第i+1 至第n 个元素要依次前移）。

本题要求删除线性表中所有值为item 的数据元素，并未要求元素间的相对位置不变。

数据结构（C语言版）（第2版）课后习题答案李冬梅2015.3目录第1章绪论................................................................................................................... 第2章线性表 ............................................................................................................... 第3章栈和队列............................................................................................................ 第4章串、数组和广义表 ............................................................................................ 第5章树和二叉树........................................................................................................ 第6章图. (41)第7章查找 ................................................................................................................... 第8章排序...................................................................................................................第1章绪论1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。

第 1 章绪论1.1简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。

解：数据是对客观事物的符号表示。

在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。

数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

数据对象是性质相同的数据元素的集合，是数据的一个子集。

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。

存储结构是数据结构在计算机中的表示。

数据类型是一个值的集合和定义在这个值集上的一组操作的总称。

抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。

是对一般数据类型的扩展。

1.2试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。

解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。

一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。

抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。

在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。

1.3设有数据结构(D,R)，其中D = {d1, d 2, d 3, d 4}，R = {r}，r = {(d1, d 2), (d 2, d3),(d 3, d 4)}试按图论中图的画法惯例画出其逻辑结构图。

解：1.4试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。

解：ADT Complex{数据对象：D={r,i|r,i 为实数}数据关系：R={<r,i>}基本操作：InitComplex(&C,re,im)操作结果：构造一个复数 C，其实部和虚部分别为re 和 imDestroyCmoplex(&C)操作结果：销毁复数 CGet(C,k,&e)操作结果：用 e 返回复数C 的第k 元的值Put(&C,k,e)操作结果：改变复数 C 的第k 元的值为eIsAscending(C)操作结果：如果复数 C 的两个元素按升序排列，则返回 1，否则返回 0IsDescending(C)操作结果：如果复数 C 的两个元素按降序排列，则返回 1，否则返回 0 Max(C,&e)操作结果：用 e 返回复数C 的两个元素中值较大的一个Min(C,&e)操作结果：用 e 返回复数C 的两个元素中值较小的一个}ADT ComplexADT RationalNumber{数据对象：D={s,m|s,m 为自然数，且 m 不为 0}数据关系：R={<s,m>}基本操作：InitRationalNumber(&R,s,m)操作结果：构造一个有理数 R，其分子和分母分别为 s 和mDestroyRationalNumber(&R)操作结果：销毁有理数 RGet(R,k,&e)操作结果：用 e 返回有理数 R 的第k 元的值Put(&R,k,e)操作结果：改变有理数 R 的第k 元的值为 eIsAscending(R)操作结果：若有理数 R 的两个元素按升序排列，则返回 1，否则返回 0 IsDescending(R)操作结果：若有理数 R 的两个元素按降序排列，则返回 1，否则返回 0 Max(R,&e)操作结果：用 e 返回有理数 R 的两个元素中值较大的一个Min(R,&e)操作结果：用 e 返回有理数 R 的两个元素中值较小的一个}ADT RationalNumber1.5试画出与下列程序段等价的框图。

数据结构章节练习题第一章绪论一、单选题1.一个数组元素a[i]与________的表示等价。

A、 *(a+i)B、 a+iC、 *a+iD、 &a+i2.下面程序段的时间复杂度为____________。

for(int i=0; i<m; i++)for(int j=0; j<n; j++)a[i][j]=i*j;A、 O(m2)B、 O(n2)C、 O(m*n)D、 O(m+n)3.执行下面程序段时，执行S语句的次数为____________。

for(int i=1; i<=n; i++)for(int j=1; j<=i; j++)S;A、 n2B、 n2/2C、 n(n+1)D、 n(n+1)/24.下面算法的时间复杂度为____________。

int f( unsigned int n ){ if ( n==0 || n==1 ) return 1; else return n*f(n-1); }A、 O(1)B、 O(n)C、 O(n2)D、 O(n!)二、填空题1.数据的逻辑结构被分为__________、_________、__________和__________四种。

2.数据的存储结构被分为__________、和__________两种。

3.在线性结构、树形结构和图形结构中，前驱和后继结点之间分别存在着________、________和________的联系。

4.一种抽象数据类型包括__________和__________两个部分。

5.当一个形参类型的长度较大时，应最好说明为_________，以节省参数值的传输时间和存储参数的空间。

6.当需要用一个形参访问对应的实参时，则该形参应说明为__________。

7.在函数中对引用形参的修改就是对相应__________的修改，对__________形参的修改只局限在该函数的内部，不会反映到对应的实参上。

第1章 绪论5．选择题：CCBDCA6．试分析下面各程序段的时间复杂度。

．试分析下面各程序段的时间复杂度。

（1）O （1） （2）O （m*n ） （3）O （n 2） （4）O （log 3n ）（5）因为x++共执行了n-1+n-2+……＋1= n(n-1)/2，所以执行时间为O （n 2） （6）O(n )第2章 线性表1．选择题．选择题babadbcabdcddac 2．算法设计题．算法设计题（6）设计一个算法，通过一趟遍历在单链表中确定值最大的结点。

）设计一个算法，通过一趟遍历在单链表中确定值最大的结点。

ElemType Max (LinkList L ){if(L->next==NULL) return NULL; pmax=L->next; //假定第一个结点中数据具有最大值假定第一个结点中数据具有最大值 p=L->next->next;while(p != NULL ){//如果下一个结点存在if(p->data > pmax->data) pmax=p; p=p->next; }return pmax->data;（7）设计一个算法，通过遍历一趟，将链表中所有结点的链接方向逆转，仍利用原表的存储空间。

的存储空间。

void inverse(LinkList &L) { // 逆置带头结点的单链表 Lp=L->next; L->next=NULL; while ( p) {q=p->next; // q 指向*p 的后继 p->next=L->next;L->next=p; // *p 插入在头结点之后 p = q; }}、空间(n)、空间（10）已知长度为n的线性表A采用顺序存储结构，请写一时间复杂度为O(n)的数据元素。

复杂度为O(1)的算法，该算法删除线性表中所有值为item的数据元素。

数据结构（C语言版）第1章习题答案1第一章概论自测题答案一、填空题1. 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和运算等的学科。

2. 数据结构被形式地定义为（D, R ），其中D 是数据元素的有限集合，R 是D 上的关系有限集合。

3. 数据结构包括数据的逻辑结构、数据的存储结构和数据的运算这三个方面的内容。

4. 数据结构按逻辑结构可分为两大类，它们分别是线性结构和非线性结构。

5. 线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。

6．在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有 1个前驱结点；最后一个结点没有后续结点，其余每个结点有且只有1个后续结点。

7. 在树形结构中，树根结点没有前驱结点，其余每个结点有且只有 1 个前驱结点；叶子结点没有后续结点，其余每个结点的后续结点数可以任意多个。

8. 在图形结构中，每个结点的前驱结点数和后续结点数可以任意多个。

9．数据的存储结构可用四种基本的存储方法表示，它们分别是顺序、链式、索引和散列。

10. 数据的运算最常用的有5种，它们分别是插入、删除、修改、查找、排序。

11. 一个算法的效率可分为时间效率和空间效率。

二、单项选择题（ B ）1. 非线性结构是数据元素之间存在一种：A ）一对多关系B ）多对多关系C ）多对一关系D ）一对一关系（ C ）2. 数据结构中，与所使用的计算机无关的是数据的结构；A) 存储 B) 物理 C) 逻辑 D) 物理和存储（ C ）3. 算法分析的目的是：A) 找出数据结构的合理性B) 研究算法中的输入和输出的关系C) 分析算法的效率以求改进 D) 分析算法的易懂性和文档性（ A ）4. 算法分析的两个主要方面是：A) 空间复杂性和时间复杂性 B) 正确性和简明性C) 可读性和文档性 D) 数据复杂性和程序复杂性（ C ）5. 计算机算法指的是：A) 计算方法 B) 排序方法 C) 解决问题的有限运算序列 D) 调度方法（ B ）6. 计算机算法必须具备输入、输出和等5个特性。

《数据结构（C语言版第2版）》（严蔚敏著）第一章练习题答案第1章绪论1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。

答案：数据：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。

如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。

数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。

在有些情况下，数据元素也称为元素、结点、记录等。

数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的一个格局（状态）、图中的一个顶点等。

数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。

例如，学生基本信息表中的学号、姓名、性别等都是数据项。

数据对象：是性质相同的数据元素的集合，是数据的一个子集。

例如：整数数据对象是集合N={0，±1，±2，…}，字母字符数据对象是集合C={‘A’，‘B’，…，‘Z’，‘a’，‘b’，…，‘z’}，学生基本信息表也可是一个数据对象。

数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。

换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。

逻辑结构：从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。

因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。

存储结构：数据对象在计算机中的存储表示，也称为物理结构。

抽象数据类型：由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。

具体包括三部分：数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。

2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。

答案：例如有一张学生基本信息表，包括学生的学号、姓名、性别、籍贯、专业等。

每个学生基本信息记录对应一个数据元素，学生记录按顺序号排列，形成了学生基本信息记录的线性序列。

严蔚敏《数据结构（C语言版）习题集》答案第一章绪论void print_descending(int x,int y,int z)....+f[m-k]=f[m-1]+f[m-2]+......+f[m-k]+f[m-k-1]-f[m-k-1]=2*f[m-1]-f[m-k-1]所以上述算法的时间复杂度仅为O(m). 如果采用递归设计,将达到O(k^m). 即使采用暂存中间结果的方法,也将达到O(m^2).typedef struct{char *sport;enum{male,female} gender;char schoolname; port!=NULL){switch(result[i].schoolname){case 'A':score[ 0 ].totalscore+=result[i].score;if(result[i].gender==0) score[ 0 ].malescore+=result[i].score;else score[ 0 ].femalescore+=result[i].score;break;case 'B':score[ 0 ].totalscore+=result[i].score;if(result[i].gender==0) score[ 0 ].malescore+=result[i].score;else score[ 0 ].femalescore+=result[i].score;break;………………}i++；}for(i=0;i<5;i++){printf("School %d:\n",i);printf("Total score of male:%d\n",score[i].malescore);printf("Total score of female:%d\n",score[i].femalescore);printf("Total score of all:%d\n\n",score[i].totalscore);}}void polyvalue(){float temp;float *p=a;printf("Input number of terms:");scanf("%d",&n);printf("Input value of x:");scanf("%f",&x);printf("Input the %d coefficients from a0 to a%d:\n",n+1,n);p=a;xp=1;sum=0;Status Insert(LinkList &L,int i,int b)void merge1(LinkList &A,LinkList &B,LinkList &C)void SqList_Intersect(SqList A,SqList B,SqList &C)void LinkList_Intersect_Delete(LinkList &A,LinkList B,LinkList C)iList为带头结点的单循环链表类型.{s=L->next;A=(CiList*)malloc(sizeof(CiLNode));p=A;B=(CiList*)malloc(sizeof(CiLNode));q=B;C=(CiList*)malloc(sizeof(CiLNode));r=C; .4,2的顺序重排双向循环链表L中的所有结点{p=;while(p->next!=L&&p->next->next!=L){p->next=p->next->next;p=p->next;} 同时进行调整的话,必须使用堆栈保存偶数结点的指针,否则将会破坏链表结构,造成结点丢失.DuLNode * Locate_DuList(DuLinkedList &L,int x) int x;int y;} coordinate;void Repaint_Color(int g[m][n],int i,int j,int color)归形式的算法该怎么写呢?void NiBoLan(char *str,char *new)题中暂不考虑串的具体操作的实现,而将其看作一种抽象数据类型stringtype,对其可以进行连接操作:c=link(a,b).Status g(int m,int n,int &s)void InitCiQueue(CiQueue &Q)Status EnCyQueue(CyQueue &Q,int x)省掉这一句,则在某些情况下,会引起不希望的后果,虽然在大多数情况下没有影响.请思考:设S='place', T='ace', V='face',则省掉i+=Strlen(V);运行时会出现什么结果?int Delete_SubString(Stringtype &s,Stringtype t)读者用此程序取代作者早些时候对题给出的程序.void StrAssign(Stringtype &T,char chars&#;)h&&T[j].ch!=c) j++; h) T[j].num++;else T[j]={c,1};}h;j++)printf("%c: %d\n",T[j].ch,T[j].num);}前一个程序的区别在于,串s业已存在.{for(p=s->next,q=t->next;p&&q;p=p->next,q=q->next){p->ch=q->ch;pre=p;}while(q){p=(LStrNode*)malloc(sizeof(LStrNode));p->ch=q->ch;pre->next=p;pre=p;}p->next=NULL;}算法的思想是,依次把串S的一个副本S2向右错位平移1格,2格,3格,...与自身S1相匹配,如果存在最长重复子串,则必然能在此过程中被发现.用变量lrs1,lrs2,maxlen来记录已发现的最长重复子串第一次出现位置,第二次出现位置和长度.题目中未说明"重复子串"是否允许有重叠部分,本算法假定允许.如不允许,只需在第二个for语句的循环条件中加上k<=i即可.本算法时间复杂度为O(Strlen(S)^2).void Get_LPubSub(Stringtype S,Stringtype T) for(k=0,j=jmin;j<=jmax;j++){if(A[j]==B[j-i]) k++;else k=0;if(k>maxlen){lps1=j-k+1;lps2=j-i-k+1;maxlen=k;}}一的区别是,由于A,B互不相同,因此B不仅要向右错位,而且还要向左错位,以保证不漏掉一些情况.当B相对于A的位置不同时,需要匹配的区间的计算公式也各不相同,请读者自己画图以帮助理解.本算法的时间复杂度是o（strlrn（s）*strlen（t））。

数据结构（C语⾔版）习题及答案第⼆章习题2.1选择题1、线性表的顺序存储结构是⼀种（A）的存储结构，线性表的链式存储结构是⼀种（B）的存储结构。

A、随机存取B、顺序存取C、索引存取D、散列存取2、对于⼀个线性，既要求能够进⾏较快的插⼊和删除，⼜要求存储结构能够反映数据元素之间的逻辑关系，则应该选择（B）。

A、顺序存储⽅式B、链式存储⽅式C、散列存储⽅式D、索引存储⽅式3、已知，L是⼀个不带头结点的单链表，p指向其中的⼀个结点，选择合适的语句实现在p结点的后⾯插⼊s结点的操作（B）。

A、p->next=s ; s->next=p->next ;B、s->next=p->next ; p->next=s ;C、p->next=s ; s->next=p ;D、s->next=p ; p->next=s ;4、单链表中各结点之间的地址（ C D）。

A、必须连续B、部分地址必须连续C、不⼀定连续D、连续与否都可以5、在⼀个长度为n的顺序表中向第i个元素（0A、n-iB、n-i+1C、n-i-1D、i2.2填空题1、顺序存储的长度为n的线性表，在任何位置上插⼊和删除操作的时间复杂度基本上都⼀样。

插⼊⼀个元素⼤约移动表中的（n/2）个元素，删除⼀个元素时⼤约移动表中的（(n-1)/2）个元素。

2、在线性表的顺序存储⽅式中，元素之间的逻辑关系是通过（物理顺序）来体现的；在链式存储⽅式，元素之间的逻辑关系是通过（指针）体现的。

3、对于⼀个长度为n的单链表，在已知的p结点后⾯插⼊⼀个新结点的时间复杂度为（o(1)），在p结点之前插⼊⼀个新结点的时间复杂度为（o(n)），在给定值为e的结点之后插⼊⼀个新结点的时间复杂度为（o(n)）。

4、在双向链表中，每个结点包含两个指针域，⼀个指向（前驱）结点，另⼀个指向（后继）结点。

5、对于循环链表来讲，逐个访问各个结点的结束判断条件是（设P为指向结点的指针，L为链表的头指针，则p->next= =L）。