算法与数据结构复习课件.ppt

1、2022-12-271一、绪论一、绪论 n（一）数据结构的研究对象：数据结构的研究对象：n数据结构数据结构的研究对象包括：数据的各种逻辑结构和存储结构以及对数据的各种操作。n（二）算法的五个特征：（二）算法的五个特征：n有穷性、确定性、可行性、输入、输出。n（三）算法的时间复杂度：（三）算法的时间复杂度：nT(n)=O(f(n)nT（n）叫算法的渐进时间复杂度，简称时间复杂度，O为数量级。2022-12-272n习题：习题：n1、写出下列算法的时间复杂度写出下列算法的时间复杂度。n（1）for(i=0;in;i+)n ci=i；n（2）for(i=0;im;i+)n for(j=0;jnext

2、=NULLnC）headnext=head D）head!=NULLn4带头结点的单链表带头结点的单链表head为空的判定条件是（为空的判定条件是（）。）。nA）head=NULL B）headnext=NULLnC）headnext=head D）head!=NULLn5带头结点的循环单链表带头结点的循环单链表head为空的判定条件是（为空的判定条件是（）。）。nA）head=NULL B）headnext=NULLnC）headnext=head D）head!=NULL2022-12-2711n6在单链表中，指针在单链表中，指针p指向元素为指向元素为x的结点，实现的结点，实现“删除删除x

3、的后继的后继”的语句是的语句是()。nA）p=p-next;B）p-next=p-next-next;nC）p-next=p;D）p=p-next-next;n7在长度为在长度为n的顺序表的第的顺序表的第i(1in+1)个位置上插个位置上插入一个元素，元素的移动次数为入一个元素，元素的移动次数为_。2022-12-2712三、栈和队列n（一）栈（一）栈n栈栈(Stack)是限制仅在表的一端进行插入和删除操作的线是限制仅在表的一端进行插入和删除操作的线性表。栈又称为后进先出的线性表，简称性表。栈又称为后进先出的线性表，简称LIFO线性表线性表。n顺序栈的顺序存储结构：顺序栈的顺序存储结构：n#d

4、efine maxsize 100/栈的最大容量栈的最大容量ntypedef structnn elemtp elemmaxsize;n int top;n sqstacktp;2022-12-2713n（二）队列（二）队列n队列（队列（queue)queue)是限定只能在表的一端进行插入，在是限定只能在表的一端进行插入，在表的另一端进行删除的线性表。表的另一端进行删除的线性表。n队尾队尾(rear)(rear)允许插入的一端；允许插入的一端；n队头队头(front)(front)允许删除的一端。允许删除的一端。n队列特点：先进先出队列特点：先进先出(FIFO)(FIFO)或后进后出或后进后出

5、(LILO)(LILO)。2022-12-2714n顺序队列的存储结构：顺序队列的存储结构：n#define maxsize 100n typedef structn n elemtp elemmaxsize;n int rear,front;n squeuetp；nrear指示队尾元素；指示队尾元素；nfront指示队头元素前一位置。指示队头元素前一位置。2022-12-2715n循环队列：循环队列：把队列设想成环形。把队列设想成环形。n为了区分队空、队满状态，少用一个元素空间：为了区分队空、队满状态，少用一个元素空间：frontfront所指单元不放元素。所指单元不放元素。n队空：队空：s

6、q.front=sq.rearsq.front=sq.rearn队满：队满：(sq.rear+1)%M=sq.front(sq.rear+1)%M=sq.front2022-12-2716n习题：习题：n1栈是限定在（栈是限定在（）处进行插入或删除操作的线性表。）处进行插入或删除操作的线性表。n A）端点）端点 B）栈底）栈底 C）栈顶）栈顶 D）中间）中间n2栈的特点是（栈的特点是（）。）。n A）先进先出）先进先出 B）后进先出）后进先出 n C）后进后出）后进后出 D）不进不出）不进不出n3顺序栈存储空间的实现使用（顺序栈存储空间的实现使用（）存储栈元素。）存储栈元素。n A）链表）链表

