中国铁道出版社数据结构(第二版)单元9练习参考答案

《数据结构》课后习题答案(第2版)数据结构课后习题答案（第2版）第一章：基本概念1. 什么是数据结构？数据结构是指数据元素之间的关系，以及相应的操作。

它研究如何组织、存储和管理数据，以及如何进行高效的数据操作。

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

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

3. 什么是算法？算法是解决特定问题的一系列有序步骤。

它描述了如何输入数据、处理数据，并产生期望的输出结果。

4. 算法的特性有哪些？算法具有确定性、有限性、输入、输出和可行性这五个特性。

5. 数据结构和算法之间的关系是什么？数据结构是算法的基础，算法操作的对象是数据结构。

第二章：线性表1. 顺序表的两种实现方式是什么？顺序表可以通过静态分配或动态分配的方式实现。

静态分配使用数组，动态分配使用指针和动态内存分配。

2. 单链表的特点是什么？单链表由节点组成，每个节点包含数据和一个指向下一个节点的指针。

它的插入和删除操作效率高，但是查找效率较低。

3. 循环链表和双向链表分别是什么？循环链表是一种特殊的单链表，在尾节点的指针指向头节点。

双向链表每个节点都有一个指向前一个节点和后一个节点的指针。

4. 链表和顺序表的区别是什么？链表的插入和删除操作效率更高，但是查找操作效率较低；顺序表的插入和删除操作效率较低，但是查找操作效率较高。

第三章：栈和队列1. 栈是什么？栈是一种特殊的线性表，只能在表的一端进行插入和删除操作。

后进先出（LIFO）是栈的特点。

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

先进先出（FIFO）是队列的特点。

3. 栈和队列的应用有哪些？栈和队列在计算机科学中有广泛的应用，例如浏览器的前进后退功能使用了栈，操作系统的进程调度使用了队列。

4. 栈和队列有哪些实现方式？栈和队列可以使用数组或链表来实现，还有更为复杂的如双端队列和优先队列。

中国铁道出版社数据结构（第二版）单元7练习参考答案单元练习7一．判断题（下列各题，正确的请在前面的括号内打√；错误的打�w ）（√）（1）树结构中每个结点最多只有一个直接前驱。

（ㄨ）（2）完全二叉树一定是满二查树。

（ㄨ）（3）在中序线索二叉树中，右线索若不为空，则一定指向其双亲。

（√）（4）一棵二叉树中序遍历序列的最后一个结点，必定是该二叉树前序遍历的最后一个结点。

（√）（5）二叉树的前序遍历中，任意一个结点均处于其子女结点的前面。

（√）（6）由二叉树的前序遍历序列和中序遍历序列，可以推导出后序遍历的序列。

（√）（7）在完全二叉树中，若一个结点没有左孩子，则它必然是叶子结点。

（ㄨ）（8）在哈夫曼编码中，当两个字符出现的频率相同，其编码也相同，对于这种情况应该做特殊处理。

（ㄨ）（9）含多于两棵树的森林转换的二叉树，其根结点一定无右孩子。

（√）（10）具有n个叶子结点的哈夫曼树共有2n-1个结点。

二．填空题（1）在树中，一个结点所拥有的子树数称为该结点的度。

（2）度为零的结点称为叶（或叶子，或终端）结点。

（3）树中结点的最大层次称为树的深度（或高度）。

（4）对于二叉树来说，第i层上至多有 2i-1 个结点。

（5）深度为h的二叉树至多有 2h-1 个结点。

（6）由一棵二叉树的前序序列和中序序列可唯一确定这棵二叉树。

（7）有20个结点的完全二叉树，编号为10的结点的父结点的编号是 5 。

（8）哈夫曼树是带权路径长度最小的二叉树。

（9）由二叉树的后序和中序遍历序列，可以唯一确定一棵二叉树。

（10）某二叉树的中序遍历序列为: DEBAC，后序遍历序列为：EBCAD。

