数据结构(C语言)第一章习题自整理

数据结构C语言版第一二章习题答案Document number：BGCG-0857-BTDO-0089-2022第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）n）（4）O（log3（5）因为x++共执行了n-1+n-2+……＋1= n(n-1)/2，所以执行时间为O（n2）（6）O(n)第2章线性表1．选择题（1）一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（）。

第 1 章 绪 论(2005-07-14) -第 1 章 绪 论课后习题讲解1. 填空⑴（ ）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

【解答】数据元素⑵（ ）是数据的最小单位，（ ）是讨论数据结构时涉及的最小数据单位。

【解答】数据项，数据元素【分析】数据结构指的是数据元素以及数据元素之间的关系。

⑶ 从逻辑关系上讲，数据结构主要分为（ ）、（ ）、（ ）和（ ）。

【解答】集合，线性结构，树结构，图结构⑷ 数据的存储结构主要有（ ）和（ ）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（ ）和（）。

【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系⑸ 算法具有五个特性，分别是（ ）、（ ）、（ ）、（ ）、（ ）。

【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性⑹ 算法的描述方法通常有（ ）、（ ）、（ ）和（ ）四种，其中，（ ）被称为算法语言。

【解答】自然语言，程序设计语言，流程图，伪代码，伪代码⑺ 在一般情况下，一个算法的时间复杂度是（ ）的函数。

【解答】问题规模⑻ 设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（ ），若为n*log25n，则表示成数量级的形式为（ ）。

【解答】Ο(1)，Ο(nlog2n)【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。

2. 选择题⑴ 顺序存储结构中数据元素之间的逻辑关系是由（ ）表示的，链接存储结构中的数据元素之间的逻辑关系是由（ ）表示的。

A 线性结构B 非线性结构C 存储位置D 指针【解答】C，D【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。

⑵ 假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。

一、单选题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、数据在计算机的存储器中表示时，逻辑上相邻的两个元素对应的物理地址也是相邻的，这种存储结构称之为 ______。

数据结构（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 ）。

数据结构第一章课后习题与答案资料1.什么是数据结构？答：数据结构是指数据对象以及数据对象之间的关系、操作和约束的一种逻辑结构。

它关注如何将数据以及数据之间的关系组织起来，以便更高效地进行操作和使用。

2.数据结构的分类有哪些？答：数据结构可以分为线性数据结构和非线性数据结构。

线性数据结构包括数组、链表、栈和队列；非线性数据结构包括树和图。

3.什么是算法？答：算法是指解决特定问题的一系列步骤和规则。

它可以描述为一个有限的指令集，用于将输入数据转换为输出结果。

4.算法的特征有哪些？答：算法具有以下特征：•输入：算法必须有输入，可以是零个或多个。

•输出：算法必须有输出，可以是零个或多个。

•有穷性：算法必须在有限步骤内结束。

•确定性：算法的每一步骤必须明确且无歧义。

•可行性：算法的每一步骤必须可行，即可以执行。

5.算法的时间复杂度是什么？如何表示时间复杂度？答：算法的时间复杂度是指算法执行所需的时间。

它通常用大O符号表示。

常见的时间复杂度有O(1)、O(n)、O(n^2)等。

6.算法的空间复杂度是什么？如何表示空间复杂度？答：算法的空间复杂度是指算法执行所需的额外空间。

它通常用大O符号表示。

常见的空间复杂度有O(1)、O(n)、O(n^2)等。

7.什么是数据的逻辑结构？答：数据的逻辑结构是指数据对象之间的关系。

常见的逻辑结构有线性结构、树形结构和图形结构。

8.什么是数据的存储结构？答：数据的存储结构是指数据在计算机内存中的表示方式。

常见的存储结构有顺序存储结构和链式存储结构。

9.顺序存储结构和链式存储结构有什么区别？答：顺序存储结构将数据存储在一块连续的内存空间中，可以随机访问元素，但插入和删除操作需要移动大量元素。

链式存储结构将数据存储在不连续的内存空间中，通过指针相连，插入和删除操作只需要修改指针，但访问元素需要遍历链表。

10.数组和链表的区别是什么？答：数组是一种顺序存储结构，元素在内存中连续存储，可以通过下标直接访问元素；链表是一种链式存储结构，元素在内存中不连续存储，通过指针相连。

《数据结构-C语言版》第一章绪论单项选择题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．在对算法的时间复杂度进行估计的时候，下列最佳的时间复杂度是______。

2A.nB.nlognC.nD.logn7．设使用某算法对n个元素进行处理，所需的时间是T(n)=100nlog2n+200n+2000，则该算法的渐近时间复杂度为_______。

A.O(1)B.O(n)C.O(200n)D.O(nlog2n)1CDCBBDD第二章线性表单项选择题1．链表不具有的特点是________。

