18. 错题集

1. 若G是一个具有36条边的非连通无向图（不含自回路和多重边），则图G至少有_____个顶点

A . 11 B. 10 C. 9 D. 8

B P4

2. 一个具有967个结点的完全二叉树，其叶子结点个数为_____

A . 483 B. 484 C. 485 D. 486

B P6 这里不用参考答案的方法也可以求解，而且更简单。由完全二叉树的特性和定义可知，一个深度为n的满二叉树的结点数为2^n-1, 第n层的结点数为2^(n-1)。 若结点有967个结点，则完全二叉树的深度应该为10，第1到9层的结点总数为2^9 - 1 = 511。 故第10层的叶子结点数为 967 - 511 = 456。第9层的叶子结点数为 Math.floor((2^(10-1) - 456)/2) = 28, 因此叶子结点个数为 456 + 28 = 484

3. 若一棵哈夫曼树共有13个结点，则其叶子结点的个数为_____

A . 5 B. 6 C. 7 D. 8

C P6 由哈夫曼树的构造过程可知哈夫曼树是严格的二叉树，不存在度为1的结点，即 n = n0 + n2。 又由于 n0 = n2 + 1, 则 n = 2n2 + 1, 求解可得 n0 = 7, n2 = 6

本文作者： ionluo
本文链接： http://www.ionluo.cn/blog/posts/6803fa9b.html
版权声明： 本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。转载请注明出处！