【算法分析】三元组表示中要求按行的顺序存放，所有转置过程不能直接将行下标和列下标转换，还必须使得列按顺序存放。因此在A中首先找出第一列中的所有元素，它们是转置矩阵中第一行非0元素，并把它们依次放在转置矩阵三元组数组B中；然后依次找出第二列中的所有元素，把它们依次放在数组B中；按照同样的方法逐列进行，直到找出第n列的所有元素，并把它们依次放在数组B中。 【算法源代码】

void transpose(TSMatrix A,TSMatrix *B)

/*A是稀疏矩阵的三元组形式，B是存放A的转置矩阵的三元组数组*/ {int i,j,k;

B->mu=A.nu; B->nu=A.mu; B->tu=A.tu; if(B->tu>0) {j=1;

for(k=1;k<=A.nu;k++) for(i=1;i<=A.tu;i++) if(A.data[i].col==k)

{B->data[j].row=A.data[i].col; B->data[j].col=A.data[i].row; B->data[j].e=A.data[i].e; j++; } } }

4．求广义表深度的递归算法。

【算法分析】在求广义表深度的递归算法中，若结点为原子则深度为0，若是空表深度为1，否则返回头指针与尾指针所指广义表的深度最大值。 【算法源代码】

int Glist_Getdeph(Glist L) {int m,n;

if(!L->tag) return 0; else if(!L) return 1;

m=Glist_Getdeph(L->ptr.hp)+1; n=Glist_Getdeph(L->ptr.tp); return m>n?n:n; }

5．按层序输出广义表A中的所有元素。

【算法分析】层次遍历的问题，一般都是借助队列来完成的，每次从队头中取出一个元素的同时把它的下一层的孩子插入队尾，这就是层序遍历的基本思想。 【算法源代码】

