数据结构复习资料ppt课件

1、总复习考试类型o选择题o填空题o简答题o编程题绪论部分o数据构造中逻辑构造与物理构造的区别o时间复杂度for (i=0;in;i+) for(j=0;jnext=p-next;s-next=p-next;Step 2Step 2：p-next=s p-next=s ；p-nexts-next元素x结点应预先生成：S=(LinkList)malloc(m);S-data=x;S-next=p-next单链表的删除单链表的删除在链表中删除某元素的表示图如下：在链表中删除某元素的表示图如下：cabp删除步骤即中心语句：删除步骤即中心语句：q = p-next; /保管保管b的指针，靠它才干指向的指针

2、，靠它才干指向cp-next=q-next; /a、c两结点相连两结点相连free(q) ； /删除删除b结点，彻底释放结点，彻底释放p-next思索：思索： 省略省略free(q)free(q)语句行不行？语句行不行？(p-next) - next 1 1、填空题：、填空题： 1 1在顺序表中插入和删除一个元素，需求平均挪动在顺序表中插入和删除一个元素，需求平均挪动 个元素，详细挪动的元素个数与个元素，详细挪动的元素个数与 有关。有关。 2 2顺序表中逻辑上相邻的元素的物理位置顺序表中逻辑上相邻的元素的物理位置 紧邻。单链表中逻辑上相邻的元紧邻。单链表中逻辑上相邻的元素的物理位置素的物理位置

3、 紧邻。紧邻。 3 3在单链表中，除了首元结点外，任一结点内的存储位置由在单链表中，除了首元结点外，任一结点内的存储位置由 指示。指示。 4 4在单链表中，设置头结点的作用是在单链表中，设置头结点的作用是 。栈和队列o栈和队列的特点o栈的入栈出栈顺序设依次进入一个栈的元素序列为设依次进入一个栈的元素序列为c，a，b，d，那么可得到出栈的元素序列是：，那么可得到出栈的元素序列是： a，b，c，d c，d，a，b b，c，d，a a，c，d，bA、D可以可以 B、C不行。不行。答：答：一、数制转换一、数制转换 十进制十进制N N和其它进制数的转换是计算机实和其它进制数的转换是计算机实现计算的根本问

4、题现计算的根本问题, ,其处理方法很多其处理方法很多, ,其中一个简单其中一个简单算法基于以下原理算法基于以下原理: : N=(n div d) N=(n div d)* *d+n mod dd+n mod d ( ( 其中其中:div:div为整除运算为整除运算,mod,mod为求余运算为求余运算) ) o循环队列的操作o少运用一个元素空间o判空条件： front=rear o判满条件： (rear+1)%M=fronto入队列：rear=(rear+1)%Mo出队列： front=(front+1)%MJ4J5J6012345rearfrontJ8J7练习o一个队列的入队序列是1，2，3，

5、4，那么出队顺 序是【1】oA 4,3,2,1 B 1,2,3,4 C 1,4,3,2 D 3,2,4,1o断定一个队列QU最多MaxSize个元素为空的条件oA QUrear-QU-front=MaxSizeoB QU-rear-QU-front-1=MaxSizeoC QU-front=QU-rear D、QU-front=QU-rear+1Bczo断定一个队列QU最多MaxSize个元素为满的条件oA 、QUrear-QU-front=MaxSizeoB、 QU-rear-QU-front-1=MaxSizeoC、 QU-front=QU-rear D、QU-front=QU-rear+

6、1Ao循环顺序队列中能否可以插入下一个元素，【2】oA、与队头指针和队尾指针值有关oB、与队头指针有关，与队尾指针值无关oC、只与数组大小有关，与队头指针和队尾指针值无关oD、与曾经进展过多少次插入操作有关(rear+1)%M=front Ao判别一个循环队列QU最多元素为MaxSize)为空的条件【1】oA、QU-front=QU-rearoB、QU-front!=QU-rearoC、QU-front=(QU-rear+1)%MaxSizeoD、QU-front!=(QU-rear+1)%MaxSizeo判别一个循环队列QU最多元素为MaxSize)为空的条件【1】oA、QU-front=Q

