《数据结构复习资料说课材料.ppt》由会员分享，可在线阅读，更多相关《数据结构复习资料说课材料.ppt（48页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构复习资料 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望考试类型o选择题o填空题o简答题o编程题绪论部分o数据结构中逻辑结构与物理结构的区别o时间复杂度for(i=0;in;i+)for(j=0;jnext=p-next;Step 2Step 2：p-next=s；p-nexts-next元素x结点应预先生成：S=(LinkList)malloc(m);S-data=x;S-next=p-next单链表的删除单链表的删除在链表中删除某元素的示意图如下：在链
2、表中删除某元素的示意图如下：cabp删除步骤（即核心语句）：删除步骤（即核心语句）：q=p-next;/保存b的指针，靠它才能指向cp-next=q-next;/a、c两结点相连两结点相连free(q)；/删除删除b结点，彻底释放结点，彻底释放p-next思考：思考：省略省略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不行）。不行）。答：答：一、数制转
4、换一、数制转换 十进制十进制N和其它进制数的转换是计算机实现和其它进制数的转换是计算机实现计算的基本问题计算的基本问题,其解决方法很多其解决方法很多,其中一个简单算其中一个简单算法基于下列原理法基于下列原理:N=(n div d)*d+n mod d (其中其中:div为整除运算为整除运算,mod为求余运算为求余运算)o循环队列的操作o少使用一个元素空间判空条件：front=rear 判满条件：(rear+1)%M=front入队列：入队列：rear=(rear+1)%M出队列：出队列：front=(front+1)%MJ4J5J6012345rearfrontJ8J7练习o一个队列的入队序列
5、是1，2，3，4，则出队顺 序是【1】A 4,3,2,1 B 1,2,3,4 C 1,4,3,2 D 3,2,4,1o判定一个队列QU（最多MaxSize个元素）为空的条件A QUrear-QU-front=MaxSizeB QU-rear-QU-front-1=MaxSizeC QU-front=QU-rear D、QU-front=QU-rear+1Bczo判定一个队列QU（最多MaxSize个元素）为满的条件A、QUrear-QU-front=MaxSizeB、QU-rear-QU-front-1=MaxSizeC、QU-front=QU-rear D、QU-front=QU-rear+
6、1Ao循环顺序队列中是否可以插入下一个元素，【2】A、与队头指针和队尾指针值有关B、与队头指针有关，与队尾指针值无关C、只与数组大小有关，与队头指针和队尾指针值无关D、与曾经进行过多少次插入操作有关(rear+1)%M=front Ao判断一个循环队列QU（最多元素为MaxSize)为空的条件【1】A、QU-front=QU-rearB、QU-front!=QU-rearC、QU-front=(QU-rear+1)%MaxSizeD、QU-front!=(QU-rear+1)%MaxSizeo判断一个循环队列QU（最多元素为MaxSize)为空的条件【1】A、QU-front=QU-rearB
7、、QU-front!=QU-rearC、QU-front=(QU-rear+1)%MaxSizeD、QU-front!=(QU-rear+1)%MaxSizeAC树和二叉树o性质性质1：在二叉树的第在二叉树的第i层上至多有层上至多有2i-1个结个结点点(i1)。o深度为深度为k的二叉树至多有的二叉树至多有2k-1个结点个结点(k1）o性质3 对任何一棵二叉树T，如果其终端结点数为n0，而其度为2的结点数为n2,则n0=n2+1。o练习一棵二叉树中，度为0的结点个数为n0，度为2的结点个数我10，则n0=【1】o具有具有n个结点的完全二叉树的深度为个结点的完全二叉树的深度为 log2n+1。1.
8、1.以下说法错误的是（）以下说法错误的是（）A.A.树形结构的特点是一个结点可以有多个直接前驱树形结构的特点是一个结点可以有多个直接前驱B.B.线性结构中的一个结点至多只有一个直接后继线性结构中的一个结点至多只有一个直接后继C.C.树形结构可以表达更复杂的数据树形结构可以表达更复杂的数据D.D.树是一种树是一种“分支层次分支层次”结构结构E.E.任何只含一个结点的集合是一棵树任何只含一个结点的集合是一棵树2.2.以下说法正确的是（）以下说法正确的是（）A.A.任何一棵二叉树中至少有一个结点的度为任何一棵二叉树中至少有一个结点的度为2 2B.B.任何一棵二叉树中每个结点的度都为任何一棵二叉树中每
9、个结点的度都为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个结点，其中叶子结个结点，其中叶子结点的个数为（）点的个数为（）A.250 B.500 C.254 D.505 E.A.250 B.500
10、 C.254 D.505 E.以上答案都以上答案都不对不对5.5.一棵二叉树的高度为一棵二叉树的高度为h h，所有结点的度为，所有结点的度为0 0或或为为2 2，则这棵二叉树最少有（）个结点，则这棵二叉树最少有（）个结点A.2h B.2hA.2h B.2h1 C.2h1 C.2h1 D.h1 D.h1 1每层有两个结点o二叉树的遍历ABCDEFGIH先序遍历：先序遍历：ABDEHICFG中序遍历：中序遍历：DBHEIAFCG后序遍历：后序遍历：DHIEBFGCAo已知二叉树的前序（后序），中序遍历序列，求后序（前序）序列o已知二叉树的先序和中序序列如下，试构造出相应的二叉树。先序：ABCDEF
11、GHIJ 中序：CDBFEAIHGJ原理：先序序列的第一个节点是根节点 中序序列根结点处于左右子树的中 序序列之间BCDEFCDBFEGHIJIHGJACDCDEFFEHIIHJJAGBAJECBFDGHIo树与二叉树的转换ACBDEFG连兄弟断父子转一转ABCEDFG二叉树二叉树转化为树树转换方法：转换方法：1、(连祖孙)将结点与其左孩子的右子孙连接；将结点与其左孩子的右子孙连接；2、(断父子)对于任一结点，只保留它与最左孩对于任一结点，只保留它与最左孩子子之间的连线；之间的连线；3、(抖一抖)使任一结点的子树无左右之分。使任一结点的子树无左右之分。ABCEDFGACBDEFG哈夫曼树（哈夫
12、曼树（huffman)例例w=5,29,7,8,14,23,3,1151429 7823 3111429 7823 1135887151429233581111358191429238715113581929 23148715292914871529113581923421135819234229148715295811358192342291487152958100例：例：已知某系统在通讯时，只出现C，A，S，T，B五种字符，它们出现的频率依次为2，4，2，3，3，试设计Huffman编码。W（权）（权）=2，4，2，3，3，叶子结点个数，叶子结点个数n=5构造的Huffman树148464
13、220001113301TBACS图o图的基本概念o图的入度和出度TD（v）=ID（v）+OD（v）一般地，若图一般地，若图G中有中有n个顶点，个顶点，e条边或弧，则图中顶点条边或弧，则图中顶点的度与边的关系如下：的度与边的关系如下：e=TD(Vi)2ni=1如如果果一一个个图图有有n个个顶顶点点和和小小于于n-1条条边边，则则是是非连通图。非连通图。如果它多于如果它多于n-1条边，则一定有环。条边，则一定有环。但是，有但是，有n-1条边的图不一条边的图不一定是生成树。定是生成树。o图的深度优先和广度优先遍历o图的prim和Kruskual最小生成树图的存储o邻接矩阵表示法邻接矩阵表示法给出一
14、个带权图的邻接矩阵（顶点编号给出一个带权图的邻接矩阵（顶点编号18），），如下：如下：(1)给出在该图上从顶点给出在该图上从顶点1出发进行出发进行DFS遍历的结果序列，遍历的结果序列，并根据此判断该图是否为连通图？并根据此判断该图是否为连通图？(2)画出该图的邻接链表。画出该图的邻接链表。(3)画出按画出按Prim算法构造的最小生成树（森林）。算法构造的最小生成树（森林）。1237845635910647635v1v2v3v4v5v6v7v81234567823713812856464518237123745635910647635812335487745635o有向图的拓扑排序查找o顺序查找
15、算法o折半查找算法o哈希表设哈希函数设哈希函数H（k）=3Kmod11，散列地址空间为，散列地址空间为010，对关键字序列（，对关键字序列（32,13,49,24,38,21,4,12）按）按下述两种解决冲突的方法构造哈希表下述两种解决冲突的方法构造哈希表（1）线性探测再散列）线性探测再散列（2）链地址法，并分别求出等概率下查找成功时）链地址法，并分别求出等概率下查找成功时的平均查找长度的平均查找长度ASLsucc。例题例题散散 列列地址地址012345678910关关 键键字字412493813243221比比 较较次数次数11121212ASLsucc=（1+1+1+2+1+2+1+2）/
16、8=11/801234567 89104 321312 4921 38 24 ASLASLsuccsucc=11/8=11/8哈希表中元素个数哈希表中元素个数哈希表的长度哈希表的长度排序o直接插入排序算法o冒泡排序算法o快速排序算法o简单排序算法n直接插入排序算法描述直接插入排序算法描述 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；简单选择排序的算法简单选择排序的算法voidSelectSort(intL,intlength)fo
17、r(inti=0;ilength-1;+i)intk=i;for(intj=i+1;jLj)k=j;if(i!=k)ElemTypetemp=L.ri;Li=Lk;Lk=temp;习题习题1.对一组数据（对一组数据（84，47，25，15，21）排）排序，数据的排列次序在排序过程中的变化为序，数据的排列次序在排序过程中的变化为（1）84，47，25，15，21（2）15，47，25，84，21 (3)15，21，25，84,47 (4)15，21，25,47,84则采用的排序是（则采用的排序是（）选择排序选择排序选择排序选择排序2.一组记录为（一组记录为（46,79,56,38,40,84）,利用快速排序的方法，以第一个记录为枢轴利用快速排序的方法，以第一个记录为枢轴得到的划分结果为（得到的划分结果为（）A.(38,40,46,56,79,84)B.(40,38,46,79,56,84)C.(40,38,46,56,79,84)D.(40,38,46,84,56,79)C C3.快速排序在（快速排序在（）情况下最不利于发挥其长）情况下最不利于发挥其长处。处。A.要排序的数据量太大要排序的数据量太大B.要排序的数据中含有多个相同的值要排序的数据中含有多个相同的值C.要排序的数据个数为奇数要排序的数据个数为奇数D.要排序的数据已基本有序要排序的数据已基本有序D D