2．证明：由于深度为k的二叉树的最大结点数为二叉树上每一层的最大结点数之和，而二叉树上第i层的最大结点数为2i-1。则
?(第i层的最大结点数)??2i?1i?1kki-1?2k?1
3. 证明：设n0为叶子结点个数，n2为度为2的结点个数，
则由二叉树的性质2可知： n2= n0－1
又：满二叉树中只有度为2的结点和叶子结点， 所以满二叉树中的结点总数n= n2+ n0=2 n0－1 又：二叉树中的分支数B=n－1 所以：B=2 n0－1－1=2(n0－1)
4.
wpl=(16+17)*2+(9+14+15)*3+6*4+(2+3)*5=229 （四）算法题：
1． void output(BiTree t)
{
if (t){
output(t->lchild); printf(t->data); output(t->rchild); } }
2. void exchange(BiTree t)
{
BiTree temp; if (t){
temp=t->lchild; t->lchild= t->rchild; t->rchild=temp; exchange (t-> lchild); exchange (t->rchild); } }
3. int depth(BiTree t)
{
int l,r; if (!t) return 0; l= depth (t->lchild); r= depth (t->rchild); return (l>=rl:r)+1; }
4. void leaf(BiTree t) {
if (!t) return 0;
if (!t->lchild && !t->rchild) return 1; return leaf(t->lchild)+leaf(t->rchild); }
第八章章节练习答案
（一）选择题： , A , C , D
（二）判断题: 1. √ 2. √ 3.× 4. × 5. √ 6. √ （三）问答及算法题：
1. 图中共有3个顶点，如果是有向图，该图共有5条弧；如果是无向图，该图共有3条边。
?0?0??02.（1）邻接矩阵： ??0?0???01000100100000010010000000?0??0?? 0?1??0??（2）可能的拓扑序列为：156234 （注意4一定是最后一个，2一定在1和5后） （3）123456 （4）562431
3. 一个拓扑排序序列：C1 C3 C2 C5 C4
4．算法： int count (AlGraph G)
{
for (i=0; i<; i++) visited[i]=false; sum=0; for (i=0; i< ; i++)
if (!visited[i]) {sum++; dfs (G, i);} return sum; }
void dfs (AlGraph G, int i) {
visited[i]=true;
for (p=[i].firstarc; p; p=p->nextarc) { k=p->adjvex;
if (!visited[k]) dfs(G, k);
}
}
第九章章节练习答案
（一）选择题： 6. B 7. B （二）判断题：1.× 2. × 3. × 4. √ （三）问答题：
1.（1）
ASL=(1+2*2+3*3+3*4+2*5)/11=36/11 (2) 2_3树:
(3) 删除55: 删除84:
2．
ASL=(1+1+1+2+5+1+1+4)/8=16/ 8=2
3.
3、
哈希表
0 11
1 2 13 1
3 24 2
4 5 5 1
6 28 1
7 72 2
8 16 4
9 18 3
10 7 4
比较次数 1
ASL=（1+1+2+1+1+2+4+3+4）/9=19/9
4. 用链地址法处理冲突:（注意链表的有序性）
ASL=(7*1+4*2+1*3)/12=18/12
第十章章节练习答案
（一）选择题： （二）判断题：1.× 2.√ 3.× 4.√ （三）问答题：
1． 应依据“三者取中”的原则，比较第一个、最后一个和中间位置处记录的关键字，取关键字居中值的记录作为枢轴记录。 2．第一个序列是堆
第二个序列不是堆。调整为堆后的序列为{35，33，26，29，19，12，22} 3．初始序列：70，83，100，65，10，9，7，32
直接插入排序每一趟结束时的关键字状态：
第一趟：（70，83），100，65，10，9，7，32 第二趟：（70，83，100），65，10，9，7，32 第三趟：（65，70，83，100），10，9，7，32 第四趟：（10，65，70，83，100），9，7，32 第五趟：（9，10，65，70，83，100），7，32
郑州大学远程教育学院数据结构试题及答案
