数据结构（C语言版）习题解答

思路：采用递归进行比较判断

bool BiTreeSimilar (BiTree T1,BiTree T2) {

if(T1==Null&&T2==Null) return 1;

else if(T1==Null || T2==Null) return 0; else

return (BiTreeSilimar(T1->lchild,T2->lchild)&&BiTreeSimilar(T1->rchild,T2->rchild)); }

6.21 写出统计树中叶子结点个数的算法，树用孩子兄弟链表表示。

思路：在孩子兄弟链表中，若结点的firstchild为Null，则为叶子结点；采用递归方法。 int CountLeaves(Tree T，int &num)//num传递的初值为0

{

if(T->nextsibling!=Null)

num+=CountLeaves (T->nextsibling); if(T->firstchild!=Null)

num+=CountLeaves(T-> firstchild); else

num+=1;//firstchild域为空，则为叶子结点 return num; }

第七章 图

V1 7.1 已知有向图如图7-1所示， 请给出该图的

(1)邻接矩阵示意图 (2)邻接表示意图 (3)逆邻接表 (4)所有强连通分量

V5 V6 V2 V4 V3 图7-1

(1) 邻接矩阵

?0?1??0??0?1???100000?00100??10001??01011?00000??10010??

（2）邻接表

0v11v22v3345v4v5v6<35504014<<2<<10<

（3）逆邻接表

0v11v22v3345

553153421<<<

V1 V5 V6 V2 V4 V3

7.2 已知图G的邻接矩阵如图7-2所示。写出该图从顶点1出发的深度优先搜索序列和广度优先搜索序列，并画出相应的深度优先生成树和广度优先生成树。

1 2 3 4 5 6 7 8 9 1 0 0 0 0 0 0 1 0 1 2 0 0 1 0 0 0 1 0 0 3 0 0 0 1 0 0 0 1 0 4 0 0 0 0 1 0 0 0 1 5 0 0 0 0 0 1 0 0 0 6 1 1 0 0 0 0 0 0 0 7 0 0 1 0 0 0 0 0 0 8 1 0 0 1 0 0 0 0 1 9 0 0 0 0 1 0 1 0 0 10 1 0 0 0 0 1 0 0 0 图7-2

深度优先序列：1 7 3 4 5 6 2 10 9 8

17348596102深度优先生成树：

广度优先序列：1 7 9 3 10 5 4 8 6 2

17931054862广度优先生成树：

10 0 0 0 0 1 0 1 0 1 0 9.1若对大小均为n的有序顺序表和无序顺序表分别进行顺序查找，试在下列三种情况下分别讨论两者在等概率时平均查找长度是否相同？

（1）查找不成功，即表中没有关键字等于给定的值K的记录； （2）查找成功，且表中只有一个关键字等于给定值K的记录；

（3）查找成功，且表中有若干个关键字等于给定值K的记录，要求找出所有这些记录。 解：

对有序顺序表： 1.

1n+21+2+...+(n+1)=[]2 （将该项看作一项混入原有序列中，问题转变成 n+1n+1个元素序列的成功查找问题） 2．

1n+11+2+...+n= []n23.

1n-k+21+2+...+n-(k-1)= 将此K项看作一项 []n-(k-1)2对无序顺序表：

1. n 2.

1n+11+2+...+n= []n23.

?ni=(n+k)(n-k+1)2i=k1n+k= 考虑最后一个记录的出现位置

n-k+12

9.3 画出对长度为17的有序表进行折半查找的判定树，并分别求其等概率时查找长度和查找失败的ASL。

1591?12?23?44?85?2)17 (17176=(4?75?24?75?)2 增加虚结点 ASL1818解：ASL=9413261115135710121416817