下载文档原格式
数据结构c语言版耿国华课后习题答案数据结构是计算机科学中的一个重要领域，它涉及到数据的组织、管理和存储方式，以便可以高效地访问和修改数据。
C语言作为一种高级编程语言，提供了丰富的数据结构实现方法。
耿国华教授编写的《数据结构C语言版》一书，为学习者提供了深入理解和实践数据结构的机会。
以下是该书课后习题的一些参考答案。
# 第一章绪论1. 习题1：数据结构的定义是什么？- 参考答案：数据结构是计算机科学中用于组织、管理和存储数据的方式，以便可以高效地访问和修改数据。
2. 习题2：为什么需要学习数据结构？- 参考答案：学习数据结构有助于提高编程效率，优化算法性能，以及更好地解决实际问题。
# 第二章线性表1. 习题1：线性表的特点是什么？- 参考答案：线性表的特点是数据元素之间存在一对一的线性关系，可以顺序存储或链式存储。
2. 习题3：如何实现线性表的插入操作？- 参考答案：线性表的插入操作通常涉及找到插入位置，然后将新元素插入到该位置，并调整后续元素。
# 第三章栈和队列1. 习题1：栈的后进先出（LIFO）特性是什么？- 参考答案：栈的后进先出特性意味着最后插入的元素将是第一个被删除的元素。
2. 习题2：如何用C语言实现一个队列？- 参考答案：可以用数组或链表来实现队列。
队列的基本操作包括入队（enqueue）和出队（dequeue）。
# 第四章树和二叉树1. 习题1：二叉树的定义是什么？- 参考答案：二叉树是每个节点最多有两个子节点的树结构，通常分为左子节点和右子节点。
2. 习题3：二叉树的遍历方法有哪些？- 参考答案：二叉树的遍历方法包括前序遍历、中序遍历、后序遍历和层序遍历。
# 第五章图1. 习题1：图的基本概念有哪些？- 参考答案：图由顶点（节点）和边组成，可以表示对象之间的关系。
2. 习题2：图的存储方式有哪些？- 参考答案：图的存储方式主要有邻接矩阵和邻接表两种。
# 结语通过学习《数据结构C语言版》一书，读者可以掌握各种数据结构的基本概念、特性以及实现方法。
![数据结构（C语言版）1800道题及答案[完整版]](https://uimg.taocdn.com/9bcf54fe59f5f61fb7360b4c2e3f5727a5e9240e.webp)
数据结构（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章绪论5．选择题：CCBDCA6．试分析下面各程序段的时间复杂度。
（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(n)第2章线性表1．选择题babadbcabdcddac2．算法设计题（6）设计一个算法，通过一趟遍历在单链表中确定值最大的结点。
ElemType Max (LinkList L ){if(L->next==NULL) return NULL;pmax=L->next; 法设计题（2）回文是指正读反读均相同的字符序列，如“abba”和“abdba”均是回文，但“good”不是回文。
试写一个算法判定给定的字符向量是否为回文。
(提示：将一半字符入栈)?根据提示，算法可设计为：合应用题（1）已知模式串t=‘abcaabbabcab’写出用KMP法求得的每个字符对应的next和nextval函数值。
（3）数组A中，每个元素A[i,j]的长度均为32个二进位,行下标从-1到9，列下标从1到11，从首地址S开始连续存放主存储器中，主存储器字长为16位。
求：①存放该数组所需多少单元②存放数组第4列所有元素至少需多少单元③数组按行存放时，元素A[7,4]的起始地址是多少④数组按列存放时，元素A[4,7]的起始地址是多少每个元素32个二进制位，主存字长16位，故每个元素占2个字长，行下标可平移至1到11。
（1）242 （2）22 （3）s+182 （4）s+142(4)请将香蕉banana用工具 H( )—Head( )，T( )—Tail( )从L中取出。
L=(apple,(orange,(strawberry,(banana)),peach),pear)H（H（T（H（T（H（T（L）））））））（5）写一个算法统计在输入字符串中各个不同字符出现的频度并将结果存入文件（字符串中的合法字符为A-Z这26个字母和0-9这10个数字）。
数据结构(c语言版)课后习题答案完整版数据结构(C语言版)课后习题答案完整版一、数据结构概述数据结构是计算机科学中一个重要的概念，用来组织和存储数据，使之可以高效地访问和操作。
在C语言中，我们可以使用不同的数据结构来解决各种问题。
本文将提供完整版本的C语言数据结构的课后习题答案。
二、顺序表1. 顺序表的定义和基本操作顺序表是一种线性表，其中的元素在物理内存中连续地存储。
在C 语言中，我们可以通过定义结构体和使用指针来实现顺序表。
以下是顺序表的一些基本操作的答案：（1）初始化顺序表```ctypedef struct{int data[MAX_SIZE];int length;} SeqList;void InitList(SeqList *L){L->length = 0;}```（2）插入元素到顺序表中```cbool Insert(SeqList *L, int pos, int elem){if(L->length == MAX_SIZE){return false; // 顺序表已满}if(pos < 1 || pos > L->length + 1){return false; // 位置不合法}for(int i = L->length; i >= pos; i--){L->data[i] = L->data[i-1]; // 向后移动元素 }L->data[pos-1] = elem;L->length++;return true;}```（3）删除顺序表中的元素```cbool Delete(SeqList *L, int pos){if(pos < 1 || pos > L->length){return false; // 位置不合法}for(int i = pos; i < L->length; i++){L->data[i-1] = L->data[i]; // 向前移动元素 }L->length--;return true;}```（4）查找顺序表中的元素```cint Search(SeqList L, int elem){for(int i = 0; i < L.length; i++){if(L.data[i] == elem){return i + 1; // 找到元素，返回位置 }}return -1; // 未找到元素}```2. 顺序表习题解答（1）逆置顺序表```cvoid Reverse(SeqList *L){for(int i = 0; i < L->length / 2; i++){int temp = L->data[i];L->data[i] = L->data[L->length - 1 - i]; L->data[L->length - 1 - i] = temp;}}```（2）顺序表元素去重```cvoid RemoveDuplicates(SeqList *L){for(int i = 0; i < L->length; i++){for(int j = i + 1; j < L->length; j++){if(L->data[i] == L->data[j]){Delete(L, j + 1);j--;}}}}```三、链表1. 单链表单链表是一种常见的链式存储结构，每个节点包含数据和指向下一个节点的指针。
数据结构(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语言版试题及答案一、选择题（每题2分，共10分）1. 在C语言中，以下哪个关键字用于定义结构体？A. structB. unionC. enumD. typedef答案：A2. 若有一个结构体数组，下列哪个函数可以用来初始化数组中的每个元素？A. memsetB. memcpyC. strcpyD. bzero答案：A3. 在C语言中，以下哪个函数用于动态分配内存？A. mallocB. callocC. reallocD. all of the above答案：D4. 对于一个链表，以下哪个操作是正确的？A. 插入节点B. 删除节点C. 遍历链表D. all of the above答案：D5. 在C语言中，以下哪个函数用于释放动态分配的内存？A. freeB. mallocC. callocD. realloc答案：A二、填空题（每题3分，共15分）1. 结构体定义的关键字是______。
答案：struct2. 在C语言中，动态分配内存失败时，malloc函数返回______。
答案：NULL3. 单链表的头节点指针通常初始化为______。
答案：NULL4. 双向链表中，每个节点包含______个指针。
答案：两个5. 树的深度优先遍历包括______、中序遍历和后序遍历。
答案：前序遍历三、简答题（每题5分，共20分）1. 请简述C语言中结构体和联合体的区别。
答案：结构体（struct）可以包含不同类型的数据，并且可以有多个实例；联合体（union）可以包含不同类型的数据，但是只能有一个实例，即在任意时刻只能存储其中一个成员的值。
2. 动态内存分配的优点是什么？答案：动态内存分配允许程序在运行时根据需要分配内存，这样可以更有效地使用内存资源，并且可以创建大小不固定的数据结构。
3. 链表相比于数组有哪些优点？答案：链表的优点包括动态大小，可以灵活地插入和删除节点，不需要预先知道数据的大小。
数据结构试题及答案c语言版一、选择题（每题2分，共20分）1. 在C语言中，以下哪个选项是正确的链表定义？A. struct Node { int data; struct Node *next; };B. struct Node { int data; Node *next; };C. struct Node { int data; struct Node *next; } *Node;D. struct Node { int data; Node *next; };答案：A2. 下列关于栈的描述中，错误的是？A. 栈是一种后进先出（LIFO）的数据结构。
B. 栈的插入操作称为push。
C. 栈的删除操作称为pop。
D. 栈可以存储任意数量的数据。
答案：D3. 在C语言中，以下哪个关键字用于定义一个结构体？A. structB. unionC. enumD. typedef答案：A4. 下列关于队列的描述中，正确的是？A. 队列是一种先进先出（FIFO）的数据结构。
B. 队列只能从队尾进行插入操作。
C. 队列的插入操作称为pop。
D. 队列的删除操作称为push。
答案：A5. 在C语言中，以下哪个函数用于创建一个动态数组？A. mallocB. callocC. reallocD. all of the above答案：D6. 下列关于二叉树的描述中，错误的是？A. 二叉树的每个节点最多有两个子节点。
B. 二叉树的子节点被称为左子树和右子树。
C. 二叉树的遍历方式包括前序、中序、后序。
D. 二叉树的每个节点只能有一个子节点。
答案：D7. 在C语言中，以下哪个函数用于释放动态分配的内存？A. freeB. mallocC. callocD. realloc答案：A8. 下列关于图的描述中，错误的是？A. 图是由顶点和边组成的数据结构。
B. 图的边可以是有向的，也可以是无向的。
C. 图的顶点可以是孤立的，没有边与之相连。
第1章绪论1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。
答案：数据：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。
如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。
数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。
在有些情况下，数据元素也称为元素、结点、记录等。
数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的一个格局（状态）、图中的一个顶点等。
数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。
例如，学生基本信息表中的学号、姓名、性别等都是数据项。
数据对象：是性质相同的数据元素的集合，是数据的一个子集。
例如：整数数据对象是集合N={0，±1，±2，…}，字母字符数据对象是集合C={‘A’，‘B’，…，‘Z’，‘a’，‘b’，…，‘z’}，学生基本信息表也可是一个数据对象。
数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。
换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。
逻辑结构：从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。
因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。
存储结构：数据对象在计算机中的存储表示，也称为物理结构。
抽象数据类型：由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。
具体包括三部分：数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。
2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。
答案：例如有一张学生基本信息表，包括学生的学号、姓名、性别、籍贯、专业等。
每个学生基本信息记录对应一个数据元素，学生记录按顺序号排列，形成了学生基本信息记录的线性序列。
1 绪论沈阳理工大学应用技术学院信息与控制学院计算机科学与技术教研室2011-5-8数据结构复习题：绪论单选题1、在数据结构中，与所使用的计算机无关的数据叫_____结构。
A存储|B物理|C逻辑|D物理和存储2、在数据结构中，从逻辑上可以把数据结构分成______。
A动态结构和静态结构|B紧凑结构和非紧凑结构|C线性结构和非线性结构|D内部结构和外部结构图3、数据结构在计算机内存中的表示是指_______。
数据的存储结构|数据结构|数据的逻辑结构|数据元素之间的关系4、在数据结构中，与所使用的计算机无关的是数据的______结构。
逻辑|存储|逻辑和存储|物理5、在以下的叙述中，正确的是_____。
线性表的线性存储结构优于链表存储结构|二维数组是其数据元素为线性表的线性表|栈的操作方式是先进先出|队列的操作方式是先进后出6、在决定选取何种存储结构时，一般不考虑_______。
各结点的值如何|结束个数的多少|对数据有哪些运算|所用编程语言实现这种结构是否方便7、在存储数据时，通常不仅要存储各数据元素的值，而且还要存储_______。
数据的处理方法|数据元素的类型|数据元素之间的关系|数据的存储方法8、下面说法错误的是_______。
(1)算法原地工作的含义是指不需要任何额外的辅助空间(2)在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法(3)所谓时间复杂度是指最坏情况下，估计算法执行时间的一个上界(4)同一个算法，实现语句的级别越高，执行效率越低(1)|(1)、(2)|(1)、(4)|(3)9、通常要求同一逻辑结构中的所有数据元素具有相同的特性。
这意味着______。
数据元素具有同一特点|不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致|每个数据元素都一样|数据元素所包含的数据项的个数要相等10、以下说法正确的是_______。
数据元素是数据的最小单位|数据项是数据的基本单位|数据结构是带结构的数据项的集合|一些表面上很不相同的数据可以有相同的逻辑结构11、____是数据的最小单元,_____是数据的基本单位.数据项|数据元素|信息项|表元素12、数据结构是指_____以及它们之间的_____.(1)数据元素(2)结构|(1)计算方法(2)关系|(1)逻辑存储(2)运算|(1)数据映像(2)算法13、计算机所处理的数据一般具备某种内在的关系,这是的指_____.数据和数据之间存在的某种关系|元素和元素之间存在某种关系|元素内部具有某种结构|数据项和数据项之间存在某种关系14、数据的逻辑结构可以分为_____两类.动态结构和表态结构|紧凑结构和非紧凑结构|线性结构和非线性结构|内部结构和外部结构15、数据的逻辑结构是指_____关系的整体.数据元素之间逻辑|数据项之间逻辑|数据类型之间|存储结构之间16、在存储数据时,通常不仅要存储各数据元素的值,而且还要存储_____.数据的处理方法|数据元素的类型|数据元素之间的关系|数据的存储方法17、在数据的存储结构中,一个存储结点存储一个_____.数据项|数据元素|数据结构|数据类型18、在计算机的存储器中表示时,物理地址和逻辑地址直接对应并且是连续的,称之为_____.逻辑结构|顺序存储结构|链式存储结构|以上都对19、数据采用链式存储结构时,要求_____.每个结点用占一片连续的存储区域|所有结点占用一片连续的存储区域|结点的最后一个数据域是指针类型|每个结点有多少个后继,就设多少个指针域20、数据的运算_____.效率与采用何种存储结构有关|是根据存储结构来定义的|有算术运算和关系运算两大类|必须用程序设计语言来描述21、下列说法中,不正确的是_____.数据元素是数据的基本单位|数据项是数据中不可分割的最小可标识单位|数据可由若干个数据元素构成|数据项可由若干个数据元素构成22、_____不是算法的基本特性.可行性|长度有限|在规定的时间内完成|确定性23、计算机中算法指的是解决某一问题的有限运算序列,它必须具备输入、输出、_____.可行性、可移植性和可扩充性|可行性、有穷性和确定性|确定性、有穷性和稳定性|易读性、稳定性和确定性24、以下不属于算法特性的是_____.可行性|有输入|确定性|健壮性25、下面关于算法的说法正确的是_____.算法最终必须由程序实现|算法的有穷性是对于任意的一组输入值必须在有穷步骤后结束|算法的可行性是指指令不能有二义性|以上几个都是错误的26、算法的时间复杂度与______有关问题规模|计算机硬件性能|编译程序质量|程序设计语言27、算法分析的主要任务是分析_____.算法是否具有较好的可读性|算法中是否存在语法错误|算法的功能是否符合设计要求|算法的执行时间和问题规模之间的关系28、某算法的时间复杂度为O(n2),表明该算法的_____.问题规模是n2|执行时间等于n2|执行时间与n2成正比|问题规模与n2成正比29、算法分析的目的是_____.找出数据结构的合理性|研究算法中输入和输出关系|分析算法的效率以求改进|分析算法的易读性和文档性30、线性表是具有n个______的有限序列。
习题一一、单选题1.在一个带有附加表头结点的单链表HL中，若要向表头插入一个由指针p指向的结点，则执行( B )。
A. HL=p; p->next=HL;B. p->next=HL->next; HL->next=p;C. p->next=HL; p=HL;D. p->next=HL; HL=p;2.若顺序存储的循环队列的QueueMaxSize=n,则该队列最多可存储（ B ）个元素.A. nB.n-1C. n+1D.不确定3.下述哪一条是顺序存储方式的优点？（A ）A．存储密度大 B.插入和删除运算方便C. 获取符合某种条件的元素方便D.查找运算速度快4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在600(10)，A[3][3]存放位置在678(10)，每个元素占一个空间，问A[2][3](10)存放在什么位置？(脚注(10)表示用10进制表示,m>3)DA．658 B．648 C．633 D．6535.下列关于二叉树遍历的叙述中，正确的是( AD ) 。
A. 若一个树叶是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序遍历最后一个结点B．若一个点是某二叉树的前序遍历最后一个结点，则它必是该二叉树的中序遍历的最后一个结点 C．若一个结点是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序最后一个结点D．若一个树叶是某二叉树的前序最后一个结点，则它必是该二叉树的中序遍历最后一个结点6.k层二叉树的结点总数最多为( A ).A．2k-1 B.2K+1 C.2K-1 D. 2k-17.对线性表进行二分法查找，其前提条件是( B ).A.线性表以链接方式存储，并且按关键码值排好序B.线性表以顺序方式存储，并且按关键码值的检索频率排好序C.线性表以顺序方式存储，并且按关键码值排好序D.线性表以链接方式存储，并且按关键码值的检索频率排好序8.对n个记录进行堆排序，所需要的辅助存储空为Cn） B. O（n） C. O（1） D. O（n2）A. O（1og29.对于线性表（7，34，77，25，64，49，20，14）进行散列存储时，若选用H（K）=K %7作为散列函数，则散列地址为0的元素有（ D ）个，A．1 B．2 C．3 D．410.下列关于数据结构的叙述中，正确的是( D ).A.数组是不同类型值的集合B.递归算法的程序结构比迭代算法的程序结构更为精炼C.树是一种线性结构D.用一维数组存储一棵完全二叉树是有效的存储方法二、填空题1.数据的逻辑结构被分为_集合结构、__线性结构、_树结构和_图结构四种。
1.3设n是正整数。
试写出下列程序段中用记号“△”标注的语句的频度：(2) i=1; k=0;do {△k+=10*i;i++;}while(i<=n-1)当n=1时，执行1；当n>=2时，执行n-1次；(3)i=1; k=0;do {△k+ = 10*i; i++;}while(i==n);当n=2时，执行2次；当n!=2时，执行1次；(4) i=1; j=0;while(i+j≤n) {△if(i<j) i++; else j++;}执行n次；(5) x=n; y=0; //n是不小于1的常数while(x>=(y+1)*(y+1)){△y++;}执行向下取整)(6) x=91; y=100;while ( y>0 )△if(x>100) { x-=10; y--; }else x++ ;}If语句执行100次(7) for( i=0; i<n; i++)for( j=i; j<n; j++)for( k=j; k<n; k++)△x+=2;过程：n1n1i0j in(n1)(n2) (n j)6--==++ -=∑∑第二章2.3 已知顺序表La中数据元素按非递减有序排列。
试写一个算法，将元素x插到La的合适位置上，保持该表的有序性。
思路：先判断线性表的存储空间是否满，若满返回Error；否则从后向前先移动数据，找到合适的位置插入。
Status Insert_SqList(SqList &La,int x)//把x 插入递增有序表La 中{if(La.length==La.listsize) return ERROR;for(i=La.length-1;La.elem[i]>x&&i>=0;i--)La.elem[i+1]=La.elem[i];La.elem[i+1]=x;La.length++;return OK;}//Insert_SqList2.5 试写一个算法，实现顺序表的就地逆置，即在原表的存储空间将线性表（a1,a2, ..., an-1,an）逆置为(an,an-1, ..., a2,a1)//思路就是两个指示变量i，j同时分别从顺序表的开始和结尾处相向改变void reverse(SqList &A)//顺序表的就地逆置{ElemType p;for(i=1,j=A.length;i<j;i++,j--){//A.elem[i]<->A.elem[j];p=A.elem[i];A.elem[i[=A.elem[j];A.elem[j]=p;}}//reverse2.7 已知线性表L采用顺序存储结构存放，对两种不同情况分别写出算法，删除L中多余的元素，使得L中没有重复元素：（1）L中数据元素无序排列；(2)L中数据元素非递减有序排列。
第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版)课后习题答案数据结构(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习题描述：什么是串？答案：串是由零个或多个字符组成的有限序列，串中的字符个数称为串的长度。
习题一一、单选题1.在一个带有附加表头结点的单链表HL中，若要向表头插入一个由指针p指向的结点，则执行( B )。
A. HL=p; p->next=HL;B. p->next=HL->next; HL->next=p;C. p->next=HL; p=HL;D. p->next=HL; HL=p;2.若顺序存储的循环队列的QueueMaxSize=n,则该队列最多可存储（ B ）个元素.A. nB.n-1C. n+1D.不确定3.下述哪一条是顺序存储方式的优点？（A ）A．存储密度大 B.插入和删除运算方便C. 获取符合某种条件的元素方便D.查找运算速度快4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在600(10)，A[3][3]存放位置在678(10)，每个元素占一个空间，问A[2][3](10)存放在什么位置？(脚注(10)表示用10进制表示,m>3)DA．658 B．648 C．633 D．6535.下列关于二叉树遍历的叙述中，正确的是( AD ) 。
A. 若一个树叶是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序遍历最后一个结点B．若一个点是某二叉树的前序遍历最后一个结点，则它必是该二叉树的中序遍历的最后一个结点 C．若一个结点是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序最后一个结点D．若一个树叶是某二叉树的前序最后一个结点，则它必是该二叉树的中序遍历最后一个结点6.k层二叉树的结点总数最多为( A ).A．2k-1 B.2K+1 C.2K-1 D. 2k-17.对线性表进行二分法查找，其前提条件是( B ).A.线性表以链接方式存储，并且按关键码值排好序B.线性表以顺序方式存储，并且按关键码值的检索频率排好序C.线性表以顺序方式存储，并且按关键码值排好序D.线性表以链接方式存储，并且按关键码值的检索频率排好序8.对n个记录进行堆排序，所需要的辅助存储空为Cn） B. O（n） C. O（1） D. O（n2）A. O（1og29.对于线性表（7，34，77，25，64，49，20，14）进行散列存储时，若选用H（K）=K %7作为散列函数，则散列地址为0的元素有（ D ）个，A．1 B．2 C．3 D．410.下列关于数据结构的叙述中，正确的是( D ).A.数组是不同类型值的集合B.递归算法的程序结构比迭代算法的程序结构更为精炼C.树是一种线性结构D.用一维数组存储一棵完全二叉树是有效的存储方法二、填空题1.数据的逻辑结构被分为_集合结构、__线性结构、_树结构和_图结构四种。
精品文档考试教学资料施工组织设计方案数据结构（C语言版）（第2版）课后习题答案李冬梅2015.3目录第1章绪论 (1)第2章线性表 (5)第3章栈和队列 (13)第4章串、数组和广义表 (26)第5章树和二叉树 (33)第6章图 (42)第7章查找 (54)第8章排序 (65)第1章绪论1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。
答案：数据：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。
如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。
数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。
在有些情况下，数据元素也称为元素、结点、记录等。
数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的一个格局（状态）、图中的一个顶点等。
数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。
例如，学生基本信息表中的学号、姓名、性别等都是数据项。
数据对象：是性质相同的数据元素的集合，是数据的一个子集。
例如：整数数据对象是集合N={0，±1，±2，…}，字母字符数据对象是集合C={‘A’，‘B’，…，‘Z’，‘a’，‘b’，…，‘z’}，学生基本信息表也可是一个数据对象。
数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。
换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。
逻辑结构：从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。
因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。
存储结构：数据对象在计算机中的存储表示，也称为物理结构。
抽象数据类型：由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。
具体包括三部分：数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。
数据结构c语言版课后习题答案完整版Document serial number【KKGB-LBS98YT-BS8CB-BSUT-BST108】第1章绪论5．选择题：CCBDCA6．试分析下面各程序段的时间复杂度。
（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．选择题babadbcabdcddac2．算法设计题（6）设计一个算法，通过一趟遍历在单链表中确定值最大的结点。
ElemType Max (LinkList L ){if(L->next==NULL) return NULL;pmax=L->next; 法设计题（2）回文是指正读反读均相同的字符序列，如“abba”和“abdba”均是回文，但“good”不是回文。
试写一个算法判定给定的字符向量是否为回文。
(提示：将一半字符入栈)根据提示，算法可设计为：合应用题（1）已知模式串t=‘abcaabbabcab’写出用KMP法求得的每个字符对应的next和nextval函数值。
-1到9，列下标从1到11，从首地址S开始连续存放主存储器中，主存储器字长为16位。
求：①存放该数组所需多少单元②存放数组第4列所有元素至少需多少单元③数组按行存放时，元素A[7,4]的起始地址是多少④ 数组按列存放时，元素A[4,7]的起始地址是多少每个元素32个二进制位，主存字长16位，故每个元素占2个字长，行下标可平移至1到11。
（1）242 （2）22 （3）s+182 （4）s+142(4)请将香蕉banana 用工具 H( )—Head( )，T( )—Tail( )从L 中取出。
L=(apple,(orange,(strawberry,(banana)),peach),pear)H （H （T （H （T （H （T （L ）））））））（5）写一个算法统计在输入字符串中各个不同字符出现的频度并将结果存入文件（字符串中的合法字符为A-Z 这26个字母和0-9这10个数字）。
附录习题参考答案习题1参考答案1.1.选择题(1). A. (2). A. (3). A. (4). B.,C. (5). A. (6). A. (7). C. (8). A. (9). B. (10.)A.1.2.填空题(1). 数据关系(2). 逻辑结构物理结构(3). 线性数据结构树型结构图结构(4). 顺序存储链式存储索引存储散列表（Hash）存储(5). 变量的取值范围操作的类别(6). 数据元素间的逻辑关系数据元素存储方式或者数据元素的物理关系(7). 关系网状结构树结构(8). 空间复杂度和时间复杂度(9). 空间时间(10). Ο(n)1.3 名词解释如下：数据：数据是信息的载体，是计算机程序加工和处理的对象，包括数值数据和非数值数据。
数据项：数据项指不可分割的、具有独立意义的最小数据单位，数据项有时也称为字段或域。
数据元素：数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理，一个数据元素可由若干个数据项组成。
数据逻辑结构：数据的逻辑结构就是指数据元素间的关系。
数据存储结构：数据的物理结构表示数据元素的存储方式或者数据元素的物理关系。
数据类型：是指变量的取值范围和所能够进行的操作的总和。
算法：是对特定问题求解步骤的一种描述，是指令的有限序列。
1.4 语句的时间复杂度为：(1) Ο(n2)(2) Ο(n2)(3) Ο(n2)(4) Ο(n-1)(5) Ο(n3)1.5 参考程序：main(){int X,Y,Z；scanf(“%d, %d, %d”,&X,&Y,Z)；if (X>=Y)if(X>=Z)if (Y>=Z){ printf(“%d, %d, %d”,X,Y,Z);}else{ printf(“%d, %d, %d”,X,Z,Y);}else{ printf(“%d, %d, %d”,Z,X,Y);}elseif(Z>=X)if (Y>=Z){ printf(“%d, %d, %d”,Y,Z,X);}else{ printf(“%d, %d, %d”,Z,Y,X);}else{ printf(“%d, %d, %d”,Y,X,Z);}}1.6 参考程序：main(){int i,n;float x,a[],p;printf(“\nn=”);scanf(“%f”,&n);printf(“\nx=”);scanf(“%f”,&x);for(i=0;i<=n;i++)scanf(“%f ”,&a[i]);p=a[0];for(i=1;i<=n;i++){ p=p+a[i]*x;x=x*x;}printf(“%f”,p)’}习题2参考答案2.1选择题(1). C. (2). B. (3). B. (4). B. 5. D. 6. B. 7. B. 8. A. 9. A. 10. D.2.2.填空题(1). 有限序列(2). 顺序存储和链式存储(3). Ｏ(n) O(n)(4). n-i+1 n-i(5). 链式(6). 数据指针(7). 前驱后继(8). Ο(1) Ο(n)(9). s->next=p->next; p->next=s ;(10). s->next2.3. 解题思路：将顺序表A中的元素输入数组a，若数组a中元素个数为n,将下标为0，1,2,…,（n-1）/2的元素依次与下标为n,n-1,…, （n-1）/2的元素交换，输出数组a的元素。
参考程序如下：main(){int i,n;float t,a[];printf(“\nn=”);scanf(“%f”,&n);for(i=0;i<=n-1;i++)scanf(“%f ”,&a[i]);for(i=0;i<=(n-1)/2;i++){ t=a[i]; a[i] =a[n-1-i]; a[n-1-i]=t;}for(i=0;i<=n-1;i++)printf(“%f”,a[i]);}2.4 算法与程序：main(){int i,n;float t,a[];printf(“\nn=”);scanf(“%f”,&n);for(i=0;i<n;i++)scanf(“%f ”,&a[i]);for(i=1;i<n;i++)if(a[i]>a[0]{ t=a[i]; a[i] =a[0]; a[0]=t;}printf(“%f”,a[0]);for(i=2;i<n;i++)if(a[i]>a[1]{ t=a[i]; a[i] =a[1]; a[1]=t;}printf(“%f”,a[0]);}2.5 算法与程序：main(){int i,j,k,n;float x,t,a[];printf(“\nx=”);scanf(“%f”,&x);printf(“\nn=”);scanf(“%f”,&n);for(i=0;i<n;i++)scanf(“%f ”,&a[i]); // 输入线性表中的元素for (i=0; i<n; i++) { // 对线性表中的元素递增排序k=i;for (j=i+1; j<n; j++) if (a[j]<a[k]) k=j;if (k<>j) {t=a[i];a[i]=a[k];a[k]=t;}}for(i=0;i<n;i++) // 在线性表中找到合适的位置if(a[i]>x) break;for(k=n-1;k>=i;i--) // 移动线性表中元素，然后插入元素xa[k+1]=a[k];a[i]=x;for(i=0;i<=n;i++) // 依次输出线性表中的元素printf(“%f”,a[i]);}2.6 算法思路：依次扫描A和B的元素，比较A、B当前的元素的值，将较小值的元素赋给C，如此直到一个线性表扫描完毕，最后将未扫描完顺序表中的余下部分赋给C即可。
C的容量要能够容纳A、B两个线性表相加的长度。
有序表的合并算法：void merge (SeqList A, SeqList B, SeqList *C){ int i，j，k；i=0；j=0；k=0；while ( i<=st && j<=st )if (A.data[i]<=B.data[j])C->data[k++]=A.data[i++]；elseC->data[k++]=B.data[j++]；while (i<=st )C->data[k++]= A.data[i++]；while (j<=st )C->data[k++]=B.data[j++]；C->last=k-1；}2.7 算法思路：依次将A中的元素和B的元素比较，将值相等的元素赋给C，如此直到线性表扫描完毕，线性表C就是所求递增有序线性表。
算法：void merge (SeqList A, SeqList B, SeqList *C){ int i，j，k；i=0；j=0；k=0；while ( i<=st)while（j<=st )if (A.data[i]=B.data[j])C->data[k++]=A.data[i++]；C->last=k-1；}习题3参考答案3.1.选择题(1). D (2). C (3). D (4). C (5). B (6). C (7). C (8). C (9). B (10).AB (11). D (12). B (13). D (14). C (15). C (16). D(17). D (18). C (19). C (20). C 3.2.填空题（1）FILO, FIFO（2）-1, 3 4 X * + 2 Y * 3 / -（3）stack.top, stack.s[stack.top]=x（4）p>llink->rlink=p->rlink, p->rlink->llink=p->rlink（5）(R-F+M)%M（6）top1+1=top2（7）F==R（8）front==rear（9）front==(rear+1)%n（10） N-13.3 答：一般线性表使用数组来表示的线性表一般有插入、删除、读取等对于任意元素的操作而栈只是一种特殊的线性表栈只能在线性表的一端插入（称为入栈,push）或者读取栈顶元素或者称为“弹出、出栈”(pop)。
3.4 答：相同点：栈和队列都是特殊的线性表，只在端点处进行插入，删除操作。
不同点：栈只在一端（栈顶）进行插入，删除操作；队列在一端（top）删除，一端(rear)插入。
3.5 答：可能序列有14种：ABCD; ACBD; ACDB; ABDC; ADCB; BACD; BADC; BCAD; BCDA; BDCA; CBAD; CBDA; CDBA; DCBA。
3.6 答：不能得到4，3，5，6，1，2，最先出栈的是4,则按321的方式出，不可能得到1在2前的序列，可以得到1，3，5，4，2，6，按如下方式进行push(1), pop(), push(2), push(3), pop(), push(4), push(5), pop(), pop(), pop(), push(6), pop()。
3.7 答：stack3.8 非递归:int vonvert (int no,int a[]) //将十进制数转换为2进制存放在a[]，并返回位数{int r;SeStack s,*p;P=&s;Init_stack(p);while(no){push(p,no%2);no/=10;}r=0;while(!empty_stack(p)){pop(p,a+r);r++;}return r;}递归算法:void convert(int no){if(no/2>0){Convert(no/2);Printf(“%d”,no%2);}elseprintf(“%d”,no);}3.9 参考程序：void view(SeStack s){SeStack *p; //假设栈元素为字符型char c;p=&s;while(!empty_stack(p)){c=pop(p);printf(“%c”,c);}printf(”\n”);}3.10 答：char3.11 参考程序：void out(linkqueue q){int e;while(q.rear !=q.front ){dequeue(q,e);print(e); //打印}}习题4参考答案4.1 选择题：(1). A (2). D (3). C (4). C (5). B (6). B (7). D (8). A (9). B (10). D 4.2 填空题：（1）串长相等且对应位置字符相等（2）不含任何元素的串，0（3）所含字符均是空格，所含空格数（4）10（5）“hello boy”（6）13（7）1066（8）模式匹配（9）串中所含不同字符的个数（10） 364.3 StrLength (s)=14, StrLength (t)=4, SubStr( s，8，7)=” STUDENT”, SubStr(t，2，1)=”O”,StrIndex(s,“A”)=3, StrIndex (s，t)=0, StrRep(s，“STUDENT”，q)=” I AM A WORKER”, 4.4 StrRep(s,”Y”,”+”);StrRep(s,”+*”,”*Y”);4.5 空串：不含任何字符；空格串：所含字符都是空格串变量和串常量:串常量在程序的执行过程中只能引用不能改变；串变量的值在程序执行过程中是可以改变和重新赋值的主串与子串：子串是主串的一个子集串变量的名字与串变量的值:串变量的名字表示串值的标识符4.6int EQUAl(S,T){char *p,*q;p=&S;q=&T;while(*p&&*q){if(*p!=*q)return *p-*q;p++;q++;}return *p-*q;}4.7(1)6*8*6=288(2)1000+47*6=1282(3)1000+(8+4)*8=1096(4)1000+(6*7+4)*8=13684.8习题5参考答案5.1 选择（1）C（2）B（3）C（4）B（5）C（6）D（7）C（8）C（9）B（10）C （11）B（12）C（13）C（14）C（15）C（16）B5.2 填空（1）1（2）1036；1040（3）2i（4） 1 ； n ; n-1 ; 2（5）2k-1；2k-1（6）ACDBGJKIHFE（7）p->lchild==NULL（8）Huffman树（9）其第一个孩子; 下一个兄弟（10）先序遍历；中序遍历5.3叶子结点:C、F、G、L、I、M、K；非终端结点：A、B、D、E、J；各结点的度：结点： A B C D E F G L I J K M 度： 4 3 0 1 2 0 0 0 0 1 0 0树深：45.4无序树形态如下：二叉树形态如下：5.5二叉链表如下:三叉链表如下:5.6先序遍历序列:ABDEHICFJG中序遍历序列:DBHEIAFJCG后序遍历序列:DHIEBJFGCA5.7(1) 先序序列和中序序列相同：空树或缺左子树的单支树；(2) 后序序列和中序序列相同：空树或缺右子树的单支树；(3) 先序序列和后序序列相同：空树或只有根结点的二叉树。
