《数据结构复习资料.ppt》由会员分享，可在线阅读，更多相关《数据结构复习资料.ppt（48页珍藏版）》请在三一文库上搜索。
1、总复习,考试类型,选择题 填空题 简答题 编程题,绪论部分,数据结构中逻辑结构与物理结构的区别 时间复杂度,for (i=0;in;i+) for(j=0;jm;j+) Aij=0;,时间复杂度为O（m*n)。,线性表,线性表的特征 线性表的物理结构（存储）： 顺序存储、链式存储 顺序存储与链式存储的区别 顺序存储：逻辑上相邻的数据元素，其物理上也相邻； 链式存储：逻辑上相邻的数据元素，其物理上不一定相邻；,顺序存储计算公式： LOC(ai) = LOC(a1) + L *（i-1） LOC(ai+1) = LOC(ai)+L,插入和删除需要移动大量元素 随机存取,每个元素由结点(Node)构
2、成, 它至少包括两个 域:数据域Data和指针域Link,存储结构：链式存储结构 特点：存储单元可以不连续。 存取方式：顺序存取。,链表结构（重点),链表结点插入和删除,插入和删除不需要移动大量元素 顺序存取,单链表的插入,在链表中插入一个元素的示意图如下：,插入步骤（即核心语句）：,Step 1：s-next=p-next; Step 2：p-next=s ；,p-next,s-next,元素x结点应预先生成： S=(LinkList)malloc(m); S-data=x; S-next=p-next,单链表的删除,在链表中删除某元素的示意图如下：,删除步骤（即核心语句）：,q = p-n
3、ext; /保存b的指针，靠它才能指向c p-next=q-next; /a、c两结点相连 free(q) ； /删除b结点，彻底释放,p-next,思考： 省略free(q)语句行不行？,(p-next) - next,1、填空题： 1）在顺序表中插入和删除一个元素，需要平均移动 个元素，具体移动的元素个数与 有关。 2）顺序表中逻辑上相邻的元素的物理位置 紧邻。单链表中逻辑上相邻的元素的物理位置 紧邻。 3）在单链表中，除了首元结点外，任一结点内的存储位置由 指示。 4）在单链表中，设置头结点的作用是 。,栈和队列,栈和队列的特点 栈的入栈出栈顺序,设依次进入一个栈的元素序列为c，a，b，
4、d，则可得到出栈的元素序列是： ）a，b，c，d ）c，d，a，b ）b，c，d，a ）a，c，d，b,A、D可以（ B、C不行）。,答：,一、数制转换 十进制N和其它进制数的转换是计算机实现计算的基本问题,其解决方法很多,其中一个简单算法基于下列原理: N=(n div d)*d+n mod d ( 其中:div为整除运算,mod为求余运算),循环队列的操作 少使用一个元素空间 判空条件： front=rear 判满条件： (rear+1)%M=front 入队列：rear=(rear+1)%M 出队列： front=(front+1)%M,J4,J5,J6,0,1,2,3,4,5,rear
5、,front,J8,J7,练习,一个队列的入队序列是1，2，3，4，则出队顺 序是【1】 A 4,3,2,1 B 1,2,3,4 C 1,4,3,2 D 3,2,4,1 判定一个队列QU（最多MaxSize个元素）为空的条件 A QUrear-QU-front=MaxSize B QU-rear-QU-front-1=MaxSize C QU-front=QU-rear D、QU-front=QU-rear+1,B,c,z,判定一个队列QU（最多MaxSize个元素）为满的条件 A 、QUrear-QU-front=MaxSize B、 QU-rear-QU-front-1=MaxSize C
6、、 QU-front=QU-rear D、QU-front=QU-rear+1,A,循环顺序队列中是否可以插入下一个元素，【2】 A、与队头指针和队尾指针值有关 B、与队头指针有关，与队尾指针值无关 C、只与数组大小有关，与队头指针和队尾指针值无关 D、与曾经进行过多少次插入操作有关,(rear+1)%M=front A,判断一个循环队列QU（最多元素为MaxSize)为空的条件【1】 A、QU-front=QU-rear B、QU-front!=QU-rear C、QU-front=(QU-rear+1)%MaxSize D、QU-front!=(QU-rear+1)%MaxSize 判断一
7、个循环队列QU（最多元素为MaxSize)为空的条件【1】 A、QU-front=QU-rear B、QU-front!=QU-rear C、QU-front=(QU-rear+1)%MaxSize D、QU-front!=(QU-rear+1)%MaxSize,A,C,树和二叉树,性质1：在二叉树的第i层上至多有2i-1个结点(i1)。 深度为k的二叉树至多有2k-1个结点(k1） 性质3 对任何一棵二叉树T，如果其终端结点数为n0 ，而其度为2的结点数为n2 , 则n0=n2+1。,练习 一棵二叉树中，度为0的结点个数为n0，度为2的结点个数我10，则n0=【1】,具有n个结点的完全二叉树
8、的深度为log2n+1。,1.以下说法错误的是（） A.树形结构的特点是一个结点可以有多个直接前驱 B.线性结构中的一个结点至多只有一个直接后继 C.树形结构可以表达更复杂的数据 D.树是一种“分支层次”结构 E.任何只含一个结点的集合是一棵树 2.以下说法正确的是（） A.任何一棵二叉树中至少有一个结点的度为2 B.任何一棵二叉树中每个结点的度都为2 C.任何一棵二叉树中的度肯定等于2 D.任何一棵二叉树中的度可以小于2,习题,3.若一棵二叉树有10个度为2的结点，5个度为1的结点，则二叉树结点总数为（） A.9 B.26 C.15 D.不确定 4.一棵完全二叉树上有1001个结点，其中叶子
9、结点的个数为（） A.250 B.500 C.254 D.505 E.以上答案都不对 5. 一棵二叉树的高度为h，所有结点的度为0或为2，则这棵二叉树最少有（）个结点 A.2h B.2h1 C.2h1 D.h1,每层有两个结点,二叉树的遍历,A,B,C,D,E,F,G,I,H,先序遍历：ABDEHICFG,中序遍历：DBHEIAFCG,后序遍历：DHIEBFGCA,已知二叉树的前序（后序），中序遍历序列，求后序（前序）序列,已知二叉树的先序和中序序列如下，试构造出相应的二叉树。 先序：ABCDEFGHIJ 中序：CDBFEAIHGJ 原理：先序序列的第一个节点是根节点 中序序列根结点处于左右子
10、树的中 序序列之间,树与二叉树的转换,连兄弟,断父子,转一转,二叉树转化为树,转换方法： 1、(连祖孙) 将结点与其左孩子的右子孙连接； 2、(断父子) 对于任一结点，只保留它与最左孩子 之间的连线； 3、(抖一抖) 使任一结点的子树无左右之分。,A B C E D F G,哈夫曼树（huffman),例 w=5, 29, 7, 8, 14, 23, 3, 11,例：已知某系统在通讯时，只出现C，A，S，T，B五种字符，它们出现的频率依次为2，4，2，3，3，试设计Huffman编码。 W（权）=2，4，2，3，3，叶子结点个数n=5,构造的Huffman树,图,图的基本概念 图的入度和出度,
11、TD（v）= ID（v）+ OD（v）,一般地，若图G中有n个顶点，e条边或弧，则图中顶点的度与边的关系如下：,如果一个图有n个顶点和小于n-1条边，则是非连通图。 如果它多于n-1条边，则一定有环。 但是，有n-1条边的图不一定是生成树。,图的深度优先和广度优先遍历 图的prim和Kruskual最小生成树,图的存储,邻接矩阵表示法 给出一个带权图的邻接矩阵（顶点编号18），如下：,(1)给出在该图上从顶点1出发进行DFS遍历的结果序列，并根据此判断该图是否为连通图？ (2)画出该图的邻接链表。 (3)画出按Prim算法构造的最小生成树（森林）。,1,2,3,7,8,4,5,6,3,5,9,
12、10,6,4,7,6,3,5,v1,v2,v3,v4,v5,v6,v7,v8,1,2,3,4,5,6,7,8,2,3,7,1,3,8,1,2,8,5,6,4,6,4,5,1,8,2,3,7,1,2,3,7,4,5,6,3,5,9,10,6,4,7,6,3,5,8,1,2,3,3,5,4,8,7,7,4,5,6,3,5,有向图的拓扑排序,查找,顺序查找算法 折半查找算法 哈希表,设哈希函数H（k）=3 K mod 11，散列地址空间为010，对关键字序列（32,13,49,24,38,21,4,12）按下述两种解决冲突的方法构造哈希表 （1）线性探测再散列 （2）链地址法，并分别求出等概率下查找
13、成功时的平均查找长度ASLsucc。,例题,ASLsucc =（1+1+1+2+1+2+1+2）/8=11/8,0 1 2 3 4,5 6 7,8 9 10,ASLsucc =11/8,排序,直接插入排序算法 冒泡排序算法 快速排序算法 简单排序算法,直接插入排序算法描述,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； ,简单选择排序的算法 void SelectSort(int L ,int length)
14、 for (int i=0; i Lj) k=j; if (i!=k) ElemType temp=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,3.快速排序在（ ）情况下最不利于发挥其长处。 A.要排序的数据量太大 B.要排序的数据中含有多个相同的值 C.要排序的数据个数为奇数 D.要排序的数据已基本有序,D,