7、 B）数组）数组 C）循环链表）循环链表 D）变量）变量 2022-12-2717n4顺序栈是空栈的条件是（顺序栈是空栈的条件是（）。）。n A）top=0 B）top=1 n C）top=-1 D）top=mn5元素元素A、B、C、D依次进顺序栈后，栈底元素是依次进顺序栈后，栈底元素是（）。）。n A）A B）B C）C D）Dn6队列是限定在（队列是限定在（）处进行删除操作的线性表。）处进行删除操作的线性表。n A）端点）端点 B）队头）队头 C）队尾）队尾 D）中间）中间2022-12-2718n7队列的特点是（队列的特点是（）。）。n A）先进先出）先进先出 B）后进先出）后进先出 n

8、 C）先进后出）先进后出 D）不进不出）不进不出n8容量是容量是10的循环队的头指针的位置的循环队的头指针的位置Sq-front为为2，则，则队头元素的位置是（队头元素的位置是（）。）。n A）3 B）2 C）1 D）0n9循环队列循环队列Sq是空队列的条件是（是空队列的条件是（）。）。nA）Sq-rear=Sq-front nB）(Sq-rear+1)%maxsize=Sq-frontnC）Sq-rear=0 nD）Sq-front=02022-12-2719n10循环队列循环队列Sq是满队列的条件是（是满队列的条件是（）。）。nA）Sq-rear=Sq-front nB）(Sq-rear+

9、1)%maxsize=Sq-frontnC）Sq-rear=0 nD）Sq-front=0n11存放循环队列存放循环队列Sq元素的数组元素的数组data有有10个元素，个元素，nSq-front为为9，队头元素的位置在（，队头元素的位置在（）。）。n A）10 B）9 C）1 D）0 2022-12-2720n12 用一维数组设计栈，初态是栈空，用一维数组设计栈，初态是栈空，top=0。现有。现有输入序列是输入序列是 a、b、c、d，经过，经过 push、push、pop、push、pop、push、pop、pop操作后，输出序列是操作后，输出序列是_。n13 设将设将a,b,c,d依次入栈依

10、次入栈,则执行则执行push(a),pop(),push(b),push(c),pop(),pop(),push(d),pop(),则出则出栈序列是栈序列是_。2022-12-2721五、树五、树n（一）树的基本概念（一）树的基本概念n结点的度结点的度结点拥有的子树数。结点拥有的子树数。n叶子叶子度为度为0 0的结点，也叫终端结点。的结点，也叫终端结点。n分支结点分支结点度不为度不为0 0的结点，也叫非终端结点。的结点，也叫非终端结点。n内部结点内部结点除根结点之外，分支结点也称为内部结点。除根结点之外，分支结点也称为内部结点。n树的度树的度一棵树中最大的结点度数。一棵树中最大的结点度数。n孩

11、子孩子结点子树的根称为该结点的孩子。结点子树的根称为该结点的孩子。n双亲双亲孩子结点的上层结点叫该结点的双亲。孩子结点的上层结点叫该结点的双亲。n兄弟兄弟同一双亲的孩子之间互成为兄弟。同一双亲的孩子之间互成为兄弟。2022-12-2722n（二）二叉树的概念和性质（二）二叉树的概念和性质n二叉树二叉树二叉树是结点的有限集合，这个集合二叉树是结点的有限集合，这个集合或者是空的，或者由一个根结点或两棵互不相交或者是空的，或者由一个根结点或两棵互不相交的称为左子树的和右子树的二叉树组成。的称为左子树的和右子树的二叉树组成。n满二叉树满二叉树深度为深度为k的满二叉树，是由的满二叉树，是由k 个结点的深

12、度为个结点的深度为K的二叉树。的二叉树。k-个结点是个结点是二叉树所具有的最大结点个数。二叉树所具有的最大结点个数。n完全二叉树完全二叉树具有具有n个结点、深度为个结点、深度为K的二叉树，的二叉树，当且仅当其所有结点对应于深度为当且仅当其所有结点对应于深度为k的满二叉树的满二叉树中编号由中编号由1到到n的那些结点时，该二叉树便是完全的那些结点时，该二叉树便是完全二叉树。二叉树。2022-12-2723n二叉树的性质：二叉树的性质：n性质性质1 在二叉树第在二叉树第i层上至多有层上至多有i-1 个结点个结点（i1）。）。n性质性质2 深度为深度为k的二叉树至多有的二叉树至多有k-1个结点个结点（

