算法与数据结构复习课件

一、绪论

（一）数据结构的研究对象：数据结构的研究对象包括：数据的各种逻辑结构和存储结构以及对数据的各种操作。（二）算法的五个特征：有穷性、确定性、可行性、输入、输出。（三）算法的时间复杂度：T(n)=O(f(n))T（n）叫算法的渐进时间复杂度，简称时间复杂度，O为数量级。12/12/20221一、绪论（一）数据结构的研究对象：12/11/20221习题：1、写出下列算法的时间复杂度。（1）for(i=0;i<n;i++)c[i]=i；（2）for(i=0;i<m;i++)for(j=0;j<n;j++)a[i][j]=i*j；2、数据结构的研究对象包括（）。3、从逻辑上可以把数据结构分为（）和（）两种类型。12/12/20222习题：12/11/20222二、线性表（一）顺序表：12/12/20223二、线性表（一）顺序表：12/11/20223顺序表的存储结构：

#defineMaxsizemaxlentypedefintelemtype;typedefstruct{elemtypev[Maxsize];intlen;}sqlist;12/12/20224顺序表的存储结构：#defineMaxsizemaxl习题：给出顺序表的结构定义，在顺序表List中元素数组下标位置i插入一个元素x。#defineMAXSIZE100structlist//顺序表结构{intv[MAXSIZE];//元素数组

intlen;//顺序表当前包含的元素个数};typedefstructlistList;intinsert(List*L,inti,intx){//略}12/12/20225习题：给出顺序表的结构定义，在顺序表List中元素数组下标位（二）单链表每个结点包括两个域:数据域、指针域。单链表存储结构：typedefstructnode{elemtypedata;structnode*next;}Lnode，*linklist;12/12/20226（二）单链表12/11/20226习题：给出单链表的结构定义，编写函数实现链表的插入和删除操作。structlinknode//单链表结点结构{intdata;//结点数据

structlinknode*next;//后继结点指针};typedefstructlinknodeLnode;（1）在结点p之后插入值为x的新节点svoidinsert(Lnode*p,intx;) { }（2）将结点p的后继结点删除，并释放结点空间voiddelete(Lnode*p){}12/12/20227习题：给出单链表的结构定义，编写函数实现链表的插入和删除操作（三）单循环链表：使单链表的最后一个节点的指针域的值不为NULL,而是指向头结点。这样，整个链表就形成了一个环，这种链表称为单循环链表。12/12/20228（三）单循环链表：12/11/20228习题：1．线性表若采用链式存储结构时，要求内存中可用存储单元的地址（

）。A）必须是连续的

B）部分地址必须是连续的C）一定是不连续的

D）连续或不连续都可以2．链表不具备的特点是（）。A）插入和删除不需要移动元素B）可随机访问任一节点C）不必预分配空间D）所需空间与其长度成正比12/12/20229习题：12/11/202293.不带头结点的单链表head为空的判定条件是（）。A）head==NULLB）head—>next==NULLC）head—>next==headD）head!=NULL4．带头结点的单链表head为空的判定条件是（）。A）head==NULLB）head—>next==NULLC）head—>next==headD）head!=NULL5．带头结点的循环单链表head为空的判定条件是（）。A）head==NULLB）head—>next==NULLC）head—>next==headD）head!=NULL12/12/2022103.不带头结点的单链表head为空的判定条件是（）。6．在单链表中，指针p指向元素为x的结点，实现“删除x的后继”的语句是(

)。A）p=p->next;

B）p->next=p->next->next;C）p->next=p;

D）p=p->next->next;7．在长度为n的顺序表的第i(1≤i≤n+1)个位置上插入一个元素，元素的移动次数为__________。12/12/2022116．在单链表中，指针p指向元素为x的结点，实现“删除x的后继三、栈和队列（一）栈栈(Stack)是限制仅在表的一端进行插入和删除操作的线性表。栈又称为后进先出的线性表，简称LIFO线性表。顺序栈的顺序存储结构：#definemaxsize100//栈的最大容量typedefstruct{elemtpelem[maxsize];inttop;}sqstacktp;12/12/202212三、栈和队列（一）栈12/11/202212（二）队列队列（queue)是限定只能在表的一端进行插入，在表的另一端进行删除的线性表。队尾(rear)——允许插入的一端；队头(front)——允许删除的一端。队列特点：先进先出(FIFO)或后进后出(LILO)。

