试题详情
- 简答题证明：生成树中最长路径的起点和终点的度均为1。
- 用反证法证明。
设v1，v2，…，vk是生成树的一条最长路径，其中，v1为起点，vk为终点。若vk的度为2，取vk的另一个邻接点v，由于生成树中无回路，所以，v在最长路径上，显然v1，v2，…，vk，v的路径最长，与假设矛盾。所以生成树中最长路径的终点的度为1。
同理可证起点v1的度不能大于1，只能为1。 关注下方微信公众号，在线模考后查看
热门试题
- 将数量级O（1），O（N），O（N2），
- 假定一个待散列存储的线性表为（32，75
- 下述算法的功能是什么？
- 当向一个大根堆插入一个具有最大值的元素时
- 在头指在单链表中，指针p指向元素为x的结
- 对于一个栈，给出输入项A,B,C,D，如
- 二维数组A[m][n]采用行序为主方式存
- 一个顺序表的第一个元素的存储地址是90，
- 对于下图，试给出一种拓扑序列，若在它的邻
- 线性结构是1对1的结构，以下结构属于线性
- 对长度为n的线性表进行顺序查找，在最坏情
- 栈是后进先出（先进后出）的（）。
- 向一个有127个元素的顺序表中插入一个新
- 在树的概念中，树的某结点的直接后继称为该
- 堆排序
- 三元组表示法，结点间的顺序按矩阵的列优先
- 顺序栈的上溢是指（）。
- 已知10个数据元素（50，30，15，3
- 在串的运算中，EqualStr（aaa，
- 不含任何结点的空树（）。