数据结构基础知识

1、NOIP提高组初赛解析数据元素相互之间的关系称为数据结构。其中数据元素是个广义概念，是所有能输入到计算机中并被计算机程序处理的符号的总称。 集合（无相互关系）线性结构（一对一）树（一对多）图（多对多）(NOIp2005)字符串“ababacbab”和字符串“abcba”的最长公共子串是（ ）。 A. abcba B. cba C. abc D. ab E. bcba（NOIp2008）. 设字符串S=”Olympic”，S的非空子串的数目是（ ）。选B 非空分别是Olympic Olympi lympic 。即1+2+3+4+5+6+7=28 先算长为一的有七个,这个你会吧.接着是大等二的,还

2、记的小学奥数的数线段题吧,其实这题就是让数有七个点的线段,那么公式是.点数乘段数除以二.即:7*6/2=21.再加上那个七 A. 29 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, f一般地，对于给定的两个集合A 和 集合B 的交集是指含有所有既属于 A 又属于 B 的元素，而没有其他元素的集合。一组集合的并集是这些集合的

3、所有元素构成的集合，而不包含其他元素。交集就是两个集合都有的部分，并集就是两个集合的加起来的全部。 交集: 表示方法 。交集是集合的公共部分。 并集 : 表示方法 。并集是所有 空集是不含任何元素 U=全班同学 A=班上男同学 B=班上女同学A的补集就是B（在U中）BAB线性表队列栈n个数据元素的的有限序列。其特点是除了表头和表尾外，表中的每一个元素有且仅有唯一的前驱和唯一的后继，表头有且只有一个后继，表尾有且只有一个前驱。存入数据下一个元素的地址链表顺序表队列是一种特殊的线性表，对这种线性表，删除操作只在表头(称为队头)进行，插入操作只在表尾(称为队尾)进行。队列的修改是按先进先出的原则进行

4、的。 栈是另一种特殊的线性表。这种表只在表头进行插入和删除操作。因此，表头对于栈来说具有特殊的意义，称为栈顶。相应地，表尾称为栈底。不含任何元素的栈称为空栈。栈的修改是按后进先出的原则进行的。 (NOIp2005).设栈S的初始状态为空，元素a, b, c, d, 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)某个车站呈狭长形，宽度只能

5、容下一台车，并且只有一个出入口。已知某时刻该车站状态为空，从 这一时刻开始的出入记录为：“进，出，进，进，进，出，出，进，进，进，出,出”。假设车辆入站的 顺序为 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（NOIp2007). 地面上有标号为A、B、C的3根细柱, 在A柱上放有10个直径相同中间有孔的圆盘, 从上到下次依次编号为1, 2, 3, ，将A柱上的部分盘子经过B柱移入C柱, 也可以在B柱上暂存。如果B柱上的操作记录为

6、：“进，进，出，进，进，出，出，进，进，出，进，出，出”。那么, 在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，则栈S的容量至少应该是（ ）。A. 6 B. 5 C. 4 D. 3 E. 2DD（NOIp2006）. 设栈S的初始状态为空，元素a, b, c, d, e 依次入栈，以下出栈序列不可能出现的有（ ）。A. a, b, c,

7、 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树的度也即是宽度，简单地说，就是结点的分支数。以组成该树各结点中最大的度作为该树的度，如下图的树，其度为3。树的深度组成该树各结点的最大层次，如下图的树，其深度为4。二叉树是树的一种重要形态，只有左、右子树且顺序不能颠倒。逻辑上二叉树有五种基本形态：(1)空二叉树(a)；(2)只有一个根结点的二

8、叉树(b)；(3)右子树为空的二叉树(c)；(4)左子树为空的二叉树(d)；(5)完全二叉树(e)满二叉树，一棵深度为K的二叉树有2K-1个结点，则称为满二叉树。 A B C D E F G H I J K L M N O 和满二叉树对照，只有最下面的两层结点度小于2，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树，称为完全二叉树。结论：满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。 A B C D E F G H I J K L 6） （NOIp2005）.完全二叉树的结点个数为4 * N + 3，则它的叶结点个数为（ ）。 A. 2 * N B. 2 * N - 1 C.