7、U-rearoB、QU-front!=QU-rearoC、QU-front=(QU-rear+1)%MaxSizeoD、QU-front!=(QU-rear+1)%MaxSizeAC树和二叉树o性质性质1：在二叉树的第：在二叉树的第i层上至多有层上至多有2i-1个结个结点点(i1)。o深度为深度为k的二叉树至多有的二叉树至多有2k-1个结点个结点(k1o性质性质3 对任何一棵二叉树对任何一棵二叉树T，假设其终端结，假设其终端结点数为点数为n0 ，而其度为，而其度为2的结点数为的结点数为n2 , 那那么么n0=n2+1。o练习o一棵二叉树中，度为0的结点个数为n0，度为2的结点个数我10，那么n

8、0=【1】o具有具有n个结点的完全二叉树的深度为个结点的完全二叉树的深度为log2n+1。1.1.以下说法错误的选项是以下说法错误的选项是A.A.树形构造的特点是一个结点可以有多个直接前树形构造的特点是一个结点可以有多个直接前驱驱B.B.线性构造中的一个结点至多只需一个直接后继线性构造中的一个结点至多只需一个直接后继C.C.树形构造可以表达更复杂的数据树形构造可以表达更复杂的数据D.D.树是一种树是一种“分支层次构造分支层次构造E.E.任何只含一个结点的集合是一棵树任何只含一个结点的集合是一棵树2.2.以下说法正确的选项是以下说法正确的选项是A.A.任何一棵二叉树中至少有一个结点的度为任何一棵

9、二叉树中至少有一个结点的度为2 2B.B.任何一棵二叉树中每个结点的度都为任何一棵二叉树中每个结点的度都为2 2C.C.任何一棵二叉树中的度一定等于任何一棵二叉树中的度一定等于2 2D.D.任何一棵二叉树中的度可以小于任何一棵二叉树中的度可以小于2 2习题3.3.假设一棵二叉树有假设一棵二叉树有1010个度为个度为2 2的结点，的结点，5 5个度为个度为1 1的结点，那么二叉树结点总数为的结点，那么二叉树结点总数为A.9 B.26 C.15 D.A.9 B.26 C.15 D.不确不确定定4.4.一棵完全二叉树上有一棵完全二叉树上有10011001个结点，其中叶子结个结点，其中叶子结点的个数为

10、点的个数为A.250 B.500 C.254 D.505 E.A.250 B.500 C.254 D.505 E.以以上答案都不对上答案都不对5. 5. 一棵二叉树的高度为一棵二叉树的高度为h h，一切结点的度为，一切结点的度为0 0或或为为2 2，那么这棵二叉树最少有个结点，那么这棵二叉树最少有个结点A.2h B.2hA.2h B.2h1 C.2h1 C.2h1 1 D.hD.h1 1每层有两个结点o二叉树的遍历ABCDEFGIH先序遍历：先序遍历：ABDEHICFG中序遍历：中序遍历：DBHEIAFCG后序遍历：后序遍历：DHIEBFGCAo知二叉树的前序后序，中序遍历序列，求后序前序序列

11、o知二叉树的先序和中序序列如下，试构造出相应的二叉树。o 先序：ABCDEFGHIJo 中序：CDBFEAIHGJo原理：先序序列的第一个节点是根节点o 中序序列根结点处于左右子树的中o 序序列之间BCDEFCDBFEGHIJIHGJACDCDEFFEHIIHJJAGBAJECBFDGHIo树与二叉树的转换ACBDEFG连兄弟断父子转一转 AB C E D F G 二叉树转化为树二叉树转化为树 转换方法：转换方法： 1、(连祖孙连祖孙) 将结点与其左孩子的右子孙衔将结点与其左孩子的右子孙衔接；接； 2、(断父子断父子) 对于任一结点，只保管它与最对于任一结点，只保管它与最左孩子左孩子 之间的连

12、线；之间的连线； 3、(抖一抖抖一抖) 使任一结点的子树无左右之分使任一结点的子树无左右之分。 AB C E D F G ACBDEFG哈夫曼树哈夫曼树huffman)51429 7823 3111429 7823 1135887151429233581111358191429238715113581929 23148715292914871529113581923421135819234229148715295811358192342291487152958100例：知某系统在通讯时，只出现例：知某系统在通讯时，只出现C，A，S，T，B五种字符，它们出现的频率依次为五种字符，它们出现的频率依

