CSP-J/S知识点 图论理论学问

来源：深圳童程童美信息学培训学校时间：2023/8/18 17:44:11

      图论理论学问
　　根本概念
　　完全图:任意两点都有边相连，我们很简洁推出来，一张完全图的边数为[n为节点个数]
　　nx(n-1)2
　　连通图:顾名思义，连通图就是连通的图，即任意两点都能直接或间接到达，这就区别于完全图必需直接用边到达的定义。
　　树：任意两点之间的简洁路径有且只有一条。树是一棵连通且无环的图。它的边数是n-1。
　　二叉树的遍历
　　二叉树有不同的遍历方式，一般来讲，我们将其分成三类:先序遍历(也叫先根遍历)、中序遍历(中根遍历)以及后序遍历(后根遍历)。
　　先序遍历:遍历方式如下:根一左儿子一右儿子
　　中序遍历:遍历方式如下:左儿子一根一右儿子后序遍历:遍历方式如下:左儿子一右儿子一根
　　这张图的先序遍历:1245367
　　中序遍历:4251637
　　后序遍历:4526731
　　一个推论
　　先序遍历+中序遍历=一棵确定的二叉树
　　后序遍历+中序遍历=一棵确定的二叉树
　　先序遍历+后序遍历=啥也不是
　　特别二叉树及其性质
　　完全二叉树：只有zui终一层不是满的，且zui终一层的全部结点均集中在左侧。
　　图例如下：
　　满二叉树：节点个数已满
　　特别二叉树的性质：
　　1、对于一棵完全二叉树来讲，它的叶子节点为n，则节点总数为2xn-1，此结论可逆。
　　2、对于一棵满二叉树来讲，它的层数(深度)为k，则它的节点总数为2k-1，此结论可逆。
　　拓扑排序
　　简洁数据构造根本理论
　　1、栈
　　想象一个桶，你从上面往里扔砖，然后你想把某一块砖拿出来，你需要先拿出来你后扔进去的砖。这就是栈。
　　栈的根本原则是:后进先出
　　2、队列
　　想象你在排队买票，这个队伍中的人都格外有素养，都自觉排队而且不会提前离开队伍。这样就只能从队首买完票再离开，从队尾进入队伍。队列的根本原则是:先进先出。
　　队列有两个口，所有元素入队从tail，出队从head，所以一定满足规律，先进先出！
　　3、链表
　　链表分两种:单向链表和双向链表。
　　单向循环列表
　　双向循环列表
　　4、字符串
　　字符串子串的概念:字符串是一串字符。
　　它的子串被定义为:字符串中任意个连续的字符组成的子序列。
　　字符串子串个数的计算公式：
　　nx(n+1)2+1
　　时空简单度的计算
　　时间简单度
　　渐进时间简单度用符号0表示。一个程序的语句执行次数可以用一个代数式表示，那么我们取这个代数式的zui高次项且无视此项系数作为时间简单度。假设一个程序的语句执行次数为2n3+3n2+n+7，那么这个程序的渐进时间简单度为0(n3)
　　计算非递归程序的简单时间度
　　数循环
　　常数
　　常数即为我们无视掉的0 0中zui高次项的系数与低次项所带来的时间消耗。
　　空间简单度
　　类比时间简单度。看开空间开了多大。
　　计算空间占用量
　　依据我们以上说过的计算机存储单位的学问:一个int占用的内存是4B，所以我们把开的int乘上4，再除以1024就是KB，同理，再除1024就是MB。
　　公式：n为元素个数，m为zui终答案[以MB为单位]
　　M=4n1024×1024
　　批注：一般来讲，竞赛中所给的256MB内存可以开6x107个nt类型的变量。另外，大数组必需开全局变量。假设扔在主函数里极简洁爆栈。

尊重原创文章，转载请注明出处与链接：http://www.peixun360.com/2476/news/652374/违者必究！ 以上就是深圳童程童美信息学培训学校 小编为您整理 CSP-J/S知识点 图论理论学问的全部内容。