9、 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 的均衡的二叉树是指：如果去掉叶结点及相应的树枝，它应该是高度为 n-1 的满二叉树。在这里，树高等于叶结点的最大深度，根结点的深度为 0，如果某个均衡的二叉树共有 2381 个结点， 则该树的树高为（ ）。A. 10 B. 11 C. 12 D. 13 E. 210 1 ECB(NOIP2009)一个包含n个分支结点（非叶结点）的非空满k叉树，k=1，

10、它的叶结点数目为：( )A) nk + 1 B) nk-1 C) (k+1)n-1 D. (k-1)n+1(NOIP2010)完全二叉树的顺序存储方案，是指将完全二叉树的结点从上到下、从左到右依次存放到一个顺序结构的数组中。假定根结点存放在数组的1号位置上，则第k号结点的父结点如果存在的话，应当存放在数组中的（ ）号位置。A.2k B.2k+1 C.k/2下取整 D.(k+1)/2DC先序遍历中序遍历后序遍历（NOIp2005）.二叉树T的宽度优先遍历序列为A B C D E F G H I，已知A是C的父结点，D是G的父结点，F是I的父结点，树中所有结点的最大深度为3（根结点深度设为0），可

11、知E的父结点可能是（ ）。 A. A B. B C. C D. D E. F（NOIp2006）. 已知 6 个结点的二叉树的先根遍历是 1 2 3 4 5 6（数字为结点的编号，以下同），后根遍历是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（NOIp2007）. 已知7个节点的二叉树的先根遍历

12、是1 2 4 5 6 3 7(数字为结点的编号，以下同)， 后根遍历是4 6 5 2 7 3 1， 则该二叉树的可能的中根遍历是（ ）A. 4 2 6 5 1 7 3 B. 4 2 5 6 1 3 7 C. 4 2 3 1 5 4 7 D. 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表达

13、式a*(b+c)-d的后缀表达式是( )A) abcd*+- B) abc+*d- C) abc*+d- D) -+*abcd(NOIP2010)前缀表达式“+ 3 * 2 + 5 12 ” 的值是（ ）。A.23 B.25 C.37 D.65BC图由顶点V的集合和边E的集合组成，如下图是一无向图（顶点的前后顺序不限）。V=V1,V2,V3,V4,V5 E=(V1,V2),(V2,V3),(V3,V4),(V4,V5),(V5,V1),(V2,V5),(V4,V1) 下图是一有向图（顶点分先后顺序）。V=V1,V2,V3,V4 E=, 顶点的度顶点的度：与顶点关联的边的数目。有向图中等于该顶点

14、的入度与出度之和。入度以该顶点为终点的边的数目和出度以该顶点为起点的边的数目和 度数为奇数的顶点叫做奇点，度数为偶数的点叫做偶点。定理定理1 图中所有顶点的度数之和等于边数的2倍。因为计算顶点的度数时。每条边均用到2次。定理定理2 任意一个图一定有偶数个奇点。无向图中，若任意两个顶点之间都存在路径，则称该无向图为连通图。深度优先遍历 1)从某一顶点出发开始访问,被访问的顶点作相应的标记,输出访问顶点号. 2)从被访问的顶点出发,搜索与该顶点有边的关联的某个未被访问的邻接点 再从该邻接点出发进一步搜索与该顶点有边的关联的某个未被访问的邻接点,直到全部接点访问完毕。 广度优先遍历 1）从某个顶点出发开始访问，被访问的顶点作相应的标记，并输出访问顶点号； 2）从被访问的顶点出发，依次搜索与该顶点有边的关联的所有未被访问的邻接点，并作相应的标记。 3）再依次根据2）中所有被访问的邻接点，访问与这些邻接点相关的所有未被访问的邻接点，直到所有顶点被访问为止。（NOIp2007）. 欧拉图G是指可以构成一个闭回路的图，且图G的每一条边恰好在这个闭回路上出现一次（即一笔画成）。