数据结构(严蔚敏)第10章

数据结构教材出版社：清华大学出版社作者：严蔚敏吴伟民ISBN ：978-7-302-02368-5目录第1章绪论1.1 什么是数据结构1.2 基本概念和术语1.3 抽象数据类型的表现与实现1.4 算法和算法分析第2章线性表2.1 线性表的类型定义2.2 线性表的顺序表示和实现2.3 线性表的链式表示和实现2.4 一元多项式的表示及相加第3章栈和队列3.1 栈3.2 栈的应有和举例3.3 栈与递归的实现3.4 队列3.5 离散事件模拟第4章串4.1 串类型的定义4.2 串的表示和实现4.3 串的模式匹配算法4.4 串操作应用举例第5章数组和广义表5.1 数组的定义5.2 数组的顺序表现和实现5.3 矩阵的压缩存储5.4 广义表的定义5.5 广义表的储存结构5.6 m元多项式的表示5.7 广义表的递归算法第6章树和二叉树6.1 树的定义和基本术语6.2 二叉树6.2.1 二叉树的定义6.2.2 二叉树的性质6.2.3 二叉树的存储结构6.3 遍历二叉树和线索二叉树6.3.1 遍历二叉树6.3.2 线索二叉树6.4 树和森林6.4.1 树的存储结构6.4.2 森林与二叉树的转换6.4.3 树和森林的遍历6.5 树与等价问题6.6 赫夫曼树及其应用6.6.1 最优二叉树（赫夫曼树）6.6.2 赫夫曼编码6.7 回溯法与树的遍历6.8 树的计数第7章图7.1 图的定义和术语7.2 图的存储结构7.2.1 数组表示法7.2.2 邻接表7.2.3 十字链表7.2.4 邻接多重表7.3 图的遍历7.3.1 深度优先搜索7.3.2 广度优先搜索7.4 图的连通性问题7.4.1 无向图的连通分量和生成树7.4.2 有向图的强连通分量7.4.3 最小生成树7.4.4 关节点和重连通分量7.5 有向无环图及其应用7.5.1 拓扑排序7.5.2 关键路径7.6 最短路径7.6.1 从某个源点到其余各顶点的最短路径7.6.2 每一对顶点之间的最短路径第8章动态存储管理8.1 概述8.2 可利用空间表及分配方法8.3 边界标识法8.3.1 可利用空间表的结构8.3.2 分配算法8.3.3 回收算法8.4 伙伴系统8.4.1 可利用空间表的结构8.4.2 分配算法8.4.3 回收算法8.5 无用单元收集8.6 存储紧缩第9章查找9.1 静态查找表9.1.1 顺序表的查找9.1.2 有序表的查找9.1.3 静态树表的查找9.1.4 索引顺序表的查找9.2 动态查找表9.2.1 二叉排序树和平衡二叉树9.2.2 B树和B+树9.2.3 键树9.3 哈希表9.3.1 什么是哈希表9.3.2 哈希函数的构造方法9.3.3 处理冲突的方法9.3.4 哈希表的查找及其分析第10章内部排序10.1 概述10.2 插入排序10.2.1 直接插入排序10.2.2 其他插入排序10.2.3 希尔排序10.3 快速排序10.4 选择排序10.4.1 简单选择排序10.4.2 树形选择排序10.4.3 堆排序10.5 归并排序10.6 基数排序10.6.1 多关键字的排序10.6.2 链式基数排序10.7 各种内部排序方法的比较讨论第11章外部排序11.1 外存信息的存取11.2 外部排序的方法11.3 多路平衡归并的实现11.4 置换一选择排序11.5 最佳归并树第12章文件12.1 有关文件的基本概念12.2 顺序文件12.3 索引文件12.4 ISAM文件和VSAM文件12.4.1 ISAM文件12.4.2 VSAM文件12.5 直接存取文件（散列文件）12.6 多关键字文件12.6.1 多重表文件12.6.2 倒排文件附录A 名词索引附录B 函数索引参考书目。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

解：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，否则返回0Max(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，否则返回0IsDescending(R)操作结果：若有理数R的两个元素按降序排列，则返回1，否则返回0Max(R,&e)操作结果：用e返回有理数R的两个元素中值较大的一个Min(R,&e)操作结果：用e返回有理数R的两个元素中值较小的一个}ADT RationalNumber1.5 试画出与下列程序段等价的框图。

数据结构严蔚敏版第十章答案第十章：图一、概述图是一种非常重要的数据结构，它由节点（顶点）和边组成，用于描述事物之间的关系。

在本章中，我们将学习图的基本概念、表示方法和常用算法。

二、基本概念1. 顶点（节点）：图中的一个元素，用于表示一个实体，如人、地点等。

2. 边：连接两个顶点的关系，可以是有向的（箭头指向一个方向）或无向的（没有箭头）。