13、k1）。）。n性质性质3 包含包含n(n0)个结点的二叉树的分支边数为个结点的二叉树的分支边数为n-1。n性质性质4 对任何一颗二叉树对任何一颗二叉树T，如果其终端结点，如果其终端结点（叶子结点）数为（叶子结点）数为n0，度为，度为2的结点数为的结点数为n2,则则n0=n2+1。2022-12-2724（三）二叉树的链式存储结构（三）二叉树的链式存储结构PARENTLCHILDRCHILDLCHILD DATARCHILDLCHILD DATA PARENTRCHILD(a)(b)(c)二叉链表的类型定义：二叉链表的类型定义：struct bnodept datatype data;struc

14、t bnodept*lchild,*rchild;typedef struct bnodept*bitreptr;2022-12-2725（四）二叉树的三种递归遍历算法（四）二叉树的三种递归遍历算法n遍历遍历：是按一定的规则和次序走遍二叉树的所有结：是按一定的规则和次序走遍二叉树的所有结点，使每个结点都被访问一次，而且只被访问一次。点，使每个结点都被访问一次，而且只被访问一次。n遍历二叉树的目的：得到二叉树中各结点的一种线遍历二叉树的目的：得到二叉树中各结点的一种线性顺序，使非线性的二叉树线性化。性顺序，使非线性的二叉树线性化。n三种递归遍历算法：三种递归遍历算法：n（1 1）先根序遍历）先根

15、序遍历n（2 2）中根序遍历）中根序遍历n（3 3）后根序遍历）后根序遍历2022-12-2726写出下图所示完全二叉树的先序、中序、后序序列：写出下图所示完全二叉树的先序、中序、后序序列：2022-12-2727n习题：习题：n二叉树的结构声明如下，写出实现二叉树二叉树的结构声明如下，写出实现二叉树的先序、中序、后序遍历算法。的先序、中序、后序遍历算法。n二叉树结点的结构：二叉树结点的结构：nstruct treenodennchar data;nstruct treenode*lChild,*rChild;n;ntypedef struct treenode Tnode;2022-12-2

16、728n(1)先序遍历递归算法先序遍历递归算法nvoid preOrder(TNode*t)nn/略略nn(2)中序遍历递归算法中序遍历递归算法nvoid inOrder(TNode*t)nn/略略nn(3)后序遍历递归算法后序遍历递归算法nvoid postOrder(TNode*t)nn/略略n2022-12-2729（五）线索二叉树线索二叉树n线索线索：指向前驱或后继结点的指针称为线索。：指向前驱或后继结点的指针称为线索。n线索二叉树线索二叉树：加上了线索的二叉链表称为线索链：加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树。表，相应的二叉树称为线索二叉树。n对二叉树进行某种

17、形式遍历使其变为线索二叉树对二叉树进行某种形式遍历使其变为线索二叉树的过程叫的过程叫线索化线索化，在遍历过程中，用线索取代空，在遍历过程中，用线索取代空指针即可。指针即可。n添加线索的方法添加线索的方法：首先要确定是何种：首先要确定是何种“序序”的线的线索化（先序、中序还是后序），只有空指针处才索化（先序、中序还是后序），只有空指针处才能加线索。结点无左孩子时，添加左线索，指向能加线索。结点无左孩子时，添加左线索，指向结点的前驱；结点无右孩子时，添加右线索，指结点的前驱；结点无右孩子时，添加右线索，指向结点的后继。向结点的后继。n习题习题：教材：教材P171 5.26P171 5.262022