12/12/202213（二）队列12/11/202213顺序队列的存储结构：#definemaxsize100typedefstruct{elemtpelem[maxsize];intrear,front;}squeuetp；rear指示队尾元素；front指示队头元素前一位置。12/12/202214顺序队列的存储结构：12/11/202214循环队列：把队列设想成环形。为了区分队空、队满状态，少用一个元素空间：front所指单元不放元素。队空：sq.front==sq.rear队满：(sq.rear+1)%M==sq.front12/12/202215循环队列：把队列设想成环形。12/11/202215习题：1．栈是限定在（

）处进行插入或删除操作的线性表。

A）端点

B）栈底

C）栈顶

D）中间2．栈的特点是（

）。

A）先进先出

B）后进先出

C）后进后出

D）不进不出3．顺序栈存储空间的实现使用（

）存储栈元素。

A）链表

B）数组

C）循环链表

D）变量12/12/202216习题：12/11/2022164．顺序栈是空栈的条件是（

）。

A）top==0

B）top==1

C）top==-1

D）top==m5．元素A、B、C、D依次进顺序栈后，栈底元素是（

）。

A）A

B）B

C）C

D）D6．队列是限定在（

）处进行删除操作的线性表。

A）端点

B）队头

C）队尾

D）中间12/12/2022174．顺序栈是空栈的条件是（

）。12/11/202217．队列的特点是（

）。

A）先进先出

B）后进先出

C）先进后出

D）不进不出8．容量是10的循环队的头指针的位置Sq->front为2，则队头元素的位置是（

）。

A）3

B）2

C）1

D）09．循环队列Sq是空队列的条件是（

）。A）Sq-﹥rear==Sq-﹥front

B）(Sq-﹥rear+1)%maxsize==Sq-﹥frontC）Sq-﹥rear==0

D）Sq-﹥front==012/12/2022187．队列的特点是（

）。12/11/20221810．循环队列Sq是满队列的条件是（

）。A）Sq-﹥rear==Sq-﹥front

B）(Sq-﹥rear+1)%maxsize==Sq-﹥frontC）Sq-﹥rear==0

D）Sq-﹥front==011．存放循环队列Sq元素的数组data有10个元素，Sq-﹥front为9，队头元素的位置在（

）。

A）10

B）9

C）1

D）012/12/20221910．循环队列Sq是满队列的条件是（

）。12/11/12用一维数组设计栈，初态是栈空，top=0。现有输入序列是a、b、c、d，经过push、push、pop、push、pop、push、pop、pop操作后，输出序列是__________。13设将a,b,c,d依次入栈,则执行push(a),pop(),push(b),push(c),pop(),pop(),push(d),pop(),则出栈序列是________。

