《NOIP信息学奥赛数据结构复习课件》由会员分享，可在线阅读，更多相关《NOIP信息学奥赛数据结构复习课件（20页珍藏版）》请在金锄头文库上搜索。
1、Noip初赛数据结构精讲第1页，共20页。一、概念是数据的基本单位，在计算机程序中通常作为一个整体来处理。一个数据元素由多个数据项（数据项（data item）组成，数据项是数据不可分割的最小单位。通常由下列四类基本结构：（1）集合:数据元素间的关系是同属一个集合。（图1）（2）线性结构:数据元素间存在一对一的关系。（图2）（3）树形结构：结构中的元素间的关系是一对多的关系。（图3）（4）图（网）状结构：结构中的元素间的关系是多对多的关系。（图4）第2页，共20页。第3页，共20页。二、线性表线性表简单的定义n个数据元素的的有限序列其特点是除了表头和表尾外，表中的每一个元素有且仅有唯一的前驱和
2、唯一的后继，表头有且只有一个后继，表尾有且只有一个前驱。第4页，共20页。三、栈栈的定义：栈是一种特殊的表这种表只在表头进行插入和删除操作。因此，表头对于栈来说具有特殊的意义，称为栈顶。相应地，表尾称为栈底。不含任何元素的栈称为空栈。栈的逻辑结构：假设一个栈S中的元素为an,an-1,.,a1，则称a1为栈底元素，an为栈顶元素。栈中的元素按a1,a2,.,an-1,an的次序进栈。在任何时候，出栈的元素都是栈顶元素。换句话说，栈的修改是按后进先出的原则进行的，如图1所示。因此，栈又称为后进先出后进先出(Last In First Out)表表，简称为LIFO表表。所以，只要问题满足LIFO原
3、则，就可以使用栈。第5页，共20页。历年奥赛试题（2006,2004）7某个车站呈狭长形，宽度只能容下一台车，并且只有一个出入口。已知某时刻该车站状态为空，从这一时刻开始的出入记录为：“进，出，进，进，进，出，出，进，进，进，出,出”。假设车辆入站的顺序为1，2，3，则车辆出站的顺序为（c）。A.1,2,3,4,5B.1,2,4,5,7C.1,4,3,7,6D.1,4,3,7,2E.1,4,3,7,5（2006）13.设栈S的初始状态为空，元素a,b,c,d,e依次入栈，以下出栈序列不可能出现的有（）。A.a,b,c,e,dB.b,c,a,e,dC.a,e,c,b,dD.d,c,e,b,a(2
4、005)（多项）14.设栈S的初始状态为空，元素a,b,c,d,e,f,g依次入栈，以下出栈序列不可能出现的有（）。A.a,b,c,e,d,f,gB.b,c,a,f,e,g,dC.a,e,c,b,d,f,gD.d,c,f,e,b,a,gE.g,e,f,d,c,b,a第6页，共20页。（2003）19已知元素(8，25，14，87，5l，90，6，19，20)，问这些元素以怎样的顺序进入栈，才能使出栈的顺序满足：8在5l前面；90在87后面；20在14后面；25在6前面；19在90后面。()A)20，6，8，51，90，25，14，19，87B)51，6，19，20，14，8，87，90，25C
5、)19，20，90，7，6，25，5l，14，87D)6，25，51，8，20，19，90，87，14E)25，6，8，51，87，90，19，14，20第7页，共20页。四、队列队列的定义：队列是一种特殊的线性表，对这种线性表，删除操作只在表头(称为队头)进行，插入操作只在表尾(称为队尾)进行。队列的修改是按先进先出的原则进行的，所以队列又称为先进先出(FirstInFirstOut)表，简称FIFO表。队列的数学性质：假设队列为a1,a2,.,an，那么a1就是队头元素，an为队尾元素。队列中的元素是按a1,a2,.,an的顺序进入的，退出队列也只能按照这个次序依次退出。也就是说，只有在a
6、1离开队列之后，a2才能退出队列，只有在a1,a2,.,an-1都离开队列之后，an才能退出队列。图1是队列的示意图。第8页，共20页。历年奥赛试题(2003)6已知队列(13，2，11，34，4l，77，5，7，18，26，15)，第一个进入队列的元素是13，则第五个出队列的元素是()。A)5B)41C)77D)13E)18（2002）20.设找栈S和队列Q的初始状态为空,元素e1,e2,e3,e4,e5,e6依次通过栈S,一个元素出栈后即进入队列Q,若出队的顺序为e2,e4,e3,e6,e5,e1,则栈S的容量至少应该为()。A)2B)3C)4D)5第9页，共20页。五、树1.树的概念树的
7、递归定义如下：（1）至少有一个结点（称为根）（2）其它是互不相交的子树1.树的度也即是宽度，简单地说，就是结点的分支数。以组成该树各结点中最大的度作为该树的度，如上图的树，其度为3;树中度为零的结点称为叶结点或终端结点。树中度不为零的结点称为分枝结点或非终端结点。除根结点外的分枝结点统称为内部结点。2.树的深度组成该树各结点的最大层次，如上图，其深度为4；第10页，共20页。2.二叉树二叉树的基本形态：二叉树也是递归定义的，其结点有左右子树之分，逻辑上二叉树有五种基本形态：(1)空二叉树(a)；(2)只有一个根结点的二叉树(b)；(3)右子树为空的二叉树(c)；(4)左子树为空的二叉树(d)；
8、(5)完全二叉树(e)第11页，共20页。3.两种重要的树(1)完全二叉树只有最下面的两层结点度小于2，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树；(2)满二叉树除了叶结点外每一个结点都有左右子女且叶结点都处在最底层的二叉树,。如下图第12页，共20页。4.二叉树的性质(1)在二叉树中，第i层的结点总数不超过2(i-1)；(2)深度为h的二叉树最多有2h-1个结点(h=1)，最少有h个结点；(3)对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1；第13页，共20页。历年奥塞试题（2006）8高度为n的均衡的二叉树是指：如果去掉叶结点及相应的树
9、枝，它应该是高度为n-1的满二叉树。在这里，树高等于叶结点的最大深度，根结点的深度为0，如果某个均衡的二叉树共有2381个结点，则该树的树高为（）。A.10B.11C.12D.13E.21(2005)4.完全二叉树的结点个数为4*N+3，则它的叶结点个数为（）。A.2*NB.2*N-1C.2*N+1D.2*N-2E.2*N+2(2004)满二叉树的叶结点个数为N，则它的结点总数为（）。A.NB.2*NC.2*N1D.2*N+1E.2N1(2002)17.按照二叉树的定义，具有3个结点的二叉树有()种。A)3B)4C)5D)6第14页，共20页。5.树的遍历第一种分法：前序遍历中序遍历后序遍历也
10、称为（前根遍历，中根遍历，后根遍历）第二种分法：深度优先遍历和广度优先遍历第15页，共20页。历年奥赛试题（2006）（多项）14.已知6个结点的二叉树的先根遍历是123456（数字为结点的编号，以下同），后根遍历是325641，则该二叉树的可能的中根遍历是（）A.321465B.321546C.231546D.231465(2005)（多项）13.二叉树T的宽度优先遍历序列为ABCDEFGHI，已知A是C的父结点，D是G的父结点，F是I的父结点，树中所有结点的最大深度为3（根结点深度设为0），可知E的父结点可能是（）。A.AB.BC.CD.DE.F(2004)二叉树T，已知其前序遍历序列为1
11、243576，中序遍历序列为4215736，则其后序遍历序列为（）。A.4257631B.4275631C.4275361B.D.4723561E.4526371第16页，共20页。六、图图是由顶点V的集合和边E的集合组成的二元组记G=（V，E），图可以分为有向图和无向图1.如下图是一无向图(顶点的前后顺序不限）无向图的记法：V=V1,V2,V3,V4,V5E=(V1,V2),(V2,V3),(V3,V4),(V4,V5),(V5,V1),(V2,V5),(V4,V1)2.有向图（顶点分先后顺序）有向图的记法：V=V1,V2,V3,V4E=,第17页，共20页。3.完全图无向完全图：有n(n-
12、1)条边有向完全图：有n(n-1)/2条边4.顶点的度顶点的度：与顶点关联的边的数目，有向图中等于该顶点的入度与出度之和。入度以该顶点为终点的边的数目和出度以该顶点为起点的边的数目和关于度的定理：度数为奇数的顶点叫做奇点，度数为偶数的点叫做偶点。定理定理1图G中所有顶点的度数之和等于边数的2倍。因为计算顶点的度数时。每条边均用到2次。定理定理2任意一个图一定有偶数个奇点。第18页，共20页。5.图的最小生成树图的生成树：连通图G的一个子图如果是一棵包含G的所有顶点的树，则该子图称为G的生成树最小生成树：如果图的边是带权值的，我们将所有权值加起来最小的树称为最小生成树第19页，共20页。历年奥赛试题（2003）20（多项）假设我们用d=(a1，a2，a5)，表示无向图G的5个顶点的度数，下面给出的哪(些)组d值合理的()。A)5，4，4，3，1B)4，2，2，1，1C)3，3，3，2，2D)5，4，3，2，lE)2，2，2，2，2)（2002）18.在一个有向图中,所有顶点的人度之和等于所有顶点的出度之和的()倍。A)1/2B)1C)2D)4第20页，共20页。
