数据结构基础知识.ppt

文档介绍：数据结构基础知识
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 先算长为一的有七个,,还记的小学奥数的数线段题吧,其实这题就是让数有七个点的线段,那么公式是...:7*6/2=
A. 29 B. 28 C. 16 D. 17 E. 7
(NOIp2005)设全集I = {a, b, c, d, e, f, g, h},集合A∪B = {a, b, c, d, e, f}, A∩C= {c, d, e}, A∩~B= {a, d},那么集合A∩B∩C 为( )。A. {c, e} B. {d, e} C. {e} D. {c, d, e} E. {d, f}
一般地,对于给定的两个集合A 和集合B 的交集是指含有所有既属于 A 又属于 B 的元素,而没有其他元素的集合。一组集合的并集是这些集合的所有元素构成的集合,而不包含其他元素。交集就是两个集合都有的部分,并集就是两个集合的加起来的全部。交集: 表示方法∩。交集是集合的公共部分。并集: 表示方法∪。并集是所有空集是不含任何元素
U=全班同学 A=班上男同学 B=班上女同学
A的补集就是B(在U中)
B
A
B
线性结构
线性表
队列
栈
线性表
n个数据元素的的有限序列。其特点是除了表头和表尾外,表中的每一个元素有且仅有唯一的前驱和唯一的后继,表头有且只有一个后继,表尾有且只有一个前驱。
线性表的修改
存入数据
下一个元素的地址
链表
顺序表
队列
队列是一种特殊的线性表,对这种线性表,删除操作只在表头(称为队头)进行,插入操作只在表尾(称为队尾)进行。队列的修改是按先进先出的原则进行的。
队列的修改
栈
栈是另一种特殊的线性表。这种表只在表头进行插入和删除操作。因此,表头对于栈来说具有特殊的意义,称为栈顶。相应地,表尾称为栈底。不含任何元素的栈称为空栈。栈的修改是按后进先出的原则进行的。