18、-12-2730（六）哈夫曼树（六）哈夫曼树n哈夫曼树：哈夫曼树：又称最优二叉树，是带权路径最短的树。又称最优二叉树，是带权路径最短的树。n树的带权路径长度：树的带权路径长度：树中所有叶子结点的带权路径树中所有叶子结点的带权路径长度之和。长度之和。n哈夫曼树的构造方法：哈夫曼树的构造方法：n（1）根据给定的）根据给定的n个权值个权值w1,w2,.,wn构造构造n棵二棵二叉树的集合叉树的集合F=T1,T2,.,Tn；（2）在）在F中选取两棵根结点的权值为最小的树作为中选取两棵根结点的权值为最小的树作为左、右子树以构造一棵新的二叉树；左、右子树以构造一棵新的二叉树；（3）将新的二叉树加入到）将新的

19、二叉树加入到F中，删除原两棵根结中，删除原两棵根结点权值最小的树；点权值最小的树；（4）重复（）重复（2）和（）和（3）直到）直到F中只含一棵树为止，中只含一棵树为止，这棵树就是哈夫曼树。这棵树就是哈夫曼树。n 习题：习题：教材教材P172 5.322022-12-2731n习题：习题：n1在一棵具有五层的满二叉树中，结点总数为（在一棵具有五层的满二叉树中，结点总数为（）。）。n A）31 B）32 C）33 D）16n2在一棵二叉树中，第在一棵二叉树中，第5层上的结点数最多为（层上的结点数最多为（）。）。n A）8 B）15 C）16 D）32n3将一棵有将一棵有100个结点的完全二叉树从上

20、到下，从左到右个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为依次对结点进行编号，根结点的编号为1，则编号为，则编号为49的结的结点的左孩子编号为（点的左孩子编号为（）。）。n A）99 B）98 C）50 D）48n4将含将含100个结点的完全二叉树从根这一层开始，按从上个结点的完全二叉树从根这一层开始，按从上到下从左到右依次对结点编号，根结点的编号为。编号到下从左到右依次对结点编号，根结点的编号为。编号为为50的结点的结点X的双亲的编号为（的双亲的编号为（）。）。nA）25 B）48 C）100 D）无法确定）无法确定2022-12-2732n5已知一棵二叉树的先序遍

21、历序列为已知一棵二叉树的先序遍历序列为EFHIGJK，中序遍历序列为中序遍历序列为HFIEJGK，则该二叉树根的右，则该二叉树根的右子树的根是子树的根是_。n6.设先序遍历某二叉树的序列为设先序遍历某二叉树的序列为ABCD，中序遍，中序遍历该二叉树的序列为历该二叉树的序列为BADC，则后序遍历该二叉，则后序遍历该二叉树的序列为树的序列为_。n7二叉树使用二叉链表存储，若二叉树使用二叉链表存储，若p指针指向二叉指针指向二叉树的一个结点，当树的一个结点，当p-lchild=NULL时，则时，则（）。）。nA）p结点左孩子为空结点左孩子为空 B）p结点有右孩子结点有右孩子nC）p结点右孩子为空结点右

22、孩子为空 D）p结点有左孩子结点有左孩子2022-12-2733n8哈夫曼树是访问叶结点的带权路径长度（哈夫曼树是访问叶结点的带权路径长度（）的二叉树。的二叉树。nA）最短）最短 B）最长）最长 C）可变）可变 D）不定）不定n9在完全二叉树中，如果一个结点是叶子结点，在完全二叉树中，如果一个结点是叶子结点，则它（则它（）。）。nA）一定没有左孩子结点，可能有右孩子结点）一定没有左孩子结点，可能有右孩子结点 nB）一定没有右孩子结点，可能有左孩子结点）一定没有右孩子结点，可能有左孩子结点nC）一定没有左、右孩子结点）一定没有左、右孩子结点 nD）一定没有左、右孩子结点和兄弟结点）一定没有左、右

