第六章树和二叉树（下载后用阅读版式视图或web版式可以看清）
习题
一、选择题
1．有一“遗传”关系：设x是y的父亲，则x可以把它的属性遗传给y。表示该遗传关系最适合的数据结构为( )。
A.向量
B.树C图 D.二叉树
2．树最合适用来表示( )。
A.有序数据元素 B元素之间具有分支层次关系的数据
C无序数据元素 D.元素之间无联系的数据
3．树B的层号表示为la，2b，3d，3e，2c，对应于下面选择的( )。
A. la (2b (3d,3e),2c)
B. a(b(D,e),c)
C. a(b(d,e),c)
D. a(b,d(e),c)
4.高度为h的完全二叉树至少有( )个结点，至多有( )个结点。
A. 2h_l
B.h C．2h-1 D. 2h
5.在一棵完全二叉树中，若编号为f的结点存在右孩子，则右子结点的编号为( )。
A. 2i
B. 2i-l
C. 2i+l
D. 2i+2
6.一棵二叉树的广义表表示为a(b(c)，d(e(，g(h))，f))，则该二叉树的高度为( )。
A.3
B.4
C.5
D.6
7.深度为5的二叉树至多有( )个结点。
A. 31
B. 32
C. 16
D. 10
8.假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为( )个。
A. 15
B. 16
C. 17
D. 47
9.题图6-1中，( )是完全二叉树，( )是满二叉树。
10.在题图6-2所示的二叉树中：
(1)A结点是
A.叶结点 B根结点但不是分支结点
C根结点也是分支结点 D.分支结点但不是根结点
(2)J结点是
A.叶结点 B．根结点但不是分支结点
C根结点也是分支结点 D.分支结点但不是根结点
(3)F结点的兄弟结点是
A.E
B.D C．空 D.I
(4)F结点的双亲结点是
A.A
B.B
C.C
D.D
(5)树的深度为
A.1
B.2
C.3
D.4
(6)B结点的深度为
A.1
B.2
C.3
D.4
(7)A结点所在的层是
A.1
B.2
C.3
D.4
11.在一棵具有35个结点的完全二叉树中，该树的深度为( )。
A.5
B.6
C.7
D.8
12. 一棵有124个叶结点的完全二叉树，最多有( )个结点。
A．247 B．248 C．249 D．250
13.用顺序存储的方法将完全二叉树中所有结点逐层存放在数组R[1…n]中，结点R[i]若
有左子树，则左子树是结点( )。
A. R[2i+l]
B. R[2i]
C.R[i/2]
D. R[2i-1]
14.在一非空二叉树的中序遍历序列中，根结点的右边( )。
A.只有右子树上的所有结点
B.只有右子树上的部分结点
C.只有左子树上的部分结点
D.只有左子树上的所有结点
15．一棵度为m的树中，有n i个度为1的结点，有n2个度为2的结点……，有n m个度为m的结点，则该树的叶结点数为( )。
A. n1+n2+...+n m
B. (m-l) n m+...+n2+1
C.n1+n2+1
D. n l-n2
16.已知某二叉树的中序遍历序列是debac，后序遍历序列是dabec，它的前序遍历序列
是( )。
A. acbed
B. decab
C. deabc
D. cedba
17.在一棵二叉树的二叉链表中，空指针域等于所有非空指针域数加( )。
A.2
B.1
C.0
D.-1
18.线索二叉树是一种( )结构。
A.逻辑B．逻辑和存储C．物理 D.线性
19.由权值分别是8，7，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为( )。
A. 23
B. 37 C．46 D. 43
20.设T是哈夫曼树，具有5个叶结点，树T的高度最高可以是( )。
A.2
B.3
C.4
D.5
二、填空题
1.对于一棵具有n个结点的树，该树中所有结点的度数之和为____。
2.在树型结构中，树根结点没有____结点，其余每个结点有且只有____个前驱
结点：叶子结点没有____结点，其余每个结点可以有____后继结点。
3.有一棵树如题图6-3所示，回答下面的问题。
这棵树的根点是____；叶子结点是____；结点k3的度是____；结点k3的
子女是____；结点k3的父结点是____；这棵树的度为____；这棵树的深度是
____。
4.假定一棵树的广义表表示为A(B(E)，C(F(H，I，J，G)，D)，则该树的度为____，树的深度为____，终端结点的个数为____，单分支结点的个数为___ _，双分支结点的个数为____，3分支结点的个数为____，C结点的双亲结点为____，其孩子结点为____。
5.一棵深度为h的满k叉树有如下性质：第h层上的结点都是叶子结点，其余各层上的每个结点都有k棵非空子树。
如果按层次顺序（同层自左至右）从1开始对全部结点编号，则：
(1)第i层结点数目是____。
(2)编号为n的结点的双亲结点（若存在）的编号是____。
(3)编号为n的结点的第i个孩子结点（若存在）的编号是____。
(4)编号为n的结点有右兄弟的条件是____：其右兄弟的编号是____。
6．前序遍历一棵树相当于____树中对应的二叉树，后序遍历一棵树则相当于树中对应的二叉树。
7．二叉树的遍历分为____ ，树与森林的遍历包括____。
8．一棵二叉树的第i(i>=1)层最多有____个结点；一棵有n(n>0)个结点的满二叉树共有____ 个叶子和____个非终端结点。
9.在一棵二叉树中，假定双分支结点数为5个，单分支结点数为6个，则叶子结点为____个。
10．在一棵二叉树中，第五层上的结点数最多为____。
11.对于一棵具有n个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为____个，其中____个用于链接孩子结点，____个空闲着。
12.前序遍历的顺序是ABDGEHICFJ，则二叉树的根是____。
13.从概念上讲，树与二叉树是两种不同的数据结构，将树转化为二叉树的基本目的是____
14.结点最少的树为____ ，结点最少的二叉树为____。
15.一棵完全二叉树按层次遍历的序列为ABCDEFGHI，则在前序遍历中结点E的直接前驱为____ ，后序遍历中结点B的直接后继是____。
16.某二叉树的中序遍历序列为ABCDEFG，后序序列为BDCAFGE，则该二叉树结点的前序序列为____，该二叉树对应的森林包括____棵树。
17.用一维数组存放的一棵完全二叉树如题图6-4所示。
则后序遍历该二叉树时结点访问的顺序为____。
18.由n个权值构成的哈夫曼树共有____个结点。
19.由带权为3，9，6，2，5的5个叶子结点构成一棵哈夫曼树，则带权路径长度为____。
20.设F是一个森林，B是由F转换得到的二叉树，F中有n个非终端结点，则B中右指针域为空的结点有____个。
21.二叉树的存储结构分为____ ，树的存储结构分为____。
三、判断题
1．树中任意结点的子树不必是有序的。( )
2．树可以看成特殊的无向图。( )
3．可以使用双链表表示树型结构。( )
4．顺序存储方式只能用于存储线性结构。( )
5．完全二叉树的某结点若无左孩子，则必是叶结点。( )
6．在叶子数目和权值相同的所有二叉树中，最优二叉树一定是完全二叉树。( )
7．由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树。( )
8．二叉树的前序遍历序列中，任意一个结点均处在其子树结点的前面。( )
9．二叉树的前序和后序遍历序列能惟一确定这棵二叉树。( )
10.中序线索二叉树中，右线索若不为空，则一定指向其父结点。( )
四、算法和操作题
1．假定一棵二叉树广义表表示为a(b(c)，d(e，D)，分别写出对它进行前序、中序、后序遍历的结果。
前序：
中序：
后序：
2．已知一棵二叉树的中序和后序序列，求该二叉树的高度和双支、单支及叶子结点数。
中根序列：c，b，d，e，a，g，i,h,j，f
后根序列：c，e，d，b，i，j，h，g，fa
高度：双支：单支：叶子：
3．已知一棵树边的集合为{
(1)哪个是根结点？
(2)哪些是叶子结点？
(3)哪个是结点G的双亲？
(4)哪些是结点G的祖先？
(5)哪些是结点G的孩子？
(6)哪些是结点E的子孙？
(7)哪些是结点E的兄弟？哪些是结点F的兄弟？
(8)结点B和N的层次号分别是什么？
(9)树的深度是多少？
(10)以结点C为根的子树的深度是多少？
4．将算术表达式((a+b)+c*(d+e)+f*(g+h)转化为二叉树。
5. 一棵二叉树的结点数据采用顺序存储结构，存储于数组BT中，如题表6-1所示。画出该二叉树的链接表示形式。数组BT的存放形式是相对于满二叉树中编号为数组下标值的结点值。若该结点不存在，则取0值。
6．假设前序遍历某棵树的结点次序为SACEFBDGHIJK；后序遍历该树的结点次序为CFEABHGIKJDS，请画出这棵树。
7．已知一棵树如题图6-5所示，将其转换为其孩子兄弟表示的二叉树。并画出该二叉树的后序线索二叉树。
8．试找出分别满足下列条件的所有二叉树：
(1)前序遍历序列和中序遍历序列相同。
(2)中序遍历序列和后序遍历序列相同。
(3)前序遍历序列和后序遍历序列相同。
9．已知信息为“ABCD BCD CB DB ACB”，请按此信息构造哈夫曼树，求出每一字符的最优编码。
10.己知中序线索二叉树采用二叉链表存储结构，链结点的构造为：
其中若ltag为0，则lchild指向结点的前驱，否则lchild指向左孩子结点；若rtag为0，则rchild指向结点的后继，否则rchild指向右孩子结点。下面的算法返回x所指结点的直接后继结点的位置。若该算法有错，则请改正错误；若无错，请写“正确”二字。
BiTree INSUCC (BiTree x)
{ s=X->rchild;
if（s->rtag）
while （s->ltag）
s=s->rchild;
return s；
)
五、算法设计题
1．编写对二叉树进行中序遍历的非递归算法，并对算法执行题图6-6所示的二叉树的情况进行跟踪（即给出各阶段栈的变化及输出的结点序列）。
栈已经定义：InitStack(S)（初始化）、Empty(S)（判栈空）、Push(S，p)（入栈）、Pop(S，p)（出栈）等操作。
2．假设在表示一棵二叉树的二叉链表上增加两个域：双亲域用于指示其双亲结点，标志域flag（可取0...2）的值，用以区分在遍历过程中到达该结点时继续向右或向左或访问该结点。试以此存储结构编写不用栈进行后序遍历的递归形式的算法。
3．一棵具有n个结点的完全二叉树，以一维数组作为存储结构，试设计一个对该完全二叉树进行前序遍历的算法。
4．设中序线索树的结点由5个域组成。
Info：给出结点的数据域。
LT:标志域，为0或1。
LL：当LT为1时，给出该结点的左孩子的地址。
当LT为0时，给出按中序遍历的前驱结点地址。
RT:标志域，为0或1。
RL：当RT为1时，给出该结点的右孩子的地址。
当RT 为O时，给出按中序遍历的后继结点地址。
请编写程序，在具有上述结点结构的中序线索二叉树上，求某一结点p按后序遍历次序的后继结点的地址q，设该中序线索二叉树的根结点地址为r。
另外，请注意必须满足：
(l)额外空间的使用只能为O(1)。
(2)程序为非递归形式。
5．假设二叉树采用链接方法存储，编写一个函数按凹入表表示法打印出该二叉树。
6．给出中序线索树的结点结构，设计算法在不使用栈和递归的情况下前序遍历一棵中序线索树，并分析它的时间复杂度。
7．以二叉链表为存储结构，写出交换各结点左右子树的算法。
8．假设二叉树采用链接方法存储，编写一个函数按凹入表表示法打印出该二叉树。
第六章树和二叉树
第6章树和二叉树
一、选择题（参考答案）
1．B 2．B 3．C 4．A，C 5．C
6．C 7．A 8．B 9．A，B
10. (1)C (2)A (3)C (4)A (5)C (6)A (7)C
11．B 12.A 13．B 14．A 15．B
16．D 17．A 18．C 19．D 20．D
二、填空题（参考答案）
1．树的总结点数-1。
2．前驱：1，后继，任意多个。
3. k l, k2, k4, k5, k7,2,k5, k6, k l,3,4。
4.3，4，6，1，1，2，A，F，G。
5.(1) k i-l, (2) ⎣⎦, (3) n-l×k+n+1,(4)i≠nk+l(n=0,l,2，…),n+1.
6．前序遍历，中序遍历。 7．前序，中序，后序，前序，后序。
8. 2i-1，「2/n,⎣2/n⎦. 9.6个。
10. 160 11. 2n，n-l，n+l。
12．A
13.树可采用二叉树的存储结构并可利用二叉树的已有算法解决树的有关问题。
14.只有1个结点的树，空树。 15.I，F。
16.前序遍历序列为：EACBDGF，森林包括1棵树。
17. HIDJKEBLFGCA0 18. 2n-l。
19. 560 20．n+l。
21.顺序存储和链式存储，双亲链表表示法，孩子链表表示法，孩子兄弟链表表示法
三、判断题
1. √
2. √
3. √
4.×
5. √
6.×
7.×
8. √
9.× 10.×
四、算法和操作题
1．假设一棵二叉树广义表表示为a(b(c)，d(e，D)，分别写出对它进行前序、中序、后序遍历的结果。
【解答】前序：a，b，c，d，e，D
中序：c，b，a，e，d，D
后序：c，b，e，D，d，a
2．已知一棵二叉树的中序和后序序列，求该二叉树的高度和双支、单支及叶子结点数。
【解答】中序序列：c，b，d，e，a，g，i，h，j，f
后序序列：c，e，d，b，i，j，h，g，f，a
由中序和后序（前序）遍历序列可惟一确定一棵二叉树，基本思想是后序（前序）定根，中序分左右。由后序序列可知该树的根结点为a，由中序遍历序列可知该树的左子树为{c，b，d，e}，右子树为{g，i，h，j，f）;再由后序序列可知该树的左子树的根结点为b，右子树的根结点为f．再由中序遍历序列可知b结点的左子树为{c}，右子树为{d，e）;再由后序遍历序列可知右子树{d，e}的根结点为d，再由中序遍历序列可知d的左子树为空，右子树为{e}。对以f为根结点的子树可做类似的分析。最后得到由中序和后序序列决定的二叉树为：
a(b(c，d(，e))，f(g(，h(i，j))))，由此可知该树：
高度：5 双分支：3 单分支：3 叶结点：4。
3．已知一棵树边的集合为{
【解答】根据边集画出的树如下所示：
(1)根结点是：A。
(2)叶子结点是：D，M，N，F，J，K，L。
(3)结点G的双亲是：C。
(4)结点G的祖先是：A，C。
(5)结点G的孩子是：J，K。
(6)结点E的子孙是：I，M，N。
(7)结点E的兄弟是：D;结点F的兄弟是：G，H。
(8)结点B和N的层次号分别是：2，5。
(9)树的深度是：5。
(10)以结点C为根的子树的深度是：3。
4．将算术表达式((a+b)+c*(d+e)+f*(g+h)转化为二叉树。
【解答】转化成如下二叉树：
5．-棵二叉树的结点数据采用顺序存储结构，存储于数组BT中，如题表6-1所示。画出该二叉树的链接表示形式。数组BT的存放形式是相对于满二叉树中编号为数组下标值的结点值。若该结点不存在，则取0值。
题表6-1
【解答】二叉树的链式表示为：
6．若前序遍历某树的结点次序：SACEFBDGHIJK;后序遍历的结点次序为：
CFEABHGIKJDS，画出这棵树。
【解答】画出树如下：
7．将原教材题图6-5转换为孩子兄弟所表示的二叉树及该二叉树的后序线索二叉树如下：
^
8．空树满足所有条件。非空树如下：
(1)前序和中序遍历序列相同的二叉树是没有左子树的二叉树（右单支树）。
(2)中序和后序遍历序列相同的二叉树是没有右子树的二叉树（左单支树）。
(3)前序和后序遍历序列相同的二叉树是只有根的二叉树。
9．在信息“ABCD BCD CB DB ACB”中A，B，C，D四个字符出现的频率依次
是：2，5，4，3。
在哈夫曼树中每个字符的最优编码：
可得编码为：
A-110 B-O C-10 D-II1
信息编码为：110010111 010111 100 1110 110100
10.错误。修改如下：
BiTree INSUCC (BiTree x)
{ S=X->rchild;
if(s->rtag)
while （s->ltag）
s=s->lchild;
return S;
}
五、算法设计题
1．编写对二叉树进行中序遍历的非递归算法，并对算法执行原教材题图6-6所示的二叉树的情况进行跟踪（即给出各阶段栈的变化及输出的结点序列）。
【解答】中序遍历的非递归算法如下：
void InorderTraverse (BTree T)
{ InitStack (S);
p=T;
while (p&& 1Empty (S))
{ if (p)
{ Push(S,p);p=p->lchild; )
else
{ pop (S,p);
printf( "ooC", p->data);
p=p->rchild);
}
}
}
对于给定的二叉树，算法执行情况如下：A入栈，B入栈，D入栈，D出栈，访问D，B
出栈，访问B，A出栈，访问A，，C入栈，E入栈，E出栈，访问E，G入栈，G出栈，访问
G，C出栈，访问C，F入栈，F出栈，访问F，栈和指针p均空，结束。
最后的遍历序列是：DBAGECF。
2．假设在表示一棵二叉树的二叉链表上增加两个域：双亲域用于指示其双亲结点，标志域flag（可取0，…，2）的值，用以区分在遍历过程中到达该结点时继续向右或向左或访问该结点。试以此存储结构编写不用栈进行后序遍历的递推形式的算法。
【解答】要解决这一问题必须区分结点在访问过程中的状态，这可通过结点的标志域来处理。对一个结点来说当前的结点可能由：(1)其双亲结点转换;(2)其左子树遍历结束转换; (3)其右予树遍历结束转换。所以，算法主要执行按这三种状态进行处理或处理当前结点或
转换结点的状态，从而算法可描述为：
void postorder (BTree T) //后序遍历二叉树
//Btree类型的结点含4个域：flag，parent，lchild，rchild; flag初值为0，指针指向根结点
{ BiTree p=T;
while (p)
switch (p->flag)
{ case O: p->flag=l; if (p->lchild) p=p->lchild;
case l: p->flag=2; if (p->rchild) p=p->rchild;
break;
case 2: p->flag=0; printf (p->data);
p=p->parent ;
}
}
3.一棵具有n个结点的完全二叉树，以一维数组作为存储结构，试设计一个对该完全二
叉树进行前序遍历的算法。
【解答】设完全二叉树的结点以层次为序，按从上至下，由左至右的顺序编号，存放在
一维数组R[1，…，n]中。对于编号为t的结点，若存在子结点，其左孩子结点一定是2*t，右孩子结点是2*t+l，由此可得对完全二叉树进行前序遍历的递归算法。
void preorder (int R[]，int n，int t) //前序遍历二叉树R[]
{ printf（”%C\n"，R[t]）; //输出当前结点值
if(t*2<=n)preorder(R，n，t*2); //递归前序遍历左子结点
if(t*2+1<=n)preorder(R，n，t*2+1); //递归前序遍历右子结点
}
4．在不使用栈和递归的条件下，后序序列遍历中序线索二叉树，需要知道任意结点的后序直接后继。中序线索树所能提供的是当前访问结点的祖先（双亲）信息，利用双亲信息，就可以对中序线索树进行后序遍历。中序线索树有如下性质：
●若x是parent的左孩子，则parent是x的最右子孙的右线索。
●若x是parent的右孩子，则parent是x的最左子孙的左线索。
因此设计两个函数求给定结点的最左子孙的左线索和最右子孙的右线索;这两个线索均
是T的祖先。具体实现如下：
typedef enum{Link, Thread} Pointer Tag;
//Link==0：指针;Thread==l：线索
typedef struct BiThrNode{ //中序线索树结点结构
ElemrType data
Struct BiThrHode lchild, rchild;
PointerTag ltag, Rtag;
} BiThrNode, *BiThrNode;
typedef enum{ lEFT, RIGHT) TagType;
BiTHrNode *LeftMose( BiTHrTree T) //求T的最左子孙的左线索
{ BighrNode *p=T;
while (p->Ltag! =Thread) p-p->lchild;
if (p->lchild) return p->lchild;
}
BiTHrNode *RightMost (BiTHrTree T) //求T的最右子孙的右线索
{ BiThrNode *p=T;
while (p->Rtag!=Thread) p-p->rchild;
if (p->rchild) return p->rchild;
else return NULL;
}
int Isrightchild (BiThrTree T,BiThrTree &parent)
//判断T是否是parent的右孩子，若是返回1，否则返回O
{ parent=LeftMost(T);
if (parent＆＆parent->rchild==p) return l;
else (parent=NUIL; return O;)
}
void posttraverse—InThrTree (BiTheTree T)
//后序遍历中序线索树，当访问标志tag为RIGHT时才访问当前结点Tagtype tag; //待访问标志，表示当前结点是从左孩子还是右孩子返回的
while (p)
{ while (p->ltag!=Thread) p=p->lchild;
if (p->rtag==link) tag=LEFT;
//左孩子为线索，右孩子为链，相当于从左返回else tag=RIGHT;//当前结点为叶结点，相当于从右返回
while( tag==RiGHT)
{ visit (p); //仅当tag==RIGHT时返回
if (Isrightchild (p, parent)
//从右孩子返回，需访问parent，修改p指向双亲{ p=parent; tag=RIGHT;)
else //p是左孩子，用最右的线索找双亲结点
{ p=RightMost (p);
if (p＆＆p->Rtag==Thread) tag=RIGHT;
else tag=LEFT;
}
}
if (tag==LEFT&＆p) p=p->rchild;
}
}
5．凹入表示法打印二叉树：
采用前序遍历的递归函数依次输出各结点的值，子结点比父结点右缩进3个字符宽度，具体实现算法如下： Void disp (BiTree T， int space) //space为空格数
{ int i;
if (t)
{ for (i=l; i printf(”%d\n¨, p->data); disp (T->lchild, space+3); disp (T->rchild, space+3); } } 6．前序遍历一棵中序线索树： 在不使用栈和递归的情况下对线索二叉树进行前序遍历，需要知道任意结点前序的直接后继。 typedef enumf Link，Thread)PointerTag; //Link:0指针，Thread:1线索 typedef struct BiThrNodet //中序线索树结点结构 ElemType data; Struct BiThrNode lchild, rchild; PointerTag Ltag, Rtag; } BiThrNode, *BiThrTree ; void pretraverse—thread(BiThrTree T) //前序遍历带头结点的中序线索树T { BiTrhTree p=T->lchild; while(p!=T) { while (p->Ltag==Link) //遍历到最左端 { visit (p); p=p->lchild;) visit (p); //访问最左端结点，然后向右转 while (p->Rtag==Thread) //由右线索向上 p=p- >rchild; if (p->Rtag==link) //右链域为指针，则转右于树，继续右于树前序遍历 p=p->rchild; } } 算法时间复杂度为O(n)。 7．以二叉链表为存储结构，写出交换各结点左右子树的算法。 【解答】要交换各结点的左右子树，最方便的办法是用后序遍历算法，每访问一个结点时把两棵子树的指针进行交换，最后一次访问是交换根结点的子树。算法如下： typedef char DataType; //定义DaTaType类型 typedef struct node { DataType data; struct node lchild，rchild; //左右孩子子树 } BinNode; //结点类型 typedef BinNode *BinTree; #include void ChangeBinTee (BinTree *T) //交换子树 { if(*T) //这里以指针为参数使交换在实参的结点上进行 { BinTreetemp; //后序遍历 ChangeBinTree(＆(*T) ->lchild); ChangeBinTree(＆(*T) ->rchlld); temp= (*T) ->lchild; (*T) ->lchild= (*T) ->rchild; (*T) ->rchild=temp; } } void PrintNode (BinTree T) //以前序序列打印结点数据 { if (T) { Printf(¨%C", T->data); PrintNode (T->lchild); PrintNode( T->rchiid); } } void main() //测试程序 { BinTree root; CreatBinTree( &root); //建立二叉链表 PrintNode (root); //输出原表 printf( "\n"); ChangeBinTree( &root); //交换子树 PrintNode (root); //输出新表 printf("＼n"); } 图 1. 填空题 ⑴ 设无向图G中顶点数为n，则图G至少有（）条边，至多有（）条边；若G为有向图，则至少有（）条边，至多有（）条边。 【解答】0，n(n-1)/2，0，n(n-1) 【分析】图的顶点集合是有穷非空的，而边集可以是空集；边数达到最多的图称为完全图，在完全图中，任意两个顶点之间都存在边。 ⑵ 任何连通图的连通分量只有一个，即是（）。 【解答】其自身 ⑶ 图的存储结构主要有两种，分别是（）和（）。 【解答】邻接矩阵，邻接表 【分析】这是最常用的两种存储结构，此外，还有十字链表、邻接多重表、边集数组等。 ⑷ 已知无向图G的顶点数为n，边数为e，其邻接表表示的空间复杂度为（）。 【解答】Ｏ(n+e) 【分析】在无向图的邻接表中，顶点表有n个结点，边表有2e个结点，共有n+2e个结点，其空间复杂度为Ｏ(n+2e)=Ｏ(n+e)。 ⑸ 已知一个有向图的邻接矩阵表示，计算第j个顶点的入度的方法是（）。 【解答】求第j列的所有元素之和 ⑹ 有向图G用邻接矩阵A[n][n]存储，其第i行的所有元素之和等于顶点i的（）。 【解答】出度 ⑺ 图的深度优先遍历类似于树的（）遍历，它所用到的数据结构是（）；图的广度优先遍历类似于树的（）遍历，它所用到的数据结构是（）。 【解答】前序，栈，层序，队列 ⑻ 对于含有n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为（），利用Kruskal 算法求最小生成树的时间复杂度为（）。 【解答】Ｏ(n2)，Ｏ(elog2e) 【分析】Prim算法采用邻接矩阵做存储结构，适合于求稠密图的最小生成树；Kruskal算法采用边集数组做存储结构，适合于求稀疏图的最小生成树。 ⑼ 如果一个有向图不存在（），则该图的全部顶点可以排列成一个拓扑序列。 【解答】回路 ⑽ 在一个有向图中，若存在弧、、，则在其拓扑序列中，顶点vi, vj, vk的相对次序为（）。 【解答】vi, vj, vk 【分析】对由顶点vi, vj, vk组成的图进行拓扑排序。 2. 选择题 ⑴ 在一个无向图中，所有顶点的度数之和等于所有边数的（）倍。 A 1/2 B 1 C 2 D 4 【解答】C 【分析】设无向图中含有n个顶点e条边，则。 图 1. 填空题 ⑴设无向图G中顶点数为n，则图G至少有（）条边，至多有（）条边；若G为有向图，则至少有（）条边，至多有（）条边。 【解答】0，n(n-1)/2，0，n(n-1) 【分析】图的顶点集合是有穷非空的，而边集可以是空集；边数达到最多的图称为完全图，在完全图中，任意两个顶点之间都存在边。 ⑵任何连通图的连通分量只有一个，即是（）。 【解答】其自身 ⑶图的存储结构主要有两种，分别是（）和（）。 【解答】邻接矩阵，邻接表 【分析】这是最常用的两种存储结构，此外，还有十字链表、邻接多重表、边集数组等。 ⑷已知无向图G的顶点数为n，边数为e，其邻接表表示的空间复杂度为（）。 【解答】Ｏ(n+e) 【分析】在无向图的邻接表中，顶点表有n个结点，边表有2e个结点，共有n+2e个结点，其空间复杂度为Ｏ(n+2e)=Ｏ(n+e)。 ⑸已知一个有向图的邻接矩阵表示，计算第j个顶点的入度的方法是（）。 【解答】求第j列的所有元素之和 ⑹有向图G用邻接矩阵A[n][n]存储，其第i行的所有元素之和等于顶点i的（）。 【解答】出度 ⑺图的深度优先遍历类似于树的（）遍历，它所用到的数据结构是（）；图的广度优先遍历类似于树的（）遍历，它所用到的数据结构是（）。 【解答】前序，栈，层序，队列 ⑻对于含有n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为（），利用Kruskal 算法求最小生成树的时间复杂度为（）。 【解答】Ｏ(n2)，Ｏ(elog2e) 【分析】Prim算法采用邻接矩阵做存储结构，适合于求稠密图的最小生成树；Kruskal算法采用边集数组做存储结构，适合于求稀疏图的最小生成树。 ⑼如果一个有向图不存在（），则该图的全部顶点可以排列成一个拓扑序列。 【解答】回路 ⑽在一个有向图中，若存在弧、、，则在其拓扑序列中，顶点vi, vj, vk的相对次序为（）。 【解答】vi, vj, vk 第六章习题 1．试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。2．对题1所得各种形态的二叉树，分别写出前序、中序和后序遍历的序列。 3．已知一棵度为k的树中有n 1个度为1的结点，n 2 个度为2的结点，……，n k 个度为k的结点， 则该树中有多少个叶子结点并证明之。 4.假设一棵二叉树的先序序列为EBADCFHGIKJ，中序序列为ABCDEFGHIJK，请画出该二叉树。 5．已知二叉树有50个叶子结点，则该二叉树的总结点数至少应有多少个？ 6．给出满足下列条件的所有二叉树： ①前序和后序相同 ②中序和后序相同 ③前序和后序相同 7． n个结点的K叉树，若用具有k个child域的等长链结点存储树的一个结点，则空的Child 域有多少个？ 8．画出与下列已知序列对应的树Ｔ： 树的先根次序访问序列为GFKDAIEBCHJ； 树的后根次序访问序列为DIAEKFCJHBG。 9．假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为： 0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10 请为这8个字母设计哈夫曼编码。 10．已知二叉树采用二叉链表存放,要求返回二叉树T的后序序列中的第一个结点指针,是否可不用递归且不用栈来完成?请简述原因. 11. 画出和下列树对应的二叉树： 12．已知二叉树按照二叉链表方式存储，编写算法，计算二叉树中叶子结点的数目。 13．编写递归算法：对于二叉树中每一个元素值为x的结点，删去以它为根的子树，并释放相应的空间。 14．分别写函数完成：在先序线索二叉树T中，查找给定结点*p在先序序列中的后继。在后序线索二叉树T中，查找给定结点*p在后序序列中的前驱。 15．分别写出算法，实现在中序线索二叉树中查找给定结点*p在中序序列中的前驱与后继。 16．编写算法，对一棵以孩子-兄弟链表表示的树统计其叶子的个数。 17．对以孩子-兄弟链表表示的树编写计算树的深度的算法。 18．已知二叉树按照二叉链表方式存储，利用栈的基本操作写出后序遍历非递归的算法。 19．设二叉树按二叉链表存放，写算法判别一棵二叉树是否是一棵正则二叉树。正则二叉树是指：在二叉树中不存在子树个数为1的结点。 20．计算二叉树最大宽度的算法。二叉树的最大宽度是指：二叉树所有层中结点个数的最大值。 21．已知二叉树按照二叉链表方式存储，利用栈的基本操作写出先序遍历非递归形式的算法。 22. 证明：给定一棵二叉树的前序序列与中序序列，可唯一确定这棵二叉树； 给定一棵二叉树的后序序列与中序序列，可唯一确定这棵二叉树； 23. 二叉树按照二叉链表方式存储，编写算法，计算二叉树中叶子结点的数目。 24. 二叉树按照二叉链表方式存储，编写算法，将二叉树左右子树进行交换。 实习题 1.[问题描述] 建立一棵用二叉链表方式存储的二叉树，并对其进行遍历（先序、中序和后序）， 打印输出遍历结果。 [基本要求] 从键盘接受输入先序序列，以二叉链表作为存储结构，建立二叉树（以先序来建立）并对其进行遍历（先序、中序、后序），然后将遍历结果打印输出。要求采用递归和非递归两种方法实现。 [测试数据] ABCффDEфGффFффф（其中ф表示空格字符） 输出结果为：先序：ABCDEGF 中序：CBEGDFA 后序：CGBFDBA 2．已知二叉树按照二叉链表方式存储，编写算法，要求实现二叉树的竖向显示（竖向显示就是二叉树的按层显示）。 一．名词解释 （1）结点—— 树的结点包含一个数据及若干指向其子树的分支。 （2）结点的度—— 结点所拥有的子树数称为该结点的度。 （3）树的度—— 树中各结点度的最大值称为该树的度。 （4）二叉树—— 一棵非空的二叉树，每个结点至多只有两棵子树，分别称为左子树和右 子树，左、右子树的次序不能任意交换，且左右子树又分别是一棵二叉树。 （5）哈夫曼树—— 带权路径长度最小的二叉树，即最优二叉树，也称为哈夫曼树。 二．判断题（下列各题，正确的请在前面的括号内打√；错误的打ㄨ） （1）√ （2）ㄨ （3）√ （4）√ （5）√ （6）ㄨ （7）ㄨ （8）√ 三．填空题 1．结点拥有的子树数 2．度为零的 3. 树内各结点度的最大值 4．深度（或高度） 5．2i-1 6． 2h -1 7. n-1 8．6 9．中序 10．5 11．20 12. ??1log 2+n 13．顺序存储结构和链式存储结构 14．最小 15．EBCAD 16．(1) ABEFHCG (2)．EBHFACG (3)．EHFBGCA 17．空二叉树 18．4 四．选择题 （1）B （2）C （3）C （4）C （5）D （6）B （7）A （8）B （9）D （10）D （11）B （12）A （13）C 五．简答题 1． 答: 一般树（非空）除了根结点之外，每个结点有且仅有一个前驱结点，但每个结点都可以有多个互不相交的子集（后继结点）。 二叉树（若非空）除了根结点之外，每个结点有且仅有一个前驱结点，但每个结点至多只有两个后继结点，称为左子树和右子树，左、右子树的次序不能交换，且左右子树又分别都是二叉树。 一般树和二叉树主要有以下区别： 二叉树结点的度最大为2，而一般树结点的最大度数无限制； 一般树的结点无左、右之分，而二叉树的结点有左、右之分。 2． 答：一棵度为2的树与一棵二叉树的区别在于：对于度为1的结点，度为2的树无须区分左右；对于二叉树必须有左右之分，且不能任意交换。 3． 答： （1）A是根结点。 （2）叶结点：M，N，D，J，K，F，I。 （3）G的双亲：C。 （4）G的祖先：A，C。 （5）G的孩子：J，K。 （6）E的子孙：L，M，N。 （7）E的兄弟：D；F的兄弟：G，H。 （8）结点B的层次为2；结点N的层次是5。 习题6 1．填空题 （1）n个顶点的无向图，最多能有（___________）条边。 答案：[n*(n-1)]/2 （2）有n个顶点的强连通图G最多有（___________）条弧。 答案：n*(n-1) （3）有n个顶点的强连通图G至少有（___________）条弧。 答案：n （4）G为无向图，如果从G的某个顶点出发，进行一次广度优先遍历，即可访问图的每个顶点，则该图一定是（___________）图。 答案：连通 （5）若采用邻接矩阵结构存储具有n个顶点的图，则对该图进行广度优先遍历的算法时间复杂度为（___________）。 答案：O（n2） （6）n个顶点的连通图的生成树有（___________）条边。 答案：n-1 （7）图的深度优先遍历类似于树的（___________）遍历；图的广度优先遍历类似于树的（___________）遍历。 答案：前序层序 （8）对于含有n个顶点e条边的连通图，用普里姆算法求最小生成树的时间复杂度为（___________）。 答案：O（n2） （9）已知无向图G的顶点数为n，边数为e，其邻接表表示的空间复杂度为（___________）。答案：O（n+e） （10）一棵具有n个顶点的生成树有且仅有（___________）条边。 答案：n-1 2．单选题 （1）在一个无向图中，所有顶点的度数之和等于所有边数的（）倍。 A. 1/2 B. 1 C. 2 D. 4 （2）在一个具有n个顶点的有向图中，若所有顶点的出度数之和为S，则所有顶点的度数之和为（）。 A. S B. S－1 C. S+1 D. 2S （3）具有n个顶点的有向图最多有（）条边。 A. n B. n(n-1) C. n(n+1) D. 2n （4）若一个图中包含有k个连通分量，若按照深度优先搜索的方法访问所有顶点，则必须调用（）次深度优先搜索遍历的算法。 E F D G A B / + + * - C * 第六章 树和二叉树 一、选择题 1．已知一算术表达式的中缀形式为 A+B*C-D/E ，后缀形式为ABC*+DE/-，其前缀形式为( D ) A ．-A+B*C/DE B. -A+B*CD/E C ．-+*ABC/DE D. -+A*BC/DE 2. 设有一表示算术表达式的二叉树（见下图）， 它所表示的算术表达式是（ C ） A. A*B+C/(D*E)+(F-G) B. (A*B+C)/(D*E)+(F-G) C. (A*B+C)/(D*E+（F-G ）) D. A*B+C/D*E+F-G 3. 在下述结论中，正确的是（ D ） ①只有一个结点的二叉树的度为0; ②二叉树的度为2； ③二叉树的左右 子树可任意交换; ④深度为K 的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A ．①②③ B ．②③④ C ．②④ D ．①④ 4. 设森林F 对应的二叉树为B ，它有m 个结点，B 的根为p,p 的右子树结点个数为n,森林F 中第一棵树的结点个数是（ A ） A ．m-n B ．m-n-1 C ．n+1 D ．条件不足，无法确定 5．设森林F 中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F 对应的二叉树根结点的右子树上的结点个数是（ D ）。 A ．M1 B ．M1+M2 C ．M3 D ．M2+M3 6. 设给定权值总数有n 个，其哈夫曼树的结点总数为( D ) A ．不确定 B ．2n C ．2n+1 D ．2n-1 7．一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有( B )结点 A ．2h B ．2h-1 C ．2h+1 D ．h+1 8. 一棵具有 n 个结点的完全二叉树的树高度（深度）是（ A ） A ．?logn ?+1 B ．logn+1 C ．?logn ? D ．logn-1 9．深度为h 的满m 叉树的第k 层有（ A ）个结点。(1= 删除40 删除70 删除60 struct node { int data; struct node *lchild, *rchild; }; typedef struct node NODE; NODE *create_tree(a,i,j) int a[ ],i,j; { NODE *p; int k; if(i>j) return(NULL); k=(i+j)/2; p=(NODE *)malloc(sizeof(NODE)); p->data=a[k]; p->lchild=create_tree(a,i,k-1); p->rchild=create_tree(a,k+1,j); return(p); } 6. 3 int check(root) NODE *root; { int x; if(root==NULL) return(0); if(root->data h=height(root->lchild); k=height(root->rchild); if(h>k) return(h+1); else return(k+1); } } 6. 5 #include “math.h” int check_beltree(root) NODE *root; { int a; if(root==NULL) return(1); if(check_beltree(root->lchild)==0||check_beltree(root->rchild)==0) return(0); a=abs(height(root->rchild)-height(root->lchild)); //上题函数 if(a<=1) return(1); } 第6章 树和二叉树（参考答案） 6.1 (1)根结点a 6.2 三个结点的树的形态： 三个结点的二叉树的形态： （1） （1） （2） （4） （5） 6．3 设树的结点数是n ，则 n=n0+n1+n2+……+nm+ (1) 设树的分支数为B ，有 n=B+1 n=1n1+2n2+……+mnm+1 (2) 由（1）和（2）有： n0=n2+2n3+……+(m-1)nm+1 6.4 (1) k i-1 (i 为层数) (2) (n-2)/k+1 (3) (n-1)*k+i+1 (4) (n-1)%k !=0; 其右兄弟的编号 n+1 6.5（1）顺序存储结构 注：#为空结点 6.6 (1) 前序 ABDGCEFH (2) 中序 DGBAECHF (3) 后序 GDBEHFCA 6.7 (1) 空二叉树或任何结点均无左子树的非空二叉树 (2) 空二叉树或任何结点均无右子树的非空二叉树 (3) 空二叉树或只有根结点的二叉树 6.8 int height(bitree bt) // bt是以二叉链表为存储结构的二叉树，本算法求二叉树bt的高度 { int bl,br; // 局部变量，分别表示二叉树左、右子树的高度 if (bt==null) return(0); else { bl=height(bt->lchild); br=height(bt->rchild); return(bl>br? bl+1: br+1); // 左右子树高度的大者加1（根） } }// 算法结束 6.9 void preorder(cbt[],int n,int i); // cbt是以完全二叉树形式存储的n个结点的二叉树，i是数 // 组下标，初始调用时为1。本算法以非递归形式前序遍历该二叉树 { int i=1,s[],top=0; // s是栈，栈中元素是二叉树结点在cbt中的序号 // top是栈顶指针，栈空时top=0 if (n<=0) { printf(“输入错误”);exit（0）；} while (i<=n ||top>0) { while(i<=n) {visit(cbt[i]); // 访问根结点 if (2*i+1<=n) s[++top]=2*i+1; //若右子树非空，其编号进栈 i=2*i;// 先序访问左子树 } if (top>0) i=s[top--]; // 退栈，先序访问右子树 } // END OF while (i<=n ||top>0) }// 算法结束 //以下是非完全二叉树顺序存储时的递归遍历算法，“虚结点”用‘*’表示void preorder(bt[],int n,int i); // bt是以完全二叉树形式存储的一维数组，n是数组元素个数。i是数 // 组下标，初始调用时为1。 { if (i<=n && bt[i]!=’*’) { visit(bt[i]); preorder(bt,n,2*i); preorder(bt,n,2*i+1); }// 算法结束 6.10 int equal(bitree T1,bitree T2); // T1和T2是两棵二叉树，本算法判断T1和T2是否等价 // T1和T2都是空二叉树则等价 // T1和T2只有一棵为空，另一棵非空，则不等价 // T1和T2均非空，且根结点值相等，则比较其左、右子树 第六章课后习题 6、1、各层的结点数目是：K 2、编号为n的结点的双亲结点是：<=(n-2)/k的最大整数 3、编号为n的结点的第i个孩子结点编号是：k*(n-1)+1+i 4、编号为n的结点有右兄弟的条件是：(n-1)能被k整除 右兄弟的编号是：n+1. 7、1、先序序列和中序序列相同：空二叉树或没有左子树的二叉树。 2、中序序列和后序序列相同：空二叉树或没有右子树的二叉树。 3、先序序列和后序序列相同：空二叉树或只有根的二叉树。 9、中序序列：BDCEAFHG和后序序列：DECBHGFA的二叉树为： A B F C G D E H 先序序列：ABCDEFGH 算法设计： 3、typedef struct { int data[100]; int top; }seqstack; seqstack *s; Perorder(char a[],int n) { int i=1,count=1; s->top=-1; if(n==0)return(0); else { if(I<=n) { s->top++; s->data[s->top]=a[I]; } while(count 习题六树和二叉树 一、单项选择题 1．以下说法错误的是 ( ) A．树形结构的特点是一个结点可以有多个直接前趋 B．线性结构中的一个结点至多只有一个直接后继 C．树形结构可以表达(组织)更复杂的数据 D．树(及一切树形结构)是一种"分支层次"结构 E．任何只含一个结点的集合是一棵树 2．下列说法中正确的是 ( ) A．任何一棵二叉树中至少有一个结点的度为2 B．任何一棵二叉树中每个结点的度都为2 C．任何一棵二叉树中的度肯定等于2 D．任何一棵二叉树中的度可以小于2 3．讨论树、森林和二叉树的关系，目的是为了（） A．借助二叉树上的运算方法去实现对树的一些运算 B．将树、森林按二叉树的存储方式进行存储 C．将树、森林转换成二叉树 D．体现一种技巧，没有什么实际意义 4．树最适合用来表示 ( ) A．有序数据元素 B．无序数据元素 C．元素之间具有分支层次关系的数据 D．元素之间无联系的数据 5．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A．9 B．11 C．15 D．不确定 6．设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F 对应的二叉树根结点的右子树上的结点个数是（）。 A．M1 B．M1+M2 C．M3 D．M2+M3 7．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（） A． 250 B． 500 C．254 D．505 E．以上答案都不对 8. 设给定权值总数有n 个，其哈夫曼树的结点总数为( ) A．不确定 B．2n C．2n+1 D．2n-1 9．二叉树的第I层上最多含有结点数为（） A．2I B． 2I-1-1 C． 2I-1 D．2I -1 10．一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有( )结点A．2h B．2h-1 C．2h+1 D．h+1 11. 利用二叉链表存储树，则根结点的右指针是（）。 A．指向最左孩子 B．指向最右孩子 C．空 D．非空 12．已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（）。 A．CBEFDA B． FEDCBA C． CBEDFA D．不定 13．已知某二叉树的后序遍历序列是dabec, 中序遍历序列是debac , 它的前序遍历是（）。 A．acbed B．decab C．deabc D．cedba 第六章树和二叉树（下载后用阅读版式视图或web版式可以看清） 习题 一、选择题 1．有一“遗传”关系：设x是y的父亲，则x可以把它的属性遗传给y。表示该遗传关系最适合的数据结构为( )。 A.向量 B.树C图 D.二叉树 2．树最合适用来表示( )。 A.有序数据元素 B元素之间具有分支层次关系的数据 … C无序数据元素 D.元素之间无联系的数据 3．树B的层号表示为la，2b，3d，3e，2c，对应于下面选择的( )。 A. la (2b (3d,3e),2c) B. a(b(D,e),c) C. a(b(d,e),c) D. a(b,d(e),c) 4.高度为h的完全二叉树至少有( )个结点，至多有( )个结点。 A. 2h_l C．2h-1 D. 2h 5.在一棵完全二叉树中，若编号为f的结点存在右孩子，则右子结点的编号为( )。 A. 2i B. 2i-l C. 2i+l D. 2i+2 6.一棵二叉树的广义表表示为a(b(c)，d(e(，g(h))，f))，则该二叉树的高度为( )。 ; 7.深度为5的二叉树至多有( )个结点。 A. 31 B. 32 C. 16 D. 10 8.假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为( )个。 A. 15 B. 16 C. 17 D. 47 9.题图6-1中，( )是完全二叉树，( )是满二叉树。 10.在题图6-2所示的二叉树中： (1)A结点是 ） A.叶结点 B根结点但不是分支结点 C根结点也是分支结点 D.分支结点但不是根结点 (2)J结点是 A.叶结点 B．根结点但不是分支结点 C根结点也是分支结点 D.分支结点但不是根结点 (3)F结点的兄弟结点是 C．空 (4)F结点的双亲结点是 (5)树的深度为 * (6)B结点的深度为 (7)A结点所在的层是 11.在一棵具有35个结点的完全二叉树中，该树的深度为( )。 12. 一棵有124个叶结点的完全二叉树，最多有( )个结点。 A．247 B．248 C．249 D．250 13.用顺序存储的方法将完全二叉树中所有结点逐层存放在数组R[1…n]中，结点R[i]若 ） 有左子树，则左子树是结点( )。 A. R[2i+l] B. R[2i] [i/2] D. R[2i-1] 数据结构课后习题解答第六章-树和二叉树 习题及参考答案 第六章树和二叉树 6.33 int Is_Descendant_C(int u,int v)//在孩子存储结构上判断u是否v的子孙,是则返回1,否则返回0 { if(u==v) return 1; else { if(L[v]) if (Is_Descendant(u,L[v])) return 1; if(R[v]) if (Is_Descendant(u,R[v])) return 1; //这是个递归算法 } return 0; }//Is_Descendant_C 6.34 int Is_Descendant_P(int u,int v)//在双亲存储结构上判断u是否v的子孙,是则返回1,否则返回0 { for(p=u;p!=v&&p;p=T[p]); if(p==v) return 1; else return 0; }//Is_Descendant_P 6.35 这一题根本不需要写什么算法,见书后注释:两个整数的值是相等的. 6.36 int Bitree_Sim(Bitree B1,Bitree B2)//判断两棵树是否相似的递归算法 { if(!B1&&!B2) return 1; else if(B1&&B2&&Bitree_Sim(B1->lchild,B2->lchild)&&Bitree_Sim(B1->rchild,B2->rchild)) return 1; else return 0; }//Bitree_Sim 6.37 void PreOrder_Nonrecursive(Bitree T)//先序遍历二叉树的非递归算法{ InitStack(S); Push(S,T); //根指针进栈 while(!StackEmpty(S)) { while(Gettop(S,p)&&p) { visit(p->data); push(S,p->lchild); } //向左走到尽头 pop(S,p); if(!StackEmpty(S)) { pop(S,p); push(S,p->rchild); //向右一步 } }//while }//PreOrder_Nonrecursive 6.38 typedef struct { BTNode* ptr; enum {0,1,2} mark; } PMType; //有mark域的结点指针类型 void PostOrder_Stack(BiTree T)//后续遍历二叉树的非递归算法,用栈{ PMType a; InitStack(S); //S的元素为PMType类型 Push (S,{T,0}); //根结点入栈 while(!StackEmpty(S)) { Pop(S,a); switch(a.mark) { case 0: 数据结构第六章图练习题及答案详细解析（精华版） 第一篇：数据结构第六章图练习题及答案详细解析(精华版) 图 1.填空题 ⑴ 设无向图G中顶点数为n，则图G至少有（）条边，至多有（）条边；若G为有向图，则至少有（）条边，至多有（）条边。【解答】0，n(n-1)/2，0，n(n-1)【分析】图的顶点集合是有穷非空的，而边集可以是空集；边数达到最多的图称为完全图，在完全图中，任意两个顶点之间都存在边。 ⑵ 任何连通图的连通分量只有一个，即是（）。【解答】其自身 ⑶ 图的存储结构主要有两种，分别是（）和（）。【解答】邻接矩阵，邻接表 【分析】这是最常用的两种存储结构，此外，还有十字链表、邻接多重表、边集数组等。⑷ 已知无向图G的顶点数为n，边数为e，其邻接表表示的空间复杂度为（）。【解答】Ｏ(n+e)【分析】在无向图的邻接表中，顶点表有n个结点，边表有2e个结点，共有n+2e个结点，其空间复杂度为Ｏ(n+2e)=Ｏ(n+e)。 ⑸ 已知一个有向图的邻接矩阵表示，计算第j个顶点的入度的方法是（）。【解答】求第j列的所有元素之和 ⑹ 有向图G用邻接矩阵A[n][n]存储，其第i行的所有元素之和等于顶点i的（）。【解答】出度 ⑺ 图的深度优先遍历类似于树的（）遍历，它所用到的数据结构是（）；图的广度优先遍历类似于树的（）遍历，它所用到的数据结构是（）。【解答】前序，栈，层序，队列 ⑻ 对于含有n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为（），利用Kruskal算法求最小生成树的时间复杂度为（）。【解答】Ｏ(n2)，Ｏ(elog2e)【分析】Prim算法采用邻接矩阵做存储结构，适合于求稠密图的最小生成树；Kruskal算法采用边集数组做存储结构，适合于求稀疏图的最小生成树。数据结构-第六章-图-练习题及答案详细解析(精华版)
数据结构 第六章 图 练习题及答案详细解析
数据结构课后习题及解析第六章
数据结构肖启宏课后习题答案第六章
数据结构第六章参考答案
数据结构第6章 树习题+答案
数据结构第六章习题答案
数据结构与算法第六章课后答案第六章 树和二叉树
数据结构第六章 树和二叉树课后习题答案
数据结构第六章树和二叉树习题及答案
数据结构课后习题答案第六章
数据结构课后习题解答第六章-树
数据结构第六章图练习题及答案详细解析（精华版）
相关主题
文本预览