《数据结构基础知识幻灯片.ppt》由会员分享，可在线阅读，更多相关《数据结构基础知识幻灯片.ppt（33页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构基础知识第1页，共33页，编辑于2022年，星期六什么是数据结构？数据元素相互之间的关系称为数据结构。其中数据元素是个广义概念，是所有能输入到计算机中并被计算机程序处理的符号的总称。第2页，共33页，编辑于2022年，星期六四大类基本数据结构集合（无相互关系）线性结构（一对一）树（一对多）图（多对多）第3页，共33页，编辑于2022年，星期六集合运算(NOIp2005)字符串“ababacbab”和字符串“abcba”的最长公共子串是（）。A.abcba B.cba C.abc D.ab E.bcba（NOIp2008）.设字符串S=”Olympic”，S的非空子串的数目是（）。A.2
2、9 B.28 C.16 D.17 E.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,e B.d,e C.e D.c,d,e E.d,fBAB第4页，共33页，编辑于2022年，星期六线性结构线性表队列栈第5页，共33页，编辑于2022年，星期六线性表n个数据元素的的有限序列。其特点是除了表头和表尾外，表中的每一个元素有且仅有唯一的前驱和唯一的后继，表头有且只有一个后继，表尾有且只有一个前驱。第6页，共33页，编辑于2022年，星期六线性表的修改第7页，共33页，编辑于2022年，
3、星期六队列队列是一种特殊的线性表，对这种线性表，删除操作只在表头(称为队头)进行，插入操作只在表尾(称为队尾)进行。队列的修改是按先进先出的原则进行的。第8页，共33页，编辑于2022年，星期六队列的修改第9页，共33页，编辑于2022年，星期六栈栈是另一种特殊的线性表。这种表只在表头进行插入和删除操作。因此，表头对于栈来说具有特殊的意义，称为栈顶。相应地，表尾称为栈底。不含任何元素的栈称为空栈。栈的修改是按后进先出的原则进行的。第10页，共33页，编辑于2022年，星期六栈的修改第11页，共33页，编辑于2022年，星期六历届试题(NOIp2005).设栈S的初始状态为空，元素a,b,c,d
4、,e,f,g依次入栈，以下出栈序列不可能出现的有（）。A.a,b,c,e,d,f,g B.b,c,a,f,e,g,d C.a,e,c,b,d,f,g D.d,c,f,e,b,a,g E.g,e,f,d,c,b,a(NOIp2006)某个车站呈狭长形，宽度只能容下一台车，并且只有一个出入口。已知某时刻该车站状态为空，从 这一时刻开始的出入记录为：“进，出，进，进，进，出，出，进，进，进，出,出”。假设车辆入站的 顺序为 1，2，3，则车辆出站的顺序为（）。A.1,2,3,4,5 B.1,2,4,5,7 C.1,4,3,7,6D.1,4,3,7,2 E.1,4,3,7,5CEC第12页，共33页，
5、编辑于2022年，星期六历届试题（NOIp2007).地面上有标号为A、B、C的3根细柱,在A柱上放有10个直径相同中间有孔的圆盘,从上到下次依次编号为1,2,3,，将A柱上的部分盘子经过B柱移入C柱,也可以在B柱上暂存。如果B柱上的操作记录为：“进，进，出，进，进，出，出，进，进，出，进，出，出”。那么,在C柱上,从下到上的盘子的编号为（）。A.2 4 3 6 5 7 B.2 4 1 2 5 7 C.2 4 3 1 7 6 D.2 4 3 6 7 5 E.2 1 4 3 7 5（NOIp2008)设栈S的初始状态为空，元素a，b，c，d，e，f依次入栈S，出栈的序列为b，d，c，f，e，a，
6、则栈S的容量至少应该是（）。A.6 B.5 C.4 D.3 E.2DD第13页，共33页，编辑于2022年，星期六历届试题（NOIp2006）.设栈S的初始状态为空，元素a,b,c,d,e 依次入栈，以下出栈序列不可能出现的有（）。A.a,b,c,e,d B.b,c,a,e,dC.a,e,c,b,d D.d,c,e,b,a(NOIP2010)元素R1、R2、R3、R4、R5入栈的顺序为R1、R2、R3、R4、R5。如果第1个出栈的是R3，那么第5个出栈的可能是()。A.R1 B.R2 C.R4 D.R5CACD第14页，共33页，编辑于2022年，星期六树树的度也即是宽度，简单地说，就是结点的
7、分支数。以组成该树各结点中最大的度作为该树的度，如下图的树，其度为3。树的深度组成该树各结点的最大层次，如下图的树，其深度为4。第15页，共33页，编辑于2022年，星期六二叉树二叉树是树的一种重要形态，只有左、右子树且顺序不能颠倒。逻辑上二叉树有五种基本形态：(1)空二叉树(a)；(2)只有一个根结点的二叉树(b)；(3)右子树为空的二叉树(c)；(4)左子树为空的二叉树(d)；(5)完全二叉树(e)第16页，共33页，编辑于2022年，星期六关于二叉树的两个重要概念满二叉树，一棵深度为K的二叉树有2K-1个结点，则称为满二叉树。第17页，共33页，编辑于2022年，星期六关于二叉树的两个重
8、要概念和满二叉树对照，只有最下面的两层结点度小于2，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树，称为完全二叉树。结论：满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。第18页，共33页，编辑于2022年，星期六历届试题（NOIp2005）.完全二叉树的结点个数为4*N+3，则它的叶结点个数为（）。A.2*N B.2*N-1 C.2*N+1 D.2*N-2 E.2*N+2（NOIp2008）完全二叉树共有2*N-1个结点，则它的叶节点数是（）。A.N-1 B.2*N C.N D.2N-1 E.N/2（NOIp2006）高度为 n 的均衡的二叉树是指：如果去掉叶结点及相应的树枝
9、，它应该是高度为 n-1 的满二叉树。在这里，树高等于叶结点的最大深度，根结点的深度为 0，如果某个均衡的二叉树共有 2381 个结点，则该树的树高为（）。A.10 B.11 C.12 D.13 E.210 1 ECB第19页，共33页，编辑于2022年，星期六历届试题(NOIP2009)一个包含n个分支结点（非叶结点）的非空满k叉树，k=1，它的叶结点数目为：()A)nk+1 B)nk-1 C)(k+1)n-1 D.(k-1)n+1(NOIP2010)完全二叉树的顺序存储方案，是指将完全二叉树的结点从上到下、从左到右依次存放到一个顺序结构的数组中。假定根结点存放在数组的1号位置上，则第k号结
10、点的父结点如果存在的话，应当存放在数组中的（）号位置。A.2k B.2k+1 C.k/2下取整 D.(k+1)/2DC第20页，共33页，编辑于2022年，星期六树的遍历（访问）先序遍历中序遍历后序遍历第21页，共33页，编辑于2022年，星期六历届试题（NOIp2005）.二叉树T的宽度优先遍历序列为A B C D E F G H I，已知A是C的父结点，D是G的父结点，F是I的父结点，树中所有结点的最大深度为3（根结点深度设为0），可知E的父结点可能是（）。A.A B.B C.C D.D E.F（NOIp2006）.已知 6 个结点的二叉树的先根遍历是 1 2 3 4 5 6（数字为结点的
11、编号，以下同），后根遍历是3 2 5 6 4 1，则该二叉树的可能的中根遍历是（）A.3 2 1 4 6 5 B.3 2 1 5 4 6C.2 3 1 5 4 6 D.2 3 1 4 6 5(NOIP2010)一颗二叉树的前序遍历序列是ABCDEFG，后序遍历序列是CBFEGDA，则根结点的左子树的结点个数可能是（）。A0 B.2 C.4 D.6 BCBCB第22页，共33页，编辑于2022年，星期六第23页，共33页，编辑于2022年，星期六历届试题（NOIp2007）.已知7个节点的二叉树的先根遍历是1 2 4 5 6 3 7(数字为结点的编号，以下同)，后根遍历是4 6 5 2 7 3
12、1，则该二叉树的可能的中根遍历是（）A.4 2 6 5 1 7 3B.4 2 5 6 1 3 7 C.4 2 3 1 5 4 7D.4 2 5 6 1 7 3（NOIp2008）.二叉树T，已知其先根遍历是1 2 4 3 5 7 6（数字为结点的编号，以下同），后根遍历是4 2 7 5 6 3 1，则该二叉树的可能的中根遍历是（）。A.4 2 1 7 5 3 6 B.2 4 1 7 5 3 6 C.4 2 1 7 5 6 3 D.2 4 1 5 7 3 6 ABDABD第24页，共33页，编辑于2022年，星期六第25页，共33页，编辑于2022年，星期六历届试题表达式a*(b+c)-d的后缀
13、表达式是()A)abcd*+-B)abc+*d-C)abc*+d-D)-+*abcd(NOIP2010)前缀表达式“+3*2+5 12”的值是（）。A.23 B.25 C.37 D.65BC第26页，共33页，编辑于2022年，星期六第27页，共33页，编辑于2022年，星期六图图由顶点V的集合和边E的集合组成，如下图是一无向图（顶点的前后顺序不限）。V=V1,V2,V3,V4,V5 E=(V1,V2),(V2,V3),(V3,V4),(V4,V5),(V5,V1),(V2,V5),(V4,V1)第28页，共33页，编辑于2022年，星期六图下图是一有向图（顶点分先后顺序）。V=V1,V2,V
14、3,V4 E=,第29页，共33页，编辑于2022年，星期六图的性质顶点的度顶点的度：与顶点关联的边的数目。有向图中等于该顶点的入度与出度之和。入度以该顶点为终点的边的数目和出度以该顶点为起点的边的数目和 度数为奇数的顶点叫做奇点，度数为偶数的点叫做偶点。定理定理1 图中所有顶点的度数之和等于边数的2倍。因为计算顶点的度数时。每条边均用到2次。定理定理2 任意一个图一定有偶数个奇点。无向图中，若任意两个顶点之间都存在路径，则称该无向图为连通图。第30页，共33页，编辑于2022年，星期六图的遍历深度优先遍历 1)从某一顶点出发开始访问,被访问的顶点作相应的标记,输出访问顶点号.2)从被访问的顶
15、点出发,搜索与该顶点有边的关联的某个未被访问的邻接点 再从该邻接点出发进一步搜索与该顶点有边的关联的某个未被访问的邻接点,直到全部接点访问完毕。第31页，共33页，编辑于2022年，星期六图的遍历广度优先遍历 1）从某个顶点出发开始访问，被访问的顶点作相应的标记，并输出访问顶点号；2）从被访问的顶点出发，依次搜索与该顶点有边的关联的所有未被访问的邻接点，并作相应的标记。3）再依次根据2）中所有被访问的邻接点，访问与这些邻接点相关的所有未被访问的邻接点，直到所有顶点被访问为止。第32页，共33页，编辑于2022年，星期六历届试题（NOIp2007）.欧拉图G是指可以构成一个闭回路的图，且图G的每一条边恰好在这个闭回路上出现一次（即一笔画成）。在以下各个描述中,不一定是欧拉图的是：（）。A.图G中没有度为奇数的顶点 B.包括欧拉环游的图(欧拉环游是指通过图中每边恰好一次的闭路径)C.包括欧拉闭迹的图(欧拉迹是指通过途中每边恰好一次的路径)D.存在一条回路,通过每个顶点恰好一次E.本身为闭迹的图（NOIp2008）.设T是一棵有n个顶点的树，下列说法正确的是（）。A.T是连通的、无环的 B.T是连通的，有n-1条边C.T是无环的，有n-1条边 D.以上都不对DABC第33页，共33页，编辑于2022年，星期六