23、孩子结点和兄弟结点2022-12-2734六、图六、图n1、图、图n 图是一种数据结构，其形式化定义可写为图是一种数据结构，其形式化定义可写为:n G=(V,E)n其中，其中，V是顶点集合，是顶点集合，E是边或弧的集合。是边或弧的集合。n结论：结论：n 在具有在具有n个顶点的有向图中，边的数目范围是个顶点的有向图中，边的数目范围是0 n(n-1)，拥有，拥有n(n-1)条边的有向图称为有向完全条边的有向图称为有向完全图。图。n 在具有在具有n个顶点的无向图中，边的数目范围是个顶点的无向图中，边的数目范围是0 n(n-1)/2，拥有，拥有n(n-1)/2条边的无向图称为无向条边的无向图称为无向完

24、全图。完全图。2022-12-2735n2 2、度、出度、入度、度、出度、入度n无向图中，无向图中，顶点的度顶点的度为与每个顶点相连的边数。为与每个顶点相连的边数。n有向图中，有向图中，顶点的度顶点的度分成入度与出度：分成入度与出度：n入度入度：以顶点：以顶点v为头的弧的数目称为为头的弧的数目称为v的入度，的入度，记为记为ID(v)；n出度出度：以顶点：以顶点v为尾的弧的数目称为为尾的弧的数目称为v的出度，的出度，记为记为OD(v)；n顶点顶点v的度为：的度为：TD(v)=ID(v)+OD(v)2022-12-2736习题：习题：n（1）在一个具有）在一个具有n个结点的无向图中，要连通全部结点

25、至个结点的无向图中，要连通全部结点至少需要（少需要（）。）。n A）n条边条边 B）n+1条边条边 C）n-1条边条边 D）n/2条边条边n（2）在一个有向图中，所有顶点的入度之和等于所有顶点）在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（的出度之和的（）。）。n A）1/2倍倍 B）1倍倍 C）2倍倍 D）4倍倍n（3）有）有n个结点的无向图的边数最多为（个结点的无向图的边数最多为（）。）。n A）n-1 B）n(n-1)/2 C）n(n-1)D）2n(n-1)n（4）有）有n个结点的有向图的边数最多为（个结点的有向图的边数最多为（）。）。n A）n-1 B）n(n-1)/2

26、C）n(n-1)D）2n(n-1)2022-12-2737n（5）图的广度优先遍历类似于二叉树的（）图的广度优先遍历类似于二叉树的（），），深度优先遍历类似于二叉树的（深度优先遍历类似于二叉树的（）。）。n A）先序遍历）先序遍历 B）中序遍历）中序遍历 n C）后序遍历）后序遍历 D）层次遍历）层次遍历n（6）设某无向图中边数为）设某无向图中边数为e，所有顶点的度数之和，所有顶点的度数之和为为d，则，则e=_。n（7）设有向图用邻接矩阵）设有向图用邻接矩阵Ann作为存储结构，则作为存储结构，则该邻接矩阵中第该邻接矩阵中第i列上所有元素之和等于顶点列上所有元素之和等于顶点i的的_，第，第i行中

27、所有非零元素个数之和等于顶点行中所有非零元素个数之和等于顶点i的的_。2022-12-2738n3 3、连通、连通图、连通、连通图n连通连通：在无向图：在无向图G中，中，如果从顶点如果从顶点v到顶点到顶点v有路径，则称有路径，则称v和和v是连通的。是连通的。n连通图连通图：如果对于图中任意两个顶点：如果对于图中任意两个顶点vi，vjV，vi，vj都都是连通的，则称是连通的，则称G是连通图。是连通图。n4 4、生成树、网、最小生成树、生成树、网、最小生成树n生成树生成树：一个连通图的生成树是一个极小连通子图，它含：一个连通图的生成树是一个极小连通子图，它含有图的全部顶点，但只有足以构成一棵树的有

28、图的全部顶点，但只有足以构成一棵树的n-1条边。条边。n网网：边带权的图称网。：边带权的图称网。n最小生成树最小生成树：最小生成树指的是（：最小生成树指的是（）。）。n A）由连通图所得到的边数最少的生成树）由连通图所得到的边数最少的生成树n B）由连通图所得到的顶点相对较少的生成树）由连通图所得到的顶点相对较少的生成树n C）连通图的所有生成树中边上的权值之和最小的生成树）连通图的所有生成树中边上的权值之和最小的生成树n D）连通图的极小连通子图）连通图的极小连通子图2022-12-2739n由无向连通图构造最小生成树的方法：由无向连通图构造最小生成树的方法：n（1）从图中任意顶点开始，将其

