信息学奥赛CSP-J/S 初赛 数据结构

来源：重庆信息学奥赛编程培训学校时间：2023/8/19 11:50:06

　　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)。哈夫曼树是带权路径长度较短的树，权值较大的结点离根较近。运用了贪心思想。

尊重原创文章，转载请注明出处与链接：http://www.peixun360.com/1866/news/652473/违者必究！ 以上就是重庆信息学奥赛编程培训学校 小编为您整理 信息学奥赛CSP-J/S 初赛 数据结构的全部内容。