则前序遍历序列为：DABEC 。

（11）设一棵二叉树结点的先序遍历序历为：ABDECFGH，中序遍历序历为：DEBAFCHG，则二叉树中叶结点是： E、F、H 。

（12）已知完全二叉树的第8层有8个结点，则其叶结点数是 68 。

（13）由树转换成二叉树时，其根结点无右子树。

《数据结构》习题答案习题1一、选择题：1、C2、B3、B4、B D5、C6、A7、C B8、D9、B 10、D二、填空题：1、相互关系2、一对一、一对多、多对多3、线性结构、集合、图、树4、有穷性、确定性、可行性、输入、输出5、O（n）6、O（n2）7、物理8、（1）、（log2n）、(n)、(n2)、(2n)、实际不可计算9、数据元素三、应用题：1、O（n/2）。

2、（略）。

3、（略）。

4、（略）。

5、（1）语句k+=10*i的频度为：n-1;（2）语句k++的频度为：n2。

四、算法设计题：1、算法程序如下：void main(){int x,y,z,temp;printf(“请输入3个整数：\n”);scanf(“%d%d%d”,&x,&y,&z);if (x<y){temp=x;x=y;y=temp;}if(x<z){temp=x;x=z;z=temp;}if(y<z){temp=y;y=z;z=temp;}printf(%d\t%d\t%d\n”,x,y,z);}2、算法程序如下：void main(){int a[10],i,max,min;printf(“请输入10个整数：\n”);for(i=0;i<10;i++)scanf(“%d”,&a[i]);for(max=min=a[0],i=1;i<10;i++){if(max<a[i])max=a[i];if(min>a[i])min=a[i];}printf(“max=%d,min=%d\n”,max,min);}习题2一、选择题：1、A2、D3、B4、C5、B6、C7、D8、C9、B 10、C 11、D 12、C13、B 14、A 15、D 16、A 17、C 18、B 19、D 20、D二、填空题：1、元素、首、尾、位置、前趋、后继2、前趋、前趋、后继、后继3、线性4、顺序、长度5、q=p->next;p->next=q->next;free(q);6、p->next=head;7、q=rear->next->next;rear->next->next=q->next;free(q);三、应用题：（略）四、算法设计题：（略）习题3一、选择题：1、A2、B3、A4、C5、A6、B7、C8、C9、B 10、C二、填空题：1、n-12、x=top->data;top=top->next;3、n-14、b,c,e,d,a5、if((rear+1)%(m+1)=front)return (eof);else{rear=(rear+1)%(m+1);A[rear]=x;return 1;}6、FILO、FIFO、只允许在端点处进行插入（删除）操作7、栈8、队尾9、队满、队空三、应用题：（略）四、算法设计题：（略）习题4一、选择题：1、C2、A3、A4、B5、B6、C7、B8、A9、C 10、C二、填空题：1、3152、11、313、i(i-1)/2+j4、（（0，2，2），（1，0，3），（2，2，-1），（2，3，5））5、N(N+1)/26、（d1-c1+1）*(d2-c2+1)*(d3-c3+1)7、15648、22109、GetTail(GetTail(GetHead(GetHead(GetTail(s)))))10、5、3三、应用题：1、（1）数组A的容量：6*8*6=288（字节）（2）行优先存储A[1，4]的地址：1000+3*6=1018（3）列优先存储A[4，7]的地址：1000+（6*6+3）*6=12342、（1）M含有的数据元素数目：2*7*6=84（2）M[2，2，2]的地址：100+（6*6+3）*2=178M[3，-3，3]的地址：100+（7*6+1*6+4）*2=204M[3，0，0]的地址：100+（6*7+4*6+1）*2=2343、A[15，15]按行压缩存储前面的元素个数是：3+4+5*13+2=54所以A[15，15]在B中的下标是：55-21=344、（略）。

数据结构(第二版)习题库章节练习题1-9章全数据结构(第二版)习题库章节练习题1-9章全第一章：引论引论部分为数据结构的开篇，主要介绍了数据结构的基本概念和分类。