29、包括在最小生成）从图中任意顶点开始，将其包括在最小生成树中；树中；n（2）再选取权值最小的边，使其一个顶点已在生）再选取权值最小的边，使其一个顶点已在生成树中，而另一个顶点尚不在生成树中，将该顶点成树中，而另一个顶点尚不在生成树中，将该顶点加入生成树。加入生成树。n（3）重复上步，直至所有顶点都包括在生成树中。）重复上步，直至所有顶点都包括在生成树中。这就是最小生成树。这就是最小生成树。2022-12-2740nPrim算法的基本思想：算法的基本思想：n设设N=(V，E)是连通网，是连通网，T=(V，E)是正在构造中的生成树。是正在构造中的生成树。n（1）初始状态时，）初始状态时，这棵生成树只

30、有一个结点，没有边，即：这棵生成树只有一个结点，没有边，即：U=u0，E=，u0是任意选定的顶点；是任意选定的顶点；n（2）在所有）在所有uU，vV-U的边的边(u，v)中找一条代价最小的中找一条代价最小的边边(u，v)并入集合并入集合E，同时，同时v并入集合并入集合U；n（3）重复（重复（2），），直到直到V=U为止。为止。n此时，此时，E中必含有中必含有n-1条边，则条边，则T=（V，E）为）为N的最小生的最小生成树。成树。n习题：习题：对对P216 图图6.38所示的连通图，利用所示的连通图，利用Prim算算法构造其最小生成树。法构造其最小生成树。2022-12-2741nKruskal

31、算法的基本思想：n假设假设N=(V,E)是连通网，将是连通网，将N中的边按权值从小到大的顺中的边按权值从小到大的顺序排列序排列:n （1）令最小生成树的初始状态为只有）令最小生成树的初始状态为只有n个顶点而无边个顶点而无边的非连通图的非连通图T=(V，)，图中每一个顶点自成一个连通分，图中每一个顶点自成一个连通分量；量；n（2）在）在E中选择权最小的边。若此边依附的顶点落在中选择权最小的边。若此边依附的顶点落在T中中不同的连通分量上，则将此边加入到不同的连通分量上，则将此边加入到T中，否则舍去此边中，否则舍去此边而选择下一条代价最小的边。而选择下一条代价最小的边。n（3）重复（）重复（2），直

32、到），直到T 中所有的顶点都在同一连通分量中所有的顶点都在同一连通分量为止。为止。2022-12-2742n习题：习题：对下图所示的连通图，利用对下图所示的连通图，利用Kruskal算法构算法构造其最小生成树。造其最小生成树。2022-12-2743七、查找七、查找n1、静态查找表与动态查找表静态查找表与动态查找表n静态查找表与动态查找表二者的根本差别在于（静态查找表与动态查找表二者的根本差别在于（）。nA）它们的逻辑结构不一样）它们的逻辑结构不一样 nB）施加在其上的操作不同）施加在其上的操作不同 nC）所包含的数据元素的类型不一样）所包含的数据元素的类型不一样 nD）存储实现不一样）存储实

33、现不一样n静态查找表只能静态查找表只能“查找查找”的操作，动态查找表还的操作，动态查找表还能进行插入、删除操作。能进行插入、删除操作。n 有序表的的折半查找的时间效率为有序表的的折半查找的时间效率为_。2022-12-2744n2、二叉排序树二叉排序树n二叉排序树或者是一棵空树；或者是具有下列性二叉排序树或者是一棵空树；或者是具有下列性质的二叉树：质的二叉树：n 若左子树不空，则左子树上所有结点的值若左子树不空，则左子树上所有结点的值均小于根结点的值；均小于根结点的值；n 若右子树不空，则右子树上所有结点的值若右子树不空，则右子树上所有结点的值均大于根结点的值。均大于根结点的值。n 左右子树也