A.可随机访问任一元素B.插入和删除时不需要移动元素C.不必事先估计存储空间D.所需空间与线性表的长度正比2．设顺序表的每个元素占8个存储单元。

第1个单元的存储地址是100，则第6个元素占用的最后一个存储单元的地址为。

A.139B.140C.147D.1483．在线性链表存储结构下，插入操作算法。

A.需要判断是否表满B.需要判断是否表空C.不需要判断表满D.需要判断是否表空和表满4．在一个单链表中，若删除p所指结点的后继结点，则执行。

A.p->next=p->next->next;B.p->next=p->next;C.p=p->next->next;D.p=p->next;p->next=p->next->next;5．将长度为 n的单链表接在长度为m的单链表之后的算法时间复杂度为。

习题一1.1有下列几种用二元组表示的数据结构，试画出它们分别对应的图形表示（当出现多个关系时，对每个关系画出相应的结构图），并指出它们分别属于何种结构。

1．A=(K,R) 其中K={a1,a2,a3,…,a n}R={}2．B=(K,R)，其中K={a,b,c,d,e,f,g,h}R={<a,b>,<b,c>,<c,d>,<d,e>,<e,f>,<f,g>,<g,h>}3．C=(K,R)，其中K={a,b,c,d,e,f,g,h}R={<d,b>,<d,g>,<b,a>,<b,c>,<g,e>,<g,h>,<e,f>}4．D=(K,R)，其中K={1,2,3,4,5,6}R={(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)} 5．E=(K,R)，其中K={48,25,64,57,82,36,75,43}R={r1,r2,r3}r1={<48,25>,<25,64>,<64,57>,<57,82>,<82,36>,<36,75>,<75,43>}r2={<48,25>,<48,64>,<64,57>,<64,82>,<25,36>,<82,75>,<36,43>}r3={<25,36>,<36,43>,<43,48>,<48,57>,<57,64>,<64,75>,<75,82>} 解：⑴是集合结构；⑵是线性结构；⑶⑷是树型结构；⑸散列结构1.2用C语言函数编写下列每一个算法，并分别求出它们的时间复杂度。

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

第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。

数据结构(C语言版)(第2版)课后习题答案数据结构(C语言版)(第2版)课后习题答案1. 简介数据结构是计算机科学领域中非常重要的一门学科，它研究的是数据的组织、存储和管理方式。

本文将针对《数据结构(C语言版)(第2版)》的课后习题提供答案，帮助读者更好地理解和应用数据结构。

2. 第一章: 绪论在第一章中，主要介绍了数据结构的基本概念、分类和基本操作。

以下是部分习题的答案：2.1 习题1习题描述：什么是数据结构？答案：数据结构是指数据对象中元素之间的关系，以及对这些关系进行操作的方法和技术的集合。

2.2 习题2习题描述：数据结构的分类有哪些？答案：数据结构可以分为线性结构和非线性结构。

线性结构包括线性表、栈、队列等；非线性结构包括树、图等。

3. 第二章: 线性表第二章介绍了线性表的定义、分类和实现。

以下是部分习题的答案：3.1 习题1习题描述：什么是线性表？答案：线性表是由n个数据元素a1, a2, ..., an组成的有限序列，其中元素之间存在着一一对应的关系。

3.2 习题2习题描述：线性表的分类有哪些？答案：线性表可以分为顺序表和链表。

顺序表是用一段地址连续的存储单元一次存储线性表的所有元素，而链表是采用链式存储结构，通过每个元素存储其后继元素的地址来实现元素之间的逻辑关系。

4. 第三章: 栈与队列第三章讲解了栈和队列的定义、特性和实现。

以下是部分习题的答案：4.1 习题1习题描述：栈和队列有什么区别？答案：栈是一种后进先出的线性表，只能在表尾进行插入和删除操作；队列是一种先进先出的线性表，只能在表的一端进行插入和删除操作。

4.2 习题2习题描述：栈的应用有哪些？答案：栈在计算机科学中有广泛的应用，如函数的调用和返回、括号匹配、表达式求值等。

5. 第四章: 串第四章讲解了串的定义、模式匹配和实现。

以下是部分习题的答案：5.1 习题1习题描述：什么是串？答案：串是由零个或多个字符组成的有限序列，串中的字符个数称为串的长度。

第一章概论自测题答案姓名班级题号一二三四五六总分题分3315982015100得分一、填空题（每空1分，共33分）1. 一个计算机系统包括硬件系统和软件系统两大部分。

2. 一台计算机中全部程序的集合，称为这台计算机的软件资源/（系统）。

3. 计算机软件可以分为系统软件和应用软件两大类。

科学计算程序包属于应用软件，诊断程序属于系统软件（工具）。

4. 一种用助忆符号来表示机器指令的操作符和操作数的语言是汇编语言。

5. 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和运算等的学科。

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

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

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

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

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

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

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

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

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

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

16. 〖00年省统考〗任何一个C程序都由一个主函数和若干个被调用的其它函数组成。