在这一章中，我们学习了数据结构的定义、作用以及与算法的关系。

接下来，将为你详细介绍第一章的习题内容。

1. 习题1-1题目：请简述数据结构的定义和作用。

要求：通过一段简洁清晰的语言来回答问题，并给出你的理解。

答案：数据结构是计算机中存储、组织和管理数据的方式。

它旨在将数据以特定的方式进行排列，以便高效地进行存储和检索。

数据结构作为计算机科学的基础，为我们解决实际问题提供了有效的工具和方法。

2. 习题1-2题目：你认为数据结构与算法之间的关系是什么？要求：结合实际案例，详细解释数据结构与算法之间的相互依赖关系。

答案：数据结构和算法是密不可分的，它们之间存在着相互依赖的关系。

数据结构提供了算法操作的基础，而算法则对数据结构进行操作和处理。

例如，在搜索算法中，我们需要合适的数据结构来存储和组织数据，以便能够高效地进行搜索操作。

而无论是数组、链表还是树，都需要通过算法来进行增删改查等操作。

第二章：算法分析算法分析是数据结构中的重要概念，它涉及到算法的运行时间和空间效率。

在这一章中，我们将学习算法分析的基本方法和常用技巧，并通过习题来巩固所学知识。

3. 习题2-1题目：请解释渐进记号中的"O"表示什么意思。

要求：简明扼要地回答问题，并辅以例子说明。

答案：在算法分析中，"O"表示渐进上界。

它描述了算法在最坏情况下的运行时间复杂度。

例如，如果一个算法的时间复杂度为O(n)，那么说明该算法的运行时间与输入规模n成正比。

即使输入规模变大，算法的运行时间也不会超过n的某个常数倍。

4. 习题2-2题目：请说明算法的平均情况分析与最坏情况分析有何区别？要求：用简洁的语言说明两种分析方法的不同之处，并给出具体的示例。

答案：算法的平均情况分析和最坏情况分析的区别在于对输入数据的预先假设。

数据结构习题及解答第1章 概述【例1-1】分析以下程序段的时间复杂度。

for(i=0;i<n;i++) for(j=0;j<m;j++) A[i][j]=0;解：该程序段的时间复杂度为O (m*n )。

【例1-2】分析以下程序段的时间复杂度。

i=s=0; ① while(s<n) { i++; ② s+=i; ③ }解：语句①为赋值语句，其执行次数为1次，所以其时间复杂度为O (1)。

语句②和语句③构成while 循环语句的循环体，它们的执行次数由循环控制条件中s 与n 的值确定。

假定循环重复执行x 次后结束， 则语句②和语句③各重复执行了x 次。

其时间复杂度按线性累加规则为O (x )。

此时s 与n 满足关系式：s ≥n ，而s=1+2+3+…+x 。