12/12/20222012用一维数组设计栈，初态是栈空，top=0。现有输入序列五、树（一）树的基本概念结点的度——结点拥有的子树数。叶子——度为0的结点，也叫终端结点。分支结点——度不为0的结点，也叫非终端结点。内部结点——除根结点之外，分支结点也称为内部结点。树的度——一棵树中最大的结点度数。孩子——结点子树的根称为该结点的孩子。双亲——孩子结点的上层结点叫该结点的双亲。兄弟——同一双亲的孩子之间互成为兄弟。12/12/202221五、树（一）树的基本概念12/11/202221（二）二叉树的概念和性质二叉树——二叉树是结点的有限集合，这个集合或者是空的，或者由一个根结点或两棵互不相交的称为左子树的和右子树的二叉树组成。满二叉树——深度为k的满二叉树，是由２k－１个结点的深度为K的二叉树。２k-１个结点是二叉树所具有的最大结点个数。完全二叉树——具有n个结点、深度为K的二叉树，当且仅当其所有结点对应于深度为k的满二叉树中编号由1到n的那些结点时，该二叉树便是完全二叉树。12/12/202222（二）二叉树的概念和性质12/11/202222二叉树的性质：性质1在二叉树第i层上至多有２i-1个结点（i≥1）。性质2深度为k的二叉树至多有２k-1个结点（k≥1）。性质3包含n(n>0)个结点的二叉树的分支边数为n-1。性质4对任何一颗二叉树T，如果其终端结点（叶子结点）数为n0，度为2的结点数为n2,则n0=n2+1。12/12/202223二叉树的性质：12/11/202223（三）二叉树的链式存储结构二叉链表的类型定义：structbnodept{datatypedata;structbnodept*lchild,*rchild};typedefstructbnodept*bitreptr;12/12/202224（三）二叉树的链式存储结构二叉链表的类型定义：12/11/2（四）二叉树的三种递归遍历算法遍历：是按一定的规则和次序走遍二叉树的所有结点，使每个结点都被访问一次，而且只被访问一次。遍历二叉树的目的：得到二叉树中各结点的一种线性顺序，使非线性的二叉树线性化。三种递归遍历算法：（1）先根序遍历（2）中根序遍历（3）后根序遍历12/12/202225（四）二叉树的三种递归遍历算法遍历：是按一定的规则和次序走遍写出下图所示完全二叉树的先序、中序、后序序列：12/12/202226写出下图所示完全二叉树的先序、中序、后序序列：12/11/2习题： 二叉树的结构声明如下，写出实现二叉树的先序、中序、后序遍历算法。二叉树结点的结构：structtreenode{ chardata; structtreenode*lChild,*rChild;};typedefstructtreenodeTnode;12/12/202227习题：12/11/202227(1)先序遍历递归算法voidpreOrder(TNode*t){ //略}(2)中序遍历递归算法voidinOrder(TNode*t){ //略}(3)后序遍历递归算法voidpostOrder(TNode*t){ //略}12/12/202228(1)先序遍历递归算法12/11/202228（五）线索二叉树线索：指向前驱或后继结点的指针称为线索。线索二叉树：加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树。对二叉树进行某种形式遍历使其变为线索二叉树的过程叫线索化，在遍历过程中，用线索取代空指针即可。添加线索的方法：首先要确定是何种“序”的线索化（先序、中序还是后序），只有空指针处才能加线索。结点无左孩子时，添加左线索，指向结点的前驱；结点无右孩子时，添加右线索，指向结点的后继。习题：教材P1715.2612/12/202229（五）线索二叉树线索：指向前驱或后继结点的指针称为线索。12（六）哈夫曼树哈夫曼树：又称最优二叉树，是带权路径最短的树。树的带权路径长度：树中所有叶子结点的带权路径长度之和。哈夫曼树的构造方法：（1）根据给定的n个权值{w1,w2,...,wn}构造n棵二叉树的集合F={T1,T2,...,Tn}；

（2）在F中选取两棵根结点的权值为最小的树作为左、右子树以构造一棵新的二叉树；

（3）将新的二叉树加入到F中，删除原两棵根结点权值最小的树；

（4）重复（2）和（3）直到F中只含一棵树为止，这棵树就是哈夫曼树。

习题：教材P1725.3212/12/202230（六）哈夫曼树哈夫曼树：又称最优二叉树，是带权路径最短的树。习题：1．在一棵具有五层的满二叉树中，结点总数为（）。A）31B）32C）33D）162．在一棵二叉树中，第5层上的结点数最多为（）。A）8B）15C）16D）323．将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为（）。A）99B）98C）50D）484．将含100个结点的完全二叉树从根这一层开始，按从上到下从左到右依次对结点编号，根结点的编号为１。编号为50的结点X的双亲的编号为（）。A）25B）48C）100D）无法确定12/12/202231习题：12/11/2022315．已知一棵二叉树的先序遍历序列为EFHIGJK，中序遍历序列为HFIEJGK，则该二叉树根的右子树的根是_____________。6.设先序遍历某二叉树的序列为ABCD，中序遍历该二叉树的序列为BADC，则后序遍历该二叉树的序列为_____________。7．二叉树使用二叉链表存储，若p指针指向二叉树的一个结点，当p->lchild==NULL时，则（）。A）p结点左孩子为空B）p结点有右孩子C）p结点右孩子为空 D）p结点有左孩子12/12/2022325．已知一棵二叉树的先序遍历序列为EFHIGJK，中序遍历序8．哈夫曼树是访问叶结点的带权路径长度（）的二叉树。A）最短 B）最长 C）可变D）不定9．在完全二叉树中，如果一个结点是叶子结点，则它（）。A）一定没有左孩子结点，可能有右孩子结点B）一定没有右孩子结点，可能有左孩子结点C）一定没有左、右孩子结点D）一定没有左、右孩子结点和兄弟结点12/12/2022338．哈夫曼树是访问叶结点的带权路径长度（）的二叉树六、图1、图图是一种数据结构，其形式化定义可写为:G=(V,E)其中，V是顶点集合，E是边或弧的集合。结论：在具有n个顶点的有向图中，边的数目范围是0~n(n-1)，拥有n(n-1)条边的有向图称为有向完全图。在具有n个顶点的无向图中，边的数目范围是0~n(n-1)/2，拥有n(n-1)/2条边的无向图称为无向完全图。12/12/202234六、图1、图12/11/2022342、度、出度、入度无向图中，顶点的度为与每个顶点相连的边数。有向图中，顶点的度分成入度与出度：入度：以顶点v为头的弧的数目称为v的入度，记为ID(v)；出度：以顶点v为尾的弧的数目称为v的出度，记为OD(v)；顶点v的度为：TD(v)=ID(v)+OD(v)12/12/2022352、度、出度、入度12/11/202235习题：（1）在一个具有n个结点的无向图中，要连通全部结点至少需要（）。A）n条边B）n+1条边C）n-1条边D）n/2条边（2）在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）。A）1/2倍B）1倍C）2倍D）4倍（3）有n个结点的无向图的边数最多为（）。A）n-1B）n(n-1)/2C）n(n-1)D）2n(n-1)（4）有n个结点的有向图的边数最多为（）。A）n-1B）n(n-1)/2C）n(n-1)D）2n(n-1)12/12/202236习题：（1）在一个具有n个结点的无向图中，要连通全部结点至少（5）图的广度优先遍历类似于二叉树的（），深度优先遍历类似于二叉树的（）。A）先序遍历B）中序遍历C）后序遍历D）层次遍历（6）设某无向图中边数为e，所有顶点的度数之和为d，则e=_______。（7）设有向图用邻接矩阵A[n][n]作为存储结构，则该邻接矩阵中第i列上所有元素之和等于顶点i的________，第i行中所有非零元素个数之和等于顶点i的________。12/12/202237（5）图的广度优先遍历类似于二叉树的（），深3、连通、连通图连通：在无向图G中，如果从顶点v到顶点v'有路径，则称v和v'是连通的。连通图：如果对于图中任意两个顶点vi，vj∈V，vi，vj都是连通的，则称G是连通图。4、生成树、网、最小生成树生成树：一个连通图的生成树是一个极小连通子图，它含有图的全部顶点，但只有足以构成一棵树的n-1条边。网：边带权的图称网。最小生成树：最小生成树指的是（）。A）由连通图所得到的边数最少的生成树B）由连通图所得到的顶点相对较少的生成树C）连通图的所有生成树中边上的权值之和最小的生成树D）连通图的极小连通子图12/12/2022383、连通、连通图12/11/202238由无向连通图构造最小生成树的方法：（1）从图中任意顶点开始，将其包括在最小生成树中；（2）再选取权值最小的边，使其一个顶点已在生成树中，而另一个顶点尚不在生成树中，将该顶点加入生成树。（3）重复上步，直至所有顶点都包括在生成树中。这就是最小生成树。12/12/202239由无向连通图构造最小生成树的方法：12/11/202239Prim算法的基本思想：设N=(V，E)是连通网，T=(V，E‘)是正在构造中的生成树。（1）初始状态时，这棵生成树只有一个结点，没有边，即：U={u0}，E’={}，u0是任意选定的顶点；（2）在所有u∈U，v∈V-U的边(u，v)中找一条代价最小的边(u’，v’)并入集合E’，同时v’并入集合U；（3）重复（2），直到V=U为止。此时，E’中必含有n-1条边，则T=（V，E’）为N的最小生成树。习题：对P216图6.38所示的连通图，利用Prim算法构造其最小生成树。12/12/202240Prim算法的基本思想：12/11/202240Kruskal算法的基本思想：假设N=(V,E)是连通网，将N中的边按权值从小到大的顺序排列:（1）令最小生成树的初始状态为只有n个顶点而无边的非连通图T=(V，Φ)，图中每一个顶点自成一个连通分量；（2）在E中选择权最小的边。若此边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则舍去此边而选择下一条代价最小的边。（3）重复（2），直到T中所有的顶点都在同一连通分量为止。12/12/202241Kruskal算法的基本思想：12/11/202241习题：对下图所示的连通图，利用Kruskal算法构造其最小生成树。

12/12/202242习题：对下图所示的连通图，利用Kruskal算法构造其最小生七、查找1、静态查找表与动态查找表静态查找表与动态查找表二者的根本差别在于（）。A）它们的逻辑结构不一样 B）施加在其上的操作不同C）所包含的数据元素的类型不一样D）存储实现不一样静态查找表只能“查找”的操作，动态查找表还能进行插入、删除操作。有序表的的折半查找的时间效率为__________。12/12/202243七、查找1、静态查找表与动态查找表12/11/2022432、二叉排序树二叉排序树或者是一棵空树；或者是具有下列性质的二叉树： ⑴若左子树不空，则左子树上所有结点的值均小于根结点的值； 若右子树不空，则右子树上所有结点的值均大于根结点的值。 ⑵左右子树也都是二叉排序树。对二叉排序树进行中序遍历，可得到一个按关键字有序的序列（从小到大的序列）。12/12/2022442、二叉排序树12/11/202244二叉排序树的生成:二叉树的生成过程是逐个插入结点的过程。插入结点原则：若二叉排序树为空，则插入结点应为新的根结点；否则，继续在其左、右子树上查找，直至某个结点的左子树或右子树为空为止，则插入结点应为该叶子结点的左孩子或右孩子。二叉排序树生成：从空树出发，经过一系列的查找、插入操作之后，可生成一棵二叉排序树。12/12/202245二叉排序树的生成:12/11/202245习题：给出关键字序列：63、90、70、55、67、42、98、83、10、45、58，构造一颗二叉排序树。12/12/202246习题：给出关键字序列：63、90、70、55、67、42、93、哈希表哈希表是一种特殊的“查找表”，在哈希表中，依据关键字能直接得到其对应的数据元素位置，即在记录的关键字与记录的存储地址之间建立了一一对应关系。这是由哈希函数来实现的。采用哈希表查找法需要解决的两个问题是：_____和____。例题：P2427.1212/12/2022473、哈希表12/11/202247习题：（1）设哈希表长m=14，哈希函数H(key)=key%11。表中已有4个结点：addr(15)=4，addr(38)=5，addr(61)=6，addr(84)=7其余地址为空，如用二次探测处理冲突，关键字为49的结点的地址是_______。（2）若根据查找表建立长度为m的哈希表，采用线性探测法处理冲突，假定对一个元素第一次计算的哈希地址为d，则下一次的哈希地址为(

)。A）d

B）(d+1)%m

C）(d+1)/m

D）d+112/12/202248习题：12/11/202248八、排序1、稳定的排序方法：直接插入排序、二路归并排序、冒泡排序；

不稳定的排序方法：堆排序、快速排序、直接选择排序、希尔排序。2、在排序算法中，每次从未排序的记录中挑出最小（或最大）关键字的记录，加入到已排序记录的末尾，该排序方法是（）。A.选择排序B.冒泡排序C.插入排序D.堆排序12/12/202249八、排序1、稳定的排序方法：12/11/2022493、冒泡排序的算法思想、冒泡排序的过程状态：P253-254习题：若用冒泡排序方法对序列{10,14,26,29,41,52}从大到小排序，需进行（）次比较。A）3B）10C）15D）254、快速排序的算法思想、快速排序的过程状态：P255-25612/12/2022503、冒泡排序的算法思想、冒泡排序的过程状态：P253-254一、绪论

（一）数据结构的研究对象：数据结构的研究对象包括：数据的各种逻辑结构和存储结构以及对数据的各种操作。（二）算法的五个特征：有穷性、确定性、可行性、输入、输出。（三）算法的时间复杂度：T(n)=O(f(n))T（n）叫算法的渐进时间复杂度，简称时间复杂度，O为数量级。12/12/202251一、绪论（一）数据结构的研究对象：12/11/20221习题：1、写出下列算法的时间复杂度。（1）for(i=0;i<n;i++)c[i]=i；（2）for(i=0;i<m;i++)for(j=0;j<n;j++)a[i][j]=i*j；2、数据结构的研究对象包括（）。3、从逻辑上可以把数据结构分为（）和（）两种类型。12/12/202252习题：12/11/20222二、线性表（一）顺序表：12/12/202253二、线性表（一）顺序表：12/11/20223顺序表的存储结构：

#defineMaxsizemaxlentypedefintelemtype;typedefstruct{elemtypev[Maxsize];intlen;}sqlist;12/12/202254顺序表的存储结构：#defineMaxsizemaxl习题：给出顺序表的结构定义，在顺序表List中元素数组下标位置i插入一个元素x。#defineMAXSIZE100structlist//顺序表结构{intv[MAXSIZE];//元素数组

intlen;//顺序表当前包含的元素个数};typedefstructlistList;intinsert(List*L,inti,intx){//略}12/12/202255习题：给出顺序表的结构定义，在顺序表List中元素数组下标位（二）单链表每个结点包括两个域:数据域、指针域。单链表存储结构：typedefstructnode{elemtypedata;structnode*next;}Lnode，*linklist;12/12/202256（二）单链表12/11/20226习题：给出单链表的结构定义，编写函数实现链表的插入和删除操作。structlinknode//单链表结点结构{intdata;//结点数据

structlinknode*next;//后继结点指针};typedefstructlinknodeLnode;（1）在结点p之后插入值为x的新节点svoidinsert(Lnode*p,intx;) { }（2）将结点p的后继结点删除，并释放结点空间voiddelete(Lnode*p){}12/12/202257习题：给出单链表的结构定义，编写函数实现链表的插入和删除操作（三）单循环链表：使单链表的最后一个节点的指针域的值不为NULL,而是指向头结点。这样，整个链表就形成了一个环，这种链表称为单循环链表。12/12/202258（三）单循环链表：12/11/20228习题：1．线性表若采用链式存储结构时，要求内存中可用存储单元的地址（

）。A）必须是连续的

B）部分地址必须是连续的C）一定是不连续的

D）连续或不连续都可以2．链表不具备的特点是（）。A）插入和删除不需要移动元素B）可随机访问任一节点C）不必预分配空间D）所需空间与其长度成正比12/12/202259习题：12/11/202293.不带头结点的单链表head为空的判定条件是（）。A）head==NULLB）head—>next==NULLC）head—>next==headD）head!=NULL4．带头结点的单链表head为空的判定条件是（）。A）head==NULLB）head—>next==NULLC）head—>next==headD）head!=NULL5．带头结点的循环单链表head为空的判定条件是（）。A）head==NULLB）head—>next==NULLC）head—>next==headD）head!=NULL12/12/2022603.不带头结点的单链表head为空的判定条件是（）。6．在单链表中，指针p指向元素为x的结点，实现“删除x的后继”的语句是(

)。A）p=p->next;

B）p->next=p->next->next;C）p->next=p;

D）p=p->next->next;7．在长度为n的顺序表的第i(1≤i≤n+1)个位置上插入一个元素，元素的移动次数为__________。12/12/2022616．在单链表中，指针p指向元素为x的结点，实现“删除x的后继三、栈和队列（一）栈栈(Stack)是限制仅在表的一端进行插入和删除操作的线性表。栈又称为后进先出的线性表，简称LIFO线性表。顺序栈的顺序存储结构：#definemaxsize100//栈的最大容量typedefstruct{elemtpelem[maxsize];inttop;}sqstacktp;12/12/202262三、栈和队列（一）栈12/11/202212（二）队列队列（queue)是限定只能在表的一端进行插入，在表的另一端进行删除的线性表。队尾(rear)——允许插入的一端；队头(front)——允许删除的一端。队列特点：先进先出(FIFO)或后进后出(LILO)。

12/12/202263（二）队列12/11/202213顺序队列的存储结构：#definemaxsize100typedefstruct{elemtpelem[maxsize];intrear,front;}squeuetp；rear指示队尾元素；front指示队头元素前一位置。12/12/202264顺序队列的存储结构：12/11/202214循环队列：把队列设想成环形。为了区分队空、队满状态，少用一个元素空间：front所指单元不放元素。队空：sq.front==sq.rear队满：(sq.rear+1)%M==sq.front12/12/202265循环队列：把队列设想成环形。12/11/202215习题：1．栈是限定在（

）处进行插入或删除操作的线性表。

A）端点

B）栈底

C）栈顶

D）中间2．栈的特点是（

）。

A）先进先出

B）后进先出

C）后进后出

D）不进不出3．顺序栈存储空间的实现使用（

）存储栈元素。

A）链表

B）数组

C）循环链表

D）变量12/12/202266习题：12/11/2022164．顺序栈是空栈的条件是（

）。

A）top==0

B）top==1

C）top==-1

D）top==m5．元素A、B、C、D依次进顺序栈后，栈底元素是（

）。

A）A

B）B

C）C

D）D6．队列是限定在（

）处进行删除操作的线性表。

A）端点

B）队头

C）队尾

D）中间12/12/2022674．顺序栈是空栈的条件是（

）。12/11/202217．队列的特点是（

）。

A）先进先出

B）后进先出

C）先进后出

D）不进不出8．容量是10的循环队的头指针的位置Sq->front为2，则队头元素的位置是（

）。

A）3

B）2

C）1

D）09．循环队列Sq是空队列的条件是（

）。A）Sq-﹥rear==Sq-﹥front

B）(Sq-﹥rear+1)%maxsize==Sq-﹥frontC）Sq-﹥rear==0

D）Sq-﹥front==012/12/2022687．队列的特点是（

）。12/11/20221810．循环队列Sq是满队列的条件是（

）。A）Sq-﹥rear==Sq-﹥front

B）(Sq-﹥rear+1)%maxsize==Sq-﹥frontC）Sq-﹥rear==0

D）Sq-﹥front==011．存放循环队列Sq元素的数组data有10个元素，Sq-﹥front为9，队头元素的位置在（

）。

A）10

B）9

C）1

D）012/12/20226910．循环队列Sq是满队列的条件是（

）。12/11/12用一维数组设计栈，初态是栈空，top=0。现有输入序列是a、b、c、d，经过push、push、pop、push、pop、push、pop、pop操作后，输出序列是__________。13设将a,b,c,d依次入栈,则执行push(a),pop(),push(b),push(c),pop(),pop(),push(d),pop(),则出栈序列是________。

12/12/20227012用一维数组设计栈，初态是栈空，top=0。现有输入序列五、树（一）树的基本概念结点的度——结点拥有的子树数。叶子——度为0的结点，也叫终端结点。分支结点——度不为0的结点，也叫非终端结点。内部结点——除根结点之外，分支结点也称为内部结点。树的度——一棵树中最大的结点度数。孩子——结点子树的根称为该结点的孩子。双亲——孩子结点的上层结点叫该结点的双亲。兄弟——同一双亲的孩子之间互成为兄弟。12/12/202271五、树（一）树的基本概念12/11/202221（二）二叉树的概念和性质二叉树——二叉树是结点的有限集合，这个集合或者是空的，或者由一个根结点或两棵互不相交的称为左子树的和右子树的二叉树组成。满二叉树——深度为k的满二叉树，是由２k－１个结点的深度为K的二叉树。２k-１个结点是二叉树所具有的最大结点个数。完全二叉树——具有n个结点、深度为K的二叉树，当且仅当其所有结点对应于深度为k的满二叉树中编号由1到n的那些结点时，该二叉树便是完全二叉树。12/12/202272（二）二叉树的概念和性质12/11/202222二叉树的性质：性质1在二叉树第i层上至多有２i-1个结点（i≥1）。性质2深度为k的二叉树至多有２k-1个结点（k≥1）。性质3包含n(n>0)个结点的二叉树的分支边数为n-1。性质4对任何一颗二叉树T，如果其终端结点（叶子结点）数为n0，度为2的结点数为n2,则n0=n2+1。12/12/202273二叉树的性质：12/11/202223（三）二叉树的链式存储结构二叉链表的类型定义：structbnodept{datatypedata;structbnodept*lchild,*rchild};typedefstructbnodept*bitreptr;12/12/202274（三）二叉树的链式存储结构二叉链表的类型定义：12/11/2（四）二叉树的三种递归遍历算法遍历：是按一定的规则和次序走遍二叉树的所有结点，使每个结点都被访问一次，而且只被访问一次。遍历二叉树的目的：得到二叉树中各结点的一种线性顺序，使非线性的二叉树线性化。三种递归遍历算法：（1）先根序遍历（2）中根序遍历（3）后根序遍历12/12/202275（四）二叉树的三种递归遍历算法遍历：是按一定的规则和次序走遍写出下图所示完全二叉树的先序、中序、后序序列：12/12/202276写出下图所示完全二叉树的先序、中序、后序序列：12/11/2习题： 二叉树的结构声明如下，写出实现二叉树的先序、中序、后序遍历算法。二叉树结点的结构：structtreenode{ chardata; structtreenode*lChild,*rChild;};typedefstructtreenodeTnode;12/12/202277习题：12/11/202227(1)先序遍历递归算法voidpreOrder(TNode*t){ //略}(2)中序遍历递归算法voidinOrder(TNode*t){ //略}(3)后序遍历递归算法voidpostOrder(TNode*t){ //略}12/12/202278(1)先序遍历递归算法12/11/202228（五）线索二叉树线索：指向前驱或后继结点的指针称为线索。线索二叉树：加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树。对二叉树进行某种形式遍历使其变为线索二叉树的过程叫线索化，在遍历过程中，用线索取代空指针即可。添加线索的方法：首先要确定是何种“序”的线索化（先序、中序还是后序），只有空指针处才能加线索。结点无左孩子时，添加左线索，指向结点的前驱；结点无右孩子时，添加右线索，指向结点的后继。习题：教材P1715.2612/12/202279（五）线索二叉树线索：指向前驱或后继结点的指针称为线索。12（六）哈夫曼树哈夫曼树：又称最优二叉树，是带权路径最短的树。树的带权路径长度：树中所有叶子结点的带权路径长度之和。哈夫曼树的构造方法：（1）根据给定的n个权值{w1,w2,...,wn}构造n棵二叉树的集合F={T1,T2,...,Tn}；

（2）在F中选取两棵根结点的权值为最小的树作为左、右子树以构造一棵新的二叉树；

（3）将新的二叉树加入到F中，删除原两棵根结点权值最小的树；

（4）重复（2）和（3）直到F中只含一棵树为止，这棵树就是哈夫曼树。

习题：教材P1725.3212/12/202280（六）哈夫曼树哈夫曼树：又称最优二叉树，是带权路径最短的树。习题：1．在一棵具有五层的满二叉树中，结点总数为（）。A）31B）32C）33D）162．在一棵二叉树中，第5层上的结点数最多为（）。A）8B）15C）16D）323．将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为（）。A）99B）98C）50D）484．将含100个结点的完全二叉树从根这一层开始，按从上到下从左到右依次对结点编号，根结点的编号为１。编号为50的结点X的双亲的编号为（）。A）25B）48C）100D）无法确定12/12/202281习题：12/11/2022315．已知一棵二叉树的先序遍历序列为EFHIGJK，中序遍历序列为HFIEJGK，则该二叉树根的右子树的根是_____________。6.设先序遍历某二叉树的序列为ABCD，中序遍历该二叉树的序列为BADC，则后序遍历该二叉树的序列为_____________。7．二叉树使用二叉链表存储，若p指针指向二叉树的一个结点，当p->lchild==NULL时，则（）。A）p结点左孩子为空B）p结点有右孩子C）p结点右孩子为空 D）p结点有左孩子12/12/2022825．已知一棵二叉树的先序遍历序列为EFHIGJK，中序遍历序8．哈夫曼树是访问叶结点的带权路径长度（）的二叉树。A）最短 B）最长 C）可变D）不定9．在完全二叉树中，如果一个结点是叶子结点，则它（）。A）一定没有左孩子结点，可能有右孩子结点B）一定没有右孩子结点，可能有左孩子结点C）一定没有左、右孩子结点D）一定没有左、右孩子结点和兄弟结点12/12/2022838．哈夫曼树是访问叶结点的带权路径长度（）的二叉树六、图1、图图是一种数据结构，其形式化定义可写为:G=(V,E)其中，V是顶点集合，E是边或弧的集合。结论：在具有n个顶点的有向图中，边的数目范围是0~n(n-1)，拥有n(n-1)条边的有向图称为有向完全图。在具有n个顶点的无向图中，边的数目范围是0~n(n-1)/2，拥有n(n-1)/2条边的无向图称为无向完全图。12/12/202284六、图1、图12/11/2022342、度、出度、入度无向图中，顶点的度为与每个顶点相连的边数。有向图中，顶点的度分成入度与出度：入度：以顶点v为头的弧的数目称为v的入度，记为ID(v)；出度：以顶点v为尾的弧的数目称为v的出度，记为OD(v)；顶点v的度为：TD(v)=ID(v)+OD(v)12/12/2022852、度、出度、入度12/11/202235习题：（1）在一个具有n个结点的无向图中，要连通全部结点至少需要（）。A）n条边B）n+1条边C）n-1条边D）n/2条边（2）在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）。A）1/2倍B）1倍C）2倍D）4倍（3）有n个结点的无向图的边数最多为（）。A）n-1B）n(n-1)/2C）n(n-1)D）2n(n-1)（4）有n个结点的有向图的边数最多为（）。A）n-1B）n(n-1)/2C）n(n-1)D）2n(n-1)12/12/202286习题：（1）在一个具有n个结点的无向图中，要连通全部结点至少（5）图的广度优先遍历类似于二叉树的（），深度优先遍历类似于二叉树的（）。A）先序遍历B）中序遍历C）后序遍历D）层次遍历（6）设某无向图中边数为e，所有顶点的度数之和为d，则e=_______。（7）设有向图用邻接矩阵A[n][n]作为存储结构，则该邻接矩阵中第i列上所有元素之和等于顶点i的________，第i行中所有非零元素个数之和等于顶点i的________。12/12/202287（5）图的广度优先遍历类似于二叉树的（），深3、连通、连通图连通：在无向图G中，如果从顶点v到顶点v'有路径，则称v和v'是连通的。连通图：如果对于图中任意两个顶点vi，vj∈V，vi，vj都是连通的，则称G是连通图。4、生成树、网、最小生成树生成树：一个连通图的生成树是一个极小连通子图，它含有图的全部顶点，但只有足以构成一棵树的n-1条边。网：边带权的图称网。最小生成树：最小生成树指的是（）。A）由连通图所得到的边数最少的生成树B）由连通图所得到的顶点相对较少的生成树C）连通图的所有生成树中边上的权值之和最小的生成树D）连通图的极小连通子图12/12/2022883、连通、连通图12/11/202238由无向连通图构造最小生成树的方法：（1）从图中任意顶点开始，将其包括在最小生成树中；（2）再选取权值最小的边，使其一个顶点已在生成树中，而另一个顶点尚不在生成树中，将该顶点加入生成树。（3）重复上步，直至所有顶点都包括