68. 已知无向树T有5片树叶, 2度与3度顶点各1个, 其余顶点的度数均为4. 求T的阶数n。 答案：
69. 求下列树的树根、树叶、树高、内点、分枝点、各个结点的层数
答案：
a是树根.
b,e,f,h,i是树叶. c,d,g是内点. a,c,d,g是分枝点.
a为0层;1层有b,c; 2层有d,e,f; 3层有g,h; 4层有i. 树高为4.
70. 求下列树的树高、内点数、分枝点树、几叉树？
第21页， 共24页
答案： 4、5、6、4
71. 下列树是不是完全二叉树？是不是满二叉树？
答案：
4叉树、完全3叉树
72. 求下列二叉树的前序、中序、后序遍历
答案：
前序：a → b → d → e → h → c → f → g → i → j 中序：d → b → h → e → a → f → c → i → g → j 后序：d → h → e → b → f → i → j → g → c → a
73. 求下列二叉树的前序、中序、后序遍历 a
b c
def ki hjml
答案：
g第22页， 共24页
74. 构造下列数的排序二叉树：15, 3, 1, 6, 18, 7, 10, 20 答案：
75. 求树叶权为4，2，3，5，1的最优树。 答案：
最优树的权重W(T)为：
1×3 + 2×3 + 3×2 + 4×2 + 5×2 =33
76. 求带权图的最小生成树。
答案：
第23页，共24页
这棵最小生成树的权为:1+1+2+2+3+4=13.
77. 求下图的邻接矩阵
答案：
?01101? ?10100? ?? A??11001??? 00001?? ??10110??
78.写出下列表达式的“波兰表示式” ((a – 4b) c – (7d + b)) / (c + 5a) 答案：先表示成二叉树的形式
/
-+ cX+X
cXba5-
7daX
b4
再对二叉树进行前序遍历即的波兰式为：/ –×– a×4bc +×7db + c×5a
第24页， 共24页