`

N结点二叉树中M个结点的连通子图个数

阅读更多
给定一棵有N个结点的二叉树。求它的所有结点数为M的连通子图数目。

设以n为根的结点数为m的连通子图数目 dp[n][m]

dp[n][m] =

dp[2n][m-1] //左孩子

+dp[2n+1][m-1] //右孩子

+SUM { dp[2n][i] * dp[2n+1][m-1-i]} //1<=i<m-1 左边有i个结点,右边有m-1-i个


input:
one tree
m

output:
SUM (dp[i][m]) //i=1...n
  • 大小: 31.7 KB
分享到:
评论

相关推荐

    数据结构习题解析

    设高度为k的二叉树上只有度为0和2的结点,则此类二叉树中所含的结点数至少为多少?** - **知识点说明:** - 二叉树的高度及其与结点数之间的关系。 - 计算二叉树最少结点数的方法。 - **解析:** - 对于高度为...

    数据结构试题1.doc

    10. 深度为6的二叉树最多有2^6 - 1 = 63个结点,因为除了根结点外,每一层的结点数最多是上一层的两倍。选项B正确。 11. 深度为k的二叉树,只有度为0和2的结点,其结点总数最少的情况是满二叉树,此时结点数为2^(k+...

    数据结构试题2.doc

    12. 删除单链表中m之后的结点,需要将m结点的next指针指向m的下一个结点的下一个结点,即p-&gt;next=p-&gt;next-&gt;next。 13. 正确的说法是:连通分量是无向图中的极小连通子图,强连通分量是有向图中的极大强连通子图。 ...

    河南科技大学《数据结构》.pdf

    "数据结构" 数据结构是计算机科学中对数据的组织、存储和...* 连通:在有向图中,从一个结点到另一个结点的路径称为连通。 数据结构是一个重要的计算机科学概念,它涉及到数据的定义、存储、操作和算法设计等方面。

    数据结构试题个人搜集

    因此,具有N个结点的连通图的生成树有N个结点和N-1条边,答案是D。 3. 算法设计目标:算法的设计通常关注可读性、可执行性和健壮性,而高空间效率是算法优化的一个目标,但并不是算法设计的基本目标。因此,答案是D...

    清华大学严蔚敏版数据结构考研要点(精华版).doc

    生成树和生成森林是图的重要概念,生成树是一个极小连通子图,它含有图中全部 n 个顶点和只有足以构成一棵树的 n-1 条边。 最小生成树是带权连通图中代价最小的生成树,在实际中具有重要用途,如设计通信网。

    数据结构考试试卷(A).doc

    10. n 个结点的无向图的边数最多有 n*(n-1)/2 条。 11. 用迪杰斯特拉算法求某一顶点到其余各顶点间的最短路径是按照路径长度非递减次序来得到最短路径。 12. 希尔排序属于插入排序,快速排序属于交换排序,堆排序...

    专升本《数据结构》考试答案.docx

    11. 二叉树的结点数:如果二叉链表有n个非空链域,那么对应的二叉树有n-1个结点,因为根结点没有父结点的链接。 12. 错误叙述:在单链表插入操作中不会发生上溢,上溢通常发生在栈或队列满时尝试插入新元素。 13. ...

    2016年暨南大学考研题.docx

    7. **完全二叉树的节点数**:高度为 n 的完全二叉树的结点数至少为 2^(n-1),因为第 n 层可能只有一个结点。 8. **生成树的概念**:在无向图 G=(V,E) 中,G' 是 G 的生成树意味着 G' 是 G 的子图,且是无环的、连通...

    数据结构试题及答案.docx

    知识点9:在含有n个项点有e条边的无向图的邻接矩阵中,零元素的个数为n^2-e 知识点10:堆的形状是一棵完全二叉树 知识点11:设单链表中结点的结构为typedef struct node { ElemType data; struct node * Link; };...

    《数据结构》期末考试题及答案.pdf

    4. **森林与二叉树的关系**:森林的第一棵树的结点个数等于二叉树右子树的结点数加1,即m-n+1。 5. **二叉树的性质**:对于任何非空二叉树,度为2的节点数总是比度为1的节点数多1,所以度为0(叶子节点)的个数为度...

    数据结构练习题1

    18. 具有n个叶子结点的哈夫曼树中,分支结点总数为n-1。 19. 装填因子α=m/n,其中m是散列表长度,n是元素个数。 20. 排序的主要目的是为了便于后续的快速查询和分析。 21. 在已知结点p后插入新结点的时间复杂度...

    数据结构试题及答案(11套最新).docx

    (10)下面关于工程计划的AOE网的表达中,不正确的选项是,A由连通网所得到的边数最少的生成树B由连通网所得到的顶点数相对较少的生成树C连通网中所有生成树中权值之和为最小的生成树D连通网的极小连通子图 ...

    期末样卷参考答案杭电计算机数据结构.pdf

    因为n个结点构成了树,所以只有n-1条边,因此剩下的n+1个指针为空。 3. **下列二叉树中,(a)可用于实现符号不等长高效编码** - **解析**: 最优二叉树(哈夫曼树)可以用于实现符号不等长高效编码,因为它的特点...

    2021数据结构期末模拟试卷及答案.docx

    2. 有n个结点的二叉树,空指针数为n+1。 3. 用于实现符号不等长高效编码的是最优二叉树。 4. 适用于有序单链表查找的是顺序查找。 5. 为避免顺序查找过程中的全表检测,可设置监视哨。 6. 具有先进先出特性的是队列...

    专升本《数据结构》-试卷-答案.docx

    17. 无向连通图的生成树至少有n-1(D)条边,因为生成树是最小的连通子图,包含所有顶点但避免环路。 18. 实现二叉树的层次遍历可以使用队列(A),按层次逐个访问节点。 19. 循环队列的入队和出队操作,需要关注队...

    杭州电子科技大学《数据结构》复习题(含答案).pdf

    - 完全二叉树是深度为k的、有n个结点的二叉树,当且仅当其每一个结点都与深度为k的满二叉树中编号从1到n的结点一一对应。 - 队列可以用链式存储结构表示,而栈通常采用顺序存储结构。 - 树的后根遍历相当于对应的...

    杭州电子科技大学数据结构期末试卷A.docx

    2. 在有 n 个结点的二叉树的二叉链表表示中,空指针数 ( )。该题考察了二叉树的存储结构和空指针数的计算。 3. 下列二叉树中,( )可用于实现符号不等长高效编码。该题考察了二叉树的应用和符号编码的实现。 ...

Global site tag (gtag.js) - Google Analytics