一、简答题

共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;

    }