因证明题部分较为简单，大多为记忆内容，因此同种证明思路不过多赘述。
1. n（n>1）个权值构造的Huffman树中不存在度为1的节点。
（反证法，1）
哈夫曼树（最优树）：带权路径最短的树。
假设存在一个度为1的节点，即该树有一棵子树。
设该节点为A，其子树为B。可将AB合并成一个节点，
则B以下叶子节点的带权路径减少，树的带权路径长度减少，
显然合并后的树，带权路径长度小于原树，
与原树是Huffman树的条件相悖，故假设不成立。
2. 若（u，v）是一条最小权值的边，其中u∈U，v∈V-U，则必存在一棵包含（u，v）的最小生成树。
（反证法， 2）
令N = （V，{E}），v∈V
设：连通网网N中的任何一棵最小生成树都不包含（u，v），T是N中的一棵最小生成树。
由生成树定义可知：
①当把边（u，v）加入T中，T中必存在一条包含（u，v）的回路。
②T中必存在另一条边（u1，v1）， u1∈U，v1∈V。
则u和u1之间，v和v1之间均有路径相通。
删去边（u1，v1），即可消除上述回路，得到新生成树【T1】.
因为（u，v）的代价不高于（u1，v1），所以【T1】的代价不高于T，
所以【T1】是包含（u，v）的一棵最小生成树，与假设矛盾。
因此，问题得证。
3. n个节点，k条边的非联通无向图是一个森林（n>k），证：森林有n-k棵树。
设：森林有x棵树，每棵树的节点数为x1，x2，... xn；
除根节点外，每个节点都有唯一的一条分支（边）与之对应，即：总边数 = 总节点数 -1；
（注：几道证明题都用到这句话，也是围着这句话展开的证明）
每棵树的边数为(x1-1)，(x2-1)，... (xn-1)；
则 n = x1 + x2 + ...+xn；
k = (x1-1) + (x2-1)+ ... + (xn-1)=(x1 + x2 + ... + xn) - x = n - x
所以： x = n - k
4. 高度为h的二叉树节点数不超过2^h-1。
（归纳法, 1）
令n表示二叉树的节点总数
①高度h = 1； n = 1 = 2^1 - 1；
②h≤k； 设 n ≤ 2^k - 1；
③h = k + 1；
定义可知：第i层最多有2^( i-1 )个节点。
n + 2^k【n表示k层节点总数，2^k表示k+1层最多节点数，相加为k+1层最多节点数】
≤2^k -1 + 2^k = 2^( k+1 ) -1;
所以，k+1层总节点数≤2^( k+1 ) -1;
综上，由归纳法得证，高度为h的二叉树节点数不超过2^h-1.
5. 高度为h的2-3B树中叶子节点数目在2^(h-1) 到 3^(h-1)之间。
（归纳法，2）
令N表示2-3B树的叶子节点总数
①h = 1，N = 1； 2^(1-1) ≤ N ≤ 3^(1-1) ，不等式成立。
②h ≤ k， 设 2^(k-1) ≤ N ≤ 3^(k-1)；
③h = k+1，
根据定义，2-3B树的子树有2~3棵，分别记为：r1，r2，r3。
对于每棵子树，高度都小于等于k，
由②可知，每棵树的叶子节点数目：2^(k-1) ≤ N ≤ 3^(k-1)；
各子树的叶子节点都是原树的叶子节点，分两种情况：
⑴最少有2棵子树，每棵子树叶子节点最少为2^(k-1)，所以N ≥ 2*2^(k-1) = 2^k
⑵最多有3棵子树，每棵子树叶子节点最多为3^(k-1)，所以N ≤ 3*3^(k-1) = 3^k
所以， 2^k ≤ N ≤ 3^k;
综上，由归纳法得：高度为h的2-3B树中叶子节点数目在2^(h-1) 到 3^(h-1)之间。
结语：大体分为这5种，后续有值得补充的再补充上。
未经允许不得转载：考研网上 - 考研网上辅导班有用吗 > 大连海事大学计算机考研——证明题部分(续)
热门信息
阅读 (126)
1 南京大学2022年硕士研究生报考人数近3万人阅读 (76)
2 湖北16所大学2021年保研率排行榜出炉,其中九高校超5%阅读 (52)
3 这所大学也太牛了!12个女、5个男学霸宿舍,考研到清华北大等名校阅读 (16)
4 2021考研类别有变,本年该专项研讨生扩招至8000人!阅读 (16)
5 国内研究生一般需要读几年 为什么有的需要2年,而有的需要3年