17. 【00年省统考题】变量一经说明，就确定该变量的取值范围（即存储单元）及确定变量所允许的运算。

二、单项选择题（每小题1分，共15分）（ B ） 1. 通常所说的主机是指∶A) CPU B) CPU和内存 C) CPU、内存与外存 D) CPU、内存与硬盘（ C ）2. 在计算机内部，一切信息的存取、处理和传送的形式是∶A) ACSII码 B) BCD码 C)二进制 D)十六进制（D）3. 软件与程序的区别是∶A) 程序价格便宜、软件价格昂贵；B) 程序是用户自己编写的，而软件是由厂家提供的；C) 程序是用高级语言编写的，而软件是由机器语言编写的；D) 软件是程序以及开发、使用和维护所需要的所有文档的总称，而程序只是软件的一部分。

数据结构章节练习题第一章绪论一、单选题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章绪论之老阳三干创作习题一、问答题1. 什么是数据结构？2. 四类基本数据结构的名称与含义。

3. 算法的定义与特性。

4. 算法的时间复杂度。

5. 数据类型的概念。

6. 线性结构与非线性结构的不同。

7. 面向对象程序设计语言的特点。

8. 在面向对象程序设计中，类的作用是什么？9. 参数传递的主要方式及特点。

10. 抽象数据类型的概念。

二、判断题1. 线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。

2. 算法就是程序。

3. 在高级语言（如C、或 PASCAL）中，指针类型是原子类型。

三、计算下列程序段中X=X+1的语句频度for(i=1;i<=n;i++)for(j=1;j<=i;j++)for(k=1;k<=j;k++)x=x+1;[提示]：i=1时：1 = (1+1)×1/2 = (1+12)/2i=2时：1+2 = (1+2)×2/2 = (2+22)/2i=3时：1+2+3 = (1+3)×3/2 = (3+32)/2…i=n时：1+2+3+……+n = (1+n)×n/2 = (n+n2)/2f(n) = [ (1+2+3+……+n) + (12 + 22 + 32 + …… + n2 ) ]/ 2=[ (1+n)n/2 + n(n+1)(2n+1)/6 ] / 2=n(n+1)(n+2)/6=n3/6+n2/2+n/3区分语句频度和算法复杂度：O(f(n)) = O(n3)四、试编写算法求一元多项式Pn(x)=a0+a1x+a2x2+a3x3+…anxn的值Pn(x0)，并确定算法中的每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能的小，规定算法中不克不及使用求幂函数。

注意：本题中的输入ai(i=0,1,…,n), x和n，输出为Pn(x0).通常算法的输入和输出可采取下列两种方式之一：（1）通过参数表中的参数显式传递；（2）通过全局变量隐式传递。

第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语⾔版）知识点总结笔记课后答案第1章绪论1.1复习笔记⼀、数据结构的定义数据结构是⼀门研究⾮数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。

⼆、基本概念和术语数据数据（data）是对客观事物的符号表⽰，在计算机科学中是指所有能输⼊到计算机中并被计算机程序处理的符号的总称，它是计算机程序加⼯的“原料”。

2.数据元素数据元素（data element）是数据的基本单位，在计算机程序中通常作为⼀个整体进⾏考虑和处理。

3.数据对象数据对象（data object）是性质相同的数据元素的集合，是数据的⼀个⼦集。

4．数据结构数据结构（data structure）是相互之间存在⼀种或多种特定关系的数据元素的集合。

（1）数据结构的基本结构根据数据元素之间关系的不同特性，通常有下列四类基本结构：①集合。

数据元素之间除了“同属于⼀个集合”的关系外，别⽆其它关系。

②线性结构。

数据元素之间存在⼀个对⼀个的关系。

③树形结构。

数据元素之间存在⼀个对多个的关系。

④图状结构或⽹状结构。

数据元素之间存在多个对多个的关系。

如图1-1所⽰为上述四类基本结构的关系图。

图1-1 四类基本结构的关系图（2）数据结构的形式定义数据结构的形式定义为：数据结构是⼀个⼆元组Data_Structure==（D，S）其中：D表⽰数据元素的有限集，S表⽰D上关系的有限集。

（3）数据结构在计算机中的表⽰数据结构在计算机中的表⽰（⼜称映象）称为数据的物理结构，⼜称存储结构。

它包括数据元素的表⽰和关系的表⽰。

①元素的表⽰。

计算机数据元素⽤⼀个由若⼲位组合起来形成的⼀个位串表⽰。

②关系的表⽰。

计算机中数据元素之间的关系有两种不同的表⽰⽅法：顺序映象和⾮顺序映象。

并由这两种不同的表⽰⽅法得到两种不同的存储结构：顺序存储结构和链式存储结构。

a.顺序映象的特点是借助元素在存储器中的相对位置来表⽰数据元素之间的逻辑关系。

《数据结构（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））。