《数据结构——期末复习.ppt》由会员分享，可在线阅读，更多相关《数据结构——期末复习.ppt（65页珍藏版）》请在三一办公上搜索。
1、数据结构期末复习,主要知识点,算法的时间复杂度计算方法,单链表,堆栈和队列的概念和应用,串的概念和应用,树的概念和应用,图的概念和应用,查找和排序,算法满足以下性质:(1)输入性(2)输出性(3)有限性(4)确定性(5)可执行性,算法设计满足以下目标:(1)正确性(2)可读性(3)健壮性(4)高时间效率(5)高空间效率,算法的时间复杂度计算方法,常见的时间复杂度表示：O(1)，O(n)，O(n2)，O(n3)，O(lbn)，O(lgn),算法时间复杂度定义:T(n)=O(f(n),当且仅当存在正常数c和n0，对所有的n(n n0)满足T(n)cf(n)。T（n）为算法的基本语句执行次数，称为时
2、间复杂度，随n增大与f（n）增长接近相同，级，用O(f（n）)表示其复杂度即可称同一个数量。,推导大O阶的方法:,(1)用常数1取代运行时间中的所有加法常数。(2)在修改后的运行次数函数中，只保留最高阶项。(3)如果最高阶项在且不是1，则去除与这个项相乘的常数,最后得到的结果就是大O阶,例1 求和算法，求1+2+3.+99+100=5050。,int i,sum=0,n=100;/执行了1次 for(i=1;i=n;i+)/执行n+1次 sum=sum+i;/执行n次 printf(“%d”,sum);/执行了1次,该算法一共执行了1+n+1+n+1=2n+3次在求时间复杂度的时候我们忽略头尾
3、循环判断的开销，只需要分析影响一个算法时间复杂度的主要部分即可，即基本操作的数量必须表示成输入规模的函数：该算法的时间复杂度为 T(n)=O(n)称为线性阶注意：分析这类算法的复杂度关键是分析循环结构的运行情况,例2 求和算法，求1+2+3.+99+100=5050。,int sum=0,n=100;/执行了1次sum=(1+n)*n/2/执行1次printf(“%d”,sum);/执行了1次,该算法一共执行了1+1+1=3次在求时间复杂度的时候只需要分析影响一个算法时间复杂度的主要部分即可，即基本操作的数量必须表示成输入规模的函数：该算法的时间复杂度为 T(n)=O(1)称为常数阶注意：不管
4、这个常数是多少，我们都记做O(1)，而不是O(3)。,例3 求和算法，求1+2+3.+99+100+.=,int i,j,x=0,sum=0,n=100;/执行了1次 for(i=1;i=n;i+)for(j=1;j=n;j+)x+;/执行n*n次 sum=sum+x;printf(“%d”,sum);/执行了1次,在求时间复杂度的时候我们忽略头尾循环判断的开销，只需要分析影响一个算法时间复杂度的主要部分即可，即基本操作的数量必须表示成输入规模的函数：该算法的时间复杂度为 T(n)=O(n2)称为平方阶注意：循环的时间复杂度等于循环体的复杂度乘以该循环的次数,例1-3 设数组a和b在前边部分已
5、赋值，求如下两个n阶矩阵相乘运算算法的时间复杂度。,for(i=0;in;i+)for(j=0;jn;j+)cij=0;/基本语句1 for(k=0;kn;k+)cij=cij+aik*bkj;/基本语句2,该算法的时间复杂度为 T(n)=O(n3),例1-4 设n为如下算法处理的数据个数，求如下算法的时间复杂度。for(i=1;i=n;i=2*i)printf(“i=%dn”，i)；,解:设基本语句的执行次数为T(n),有2T(n)n,即有T(n)lbn。所以该算法的时间复杂度为T(n)=O(lb n)。称为对数阶,例1-5:下边的算法是用冒泡排序法对数字a中的n个整数类型的数据元素(a0a
6、n-1)，从小到大进行排序，求该算法的时间复杂度。,void BubbleSort(int a,int n)int i,j,flag=1;int temp;for(i=1;iaj+1)flag=1;temp=aj;aj=aj+1;aj+1=temp;,解:该算法基本语句执行次数与原始数据序列大小情况有关系，此时，按最坏情况统计。设基本语句的执行次数为T(n),最坏情况下有 T(n)n+4*n2/2因T(n)n+2*n2 c*n2,其中c为常数，所以该算法的时间复杂度为T(n)=O(n2)。,算法的时间复杂度是衡量一个算法好坏的重要指标。一般来说，具有多项式时间复杂度的算法，是可接受、可实际使用
7、的算法;具有指数时间复杂度的算法，是只有当n足够小时才可使用的算法。,例1-6 下面的算法是在一个有n个数据元素的数组a中删除第i个位置的数组元素，要求当删除成功时数组元素个数减1，求该算法的时间复杂度。其中数组下标从0至n-1。,int Delete(int a,int/删除成功返回,解:该算法与要删除元素位置i有关，此时一般按i所有取值情况下的平均执行次数来统计。假设删除任何位置上的数据元素都是等概率的,设Pi为删除第i个位置上数据元素的概率，则有Pi=1/n，设E为删除数组元素的平均次数，则有,因T(n)=E(n+1)/2 c*n,其中c为常数，所以该算法的等概率平均时间复杂度为T(n)
8、=O(n)。,插入效率：,删除效率：,顺序表操作的效率分析,单链表操作的效率分析单链表的插入和删除操作不需移动数据元素，只需比较数据元素。因此，当在单链表的任何位置上插入数据元素的概率相等时，在单链表中插入一个数据元素时比较数据元素的平均次数为：,删除一个数据元素时比较数据元素的平均次数为：,另外，单链表求数据元素个数操作的时间复杂度为O(n)。,1、在数据结构中，从逻辑上可以把数据结构分为（）。A动态结构和静态结构。B紧凑结构和非紧凑结构。C线性结构和非线性结构。D内部结构和外部结构。2、数据结构在计算机内存中的表示是指（）。A.数据的存储结构。B.数据结构。C.数据的逻辑结构。D.数据元素
9、之间的关系。,C,A,习题练习,3、在数据结构中，与所使用的计算机无关的是数据的（）结构。A逻辑B存储C逻辑和存储D物理4、在存储数据时，通常不仅要存储各数据元素的值，而且还要存储（）。A数据的处理方法B数据元素的类型C数据元素之间的关系D数据的存储方法5、在决定选取何种存储结构时，一般不考虑（）。A各结点的值如何。B结点个数的多少。C对数据有哪些运算。D所用的编程语言实现这种结构是否方便。,A,C,A,6、算法分析的目的是（），算法分析的两个主要方面是（）。（1）A找出数据结构的合理性。B研究算法中的输入和输出的关系。C分析算法的效率以求改进。D分析算法的易读性和文档性。（2）A空间复杂度和
10、时间复杂度。B正确性和简明性。C可读性和文档性。D数据复杂性和程序复杂性。,C,A,7、下面程序段的时间复杂度是。s 0；for（i 0；in；i）for（j0；jn；j）s Bij；sum s；8、下面程序段的时间复杂度是。for（i 0；in；i）for（j0；jm；j）Aij 0；9、下面程序段的时间复杂度是。i 0；while（in）i i*2；,O（n2）,O（n*m）,O（log2n）,1).在带头结点单链表第一个数据元素前插入结点,带头结点单链表和不带头结点单链表的比较,核心操作语句为：p=head；s-next=p-next;p-next=s;,注：两条语句顺序不能颠倒，即“先
11、勾右链，再勾左链”,单链表,2).删除带头结点单链表第一个数据元素结点,核心操作语句为：p=head；s=p-next;*x=s-datap-next=p-next-next;free(s);,3).在不带头结点单链表第一个数据元素前插入结点,核心操作语句为：s-next=head;head=s;,4).在不带头结点单链表其他数据元素前插入结点,核心操作语句为：s-next=p-next;p-next=s;,5).删除不带头结点单链表第一个数据元素结点,6).删除不带头结点单链表其他数据元素结点,核心操作语句为：s=head-next;head=head-next;free(s);,核心操作语
12、句为：s=p-next;*x=s-datap-next=p-next-next;free(s);,1、在带头结点的单链表head中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行的核心代码是（）。s-next=p；p-next=s；s-next=p-next；p-next=s；C.s-next=p-next；p=s；D.p-next=s；s-next=p；2、在带头结点的单链表head中，若删除p所指结点的后继结点，则执行的核心代码是（）。p-next=p-next-next；p=p-next；p-next=p-next-next；C.p-next=p-next；D.p=p-next
13、-next；,习题练习,B,A,4、单链表中，增加一个头结点的目的是为了（）。使单链表至少有一个结点。标识表结点中首结点的位置。C.方便运算的实现。D.说明单链表是线性表的链式存储。5、带头结点的单链表head为空的判定条件是（）。A.head=NULL B.head-Next=NULL C.head-next=head D.head!=NULL,C,B,6、已知head为带头结点的单链表，p为其中非首元的结点，分别写出以下操作的序列：（1）将s结点插入p结点之后；（2）删除p的直接后继结点；（3）删除尾元结点；,s-Next=p-Next;p-Next=s;,q=p-Next;p-Next=
14、p-Next-Next;free(q);,p=head;While(p-Next-Next!=NULL)p=p-Next;q=p-Next;p-Next=p-Next-Next;free(q);,堆栈和队列的基本概念和应用,堆栈的数据元素及逻辑关系与线性表完全相同，但是操作受限。(1)定义:限定只能在固定一端进行插入和删除操作的线性表。特点：后进先出。故又称后进先出表,(2)允许进行插入和删除操作的一端称为栈顶，另一端称为栈底。,队列的基本概念,堆栈的基本概念,(1)定义:只能在表的一端进行插入操作，在表的另一端进行删除操作的线性表（又称先进先出表）。一个队列的示意图如下：,队尾插入,队头删除
15、,1、有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（）。5 4 3 6 1 2 B.4 5 3 1 2 6 C.3 4 6 5 2 1 D.2 3 4 1 5 6 2、一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（）。A.2 3 4 1 5 B.5 4 1 3 2 C.2 3 1 4 5 D.1 5 4 3 23、某堆栈的输入序列为a,b，c，d,下面的四个序列中，不可能是它的输出序列的是（）。a，c，b，d B.b,c，d，a C.c，d，b，a D.d,c，a，b,习题练习,C,B,D,5、栈和队列的共同点是（）。A都是先进后
16、出。B都是先进先出。C只允许在端点处插入和删除元素。D没有共同点。6、以下（）不是队列的基本运算?A从队尾插入一个新元素。B从队列中删除第i个元素。C判断一个队列是否为空。D读取队头元素的值。,C,B,7、顺序循环队列中判定队列满的条件为（）。A.rear=front B.count 0 C.count 0&rear=front D.count 0|rear=front8、顺序循环队列中判定队列空的条件为（）。A.rear=front B.count=0 C.count 0&rear=front D.count 0|rear=front,C,B,9、输入序列为ABC，可以变为CBA时，经过的栈
17、操作为（）。Apush，pop，push，pop，push，popBpush，push，push，pop，pop，popCpush，push，pop，pop，push，popDpush，pop，push，push，pop，pop10、允许对队列进行的操作有（）。A对队列中的元素排序B取出最近进队的元素C在队头元素之前插入元素D删除队头元素11、对于循环队列（）。A无法判断队列是否为空B无法判断队列是否为满C队列不可能满D以上说法都不对,B,D,D,12、若用一个大小为6的数值来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和fron
18、t的值分别为（）。A1和5 B2和4 C4和2D5和113、队列的“先进先出”特性是指（）。A最早插入队列中的元素总是最后被删除。B当同时进行插入、删除操作时，总是插入操作优先。C每当有删除操作时，总是要先做一次插入操作。D每次从队列中删除的总是最早插入的元素。,D,B,、串（又称字符串）是由n(n 0)个字符组成的有限序列。（它是数据元素为单个字符的特殊线性表。）、串长:串中字符的个数（n0）。、空串:串中字符的个数为0 时称为空串。、空格串:由一个或多个空格符组成的串。、子串:串S中任意个连续的字符序列叫S的子串;S叫主串。、子串位置:子串的第一个字符在主串中的序号(从0开始)。、字符位置
19、:字符在串中的序号(从0开始)。、串相等:串长度相等，且对应位置上字符相等。（即两个串中的字符序列一一对应相等。）,串的基本概念和应用,35,1、现有以下4个字符串：a=“BEI”b=“JING”c=“BEIJING”d=“BEI JING”,他们各自的长度？,答：a是c和d的子串，在c和d中的位置都是0。,a是哪个串的子串？在主串中的位置是多少？,答：a：3，b：4，c：7，d：8。,空串是哪个串的子串？a是不是自己的子串？,答：空串是任意串的子串；任意串S都是S本身的子串，除S本身外，S的其他子串称为S的真子串。子串个数问题？如：串S=“produce”，则S共多少个子串？长为2,3的子串
20、分别多少个？,习题练习,2、设S1=“Data Structure Course”,S2=“Structure”,S3=“Base”，求（1）Length(S1);（2）Compare(S2,S3)；（3）Insert(S1,5,S3)；（4）Delete(S1,5,9);（5）SubString(S1,5,9,T)；（6）Search(S1,0,S2);（7）Replace(S1,0,S2,S3);,36,Length(S1)=21。,返回值为1。,输出“Data BaseStructure Course”。,输出“Data Course”。,输出T=“Structure”。,返回值为5。,
21、输出“Data Base Course”。,3、串的长度是指（）。A串中所含不同字母的个数B串中所含字符的个数C串中所含不同字符的个数D串中所含非空格字符的个数4、串是一种特殊的线性表，其特殊性体现在（）。A可以顺序存储B数据元素是一个字符C可以链式存储D数据元素可以是多个字符,B,B,若干术语（要求:理解、认识这些术语）,结点的度：结点所拥有的子树的个数(也可称分支数)。,叶结点（或叶子结点）：度为0的结点，也称作终端结点。,分支结点：度不为0的结点，一棵树中除叶结点外的所有结点都是分支结点。,树的基本概念和应用,孩子结点：树中某个结点的所有子树的根结点，称为该结点的孩子结点。,双亲结点：若
22、树中某结点有孩子结点，则这个结点就称作它的孩子结点的双亲结点。,兄弟结点：具有相同的双亲结点的结点之间互为兄弟结点。,树的度：树中所有结点的度的最大值。,结点的层次：从根结点到树中某结点所经路径上的分支数，根的层次为0，其它为双亲层次加1。,树的深度：树中所有结点的层次的最大值。,无序树：树中任意一个结点的各孩子结点之间的不要求区分次序，即左右颠倒后还是同一棵树；（本章的“树”）。,有序树：树中任意一个结点的各孩子结点有严格排列次序的树（本章的“二叉树”）。,森林：m（m0）棵树的集合。,二叉树基本特点：每个结点最多只有两棵子树（不存在度大于2的结点）；左子树和右子树次序不能颠倒。所以下面是两
23、棵不同的树。,二叉树形态：二叉树的所有结点的形态有五种：空、无左右子树、只有左子树、只有右子树、左右子树均存在。（形态只看形状，不看具体结点元素值）分析：只有三个结点（假设分别为A,B,C）的二叉树形态共有哪些情况？,满二叉树：在一棵二叉树中，如果所有分支结点都存在左 子树和右子树，并且所有叶子结点都在同一层上，这样的 二叉树称为满二叉树。（所有的存在的层次上结点都满）完全二叉树：如果一棵深度为k，有n个结点的二叉树中各 结点能够与深度为k的顺序编号的满二叉树从1到n标号的 结点相对应的二叉树称为完全二叉树。（相对于深度相同 的满二叉树来说完全二叉树只可能最后一层缺少最后面连 续的结点）如下图
24、所示满二叉树也是一棵特殊的完全二叉树。,(a)满二叉树,(b)完全二叉树,问题:一个深度为h的完全二叉树最多有多少个结点?最少有多少个结点?根结点深度为0。最多2(h+1)-1个，最少2h个,二叉树的性质,性质1 在一棵非空二叉树的第i层上至多有2i个结点（i0）。（理解、记结论）,性质2 深度为k的二叉树至多有2k+1-1个结点。说明：深度k=-1，表示空二叉树，没有一个结点；深度k=0，表示只有一个根结点。（理解、记结论）性质3 具有n个结点的完全二叉树的深度k为大于或等于lb(n+1)-1的最小整数。（要求会根据结点数求深度）如：20个结点的完全二叉树深度为？,答：2k-1n=2k+1-
25、1，k=4,哈夫曼树的基本概念,从A结点到B结点所经过的分支序列叫做从A结点到B结点的路径；从A结点到B结点所经过的分支个数叫做从A结点到B结点的路径长度；从二叉树的根结点到二叉树中所有叶结点的路径长度之和称作该二叉树的路径长度。设二叉树有n个带权值的叶结点，定义从二叉树的根结点到二叉树中所有叶结点的路径长度与相应叶结点权值的乘积之和称作该二叉树的带权路径长度（WPL），即：,WPL=,其中，wi为第i个叶结点的权值，li为从根结点到第i个叶结点的路径长度。,1、已知一棵树T=(D,R),D=A,B,C,D,E,F,G,H,I,J,K,L,M,N；R=,，,请画出这棵树，并回答以下问题：(1)
26、哪个是根结点？(2)哪些是叶子结点？(3)哪个是结点G的双亲？(4)哪些是结点E的孩子？(5)哪些是E的兄弟？,习题练习,(6)哪些是F的兄弟？(7)结点N的层次是多少？(8)以结点C为根的子树的深度是多少？(9)该树的深度是多少？(10)该树的度是多少？,2、某二叉树结点的中序序列为ABCDEFG，后序序列为BDCAFGE，则其左子树中结点数目为（）。A3B2 C4D53、对某二叉树进行先序遍历的结果为ABDEFC，中序遍历的结果为DBFEAC，则后序遍历的结果是（）。DBFEAC B.DFEBCAC.BDFECAD.BDEFAC,C,B,4、设a,b为一棵二叉树上的两个结点，在中序遍历时，
27、a在b前面的条件是（）。a在b的右方 B.a在b的左方C.a是b的祖先D.a是b的子孙5、若以4,5,6,7,8作为权值构造哈夫曼树，则该树的带权路径长度为（）。A.67 B.68C.69 D.70,B,C,6、树最适合用来表示（）。有序数据元素。无序数据元素。C.元素之间具有分支层次关系的数据。D.元素之间无联系的数据。7、假设用于通讯的电文仅由8个字母A、B、C、D、E、F、G、H组成，字母在电文中出现的频率分别为：0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。请为这8个字母设计哈夫曼编码。,C,8、已知权值集合为5,7,2,3,6,9，要求给出哈夫曼树，
28、并计算带权路径长度WPL。9、已知一棵二叉树的先序序列：ABDGJEHCFIKL；中序序列：DJGBEHACKILF。画出二叉树的形态。,10、设有如下图所示的树，要求：（1）将其转换为二叉树；（2）分别写出该树的先根遍历序列和后根遍历序列；（3）分别写出转换后的二叉树的前序、中序以及后序遍历序列。,（1）完全图：在有n个顶点的无向图中，若有n(n-1)/2条边，即任意两个顶点之间有且只有一条边，则称此图为无向完全图；在有n个顶点的有向图中，若有n(n-1)条边，即任意两个顶点之间有且只有方向相反的两条边，则称此图为有向完全图。（2）邻接结点：在无向图G中，若（u,v）是E(G)中的一条边，则
29、称u和v互为邻接结点，并称边（u,v）依附于结点u和v；在有向图G中，若u,v是E(G)中的一条边，则称结点u邻接到结点v，结点v邻接自结点u，并称边u,v和结点u和结点v相关联。,图的基本概念和应用,（3）结点的度：结点v的度是与它相关联的边的条数，记作TD(v)。有向图中：结点的度=入度+出度。即TD(v)=ID(v)+OD(v)思考：在无向图中，所有顶点度的和是图中边数有何关系？答：所有顶点度的和是图中边数的2倍。有向图中：所有出度和=入度和=边总数（4）连通图和强连通图：在无向图中，若从结点vi到结点vj有路径，则称结点vi和结点vj是连通的。如果图中任意一对结点都是连通的，则称该图是
30、连通图。在有向图中，若对于任意一对结点vi和结点vj（vivj）都存在路径，则称图G是强连通图。（5）最小连通子图：G1包含G的全部结点，但只有G中足够构成连通图的最少数目的边，则G1称为G的最小连通子图,（6）生成树：一个连通图的最小连通子图称作该图的生成树。有n个结点的连通图的生成树有n个结点和n-1条边。生成树一般是对无向图来讨论。一个有n个顶点的连通图的生成树是原图的极小连通子图，它包含原图中的所有n个顶点，并且有保持图连通的最少的边。若在生成树中删除一条边就会使该生成树因变成非连通图而不再满足生成树的定义；若在生成树中增加一条边就会使该生成树中因存在回路而不再满足生成树的定义；一个连
31、通图的生成树可能有许多；有n个顶点的无向连通图，无论它的生成树的形状如何，一定有且只有n-1条边。,1、采用邻接表存储的图的深度优先遍历算法类似于二叉树的（）。A先序遍历 B中序遍历 C后序遍历 D按层遍历2、采用邻接表存储的图的广度优先遍历算法类似于二叉树的（）。A先序遍历 B中序遍历 C后序遍历 D按层遍历3、具有n 个结点的连通图至少有（）条边。An1B n C n（n1）/2 D 2n,A,A,D,4、使用克鲁斯卡尔算法构造出图G的一颗最小生成树。,5、使用普里姆算法构造如下图所示的一颗最小生成树。,6、已知如下图的邻接表，请给出顶点V1出发的深度优先遍历序列，以及顶点V1出发的广度优
32、先遍历序列。,直接插入排序算法原理：顺序地把待排序的数据元素按其关键字值的大小插入到已排序数据元素子集合的适当位置。直接插入算法效率时间复杂度：最好情况下（已经按关键字排序），时间复杂度为O(n)；最坏情况下（按关键字反序），时间复杂度为O(n2)。空间复杂度O(1)。算法是稳定的。n个数据元素共n-1次排序,排序的基本概念和应用,直接选择排序算法原理：基本思想是：从待排序的数据元素集合中选取关键字最小的数据元素并将它与原始数据元素集合中的第一个数据元素交换位置；然后从不包括第一个位置上数据元素的集合中选取关键字最小的数据元素并将它与原始数据元素集合中的第二个数据元素交换位置；如此重复，直到数
33、据元素集合中只剩一个数据元素为止。时间效率：O(n2)虽移动次数较少，但比较次数仍多。空间效率：O(1)没有附加单元（仅用到1个temp)算法的稳定性：不稳定例：(10，10，9)(9，10，10)。,冒泡排序算法原理：基本思想：每趟不断将数据元素两两比较，并按“前小后大”（或“前大后小”）规则交换。,时间效率：O（n2)考虑最坏情况空间效率：O（1）只在交换时用到一个缓冲单元稳 定 性：稳定的,1、对以下序列使用直接插入排序、直接选择排序和冒泡排序，并描述每趟排序后关键字序列的情况。（1）关键字序列（20,19,49,50,35,69,49）（2）关键字序列（30,28,19,35,50,1
34、4,35）,习题练习,理解顺序查找和折半查找算法 哈希函数：数据元素的关键字和该数据元素的存放位置之间的映射函数。哈希表：通过哈希函数来确定数据元素存放位置的一种特殊表结构。,查找的基本概念和应用,1、已知一个长度为12的表（6，8，4，12，2，10，7，3，9，1，11，5）。将表中的元素依次插入到一个初始为空的二叉排序树中，画出该二叉排序树。,习题练习,2、已知哈希表地址空间为0.6，哈希函数为H(key)=key MOD 7，设有数据元素系列为38，25，74，63，52，48。要求用线性探测法处理冲突，用除留余法构造哈希表，要求：请给出用开放地址法的线性探查解决哈希冲突的哈希表结构，并填写下表，同时请写出构造哈希表解决哈希冲突的过程。地址关键字探测次数,