void Glist_printf(Glist L) {InitQueue(Q);

for(p=L;p;p=p->ptr.tp) EnQueue(Q,p); while(!QueueEmpty(Q)) {DeQueue(Q,r); if(!r->tag)

printf(\ else

for(r=r->ptr.hp;r;r=r->ptr.tp) EnQueue(Q,r); } }

第6章 树

6.1 选择题

1．一棵具有 n个结点的完全二叉树的树高度（深度）是（ ） A）?log2n ?+1 B）log2n +1 C）? log2n ? D）log2n-1 【答案】A

2．有关二叉树下列说法正确的是（ ）

29

A）二叉树的度为2 B）一棵二叉树的度可以小于2

C）二叉树中至少有一个结点的度为2 D）二叉树中任何一个结点的度都为2 【答案】B

3．二叉树的第I层上最多含有结点数为（ ）

I I-1I-1I

A）2B）2-1 C）2 D）2-1 【答案】C

4．具有10个叶结点的二叉树中有（ ）个度为2的结点

A）8 B）9 C）10 D）11 【答案】B

5．在下述结论中，正确的是（ ） ①只有一个结点的二叉树的度为0； ②二叉树的度为2；

③二叉树的左右子树可任意交换；

④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A）①②③ B）②③④ C）②④ D）①④ 【答案】D

6．由3 个结点可以构造出多少种不同的二叉树？（ ） A）2 B）3 C）4 D）5 【答案】D

7．引入二叉线索树的目的是（ ） A）加快查找结点的前驱或后继的速度

B）为了能在二叉树中方便的进行插入与删除 C）为了能方便的找到双亲 D）使二叉树的遍历结果惟一 【答案】A

8．有n个叶子的哈夫曼树的结点总数为（ ） A）不确定 B）2n C）2n+1 D）2n-1 【答案】D

9．一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（ ） A）所有的结点均无左孩子 B）所有的结点均无右孩子 C）只有一个叶子结点 D）是任意一棵二叉树 【答案】C

【解析】先序序列是“根左右”，后序序列是“左右根”，若要这两个序列相反，只有单支树，单支树的特点是只有一个叶子结点或高度等于其结点数，故选C。

10．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ ） A）250 B）500 C）505 D）以上答案都不对 【答案】D

【解析】若每个结点均已经编号，则最大的编号为1001，其父亲结点的编号为500，那么从501到1001均为叶子结点。因此，叶子结点数为1001-500=501。故答案为D。

11．已知一棵二叉树的后序遍历序列为DABEC，中序遍历序列为DEBAC，则它的先序遍历序列为（ ） A）ACBED B）DECAB C）DEABC D）CEDBA 【答案】D

【解析】依据后序遍历序列可确定根结点为C；再依据中序遍历序列可知其左子树由DEBA构成，右子树为空；又由左子树的后序遍历序列可知其根结点为E，由中序遍历序列可知E的左子树为D，右子树由BA构成，所以求得该二叉树的先序遍历序列为选项D）。

12．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ） A）9 B）11 C）15 D）不确定 【答案】B

13．利用二叉链表存储树时，根结点的右指针是（ ） A）指向最左孩子 B）指向最右孩子 C）空 D）非空

30

【答案】C

【解析】利用二叉链表存储树时，即用孩子兄弟链表存储树，根结点的左指针指向其第一子女，根结点的右指针指向其下一兄弟，所以为空。

14．设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（ ） A）M1 B）M1+M2 C）M3 D）M2+M3 【答案】D

【解析】当森林转化为对应的二叉树时，二叉树的根结点及其左子树是由森林的第一棵树转化而来，二叉树的右子树是由森林的其余树转化而来。

15．若X是中序线索二叉树中一个有左孩子的结点，且X不为根，则X的前驱为（ ） A）X的双亲 B）X的右子树中最左的结点 C）X的左子树中最右结点 D）X的左子树中最右叶结点 【答案】C

16．n个结点的线索二叉树上含有的线索数为（ ） A）2n B）n-l C）n+l D）n 【答案】C

【解析】线索二叉树是利用二叉树的空链域加上线索，n个结点的二叉树有n+1个空链域。

17．在一棵高度为k的满二叉树中，结点总数为（ ）

k-1 k kk

A）2B）2C）2-1 D）?log2?+1 【答案】C

18．一棵树高为K的完全二叉树至少有（ ）个结点

kk-1k-1 k

A）2-1 B）2-1 C）2D）2 【答案】C

6.2 填空题

1．在二叉树中，指针p所指结点为叶子结点的条件是_____________。 【答案】p->lchild==NULL && p->rchlid==NULL

2．深度为H 的完全二叉树至少有_____________个结点；至多有_____________个结点；H和结点总数N之间的关系是_____________。

H-1H

【答案】（1）2 （2）2-1 （3）H=?log2N?+1

3．一棵有n个结点的满二叉树有_____________个度为1的结点，有_____________个分支（非终端）结点和_____________个叶子，该满二叉树的深度为_____________。 【答案】（1）0 （2）(n-1）/2 （3）(n+1）/2 （4）?log2n? +1

4．对于一个具有n个结点的二叉树，当它为一棵_____________时，具有最小高度，当它为一棵_____________时，具有最大高度。 【答案】（1）完全二叉树 （2）单支树，树中任一结点（除最后一个结点是叶子外），只有左子女或只有右子女。

5．在一棵二叉树中，度为0的结点的个数为N0，度为2的结点的个数为N2，则有N0 =_____________ 【答案】N2+1

6．已知二叉树有50个叶子结点，则该二叉树的总结点数至少是_____________。 【答案】99

【解析】在二叉树中，N0 = N2+1，所以，有50个叶子结点的二叉树，有49个度为2的结点。若要使该二叉树的结点数最少，度为1的结点应为0个，即总结点数N= N0 +N1+ N2 =99。

7．具有n个结点的满二叉树，其叶结点的个数是_____________。 【答案】(n+1）/2

8． 每一棵树都能惟一的转换为它所对应的二叉树。若已知一棵二叉树的先序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列是_____________。设上述二叉树是由某森林转换而成，则其第一棵的

31

先根次序序列是_____________。 【答案】

（1）FEGHDCB

（2）BEF（该二叉树转换成森林，含三棵树，其第一棵树的先根次序是BEF）

9．已知一棵二叉树的先序序列为ABDECFHG，中序序列为DBEAHFCG，则该二叉树的根为_____________，左子树中有_____________， 右子树中有_____________。 【答案】（1）A （2）DBE （3）HFCG

10．先根次序周游树林正好等同于按_____________周游对应的二叉树；后根次序周游树林正好等同于_____________周游对应的二叉树。 【答案】（1）先根次序 （2）中根次序

11．一个深度为k的，具有最少结点数的完全二叉树按层次，（同层次从左到右）用自然数依此对结点编号，则编号最小的叶子的序号是_____________；编号是i的结点所在的层次号是_____________（根所在的层次号规定为1层）。

k-2

【答案】（1）2+1 （2）?log2i?+1

k-1k-1k2

【解析】第k层1个结点，总结点个数是2，其双亲是2/2=2-。

12．某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点数为_____________。 【答案】69

【解析】在二叉树中，N0 = N2+1，所以，有20个叶子结点的二叉树，有19个度为2的结点。又已知该二叉树中度为1的结点有30个，则总结点数N= N0 +N1+ N2 =69。

13．有数据WG={7，19，2，6，32，3，21，10}，则所建Huffman树的树高是_____________，带权路径长度WPL为_____________。 【答案】（1）6 （2）261

14．有一份电文中共使用 6个字符：a，b，c，d，e，f，它们的出现频率依次为2，3，4，7，8，9，试构造一棵哈夫曼树，则其加权路径长度WPL为_____________，字符c的编码是_____________。 【答案】（1）80 （2）001（不惟一）

15．具有N个结点的二叉树，采用二叉链表存储，共有_____________个空链域。 【答案】N+1

【解析】在二叉树中， N= N0 +N1+ N2 ，N0 = N2+1，空分支数为2 N0+N1= N0 +N1+ （N2+1）= N+1。

16．8层完全二叉树至少有_____________个结点，拥有100个结点的完全二叉树的最大层数为_____________。 【答案】（1）128（第7层满，加第8层１个） （2）7

17．一棵树T中，包括一个度为1的结点，两个度为2的结点，三个度为3的结点，四个度为4的结点和若干叶子结点，则T的叶结点数为_____________。 【答案】21

【解析】已知该树中结点数和分支数的关系分别如下： N= N0 +N1+ N2+N3+ N4 （1） N-1= N1+ 2N2+3N3+ 4N4 （2）

由（2）式求得N=（1+2*2+3*3+4*4）+1=31，再由（1）式求得N0=21。

18． n（n大于1）个结点的各棵树中，其深度最小的那棵树的深度是_____________。它共有_____________个叶子结点和_____________个非叶子结点，其中深度最大的那棵树的深度是_____________，它共有_____________个叶子结点和_____________个非叶子结点。 【答案】（1）2 （2）n-1 （3）1 （4）n （5）1 （6）n-1

19．设y指向中序二叉线索树的一叶子，x指向一待插入结点，现x作为y的左孩子插入，树中标志域为ltag和rtag，并规定标志为1是线索，则下面的一段算法将x插入并修改相应的线索，试补充完整：(lchild，rchild分别代表左，右孩子)

x->ltag= _____________; x->lchild= _____________; y->ltag= _____________; y->lchild= _____________; x->rtag= _____________;

32