一、简答题
共60分。
1、如果一棵树有n1个度为1的节点，n2个度为2的节点，…，nm个度为m的节点，则该树共有多少个叶子节点?(给出计算公式和结果)
2、已知关键字序列(55，31，11，35，46，73，63，02，07)，从空树开始构造一棵平衡二叉树，画出每加入一个新结点时二叉树的形态。
3、采用折半查找方法在关键字序列(5，23，45，58，67，74，80，85，96)中查找关键字45，给出查找过程，并计算在等概率情况下查找成功的平均查找长度。
4、已知一棵二叉树的中序遍历结点序列为DGBAECHIF，后序遍历结点为GDBEIHFCA。
(1)试画出该二叉树
(2)试画出该二叉树的中序线索树
(3)试画出该二叉树对应的森林
5、已知一个有向图如下所示：
(1)给出该图的邻接表表示；
……此处隐藏8870个字……
pos=i+1;
}
}
print(s,pos,s.size());
cout＜＜endl;
}
int main() {
int T;
scanf("%d",&T);
getchar();
while(T--){
string str;
getline(cin, str);
reverse(str);
}
return 0;
}