大连海事大学计算机考研——证明题部分(续)

因证明题部分较为简单,大多为记忆内容,因此同种证明思路不过多赘述。

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种,后续有值得补充的再补充上。

推荐文章

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

|京ICP备2022015867号-11