34、都是二叉排序树。左右子树也都是二叉排序树。n对二叉排序树进行中序遍历，可得到一个按关键对二叉排序树进行中序遍历，可得到一个按关键字有序的序列（从小到大的序列）。字有序的序列（从小到大的序列）。2022-12-2745n二叉排序树的生成二叉排序树的生成:n二叉树的生成过程是逐个插入结点的过程。二叉树的生成过程是逐个插入结点的过程。n插入结点原则插入结点原则：若二叉排序树为空，则插入结点：若二叉排序树为空，则插入结点应为新的根结点；否则，继续在其左、右子树上应为新的根结点；否则，继续在其左、右子树上查找，直至某个结点的左子树或右子树为空为止，查找，直至某个结点的左子树或右子树为空为止，则插入结点应

35、为该叶子结点的左孩子或右孩子。则插入结点应为该叶子结点的左孩子或右孩子。n二叉排序树生成二叉排序树生成：从空树出发，经过一系列的查：从空树出发，经过一系列的查找、插入操作之后，可生成一棵二叉排序树。找、插入操作之后，可生成一棵二叉排序树。2022-12-2746n习题：习题：给出关键字序列：给出关键字序列：63、90、70、55、67、42、98、83、10、45、58，构造一颗二叉，构造一颗二叉排序树。排序树。2022-12-2747n3、哈希表、哈希表n哈希表哈希表是一种特殊的是一种特殊的“查找表查找表”，在哈希表中，在哈希表中，依据关键字能直接得到其对应的数据元素位置，依据关键字能直接得

36、到其对应的数据元素位置，即在记录的关键字与记录的存储地址之间建立了即在记录的关键字与记录的存储地址之间建立了一一对应关系。这是由哈希函数来实现的。一一对应关系。这是由哈希函数来实现的。n采用哈希表查找法需要解决的两个问题是：采用哈希表查找法需要解决的两个问题是：_和和_。n例题：例题：P242 7.122022-12-2748n 习题：习题：n（1）设哈希表长设哈希表长m=14，哈希函数，哈希函数H(key)=key%11。表中已有表中已有4个结点：个结点：addr(15)=4，addr(38)=5，addr(61)=6，addr(84)=7其余地址为空，如用二次探其余地址为空，如用二次探测处

37、理冲突，关键字为测处理冲突，关键字为49的结点的地址是的结点的地址是_。n（2）若根据查找表建立长度为若根据查找表建立长度为 m 的哈希表，采用线的哈希表，采用线性探测法处理冲突，假定对一个元素第一次计算的性探测法处理冲突，假定对一个元素第一次计算的哈希地址为哈希地址为 d，则下一次的哈希地址为，则下一次的哈希地址为()。nA）d B）(d+1)%m C）(d+1)/m D）d+12022-12-2749八、排序八、排序n1、稳定的排序方法：稳定的排序方法：n直接插入排序、二路归并排序、冒泡排序；直接插入排序、二路归并排序、冒泡排序；n 不稳定的排序方法：不稳定的排序方法：n堆排序、快速排序、

38、直接选择排序、希尔排序。堆排序、快速排序、直接选择排序、希尔排序。n 2、在排序算法中，每次从未排序的记录中挑出最、在排序算法中，每次从未排序的记录中挑出最小（或最大）关键字的记录，加入到已排序记录的小（或最大）关键字的记录，加入到已排序记录的末尾，该排序方法是（末尾，该排序方法是（）。）。nA.选择排序选择排序 B.冒泡排序冒泡排序 C.插入排序插入排序 D.堆排序堆排序2022-12-2750n3、冒泡排序的算法思想、冒泡排序的过程状态：、冒泡排序的算法思想、冒泡排序的过程状态：P253-254n习题：习题：若用冒泡排序方法对序列若用冒泡排序方法对序列10,14,26,29,41,52从大到小排序，需进行从大到小排序，需进行（）次比较。）次比较。nA）3 B）10 C）15 D）25n4、快速排序的算法思想、快速排序的过程状态：、快速排序的算法思想、快速排序的过程状态：P255-256