所以有：1+2+3+…+x ≥n ，可以推出：x=nn 241212811+±-=+±-x 与n 之间满足x=f(n ），所以循环体的时间复杂度为O (n )，语句①与循环体由线性累加规则得到该程序段的时间复杂度为O (n ）。

【例1-3】分析以下程序段的时间复杂度。

i=1; ① while(i<=n) i=2*i; ②解：其中语句①的执行次数是1，设语句②的执行次数为f (n )，则有：n n f ≤)(2。

log)得：T（n）=O(n2【例1-4】有如下递归函数fact(n)，分析其时间复杂度。

fact(int n){ if(n<=1)return(1);①elsereturn(n*fact(n-1));②}解：设fact（n）的运行时间函数是T(n)。

该函数中语句①的运行时间是O(1)，语句②的运行时间是T(n-1)+ O(1)，其中O(1)为常量运行时间。

由此可得fact（n）的时间复杂度为O(n)。

习题1一、单项选择题1.数据结构是指（1. A ）。

A.数据元素的组织形式B.数据类型C.数据存储结构D.数据定义2.数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（2. C ）。

单元练习5一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳）（ㄨ）（1）串是n个字母的有限序列。

（√）（2）串的数据元素是一个字符。

（ㄨ）（3）串的长度是指串中不同字符的个数。

（ㄨ）（4）如果两个串含有相同的字符，则说明它们相等。

（ㄨ）（5）如果一个串中所有的字母均在另一个串中出现，则说明前者是后者的子串。

（√）（6）串的堆分配存储是一种动态存储结构。

（ㄨ）（7）“DT”是“DA TA”的子串。

（ㄨ）（8）串中任意个字符组成的子序列称为该串的子串。

（√）（9）子串的定位运算称为模式匹配。

（√）（10）在链串中为了提高存储密度，应该增大结点的大小。

二．填空题（1）由零个或多个字符组成的有限序列称为字符串（或串）。

（2）字符串按存储方式可以分为：顺序存储、链接存储和堆分配存储。

（3）串的顺序存储结构简称为顺序串。

（4）串顺序存储非紧凑格式的缺点是：空间利用率低。

（5）串顺序存储紧凑格式的缺点是对串的字符处理效率低。

（6）串链接存储的优点是插入、删除方便，缺点的空间利用率低。

（7）在C或C++语言中，以字符\0 表示串值的终结。

（8）空格串的长度等于空格的个数。

（9）在空串和空格串中，长度不为0的是空格串。

（10）两个串相等是指两个串相长度等，且对应位置的字符都相同。

（11）设S="My Music"，则LenStr(s)= _ 8 。

（12）两个字符串分别为：S1="Today is"，S2="30 July,2005",ConcatStr(S1,S2)的结果是： Today is 30 July,2005 。

（13）求子串函数SubStr("Today is 30 July,2005",13,4)的结果是：July 。

（14）在串的运算中，EqualStr(aaa,aab)的返回值为<0 。

（15）在串的运算中，EqualStr(aaa,aaa)的返回值为0 。

单元练习1一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳）（√）（1）数据的逻辑结构与数据元素本身的内容和形式无关。

（√）（2）一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。

（ㄨ）（3）数据元素是数据的最小单位。

（ㄨ）（4）数据的逻辑结构和数据的存储结构是相同的。

（ㄨ）（5）程序和算法原则上没有区别，所以在讨论数据结构时可以通用。

（√）（6）从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。

（√）（7）数据的存储结构是数据的逻辑结构的存储映像。

（√）（8）数据的物理结构是指数据在计算机内实际的存储形式。

（ㄨ）（9）数据的逻辑结构是依赖于计算机的。

（√）（10）算法是对解题方法和步骤的描述。

二．填空题（1）数据有逻辑结构和存储结构两种结构。

（2）数据逻辑结构除了集合以外，还包括：线性结构、树形结构和图形结构。

（3）数据结构按逻辑结构可分为两大类，它们是线性结构和非线性结构。

（4）树形结构和图形结构合称为非线性结构。

（5）在树形结构中，除了树根结点以外，其余每个结点只有 1 个前趋结点。

（6）在图形结构中，每个结点的前趋结点数和后续结点数可以任意多个。

（7）数据的存储结构又叫物理结构。

（8）数据的存储结构形式包括：顺序存储、链式存储、索引存储和散列存储。

（9）线性结构中的元素之间存在一对一的关系。

（10）树形结构结构中的元素之间存在一对多的关系，（11）图形结构的元素之间存在多对多的关系。

（12）数据结构主要研究数据的逻辑结构、存储结构和算法（或运算）三个方面的内容。

（13）数据结构被定义为(D，R)，其中D是数据的有限集合，R是D上的关系的有限集合。

（14）算法是一个有穷指令的集合。

（15）算法效率的度量可以分为事先估算法和事后统计法。

（16）一个算法的时间复杂性是算法输入规模的函数。

（17）算法的空间复杂度是指该算法所耗费的存储空间，它是该算法求解问题规模n的函数。

单元测验10一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳）（ㄨ）（1）如果某种排序算法不稳定，则该排序方法就没有实用价值。

（√）（2）希尔排序是不稳定的排序。

（ㄨ）（3）冒泡排序是不稳定的排序。

（√）（4）对n个记录的进行快速排序，所需要的平均时间是O(nlog2n)。

（ㄨ）（5）堆排序所需的时间与待排序的记录个数无关。

（√）（6）当待排序的元素个数很多时，为了交换元素的位置要占用较多的时间，这是影响时间复杂度的主要因素。

（ㄨ）（7）快速排序在任何情况下都比其它排序方法速度快。

（√）（8）对快速排序来说，初始序列为正序或反序都是最坏情况。

（√）（9）采用归并排序可以实现外排序。

（√）（10）采用希尔方法排序时，若关键字的排列杂乱无序，则效率最高。

（√）（11）快速排序算法在每一趟排序中都能找到一个元素放在其最终位置上。

（√）（12）冒泡排序的时间复杂度是O（n2）。

二．填空题（1）大多数排序算法都有两个基本的操作：比较和移动。

（2）评价排序算法优劣的主要标准是时间复杂度和算法所需的附加空间。

（3）根据被处理的数据在计算机中使用不同的存储设备，排序可分为：内排序和外排序。

（4）外排序是指在排序过程中，数据的主要部分存放在计算机的外存中。

（5）对n个关键字进行冒泡排序，其可能的最小比较次数为： n-1 次。

（6）在最坏情况下，在第i趟直接插入排序中，要进行 i-1 次关键字的比较。

（7）对n个关键字进行冒泡排序，时间复杂度为 O(n2) 。

（8）快速排序在最坏情况下的时间复杂度是 O(n2) 。

（9）对于n个记录的集合进行归并排序，所需要的平均时间为： O(log2n) 。

（10）对于n个记录的集合进行归并排序，所需要的附加空间是 O(n) 。

（11）若原始数据接近无序，则选用快速排序最好。

（12）在排序前，关键字值相等的不同记录，排序后相对位置保持不变的排序方法，称为稳定排序方法。

《数据结构》教材课后习题+答案数据结构第一章介绍数据结构是计算机科学中重要的概念，它涉及到组织和存储数据的方法和技术。

数据结构的选择对于算法的效率有着重要的影响。

本教材为读者提供了丰富的课后习题，以帮助读者巩固所学知识并提高解决问题的能力。

下面是一些选定的习题及其答案，供读者参考。

第二章线性表习题一：给定一个顺序表L，编写一个算法，实现将其中元素逆置的功能。

答案一：算法思路：1. 初始化两个指针i和j，分别指向线性表L的首尾两个元素2. 对于L中的每一个元素，通过交换i和j所指向的元素，将元素逆置3. 当i>=j时，停止逆置算法实现：```pythondef reverse_list(L):i, j = 0, len(L)-1while i < j:L[i], L[j] = L[j], L[i]i += 1j -= 1```习题二：给定两个线性表A和B，编写一个算法，将线性表B中的元素按顺序插入到线性表A中。

答案二：算法思路：1. 遍历线性表B中的每一个元素2. 将B中的元素依次插入到A的末尾算法实现：```pythondef merge_lists(A, B):for element in B:A.append(element)```第三章栈和队列习题一：编写一个算法，判断一个表达式中的括号是否匹配。

表达式中的括号包括小括号"()"、中括号"[]"和大括号"{}"。

答案一：算法思路：1. 遍历表达式中的每一个字符2. 当遇到左括号时，将其推入栈中3. 当遇到右括号时，判断栈顶元素是否与其匹配4. 当遇到其他字符时，继续遍历下一个字符5. 最后判断栈是否为空，若为空则表示括号匹配算法实现：```pythondef is_matching(expression):stack = []for char in expression:if char in "([{":stack.append(char)elif char in ")]}":if not stack:return Falseelif (char == ")" and stack[-1] == "(") or (char == "]" and stack[-1] == "[") or (char == "}" and stack[-1] == "{"):stack.pop()else:return Falsereturn not stack```习题二：利用两个栈实现一个队列。

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

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

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

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

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

第二章：线性表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：请问队列可以用哪些方式实现？答案：队列可以用数组或链表来实现。

数据结构(c版)第二版课后习题答案在计算机科学中，数据结构是组织、管理和存储数据的方式，它对程序的效率和性能有着直接的影响。

《数据结构（C版）》第二版是一本广泛使用的教材，它详细介绍了各种基本的数据结构以及它们在C语言中的实现。

课后习题是帮助学生巩固理论知识和提高编程技能的重要部分。

以下是一些可能的习题答案示例，但请注意，实际的习题答案应根据具体习题内容来确定。

习题1：数组和链表问题：编写一个函数，该函数接受一个整数数组和它的大小，然后返回数组中的最大值。

答案：```c#include <stdio.h>int findMax(int arr[], int size) {int max = arr[0];for (int i = 1; i < size; i++) {if (arr[i] > max) {max = arr[i];}}return max;}int main() {int arr[] = {10, 20, 30, 40, 50};int size = sizeof(arr) / sizeof(arr[0]);printf("The maximum value in the array is: %d\n", findMax(arr, size));return 0;}```习题2：栈问题：实现一个栈的数据结构，并编写一个函数来检查一个字符串是否是回文。

答案：```c#include <stdio.h>#include <string.h>#include <stdbool.h>#define MAX_SIZE 100typedef struct {char data[MAX_SIZE];int top;} Stack;void initializeStack(Stack *s) {s->top = -1;}bool isEmpty(Stack s) {return s.top == -1;}void push(Stack *s, char item) {if (s->top < MAX_SIZE - 1) {s->top++;s->data[s->top] = item;}}char pop(Stack *s) {if (!isEmpty(*s)) {return s->data[s->top--];}return '\0';}bool isPalindrome(const char *str) {Stack s;initializeStack(&s);int length = strlen(str);for (int i = 0; i < length; i++) {push(&s, str[i]);}for (int i = 0; i < length / 2; i++) { char c1 = str[i];char c2 = pop(&s);if (c1 != c2) {return false;}}return true;}int main() {char str[] = "radar";if (isPalindrome(str)) {printf("The string is a palindrome.\n");} else {printf("The string is not a palindrome.\n");}return 0;}```习题3：队列问题：实现一个循环队列，并编写一个函数来模拟银行的顾客服务，顾客到达和离开。

第9章集合部分答案解释如下。

4．不能说哪种哈希函数的选取方法最好，各种选取方法有自己的适用范围。

8．哈希表的结点中可以包括指针，指向其元素。

11．单链表不能使用折半查找方法。

20．按插入后中序遍历是递增序列的原则，若某结点只有右子树，而插入元素的关键字小于该结点的关键字，则会插入到该结点的左侧，成为其左孩子。

这种插入就不是插入到叶子下面。

21．从平衡因子定义看，完全二叉树任一结点的平衡因子的绝对值确实是小于等于1。

但是，平衡二叉树本质上是二叉排序树，完全二叉树不一定是排序树。

故不能说完全二叉树是平衡二叉树。

23．某结点的左子树根结点不一定是它的中序前驱，其右子树根结点也不一定是它的中序后继。

24．在等概率下，查找成功时的平均查找长度相同，查找失败时的平均查找长度不相同。

26．只有被删除结点是叶子结点时命题才正确。

三．填空题1．n n+1 2．4 3．6,9,11,12 4．55．26（第4层是叶子结点，每个结点两个关键字） 6．1,3,6,8,11,13,16,19 7．5,96 8．m-1,「m/2⎤-1 9．2,4,310．(1)哈希函数(2)解决冲突的方法 (3)选择好的哈希函数 (4)处理冲突的方法 (5)均匀(6)简单11．AVL树（高度平衡树，高度平衡的二叉排序树），或为空二叉树，或二叉树中任意结点左子树高度与右子树高度差的绝对值小于等于1。

12．小于等于表长的最大素数或不包含小于20的质因子的合数 13．16 14．⎣㏒n」+1215．(1)45 (2)45 (3)46（块内顺序查找） 16．k(k+1)/2 17．30，31.5（块内顺序查找）18．(1)顺序存储或链式存储 (2)顺序存储且有序 (3)块内顺序存储，块间有序 (4) 散列存储19．(n+1)/2 20．(n+1)/n*log2(n+1)-1 21．结点的左子树的高度减去结点的右子树的高度22．(1)顺序表(2)树表(3)哈希表(4)开放定址方法(5)链地址方法(6)再哈希(7)建立公共溢出区23．直接定址法 24．log⎡m/2⎤(21n+)+1 25．O(N) 26．n(n+1)/227．54 28．31 29．37/12 30．主关键字 31．左子树右子树32．插入删除 33．14 34．(1)126 (2)64 (3)33 (4)65 35．（1）low<=high (2) (low+hig) DIV 2 (3) binsrch:=mid (4)binsrch:=0 36．(1) k (2) I<n+1 37．(1)rear=mid-1 (2)head=mid+1 (3)head>rear 38．(1)p!=null (2)pf=p (3)p!=*t (4)*t=null四．应用题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’}，学生基本信息表也可是一个数据对象。

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

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

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

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

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

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

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

单元练习8一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳）（√）（1）图可以没有边，但不能没有顶点。

（ㄨ）（2）在无向图中，（V1，V2）与（V2，V1）是两条不同的边。

（ㄨ）（3）邻接表只能用于有向图的存储。

（√）（4）一个图的邻接矩阵表示是唯一的。

（ㄨ）（5）用邻接矩阵法存储一个图时，所占用的存储空间大小与图中顶点个数无关，而只与图的边数有关。

（ㄨ）（6）有向图不能进行广度优先遍历。

（√）（7）若一个无向图的以顶点V1为起点进行深度优先遍历，所得的遍历序列唯一，则可以唯一确定该图。

（√）（8）存储无向图的邻接矩阵是对称的，因此只要存储邻接矩阵的上三角（或下三角）部分就可以了。

（ㄨ）（9）用邻接表法存储图时，占用的存储空间大小只与图中的边数有关，而与结点的个数无关。

（√）（10）若一个无向图中任一顶点出发，进行一次深度优先遍历，就可以访问图中所有的顶点，则该图一定是连通的。

二．填空题（1）图常用的存储方式有邻接矩阵和邻接表等。

（2）图的遍历有：深度优先搜和广度优先搜等方法。

（3）有n条边的无向图邻接矩阵中，1的个数是 _2n____。

（4）有向图的边也称为 _ 弧___ 。

（5）图的邻接矩阵表示法是表示 __顶点____之间相邻关系的矩阵。

（6）有向图G用邻接矩阵存储，其第i行的所有元素之和等于顶点i的 __出度____。

（7）n个顶点e条边的图若采用邻接矩阵存储，则空间复杂度为：O（n2）。

（8）n个顶点e条边的图若采用邻接表存储，则空间复杂度为：O（n+e）。

（9）设有一稀疏图G，则G采用 _邻接表____存储比较节省空间。

（10）设有一稠密图G，则G采用 _邻接矩阵____存储比较节省空间。

（11）图的逆邻接表存储结构只适用于 __有向____图。

（12） n个顶点的完全无向图有 n(n-1)/2_ 条边。

（13）有向图的邻接表表示适于求顶点的出度。

（14）有向图的邻接矩阵表示中，第i列上非0元素的个数为顶点V i的入度。

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

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

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

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

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

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

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

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

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

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

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

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

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

则表示该遗产继承关系的最合适的数据结构应该是（）。