10、 二叉树按某种顺序线索化后，任一结点均有指向其前驱和后继的线索。（ ） 11、 中序线索二叉树中，右线索若不为空，则一定指向其父结点。（ ） 五、 简答题
1、 二叉树与树有何区别？一棵度为2的树与二叉树有何区别？
2、 一棵树有度为1的结点n1个，度为2的结点n2个，…，度为m的结点nm个，问它有多少叶结点？
有多少非终端结点？
3、 一棵有n个结点的树中所有非叶子结点的度均为k，求该树中有多少叶子结点？ 4、 含有n个结点和n0个叶子结点的完全k叉树的高度各为多少？ 5、 将算术表达式((a+b)+c*(d+e)+f)*(g+h)转化为二叉树。
6、 对于二叉树T的两个结点n1和n2，应选择前序、中序和后序的哪两个序列来判定结点n1必定是结
点n2的祖先，并给出判断方法。
7、 具有7个结点的互不相似的二叉树共有多少棵？
8、 具有3个结点的树和二叉树，它们的所有不同形态有哪些？ 9、 试找出分别满足下列条件的所有二叉树。
（1） 前序和中序遍历序列相同。（2）中序和后序遍历序列相同。（3）前序和后序遍历序列相同。 10、 现有按中序遍历二叉树的结果为ABC，问有多少种不同形态的二叉树可以得到这一遍历结果？
画出这些树。 11、 已知一棵二叉树的中序遍历序列为CDBAEGF，前序遍历序列为ABCDEFG，问能否唯一确定
一棵树，请画出。若给定前序和后序遍历序列，能否唯一确定，请说明理由。 12、 假定先根次序遍历某棵树的结点次序为SACEFBDBHIJK，后根次序遍历该树的结点次序为
CFEABHGIKJDS，画出这棵树。 13、 什么是线索二叉树？简述中序线索二叉树中查找指定结点的直接前驱和直接后继的基本思想。 14、 有7个带权结点，其权值分别为4，7，8，2，5，16，30，试以它们为叶子结点构造一棵哈夫
曼树（要求按每个结点的左子树根结点的权值小于或等于右子树根结点的权值的次序构造），并计算其带权路径长度。
15、分别画出含3个结点的树与二叉树的所有不同形态。
16、设在树中，结点x是结点y的双亲时，用(x,y)来表示边。已知一棵树边的集合为：{(i,j),(i,k),(b,e),(e,i),(b,d),(a,b),(c,g),(c,f),(c,h),(a,c)}，用树形表示法画出此树，并回答下列问题：
（1） 哪个是根结点？ （2） 哪些是叶子结点？ （3） 哪个是g 的双亲？ （4） 哪些是g的祖先？ （5） 哪些是e的子孙？ （6） 哪些是f的兄弟？ （7） 结点b和j的层次各是多少？ （8） 树的深度是多少？ （9） 树的度数是多少？
17、任意一个有n(n>0)个结点的二叉树，已知它有m个叶子结点，试证明非叶子结点有m-1个度为2，其余度为1。
18、分别画出图6.6所示二叉树的二叉链表、三叉链表和顺序存储结构。 A B D
C E F 图6.6
19、分别写出图6.7所示二叉树的前序、中序和后序序列。
F
图6.7
A B C D E 20、试分别画出图6.8所示树的孩子链表、孩子兄弟链表和静态双亲链表。
A
C B D F G H I E J
L K 图6.8
21、将图6.9所示的森林转换成二叉树。 A G J
I K B C D H
F L M N E
图6.9
22、分别画出图6.10所示各二叉树对应的森林。并写出森林的前序和中序遍历序列。 A
B C
D E F
G H I J
图6.10
K
23、设某密码电文由8个字母组成，每个字母在电文中的出现频率分别是7，19，2，6，32，3，21，10，试为这8个字母设计相应的哈夫曼编码。
24、将代数式：y=3*(x+a)-a/x2 描述成表达式树，并写出前缀式和后缀式来。
25、下述编码{00，01，10，11}，{0，1，00，11，}，{0，10，110，111}哪一组不是前缀码？ 26、将图6.11所示的森林转化成一棵二叉树，并分别按以下要求画出线索二叉树。 （1）前序前趋线索化； （2）后序后继线索化； （3）中序全线索化。 A E F
B
G H I
C D 图6.11
第七章：图 练习题
一、 选择题
1、一个有n个顶点的无向图最多有（ ）条边。 A、n B、n(n-1) C、n(n-1)/2 D、2n
2、具有6个顶点的无向图至少有（ ）条边才能保证是一个连通图。 A、5 B、6 C、7 D、8
3、具有n个顶点且每一对不同的顶点之间都有一条边的图被称为（ ）。 A、线性图 B、无向完全图 C、无向图 D、简单图 4、具有4个顶点的无向完全图有（ ）条边。 A、6 B、12 C、16 D、20
5、G是一个非连通无向图，共有28条边，则该图至少有（ ）个顶点 A、6 B、7 C、8 D、9
6、存储稀疏图的数据结构常用的是（ ）。
A、邻接矩阵 B、三元组 C、邻接表 D、十字链表
7、对一个具有n个顶点的图，采用邻接矩阵表示则该矩阵的大小为（ ）。 A、n B、(n-1)2 C、(n+1)2 D、n2
8、设连通图G的顶点数为n，则G的生成树的边数为（ ）。 A、n-1 B、n C、2n D、2n-1
9、对于一个具有N个顶点和E条边的无向图，若采用邻接表表示，则表头向量的大小为（邻接表中的结点总数是（ （2） ）
（1）A、N B、N+1 C、N-1 D、N+E （2）A、E/2 D、E C、2E D、N+E
10、对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表向量的大小为（ 邻接表的结点总数为（ ）。
A、n B、n+1 C、n-1 D、2n E、e/2 F、e G、2e H、n+e 11、在有向图的邻接表存储结构中，顶点v在表结点中出现的次数是（ ）。
1） ）；所有 ），所有顶点 （
A、顶点v的度 B、顶点v的出度 C、顶点v 的入度 D、依附于顶点v的边数
12、已知一个图，若从顶点a出发进行深度和广度优先搜索遍历，则可能得到的顶点序列分别为（ ）和（ ）
（1） A、abecdf B、acfebd C、acebfd D、acfdeb （2） A、abcedf B、abcefd C、abedfc D、acfdeb
13、采用邻接表存储的图的深度和广度优先搜索遍历算法类似于二叉树的（ ）和（ ）。 A、中序遍历 B、先序遍历 C、后序遍历 D、层次遍历
14、已知一有向图的邻接表存储结构如下图所示，分别根据图的深度和广度优先搜索遍历算法，从顶点v1出发，得到的顶点序列分别为（ ）和（ ）。
A、v1,v2,v3,v4,v5 B、v1,v3,v2,v4,v5 C、v1,v2,v3,v5,v4 D、v1,v4,v3,v5,v2
15、已知有8个顶点为A，B，C，D，E，F，G，H的无向图，其邻接矩阵存储结构如下，由此结构，从A点开始深度遍历，得到的顶点序列为（ ）。 A B C D E F G H A 0 1 0 1 0 0 0 0 B 1 0 1 0 1 1 1 0 C 0 1 0 1 0 0 0 0 D 1 0 1 0 0 0 1 0 E 0 1 0 0 0 0 0 1 F 0 1 0 0 0 0 1 1 G 0 1 0 1 0 1 0 1 H 0 0 0 0 1 1 1 0 A、ABCDGHFE B、ABCDGFHE C、ABGHFECD D、ABFHEGDC E、ABEHFGDC F、ABEHGFCD
16、已知一个图如下，在该图的最小生成树中各边上权值之和为（ ），在该图的最小生成树中，从v1到v6的路径为（ ）。
A、31 B、38 C、36 D、43 E、v1,v3,v6 F、v1,v4,v6 G、v1,v5,v4,v6 H、v1,v4,v3,v6
17、关键路径是事件结点网络中的（ ）。
A、从源点到汇点的最长路径 B、从源点到汇点的最短路径 C、最长的回路 D、最短的回路 18、正确的AOE网必须是（ ），AOE网中某边权值应当是（ ），权值为0的边表示（ ）。 （1）A、完全图 B、哈密尔顿图 C、无环图 D、强连通图
（2）A、实数 B、正整数 C、正数 D、非负数 （3）A、为决策而增加的活动 B、为计算方便而增加的活动 C、表示活动间的时间顺序关系 D、该活动为关键活动
19、已知一个图如下，则由该图得到的一种拓扑序列为（ ）。
A、v1,v4,v6,v2,v5,v3 B、v1,v2,v3,v4,v5,v6 C、v1,v4,v2,v3,v6,v5 D、v1,v2,v4,v6,v3,v5
20、下面结论中正确的是（ ）
A、在无向图中，边的条数是顶点度数之和。 B、在图结构中，顶点可以没有任何前驱和后继。 C、在n个顶点的无向图中，若边数大于n-1，则该图必定是连通图 D、图的邻接矩阵必定是对称矩阵。 21、下面结论中正确的是（ ）
A、若有向图的邻接矩阵中对角线以下元素均为0，则该图的拓扑排序序列必定存在。 B、网络的最小代价生成树是唯一的。 C、在拓扑排序序列中，任意两个相继顶点vi和vj都存在从vi到vj的路径。 D、在有向图中，从一个顶点到另一个顶点的最短路径是唯一的。 22、下面结论不正确的是（ ）。
A、无向图的连通分量是该图的极大连通子图。 B、有向图用邻接矩阵表示容易实现求顶点度数的操作。 C、无向图用邻接矩阵表示，图中的边数等于邻接矩阵元素之和的一半。 D、有向图的邻接矩阵必定不是对称矩阵。
23、下面结论中正确的是（ ）。
A、按深度优先搜索遍历图时，与始点相邻的顶点先于不与始点相邻的顶点访问。 B、一个图按深度优先搜索遍历的结果是唯一的。 C、若有向图G中包含一个环，则G的顶点间不存在拓扑排序。 D、图的拓扑排序序列是唯一的。
24、下面结论中不正确的是（ ）。
A、按广度优先搜索遍历图时，与始点相邻的顶点先于不与始点相邻的顶点访问。 B、一个图按广度优先搜索遍历的结果是唯一的。 C、无向图的邻接表表示法中，表中结点的数目是图中边的条数的2倍。