13、次为2，4，2，3，3，试设计，试设计Huffman编码。编码。 W权权=2，4，2，3，3，叶子结点个数，叶子结点个数n=5 构造的Huffman树148464220001113301 T B A C S图o图的根本概念o图的入度和出度TDv= IDv+ ODv 普通地，假设图普通地，假设图G中有中有n个顶点，个顶点，e条边或弧，那么图中条边或弧，那么图中顶点的度与边的关系如下：顶点的度与边的关系如下：e=TD(Vi)2ni=1假设一个图有假设一个图有n个顶点和小于个顶点和小于n-1条边，那么条边，那么是非连通图。是非连通图。假设它多于假设它多于n-1条边，那么一定有环。条边，那么一定有环。

14、但是，有但是，有n-1条边的图不一定是生成树。条边的图不一定是生成树。o图的深度优先和广度优先遍历o图的prim和Kruskual最小生成树图的存储o邻接矩阵表示法邻接矩阵表示法o给出一个带权图的邻接矩阵顶点编号给出一个带权图的邻接矩阵顶点编号18，如下：，如下：074107090565036304065106039530(1)给出在该图上从顶点给出在该图上从顶点1出发进展出发进展DFS遍历的结果序列，并遍历的结果序列，并根据此判别该图能否为连通图？根据此判别该图能否为连通图？ (2)画出该图的邻接链表。画出该图的邻接链表。 (3)画出按画出按Prim算法构造的最小生成树森林。算法构造的最小生

15、成树森林。0741070905650363040651060395301237845635910647635074107090565036304065106039530v1v2v3v4v5v6v7v81234567823713812856464518237123745635910647635812335487745635o有向图的拓扑排序查找o顺序查找算法o折半查找算法o哈希表设哈希函数设哈希函数Hk=3 K mod 11，散列地址空间为，散列地址空间为010，对关键字序列，对关键字序列32,13,49,24,38,21,4,12按按下述两种处理冲突的方法构造哈希表下述两种处理冲突的方法构造哈

16、希表1线性探测再散列线性探测再散列2链地址法，并分别求出等概率下查找胜利时链地址法，并分别求出等概率下查找胜利时的平均查找长度的平均查找长度ASLsucc。例题例题散列散列地址地址012345678910关键关键字字 4 12493813243221 比较比较次数次数 1 1121212 ASLsucc =1+1+1+2+1+2+1+2/8=11/801234567 89104 321312 4921 38 24 ASLsucc =11/8ASLsucc =11/8哈希表中元素个数哈希表中元素个数哈希表的长度哈希表的长度排序o直接插入排序算法o冒泡排序算法o快速排序算法o简单排序算法n直接插入

17、排序算法描画直接插入排序算法描画 void InsertSort (int r,int length) for(i=2；i=length；+ i )if (ri ri -1) r0=ri； for(j=i-1；r0 rj；j -) rj+1=rj； rj+1=r0； 习题习题1.对一组数据对一组数据84，47，25，15，21排排序，数据的陈列次序在排序过程中的变化为序，数据的陈列次序在排序过程中的变化为184，47，25，15，212 15 ，47，25 ，84 ，21 (3) 15 ， 21 ，25 ，84 , 47 (4) 15 ， 21 ，25 ,47, 84那么采用的排序是那么采用的排序是 2.一组记录为一组记录为46,79,56,38,40,84,利利用快速排序的