3. 路径：由一系列顶点和边组成的序列，表示从一个顶点到另一个顶点的通路。

4. 无环图：不存在回路（从一个顶点出发，经过若干边又回到该顶点）的图。

5. 有环图：存在回路的图。

三、表示方法1. 邻接矩阵：使用二维数组来表示图的连接关系，数组的行和列分别对应图中的顶点，数组元素表示边的权重或连接状态。

2. 邻接表：使用链表来表示图的连接关系，每个顶点对应一个链表，链表中存储与该顶点相连的其他顶点。

四、图的遍历1. 深度优先搜索（DFS）：从一个顶点开始，沿着一条路径尽可能深入地访问顶点，直到无法继续为止，然后回溯到上一个顶点，继续访问其他路径。

使用栈来实现。

2. 广度优先搜索（BFS）：从一个顶点开始，先访问其所有相邻顶点，然后再访问相邻顶点的相邻顶点，以此类推，直到所有顶点都被访问到。

使用队列来实现。

五、最小生成树最小生成树是指在一个连通图中，选择其中的一些边，使得这些边构成一棵树，并且树上所有边的权重之和最小。

常用的算法有Prim算法和Kruskal算法。

六、最短路径最短路径是指从一个顶点到另一个顶点的路径中，路径上所有边的权重之和最小。

常用的算法有Dijkstra算法和Floyd算法。

七、拓扑排序拓扑排序是对有向无环图进行排序的一种算法。

它将图中的顶点按照一定的顺序排列，使得所有的有向边都从前面的顶点指向后面的顶点。

八、关键路径关键路径是指在一个有向无环图中，从开始顶点到结束顶点的最长路径。

关键路径上的活动不能延误，否则将影响整个工程的进度。

九、其他图算法除了上述提到的算法，还有许多其他的图算法，如最大流问题、二分图匹配等。

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

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

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

