数据结构基础知识NOIP提高组初赛解析什么是数据结构？数据元素相互之间的关系称为数据结构。其中数据元素是个广义概念，是所有能输入到计算机中并被计算机程序处理的符号的总称。 四大类基本数据结构集合（无相互关系）线性结构（一对一）树（一对多）图（多对多）集合运算(NOIp2005)字符串“ababacbab”和字符串“abcba”的最长公共子串是（ ）。 A.abcbaB.cbaC.abcD.abE.bcba（NOIp2008）.设字符串S=”Olympic”，S的非空子串的数目是（ ）。选B非空分别是OlympicOlympilympic。即1+2+3+4+5+6+7=28先算长为一的有七个,这个你会吧.接着是大等二的,还记的小学奥数的数线段题吧,其实这题就是让数有七个点的线段,那么公式是.点数乘段数除以二.即:7*6/2=21.再加上那个七 A.29B.28C.16D.17E.7(NOIp2005)设全集I=a,b,c,d,e,f,g,h，集合AB=a,b,c,d,e,f， AC=c,d,e， AB=a,d，那么集合ABC为（ ）。 A.c,eB.d,eC.eD.c,d,eE.d,f一般地，对于给定的两个集合A和 集合B的交集是指含有所有既属于 A又属于 B的元素，而没有其他元素的集合。一组集合的并集是这些集合的所有元素构成的集合，而不包含其他元素。交集就是两个集合都有的部分，并集就是两个集合的加起来的全部。 交集:表示方法 。交集是集合的公共部分。 并集 :表示方法 。并集是所有 空集是不含任何元素 U=全班同学 A=班上男同学 B=班上女同学A的补集就是B（在U中）BAB线性结构线性表队列栈线性表n个数据元素的的有限序列。其特点是除了表头和表尾外，表中的每一个元素有且仅有唯一的前驱和唯一的后继，表头有且只有一个后继，表尾有且只有一个前驱。线性表的修改存入数据下一个元素的地址链表顺序表队列队列是一种特殊的线性表，对这种线性表，删除操作只在表头(称为队头)进行，插入操作只在表尾(称为队尾)进行。队列的修改是按先进先出的原则进行的。 队列的修改栈栈是另一种特殊的线性表。这种表只在表头进行插入和删除操作。因此，表头对于栈来说具有特殊的意义，称为栈顶。相应地，表尾称为栈底。不含任何元素的栈称为空栈。栈的修改是按后进先出的原则进行的。 栈的修改历届试题(NOIp2005).设栈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(NOIp2006)某个车站呈狭长形，宽度只能容下一台车，并且只有一个出入口。已知某时刻该车站状态为空，从 这一时刻开始的出入记录为：“进，出，进，进，进，出，出，进，进，进，出,出”。假设车辆入站的 顺序为 1，2，3，则车辆出站的顺序为（ ）。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,5CEC历届试题（NOIp2007).地面上有标号为A、B、C的3根细柱,在A柱上放有10个直径相同中间有孔的圆盘,从上到下次依次编号为1,2,3,，将A柱上的部分盘子经过B柱移入C柱,也可以在B柱上暂存。如果B柱上的操作记录为：“进，进，出，进，进，出，出，进，进，出，进，出，出”。那么,在C柱上,从下到上的盘子的编号为（ ）。 A.243657B.241257C.243176D.243675E.214375（NOIp2008)设栈S的初始状态为空，元素a，b，c，d，e，f依次入栈S，出栈的序列为b，d，c，f，e，a，则栈S的容量至少应该是（ ）。A.6B.5C.4D.3E.2DD历届试题（NOIp2006）.设栈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(NOIP2010)元素R1、R2、R3、R4、R5入栈的顺序为R1、R2、R3、R4、R5。如果第1个出栈的是R3，那么第5个出栈的可能是()。A.R1B.R2C.R4D.R5CACD树树的度也即是宽度，简单地说，就是结点的分支数。以组成该树各结点中最大的度作为该树的度，如下图的树，其度为3。树的深度组成该树各结点的最大层次，如下图的树，其深度为4。二叉树二叉树是树的一种重要形态，只有左、右子树且顺序不能颠倒。逻辑上二叉树有五种基本形态：(1)空二叉树(a)；(2)只有一个根结点的二叉树(b)；(3)右子树为空的二叉树(c)；(4)左子树为空的二叉树(d)；(5)完全二叉树(e)关于二叉树的两个重要概念满二叉树，一棵深度为K的二叉树有2K-1个结点，则称为满二叉树。关于二叉树的两个重要概念和满二叉树对照，只有最下面的两层结点度小于2，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树，称为完全二叉树。结论：满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。历届试题（NOIp2005）.完全二叉树的结点个数为4*N+3，则它的叶结点个数为（ ）。 A.2*NB.2*N-1C.2*N+1D.2*N-2E.2*N+2（NOIp2008）完全二叉树共有2*N-1个结点，则它的叶节点数是（ ）。A.N-1B.2*NC.ND.2N-1E.N/2（NOIp2006）高度为 n的均衡的二叉树是指：如果去掉叶结点及相应的树枝，它应该是高度为 n-1的满二叉树。在这里，树高等于叶结点的最大深度，根结点的深度为 0，如果某个均衡的二叉树共有 2381个结点， 则该树的树高为（ ）。A.10B.11C.12D.13E.2101ECB历届试题(NOIP2009)一个包含n个分支结点（非叶结点）的非空满k叉树，k=1，它的叶结点数目为：()A)nk+1B)nk-1C)(k+1)n-1D.(k-1)n+1(NOIP2010)完全二叉树的顺序存储方案，是指将完全二叉树的结点从上到下、从左到右依次存放到一个顺序结构的数组中。假定根结点存放在数组的1号位置上，则第k号结点的父结点如果存在的话，应当存放在数组中的（）号位置。A.2kB.2k+1C.k/2下取整D.(k+1)/2DC树的遍历（访问）先序遍历中序遍历后序遍历历届试题（NOIp2005）.二叉树T的宽度优先遍历序列为ABCDEFGHI，已知A是C的父结点，D是G的父结点，F是I的父结点，树中所有结点的最大深度为3（根结点深度设为0），可知E的父结点可能是（ ）。 A.AB.BC.CD.DE.F（NOIp2006）.已知 6个结点的二叉树的先根遍历是 123456（数字为结点的编号，以下同），后根遍历是325641，则该二叉树的可能的中根遍历是（ ）A.321465B.321546C.231546D.231465(NOIP2010)一颗二叉树的前序遍历序列是ABCDEFG，后序遍历序列是CBFEGDA，则根结点的左子树的结点个数可能是（）。A0B.2C.4D.6BCBCB历届试题（NOIp2007）.已知7个节点的二叉树的先根遍历是1245637(数字为结点的编号，以下同)， 后根遍历是4652731， 则该二叉树的可能的中根遍历是（ ）A.4265173B.4256137C.4231547D.4256173（NOIp2008）.二叉树T，已知其先根遍历是1243576（数字为结点的编号，以下同），后根遍历是4275631，则该二叉树的可能的中根遍历是（ ）。A.4217536B.2417536C.4217563D.2415736ABDABD历届试题表达式a*(b+c)-d的后缀表达式是()A)abcd*+-B)abc+*d-C)abc*+d-D)-+*abcd(NOIP2010)前缀表达式“+3*2+512”的值是（ ）。A.23B.25C.37D.65BC图图由顶点V的集合和边E的集合组成，如下图是一无向图（顶点的前后顺序不限）。V=V1,V2,V3,V4,V5E=(V1,V2),(V2,V3),(V3,V4),(V4,V5),(V5,V1),(V2,V5),(V4,V1)图下图是一有向图（顶点分先后顺序）。V=V1,V2,V3,V4E=,图的性质顶点的度顶点的度：与顶点关联的边的数目。有向图中等于该顶点的入度与出度之和。入度以该顶点为终点的边的数目和出度以该顶点为起点的边的数目和 度数为奇数的顶点叫做奇点，度数为偶数的点叫做偶点。定理定理1图中所有顶点的度数之和等于边数的2倍。因为计算顶点的度数时。每条边均用到2次。定理定理2任意一个图一定有偶数个奇点。无向图中，若任意两个顶点之间都存在路径，则称该无向图为连通图。图的遍历深度优先遍历 1)从某一顶点出发开始访问,被访问的顶点作相应的标记,输出访问顶点号.2)从被访问的顶点出发,搜索与该顶点有边的关联的某个未被访问的邻接点 再从该邻接点出发进一步搜索与该顶点有边的关联的某个未被访问的邻接点,直到全部接点访问完毕。 图的遍历广度优先遍历 1）从某个顶点出发开始访问，被访问的顶点作相应的标记，并输出访问顶点号； 2）从被访问的顶点出发，依次搜索与该顶点有边的关联的所有未被访问的邻接点，并作相应的标记。 3）再依次根据2）中所有被访问的邻接点，访问与这些邻接点相关的所有未被访问的邻接点，直到所有顶点被访问为止。历届试题（NOIp2007）.欧拉图G是指可以构成一个闭回路的图，且图G的每一条边恰好在这个闭回路上出现一次（即一笔画成）。在以下各个描述中,不一定是欧拉图的是：（ ）。A.图G中没有度为奇数的顶点 B.包括欧拉环游的图(欧拉环游是指通过图中每边恰好一次的闭路径)C.包括欧拉闭迹的图(欧拉迹是指通过途中每边恰好一次的路径)D.存在一条回路,通过每个顶点恰好一次E.本身为闭迹的图（NOIp2008）.设T是一棵有n个顶点的树，下列说法正确的是（ ）。A.T是连通的、无环的 B.T是连通的，有n-1条边C.T是无环的，有n-1条边 D.以上都不对DABC