资源描述：
《NOIP信息学奥赛数据结构复习精品.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。
1、Noip初赛数据结构精讲一、概念是数据的基本单位，在计算机程序中通常作为一个整体来处理。一个数据元素由多个数据项（dataitem）组成，数据 项是数据不可分割的最小单位。通常由下列四类基本结构：（1）集合:数据元素间的关系是同属一个集合。（图1）（2）线性结构:数据元素间存在一对一的关系。（图2）（3）树形结构：结构中的元素间的关系是一对多的关系。（图3）（4）图（网）状结构：结构中的元素间的关系是多对多的关系。（图4）二、线性表线性表简单的定义n个数据元素的的有限序列其特点是除了表头和表尾外，表中的每一个元素有且仅有唯一的前驱和唯
2、一的后继，表头有且只有一个后继，表尾有且只有一个前驱。三、栈栈的定义：栈是一种特殊的表这种表只在表头进行插入和删除操作。因此，表头对于栈来说具有特殊的意义，称为栈顶。相应地，表尾称为栈底。不含任何元素的栈称为空栈。栈的逻辑结构：假设一个栈S中的元素为an,an-1,..,a1，则称a1为栈底元素，an为栈顶元素。栈中的元素按a1,a2,..,an-1,an的次序进栈。在任何时候，出栈的元素都是栈顶元素。换句话说，栈的修改是按后进先出的原则进行的，如图1所示。因此，栈又称为后进先出(LastInFirstOut)表，简称为LIFO表。所
3、以，只要问题满足LIFO原则，就可以使用栈。历年奥赛试题（2006,2004）7．某个车站呈狭长形，宽度只能容下一台车，并且只有一个出入口。已知某时刻该车站状态为空，从 这一时刻开始的出入记录为：“进，出，进，进，进，出，出，进，进，进，出,出”。假设车辆入站的 顺序为1，2，3，……，则车辆出站的顺序为（c）。 A.1,2,3,4,5 B.1,2,4,5,7 C.1,4,3,7,6 D.1,4,3,7,2 E.1,4,3,7,5（2006）13.设栈S的初始状态为空，元素a,b,c,d,e依次入栈，以下
4、出栈序列不可能出现的有（ ）。 A.a,b,c,e,d B.b,c,a,e,d C.a,e,c,b,d D.d,c,e,b,a(2005)（多项）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,g D.d,c,f,e,b,a,gE.g,e,f,d,c,b,a（2003）19．已知元素(8，25，14，87，5l，90，6，19，20)，问这些元素以
5、怎样的顺序进入栈，才能使出栈的顺序满足：8在5l前面；90在87后面；20在14后面；25在6前面；19在90后面。()A)20，6，8，51，90，25，14，19，87 B)51，6，19，20，14，8，87，90，25 C)19，20，90，7，6，25，5l，14，87 D)6，25，51，8，20，19，90，87，14 E)25，6，8，51，87，90，19，14，20四、队列队列的定义：队列是一种特殊的线性表，对这种线性表，删除操作只在表头(称为队头)进行，插入操作只在表尾(称为队尾)
6、进行。队列的修改是按先进先出的原则进行的，所以队列又称为先进先出(FirstInFirstOut)表，简称FIFO表。队列的数学性质：假设队列为a1,a2,..,an，那么a1就是队头元素，an为队尾元素。队列中的元素是按a1,a2,..,an的顺序进入的，退出队列也只能按照这个次序依次退出。也就是说，只有在a1离开队列之后，a2才能退出队列，只有在a1,a2,..,an-1都离开队列之后，an才能退出队列。图1是队列的示意图。历年奥赛试题(2003)6．已知队列(13，2，11，34，4l，77，5，7，18，26，15)，第一个进
7、入队列的元素是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)2 B)3 C)4 D)5五、树1.树的概念树的递归定义如下：（1）至少有一个结点（称为根）（2）其它是互不相交的子树1.树的度——也即是宽度，简单地说，就是结点的分支数。以组成该树各结点中最大的度作为该树的度，如上图的树，其
8、度为3;树中度为零的结点称为叶结点或终端结点。树中度不为零的结点称为分枝结点或非终端结点。除根结点外的分枝结点统称为内部结点。2.树的深度——组成该树各结点的最大层次，如上图，其深度为4；2.二叉树二叉树的基本形态：