i=s=0; ① while(s<="" ②="" ③="">解：语句①为赋值语句，其执行次数为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 ）。

数据结构习题集答案(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、数据结构是计较机中存储、组织数据的方法.精心选择的数据结构可以带来最优效率的算法.2、程序设计=算法+数据结构3、解决问题办法的效率：●跟数据的组织方法有关●跟空间的利用效率有关●跟算法的巧妙程度有关4、数据：所有能输入到计较机中,且被计较机处理的符号的荟萃，是计较机操纵对象的总称；是计较机处理的信息的某种特定的符号暗示形式.5、数据元素：数据中的一个“个别”,数据结构中讨论的根本单位.相当于“记实”,在计较机程序中通常作为一个整体考虑和处理.6、数据项: 相当于记实的“域”, 是数据的不成联系的最小单位,如学号.数据元素是数据项的荟萃.7、数据对象：性质相同的数据元素的荟萃.例如: 所有运动员的记实荟萃8、数据结构：是相互间存在某种关系的数据元素荟萃.9、数据结构是带结构的数据元素的荟萃.10、不合的关系组成不合的结构.11、次序关系：{<ai,ai+1>|i=1,2,3,4,5,6}12、对每种数据结构，主要讨论如下两方面的问题：1）数据的逻辑结构，数据结构的根本操纵；2）数据的存储结构，数据结构根本操纵的实现；13、数据的逻辑结构：数据之间的结构关系，是具体关系的抽象.数据结构的根本操纵：指对数据结构的加工处理.14、数据的存储结构(物理结构)：数据结构在计较机内存中的暗示.数据结构根本操纵的实现：根本操纵在计较机上的实现（办法).15、数据结构的有关概念16、数据元素的4类的根本结构：○1荟萃；○2线性结构：结构中数据元素之间存在一对一的关系；○3树形结构：结构中数据元素之间存在一对多的关系；○4图状结构或网状结构：结构中数据元素之间存在多对多的关系.17、C语言的优点：C语言可以直接操纵内存.18、每个节点都由两部分组成：数据域和指针域.19、链接存储结构特点：●比顺序存储结构的存储密度小(每个节点都由数据域和指针域组成).●逻辑上相邻的节点物理上不必相邻.●拔出、删除灵活(不必移动节点，只要改叛变点中的指针).20、数据类型是一个值的荟萃和定义在此荟萃上的一组操纵的总称.21、ADT 有两个重要特征:数据抽象和数据封装.22、抽象数据类型(Abstract Data Type 简称ADT)：是指一个数学模型以及定义在此数学模型上的一组操纵.23、抽象数据类型有：数据对象〈数据对象的定义〉、数据关系〈数据关系的定义〉、根本操纵〈根本操纵的定义〉.24、数据类型的定义和寄义.定义：数据类型是一个值的荟萃和定义在这个值集上的一组操纵的总称.寄义：将数据按一定次序与形式存放的结构.24、算法空间庞杂度S(n)算法的存储量包含：①输入数据所占的空间；②程序自己所占的空间；③帮助变量所占的空间.25、算法具有有穷性、确定性、可行性、输入和输出五大特性.26、抽象数据类型具有数据抽象、数据封装的特点.27、数据的储存结构分为：顺序存储结构和链式存储结构.第二章线性表1、线性结构的特点：在数据元素中的非空有限集中.（1）存在唯一的一个被称作“第一”的数据元素；（2）存在唯一的一个被称作“最后一个”的数据元素；（3）除第一个外，荟萃中的每一个数据元素均只有一个前驱；（4）除最后一个外，荟萃中的每一个数据元素均只有一个后继.2、线性表(Linear List) ：一个线性表是n个数据元素的有限序列.3、线性表的顺序存储实现：typedef struct {ElementType Data[MAXSIZE];int Last;} List;List L, *PtrL;4、初始化（成立空的顺序表）List *MakeEmpty( ){ List *PtrL;PtrL = (List *)malloc( sizeof(List) );PtrL->Last = -1;return PtrL;}5、查找int Find( ElementType X, List *PtrL ){ int i = 0;while( i <= PtrL->Last && PtrL->Data[i]!= X )i++;if (i > PtrL->Last) return -1; /* 如果没找到，前往-1 */else return i; /* 找到后前往的是存储位置*/}6、拔出算法void Insert( ElementType X, int i, List *PtrL ){ int j;if ( PtrL->Last == MAXSIZE-1 ){ /* 表空间已满，不克不及拔出*/printf(＂表满＂);return;}if ( i < 1 || i > PtrL->Last+2) { /*查抄拔出位置的正当性*/printf(＂位置不正当＂);return;}for ( j = PtrL->Last; j >= i-1; j-- )PtrL->Data[j+1] = PtrL->Data[j]; /*将ai～an 倒序向后移动*/PtrL->Data[i-1] = X; /*新元素拔出*/PtrL->Last++; /*Last仍指向最后元素*/return;}7、删除算法void Delete( int i, List *PtrL ){ int j;if( i < 1 || i > PtrL->Last+1 ) { /*查抄空表及删除位置的正当性*/printf (“不存在第%d个元素”, i );return ;}for ( j = i; j <= PtrL->Last; j++ )PtrL->Data[j-1] = PtrL->Data[j]; /*将ai+1～an顺序向前移动*/PtrL->Last--; /*Last仍指向最后元素*/return;}8、求表长int Length ( List *PtrL ){ List *p = PtrL; /* p指向表的第一个结点*/ int j = 0;while ( p ) {p = p->Next;j++; /* 当前p指向的是第j 个结点*/}return j;}9、查找（1）顺次号查找: FindKth;List *FindKth( int K, List *PtrL ){ List *p = PtrL;int i = 1;while (p !=NULL && i < K ) {p = p->Next;i++;}if ( i == K ) return p;/* 找到第K个，前往指针*/else return NULL;/* 不然前往空*/}（2）按值查找: FindList *Find( ElementType X, List *PtrL ){List *p = PtrL;while ( p!=NULL && p->Data != X )p = p->Next;return p;}10、拔出（在链表的第i-1(1≤i≤n+1)个结点后拔出一个值为X 的新结点)List *Insert( ElementType X, int i, List *PtrL ){ List *p, *s;if ( i == 1 ) { /* 新结点拔出在表头*/s = (List *)malloc(sizeof(List)); /*申请、填装结点*/s->Data = X;s->Next = PtrL;return s; /*前往新表头指针*/}p = FindKth( i-1, PtrL ); /* 查找第i-1个结点*/if ( p == NULL ) { /* 第i-1个不存在，不克不及拔出*/printf(＂参数i错＂);return NULL;}else {s = (List *)malloc(sizeof(List)); /*申请、填装结点*/s->Data = X;s->Next = p->Next; /*新结点拔出在第i-1个结点的前面*/p->Next = s;return PtrL;}}11、删除（删除链表的第i (1≤i≤n)个位置上的结点)List *Delete( int i, List *PtrL ){ List *p, *s;if ( i == 1 ) { /* 若要删除的是表的第一个结点*/s = PtrL; /*s指向第1个结点*/PtrL = PtrL->Next; /*从链表中删除*/free(s); /*释放被删除结点*/return PtrL;}p = FindKth( i-1, PtrL ); /*查找第i-1个结点*/if ( p == NULL ) {printf(“第%d个结点不存在”, i-1); return NULL;} else if ( p->Next == NULL ){printf(“第%d个结点不存在”, i); return NULL;} else {s = p->Next; /*s指向第i个结点*/p->Next = s->Next; /*从链表中删除*/free(s); /*释放被删除结点*/return PtrL;}}12、链表不具备的特点是 1 .①可随机拜访任一节点②拔出删除不须要移动元素③不必事先估量存储空间④所需空间与其长度成正比13、带头结点的单链表head为空的判定条件是 2 .①head==NULL ②head->next==NULL③head->next==head ④head!=NULL14、如果最经常使用的操纵是取第i个结点及其前驱，则采取 4 存储方法最节省时间.①单链表②双链表③单循环链表④顺序表第三章Chapter 3 栈(stacks)和队列（queues）1、栈是限定仅能在表尾一端进行拔出、删除操纵的线性表.2、栈的特点是“落后栈的元素先出栈”（last in, first out），故栈又称为落后先出表（LIFO）.3、一个栈是一些元素的线形列表，其中元素的拔出和删除均在表的同一端进行.拔出和删除产生的一端称为栈顶（the top of the stack）.4、第一个进栈的元素在栈底，最后一个进栈的元素在栈顶，第一个出栈的元素为栈顶元素，最后一个出栈的元素为栈底元素.5、连续栈(Contiguous Stack)的类型定义#define MaxStack 50Typedef struct{datatype stack[MaxStack];int top;}Seqstack;Seqstack *s;6、判断栈是否已满？viod Push(Seqstack *s, datatype x ){if (s->top>=MaxStack-1) printf(“ overflow” );else {s-> top++;s->stack[s->top]=x;}}7、判断栈是否为空？datatype pop(Seqstack *s ){ if (s->top<0){printf(“underflow”); return(NULL);}return(s->stack[s->top]);s->top--;}8、前往栈顶元素的值，栈不产生变更.datatype top(Seqstack *s ){ if (s->top<0){printf(“underflow”); return(NULL);}return(s->stack[s->top]);}9、链栈（Linked Stack)的类型定义栈的链式存储结构称为链栈，它是运算受限的单链表，拔出和删除操纵仅限制在表头位置上进行.由于只能在链表头部进行操纵，故链表没有需要像单链表那样附加头结点.栈顶指针就是链表的头指针.链栈的类型说明如下：typedef struct stacknode {datatype datastruct stacknode *next}stacknode10、链式栈的特点：链式栈无栈满问题；空间可扩充；拔出与删除仅在栈顶处执行；链式栈的栈顶在链头；适合于多栈操纵.11、栈是限定仅能在表的一端进行拔出、删除操纵的线性表.12、栈的元素具有落后先出的特点.13、栈顶元素的位置由栈顶指针的指示, 进栈、出栈操纵要修改栈顶指针.14、抽象数据类型队列的定义：队列(Queue)也是一种运算受限的线性表.它只允许在表的一端进行拔出，而在另一端进行删除.允许删除的一端称为队头(front)，允许拔出的一端称为队尾(rear).15、队列亦称作先进先出(First In First Out)的线性表，简称FIFO表.16、双端队列：就是限定拔出和删除操纵在表的两端进行的线性表.17、链队列结点定义：typedef struct Qnode{ QElemType data;struct QNode *next;} QNode,*QueuPtr;18、队列的顺序存储结构称为顺序队列，在队列的顺序存储结构中，除了用一组地址连续的储存单元依次存放从队头到队尾的元素之外，尚需要附设两个指针front和rear 辨别指示队列头元素和队列尾元素的位置.19、在非空队列中，头指针始终指向队头元素，而尾指针始终指向队尾元素的下一位置.20、栈的特点是先进后出，队列的特点是先进后出.21、栈和队列的配合特点是只允许在端点处拔出和删除元素.22、一个栈的进栈序列是a，b，c，d，e，则栈的不成能的输出序列是C .（A）edcba （B）decba （C）dceab （D）abcde23、若已知一个栈的进栈序列是p1，p2，p3，…，pn .其输出序列为1，2，3，…，n ，若p3=1，则p1为 C .（A）可能是2（B）一定是2（C）不成能是2 （D）不成能是324、设有一个空栈，栈顶指针为1000H（十六进制，下同），现有输入序列为1、2、3、4、5，经过PUSH，PUSH，POP，PUSH，POP，PUSH，PUSH后，输出序列是3，栈顶指针是8.①5、4、3、2、1 ②2、1 ③2、3④3、4 ⑤1002H ⑥1004H⑦1005H ⑧1003H24、一个队列的入队序列是若1，2，3，4，则队列的输出序列是 B .（A）4，3，2，1 （B）1，2，3，4（C）1，4，3，2 （D）3，2，4，125、若用一个大小为6的一维数组来实现循环队列，且当前rear和front的值辨别为0和3.当从队列中删除一个元素，再参加两个元素后，rear和front的值辨别是 B .（A）1和5 （B）2和4 （C）4和2 （D）5和126、有5个元素，其入栈次序为A、B、C、D、E，在各类可能的出栈次序中，以元素C、D最先出栈（即C第一个且D第二个出栈）的次序有哪几个？C、D、B、A、E C、D、E、B、AC、D、B、E、A第六章树和二叉树1、树型结构是一类重要的非线性结构.2、树的定义：树是n(n>=0)个结点的有限集T，T为空时称为空树，不然它满足如下两个条件：（1）有且仅有一个特定的称为根的结点；（2）当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1，T2，T3…Tm，其中每个子集又是一棵树，并称其为根的子树.3、根本术语结点——暗示树中的元素，包含数据项及若干指向其子树的分支结点的度(degree)——结点拥有的子树数叶子(leaf)——度为0的结点孩子(child)——结点子树的根称为该结点的孩子双亲(parents)——孩子结点的上层结点叫该结点的~兄弟(sibling)——同一双亲的孩子树的度——一棵树中最大的结点度数结点的条理(level)——从根结点算起，根为第一层，它的孩子为第二层……深度(depth)——树中结点的最大条理数森林(forest)——m(m0)棵互不相交的树的荟萃例题:4、二叉树是由n(n>=0)个结点的有限荟萃组成，此荟萃或为空集，或由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树.二叉树可以是空荟萃，根可以有空的左子树或空的右子树.性质1: 在二叉树的第i层上至多有2i-1个结点(i>=1).性质2：深度为k的二叉树至多有2k－1个结点（k>=1).性质3：对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0＝n2＋1.性质4：具有n个结点的完全二叉树的深度为log2n＋1.性质5：如果对一棵有n个结点的完全二叉树的结点按层序编号（从第1层到第log2n +1层，每层从左到右)，则对任一结点i（1<=i<=n)，有：（1）如果i＝1，则结点i无双亲，是二叉树的根；如果i>1，则其双亲是结点i/2.（2）如果2i>n，则结点i为叶子结点，无左孩子；不然，其左孩子是结点2i.（3）如果2i＋1>n，则结点i无右孩子；不然，其右孩子是结点2i＋1.一棵深度为k且有2k-1个结点的二叉树称为满二叉树.如：5、二叉树的存储结构●顺序存储结构define MAX-TREE-SIZE 100Typedef TelemType SqBiTree[ MAX-TREE-SIZE];SqBitree bt;缺点是有可能对存储空间造成极大的浪费.●链式存储结构二叉链式存储结构typedef struct BiTNode{ TElemType data;struct BiTNode *lchild, *rchild;}BiTNode,*BiTree;三叉链表typedef struct node{ datatype data;struct node *lchild, *rchild, *parent;}JD;6、遍历二叉树二叉树是由三个根本单元组成：根结点、左子树和右子树.若限定先左后右，则只有前三种情况，辨别称之为先（根）序遍历，中（根）序遍历和后（根）序遍历.（1）先序遍历算法若二叉树为空树，则空操纵；不然，●拜访根结点；●先序遍历左子树；●先序遍历右子树.void PreOrder（BiTree bt）{/*先序遍历二叉树bt*/if (bt==NULL) return; /*递归调用的结束条件*/Visite（bt->data）; /*(1)拜访结点的数据域*/PreOrder（bt->lchild）; /*(2)先序递归遍历bt的左子树*/ PreOrder（bt->rchild）;/*(3)先序递归遍历bt的右子树*/}例题：先序遍历序列：A B D Cvoid preorder(JD *bt){ if(bt!=NULL){ printf("%d\t",bt->data);preorder(bt->lchild);preorder(bt->rchild);}}（2）中序遍历算法若二叉树为空树，则空操纵；不然，●先序遍历左子树；●拜访根结点；●先序遍历右子树.void InOrder（BiTree bt）{/*先序遍历二叉树bt*/if (bt==NULL) return; /*递归调用的结束条件*/InOrder（bt->lchild）; /*(2)先序递归遍历bt的左子树*/ Visite（bt->data）; /*(1)拜访结点的数据域*/InOrder（bt->rchild）;/*(3)先序递归遍历bt的右子树*/}例题：中序遍历序列：B D A C（3）后序遍历算法若二叉树为空树，则空操纵；不然，●先序遍历左子树；●先序遍历右子树；●拜访根结点.void PostOrder（BiTree bt）{/*后序遍历二叉树bt*/if (bt==NULL) return; /*递归调用的结束条件*/PostOrder（bt->lchild）;/*(1)后序递归遍历bt的左子树*/PostOrder（bt->rchild）; /*(2)后序递归遍历bt的右子树Visite（bt->data）; /*(3)拜访结点的数据域*/}例题：后序遍历序列：D B C A（4）条理遍历所谓二叉树的条理遍历，是指从二叉树的第一层（根结点）开始，从上至下逐层遍历，在同一层中，则按从左到右的顺序对结点逐个拜访.条理遍历序列:1 2 3 4 5 67、例题：1、先序序列：A B C D E F G H K中序序列：B D C A E H G K F后序序列：D C B H K G F E K条理序列：A B E C F D G H K2、若先序遍历此二叉树，按拜访结点的先后次序将结点排列起来，其先序序列为：-+a*b-cd/ef按中序遍历，其中序序列为：a+b*c-d-e/f按后序遍历，其后序序列为：abcd-*+ef/ -8、（1）查询二叉树中某个结点Status Preorder (BiTree T, ElemType x, BiTree &p) {// 若二叉树中存在和x 相同的元素，则p 指向该结点并//前往OK,// 不然前往FALSEif (T) {if (T->data= =x) { p = T; return OK,}else {if (Preorder(T->lchild, x, p)）return OK;else (Preorder(T->rchild, x, p)) return OK;}//else}//ifelse return FALSE;}（2）计较二叉树中叶子结点的个数int CountLeaf (BiTree T){//前往指针T所指二叉树中所有叶子结点个数if (!T ) return 0;if (!T->lchild && !T->rchild) return 1;else{m = CountLeaf( T->lchild);n = CountLeaf( T->rchild);return (m+n);} //else } // CountLeaf（3）求二叉树的深度(后序遍历)int Depth (BiTree T ){ // 前往二叉树的深度if ( !T ) depthval = 0; else {depthLeft = Depth( T->lchild );depthRight= Depth( T->rchild );depthval = 1 + (depthLeft > depthRight ?depthLeft : depthRight);}return depthval;}（4）按先序遍历序列成立二叉树Status CreateBiTree (BiTree &T ){ //按先序次序输入二叉树中结点的值（一个字符），空格字符暗示空树，机关二叉链表暗示的二叉树Tscanf (&ch);if ( ch==‘‘ ) T=NULL; else {if(!T=(BiTNode *)malloc(sizeof(BiTNode)))) exit (OVERFLOW);T->data=ch; //生成根结点CreateBiTree(T->lchild);//机关左子树CreateBiTree(T->rchild);//机关右子树}Return OK; }//CreateBiTree9、遍历二叉树的非递归算法（1）先序遍历二叉树的非递归算法void inorder(JD *r)//先序遍历二叉树非递归算法// { int i=0; JD *p,*s[M]; p=r;do {while(p!=NULL) {printf("%d\t",p->data);if (p->rc!=NULL)s[i++]=p->rc;p=p->lc;}if ( i > 0) p=s[--i];}while( i>0 || p!=NULL); }（2）中序遍历二叉树的非递归算法void inorder(JD *r)//先序遍历二叉树非递归算法// { int i=0; JD *p,*s[M]; p=r;do {while(p!=NULL) {{s[i++]=p; p=p->lc;}if (i>0){p=s[--i];printf("%d\t",p->data);p=p->lc;}if ( i > 0) p=s[--i];}while( i>0 || p!=NULL); }（3）后序遍历二叉树的非递归算法void inorder(JD *r)//先序遍历二叉树非递归算法//{ int s2[M],b,i=0; JD *p,*s1[M]; p=r;do {while(p!=NULL) {{s1[i-1]=p;s2[i++]=0;p=p->lc;}while (i>0 && (s2[i-1]=1)){p=s1[--i]; printf(“%d\t”,p->data ); }if (i>0){p=s[--i];printf("%d\t",p->data);p=p->lc;}if ( i > 0){ s2[i-1]=1; p=s1[i-1]; p=p->rc; }}while( i>0); }11、线索二叉树：以二叉链表作为存储结构时，只能找到结点的左右孩子的信息，而不克不及在结点的任一序列的前驱与后继信息，这种信息只有在遍历的动态进程中才干得到，为了能保管所需的信息，可增加标记域;Ltag=0 ，lchild 域指示结点的左孩子；Ltag=1，lchild 域指示结点的前驱.Rtag=0，rchild 域指示结点的右孩子；Rtag=1，rchild 域指示结点的后驱.以这种结构组成的二叉链表作为二叉树的存储结构，叫做线索链表，其中指向结点前驱与后继的指针叫做线索，加上线索的二叉树称之为线索二叉树.（1）先序线索二叉树（2）中序线索二叉树（3）后序线索二叉树12、树的存储结构○1双亲暗示法#define MAX_TREE_SIZE 100typedef struct PTNode {//结点结构ElemType data;int parent; // 双亲位置域} PTNode;typedef struct {//树结构PTNode nodes[MAX_TREE_SIZE];int r, n; // 根结点的位置和结点个数} PTree;○2孩子暗示法○3带双亲的孩子链表○4孩子兄弟暗示法链表中每个结点的两个指针域辨别指向其第一个孩子结点和下一个兄弟结点.typedef struct node{ datatype data;struct node *fch, *nsib;}JD;13、树和森林与二叉树的转换加线：在兄弟之间加一连线.抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的关系，旋转：以树的根结点为轴心，将整树顺时针转45°.13、将二叉树转换成树●加线：若p结点是双亲结点的左孩子，则将p的右孩子，右孩子的右孩子，……沿分支找到的所有右孩子，都与p的双亲用线连起来.●抹线：抹掉原二叉树中双亲与右孩子之间的连线●调整：将结点按条理排列，形成树结构14、森林转换二叉树（1）将各棵树辨别转换成二叉树.（2）将每棵树的根结点用线相连.（3）以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，组成二叉树型结构14、二叉树转换成森林抹线：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之酿成孤立的二叉树.复原：将孤立的二叉树复原成15、树和森林的遍历树的遍历两种次序遍历树的办法：一种是先根（次序）遍历树，即先拜访树的根结点，然后依次先根遍历根的每棵子树；一种是后根（次序）遍历，即先依次后根遍历每棵子树，然后拜访根结点.森林的遍历先序遍历：A B C D E F G H I J中序遍历：B C D A F E H J I G16、赫夫曼树及其应用例题：w={5, 29, 7, 8, 14, 23, 3, 11}习题：1、由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法B .（A）正确（B）错误2、某二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树一定是D .（A）空或只有一个结点（B）完全二叉树（C）二叉排序树（D）高度等于其节点数3、深度为5的二叉树至多有C 个结点.（A）16 （B）32 （C）31 （D）104、按照使用频率为5个字符设计的赫夫曼编码不成能是C .（A）111，110，10，01，00（B）000，001，010，011，1（C）100，11，10，1，0（D）001，000，01，11，105、树和二叉树的主要不同是（1）树的结点个数至少为1，而二叉树的结点个数可以为0（2）树中结点的最大度数没有限制，而二叉树结点的最大度数为2（3）树的结点无左、右之分，而二叉树的结点右左、右之分.6、深度为k的完全二叉树至少有个结点，至多有个结点，若按自上而下，从左到右次序给结点编号（从1开始），则编号最小的叶子结点的编号.7、一棵二叉树的第i(i1)层最多有个结点；一棵有n（n>0）个结点的满二叉树共有个叶子结点和个非叶子结点.8、已知二叉树的先序、中序和后序序列辨别如下，其中有一些看不清的字母用*暗示，请机关出一棵适合条件的二叉树并画出该二叉树.●先序序列是：*BC**FG●中序序列是：CB*EAG*●后序序列是：*EDB*FA9、将右图所示的树转化为二叉树，并写出先序遍历，中序遍历和后序遍历的结果.解：先序：ABEFGCDHI中序：EFGBCHIDA后序：GFEIHDCBA10、设给定权集w={2，3，4，7，8，9}，试机关关于w的一棵赫夫曼树，并求其加权路径长度WPL.WPL=(9+7+8)*2+4*3+(2+3)*4=80第十章内部排序1、内排序大致可分为五类：拔出排序、互换排序、选择排序、归并排序和分派排序.2、直接拔出排序直接拔出的算法实现void sort(NODE array[],int n)//待排序元素用一个数组array[ ] 暗示，数组有n 个元素 { int i, j;NODE x; // x 为中间结点变量for ( i=1; i<n; i++) //i 暗示拔出次数,共进行n-1次拔出{ x=array[i]; //把待排序元素赋给 xj=i-1;while ((j>=0)&& ( x.key<array[j].key)){array[j+1]=array[j]; j--; } // 顺序比较和移动 array[j+1]=x; }}例如，n=6，数组R 的六个排序码辨别为：17，3，25，14，20，9.它的直接拔出排序的执行进程如图7-1所示. 直接拔出排序的时间庞杂度为O （n2）. 直接拔出算法的元素移动是顺序的，该办法是稳定的. 3、希尔排序 希尔排序的时间庞杂性在O （nlog2n ）和O （n2 ）之间，大致为O （n1.3）.由于希尔排序对每个子序列单独比较，在比较时进行元素移动，有可能改动相同排序码元素的原始顺序，因此希尔0 1 2 3 4 5初始状态 (17 ) 3 25 14 20 9 第一次插入 (3 17 ) 25 14 20 9 第二次插入 (3 17 25 ) 14 20 9 第三次插入 (3 14 17 25 ) 20 9 第四次插入 (3 14 17 20 25 ) 9第五次插入 (3 9 14 17 20 25)图10-1直接插入排序示例排序是不稳定的.例如，n=8，数组array[ ]的八个元素辨别为：91，67，35，62，29，72，46，57.下面用图10-2给出希尔排序算法的执行进程.4、互换排序1）冒泡排序冒泡排序的算法实现void Bubblesort( NODE array[],int n){ int i, j, flag; //当flag为0则停止排序NODE temp;for ( i=1; i<n; i++) // i 暗示趟数，最多n-1趟{ flag=0; //开始时元素未互换for ( j=n-1; j>=i; j--)if (array[j].key<array[j-1].key) //产生逆序temp=array[j];array[j]=array[j-1];array[j-1]=temp;flag=1; } //互换，并标识表记标帜产生了互换if(flag==0) break; }}例如，n=6，数组R的六个排序码辨别为：17，3，25，14，20，9.下面用图10-3给出冒泡排序算法的执行进程.冒泡排序算法的时间庞杂度为O（n2）.由于其中的元素移动较多，所以属于内排序中速度较慢的一种.因为冒泡排序算法只进行元素间的顺序移动，所以是一个稳定的算法.2）快速排序快速排序（Quick Sorting）是迄今为止所有内排序算法中速度最快的一种.快速排序的算法实现void quicksort(NODE array[],int start , int end){ int i , j; NODE mid;if (start>=end) return;i=start;j=end;mid=array[i];while (i<j){ while (i<j && array[j].key>mid.key) j--;if (i<j) {array[i]=array[j]; i++; }while (i<j && array[i].key<=mid.key) i++;if (i<j) {array[j]=array[i]; j--; } } //一次划分得到基准值的正确位置array[i]=mid;quicksort(array,start,i-1); //递归调用左子区间quicksort(array,i+1,end); }//递归调用右子区间例如，给定排序码为：（46，55，13，42，94，05，17，70），具体划分如图10-4所示.快速排序所占用的帮助空间为栈的深度，故最好的空间庞杂度为O（log2n），最坏的空间庞杂度为O(n).快速排序是一种不稳定的排序办法.5、选择排序1）直接选择排序例如，给定n=8，数组R中的8个元素的排序码为：（8，3，2，1，7，4，6，5），则直接选择排序进程如图7-5所示.直接选择排序的时间庞杂度为O(n2)数量级2）树形选择排序例如，给定排序码头50，37，66，98，75，12，26，49，树形选择排序进程见图7-7.3）堆排序例如，给定排序码49，38，65，97，76，13，27，70，成立初始堆的进程如图7-8所示.按条理遍历完全二叉树，得到一个由大到小排列的有序序列：97，76，70，65，49，38，27，13每次筛选运算的时间庞杂度为O(log2n)，故整个堆排序进程的时间庞杂度为O(nlog2n).5、归并排序例如，给定排序码46，55，13，42，94，05，17，70，二路归并排序进程如图7-10所示.二路归并排序的时间庞杂度为O(nlog2n).6、各类内排序办法的比较和选择1）从时间庞杂度比较从平均时间庞杂度来考虑，直接拔出排序、冒泡排序、直接选择排序是三种复杂的排序办法，时间庞杂度都为O(n2)，而快速排序、堆排序、二路归并排序的时间庞杂度都为O(nlog2n)，希尔排序的庞杂度介于这两者之间.若从最好的时间庞杂度考虑，则直接拔出排序和冒泡排序的时间庞杂度最好，为O(n)，其它的最好情形同平均情形相同.若从最坏的时间庞杂度考虑，则快速排序的为O(n2)，直接拔出排序、冒泡排序、希尔排序同平均情形相同，但系数大约增加一倍，所以运行速度将下降一半，最坏情形对直接选择排序、堆排序和归并排序影响不大.2）从空间庞杂度比较归并排序的空间庞杂度最大，为O(n)，快速排序的空间庞杂度为O(log2n)，其它排序的空间庞杂度为O（1）.3）从稳定性比较直接拔出排序、冒泡排序、归并排序是稳定的排序办法，而直接选择排序、希尔排序、快速排序、堆排序是不稳定的排序办法.4）从算法复杂性比较直接拔出排序、冒泡排序、直接选择排序都是复杂的排序办法，算法复杂，易于理解，而希尔排序、快速排序、堆排序、归并排序都是改良型的排序办法，算法比复杂排序要庞杂得多，也难于理解.8、各类内排序办法的选择1）从时间庞杂度选择对元素个数较多的排序，可以选快速排序、堆排序、归并排序，元素个数较少时，可以选复杂的排序办法.2）从空间庞杂度选择尽量选空间庞杂度为O（1）的排序办法，其次选空间庞杂度为O(log2n)的快速排序办法，最后才选空间庞杂度为O（n）二路归并排序的排序办法.3）一般选择法则●当待排序元素的个数n较大，排序码散布是随机，而对稳定性不做要求时，则采取快速排序为宜.●当待排序元素的个数n大，内存空间允许，且要求排序稳定时，则采取二路归并排序为宜.●当待排序元素的个数n大，排序码散布可能会出现正序或逆序的情形，且对稳定性不做要求时，则采取堆排序或二路归并排序为宜.●当待排序元素的个数n小，元素根本有序或散布较随机，。