新东方网>app资讯>宁波素质中心>正文

信息学奥赛CSP-J/S 初赛知识点整理:数据结构

2023-08-17 19:46

来源:新东方素质教育中心

作者:

1.存储结构

 


数组:具有相同类型的若干变量按有序的形式组织起来,因此占用的空间是连续的。数组可分为数值数组、字符数组、指针数组、结构数组等。

bool a[x] 数组占字节数:1xy

char/unsigned (short) a[x] [y]数组占字节数:2xy

int/unsigned long/float a[x] [y]数组占字节数:4xy

(unsigned) long long/double a[x] [y]数组占字节数:8xy

 


链表:物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。相比于线性表顺序结构,链表比较方便插入和删除。(NOIP2015提高组)

 


单链表:每个节点只有一个存储直接后继结点地址的链域。

 


双向链表:既有存储直接后继结点地址的链域,称为右链域。又有存储直接前驱节点地址的链域,称为左链域。(NOIP2015提高组T13:插入结点;NOIP2010T9:删除结点)

 


2.数据结构

 


散列表:又称哈希表,通过关键码映射到表中一个位置来访问记录,以加快查找的速度。

 


栈:后进先出,栈顶允许进行插入和删除操作,栈底固定。(NOIP2015提高组)

 


队列:先进先出,队头进行删除操作,队尾进行插入操作。

 


3.树

 


树上每个元素称为节点,有一个特定的节点称为根节点。树是递归定义的,因此树的操作和应用大都是采用递归思想来解决的。

 


节点的度:一个节点的子树个数。度为0的节点称为叶节点(or 树叶),度不为0的节点称为分支节点,根节点以外的分支节点称为内部节点。树中各节点的度的最大值称为这棵树的(宽)度。

 


深度:节点的层次等于其父节点的层次数加1,树中各点的层次的最大值称为这棵树的深度。

 


森林:m(m≥0)棵互不相交的树的集合。

 


性质:

①树上任意两个节点之间有且只有一条路径

②一个拥有N个节点的树,必然存在N-1条边(NOIP2015、2017提高组)

③树中任意一条边的删除都会导致不连通

前序遍历:根左右 中序遍历:左根右 后序遍历:左右根 (NOIP2015提高组)

 


4.图

 


有向图:若有n个顶点,则最多有n(n-1)条弧,此时称作有向完全图。以顶点v为弧尾的弧的数目称作顶点v的出度,以顶点v为弧头的弧的数目称作顶点v的入度。任意两点之间有双向路径的有向图称为强连通图,否则,将其中的极大连通子图称为强连通分量。

 


无向图:若有n个顶点,则最多有n(n-1)/2条边,此时称作无向完全图。与顶点v相关的边的条数称作顶点v的度。任意两点之间都连通的无向图称为连通图,否则,将其中的极大连通图称为连通分量。

 


定理:

①图G中所有顶点的度数之和等于边数的两倍。

②任意一个图一定有偶数个奇点。

路径长度:路径上边或弧的数目。若路径上顶点没有重复出现,则称这条路径为简单路径。

 


生成树:极小连通子图。包含图的所有n个结点,但只含图的n-1条边。在生成树中添加一条边之后,必定会形成回路或环。

 


哈夫曼树:给定n个权值作为n个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。运用了贪心思想。

版权及免责声明

凡本网注明"稿件来源:新东方"的所有文字、图片和音视频稿件,版权均属新东方教育科技集团(含本网和新东方网) 所有,任何媒体、网站或个人未经本网协议授权不得转载、链接、转贴或以其他任何方式复制、发表。已经本网协议授权的媒体、网站,在下载使用时必须注明"稿件来源:新东方",违者本网将依法追究法律责任。

本网未注明"稿件来源:新东方"的文/图等稿件均为转载稿,本网转载仅基于传递更多信息之目的,并不意味着赞同转载稿的观点或证实其内容的真实性。如其他媒体、网站或个人从本网下载使用,必须保留本网注明的"稿件来源",并自负版权等法律责任。如擅自篡改为"稿件来源:新东方",本网将依法追究法律责任。

如本网转载稿涉及版权等问题,请作者见稿后在两周内速来电与新东方网联系,电话:010-60908555。