3．利用广义表的head和tail操作写出函数表达式，把以下各题中的单元素banana从广义表中分离出来：
（1）L1（apple,pear,banana,orange）
（2）L2（（apple,pear）,（banana,orange））
（3）L3（（（apple）,（pear）,（bananA）,（orange）））
（4）L4（（（（apple）））,（（pear））,（bananA）,orange）
（5）L5（（（（apple）,pear）,bananA）,orange）
【答案】
（1）Head（Tail（Tail（L1）））
（2）Head（Head（Tail（L2）））
（3）Head（Head（Tail（Tail（Head（L3）））））
（4）Head（Head（Tail（Tail（L4））））
（5）Head（Tail（Head（L5）））
1．从概念上讲，树，森林和二叉树是三种不同的数据结构，将树，森林转化为二叉树的基本目的是什么，并指出树和二叉树的主要区别。
【答案】树的孩子兄弟链表表示法和二叉树二叉链表表示法，本质是一样的，只是解释不同，也就是说树（树是森林的特例，即森林中只有一棵树的特殊情况）可用二叉树惟一表示，并可使用二叉树的一些算法去解决树和森林中的问题。
树和二叉树的区别有3：
一是二叉树的度至多为2，树无此限制；二是二叉树有左右子树之分，即使在只有一个分支的情况下，也必须指出是左子树还是右子树，树无此限制；三是二叉树允许为空，树一般不允许为空（个别书上允许为空）。
2．若在内存中存放一个完全二叉树，在二叉树上只进行下面两个操作：
（1）寻找某个结点双亲；
（2）寻找某个结点的子女；
请问应该用何种结构来存储该二叉树？
【答案】用顺序存储结构存储n个结点的完全二叉树。
编号为i的结点，其双亲编号是⎣i/2⎦（i=1时无双亲），其左子女是2i（若2i≤n，否则i无左子女），右子女是2i+1（若2i+1≤n，否则无右子女）。
3．求含有n个结点、采用顺序存储结构的完全二叉树中的序号最小的叶子结点的下标。
要求写出简要步骤。
【答案】根据完全二叉树的性质，最后一个结点（编号为n）的双亲结点的编号是⎣n/2⎦，这是最后一个分支结点，在它之后是第一个终端（叶子）结点，故序号最小的叶子结点的下标是⎣n/2⎦+1。
4．试证明，同一棵二叉树的所有叶子结点，在先序序列、中序序列以及后序序列中都按相同的相对位置出现（即先后顺序相同），例如先序abc，后序bca，中序bac。
【答案】先序遍历是“根左右”，中序遍历是“左根右”，后序遍历是“左右根”。
三种遍历中只是访问“根”结点的时机不同，对左右子树均是按左右顺序来遍历的，因此所有叶子都按相同的相对位置出现。
5．试找出满足下列条件的二叉树：
1）先序序列与后序序列相同；2）中序序列与后序序列相同；
3）先序序列与中序序列相同；4）中序序列与层次序列相同；
【答案】先序遍历二叉树的顺序是“根—左子树—右子树”，中序遍历“左子树—根—右子树”，后序遍历顺序是：
“左子树—右子树―根”，根据以上原则，解答如下：
1）若先序序列与后序序列相同，则或为空树，或为只有根结点的二叉树。
2）若中序序列与后序序列相同，则或为空树，或为任一结点至多只有左子树的二叉树。
（3）若先序序列与中序序列相同，则或为空树，或为任一结点至多只有右子树的二叉树。
（4）若中序序列与层次遍历序列相同，则或为空树，或为任一结点至多只有右子树的二叉树
6．已知一棵二叉树的中序序列和后序序列分别为GLDHBEIACJFK和LGHDIEBJKFCA
（1）给出这棵二叉树；
（2）转换为对应的森林。
【答案】
7．一棵非空二叉树其先序序列和后序序列正好相反，画出二叉树的形状。
【答案】先序序列是“根左右”后序序列是“左右根”，可见对任意结点，若至多只有左子女或至多只有右子女，均可使先序序列与后序序列相反，图示如下：
8．假设一棵二叉树的层次次序（按层次递增顺序排列，同一层次自左向右）为ABECFGDHI,中序序列为BCDAFEHIG。
请画出该二叉树，并将其转换为对应的森林。
【答案】按层次遍历，第一个结点（若树不空）为根，该结点在中序序列中把序列分成左右两部分：
左子树和右子树。
若左子树不空，层次序列中第二个结点为左子树的根；若右子树为空，则层次序列中第三个结点为右子树的根。
对右子树也作类似的分析。
层次序列的特点是，从左到右每个结点或是当前情况下子树的根或是叶子。
9．已知一个森林的先序序列和后序序列如下，请构造出该森林。
先序序列：
ABCDEFGHIJKLMNO
后序序列：
CDEBFHIJGAMLONK
【答案】森林的先序序列和后序序列对应其转换的二叉树的先序序列和中序序列，应先据此构造二叉树，再构造出森林。
10．一棵二叉树的先序、中序、后序序列如下，其中一部分未标出，请构造出该二叉树。
先序序列：
__CDE_GHI_K
中序序列：
CB__FA_JKIG
后序序列：
_EFDB_JIH_A
【答案】
11．设有正文AADBAACACCDACACAAD，字符集为A，B，C，D，设计一套二进制编码，使得上述正文的编码最短。
【答案】字符A，B，C，D出现的次数为9，1，5，3。
其哈夫曼编码如下：
A:
1，B:
000，C:
01，D:
001。
AOE网的性质
（1）只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始。
（2）只有在进入某点的各有向边所代表的活动都已结束，该顶点所代表的时事件才能发生。
整个工程只有一个开始点，一个结束点。
AOV网
用顶点表示活动，用弧表示活动间的优先关系的有向图称为顶点表示活动的网，简称AOV网。
在网中，若从顶点i到顶点j有一条有向路径，则i是j的前驱
AOV网是一种有向无环图。
强连通图是指一个有向图中任意两点v1、v2间存在v1到v2的路径及v2到v1的路径的图。
1．设有一有向图为G=（V，E）。
其中，V={v1,v2,v3,v4,v5}，E={,,,,,,}，请画出该有向图并判断是否是强连通图。
分析：
作该题的关键是弄清楚以下两点
（1）边集E中表示一条以vi为弧尾，vj为弧头的有向弧。
（2）强连通图是任意两顶点间都存在路径的有向图。
【答案】该有向图是强连通图，表示如下：
2．画出1个顶点、2个顶点、3个顶点、4个顶点和5个顶点的无向完全图。
并说明在n个顶点的无向完全图中，边的条数为n（n-1）/2。
【答案】
【解析】因为在有n个顶点的无向完全图中，每一个顶点与其它任一顶点都有一条边相连，所以每一个顶点有n-1条边与其他顶点相连，则n个顶点有n（n-1）条边。
但在无向图中，顶点i到顶点j与顶点j到顶点i是同一条边，所以总共有n（n-1）/2条边。
3．对n个顶点的无向图G，采用邻接矩阵表示，如何判别下列有关问题：
（1）图中有多少条边?
（2）任意两个顶点i和j是否有边相连?
（3）任意一个顶点的度是多少?
【答案】
（1）无向图的邻接矩阵是对称的，故它的边数应是上三角或下三角的非0元个数。
（2）邻接矩阵中如果第i行第j列的元素非0则表示顶点i与顶点j相连。
（3）任意一个顶点vi的度是第i行或第i列上非0元的个数。
4．熟悉图的存储结构，画出下面有向图的邻接矩阵、邻接表、逆邻接表、十字链表。
写出邻接表表示的图从顶点A出发的深度优先遍历序列和广度优先遍历序列。
【答案】邻接矩阵如下：
邻接表如下：
逆邻接表如下：
十字链表如下：
深度优先遍历序列为ABCFED，广度优先遍历序列为ABDCEF
5．已知下面是某无向图的邻接表，画出该无向图，并分别给出从A出发的深度优先搜索生成树和广度优先搜索生成树。
【解析】作该题的关键是弄清楚邻接表的概念，理解深度优先搜索和广度优先搜索的全过程以及二者的区别。
【答案】该无向图如下所示：
深度优先搜索生成树为：
广度优先搜索生成树为：
6．请分别用Prim算法和Kruskal算法构造以下网络的最小生成树，并求出该树的代价。
【解析】Prim算法的操作步骤：
首先从一个只有一个顶点的集合开始，通过加入与其中顶点相关联的最小代价的边来扩充顶点集，直到所有顶点都在一个集合中。
【答案】
【解析】Kruscal算法的操作步骤：
首先将n个顶点看成n个互不连通的分量，从边集中找最小代价的边，如果落在不同连通分量上，则将其加入最小生成树，直到所有顶点都在同一连通分量上。
【答案】
7．写出求以下AOE网的关键路径的过程。
要求：
给出每一个事件和每一个活动的最早开始时间和最晚开始时间。
【解析】求关键路径首先求关键活动，关键活动ai的求解过程如下
（1）求事件的最早发生时间ve（j）,最晚发生时间vl（j）;
（2）最早发生时间从ve（0）开始按拓扑排序向前递推到ve（6）,最晚发生时间从vl（6）按逆拓扑排序向后递推到vl（0）;
（3）计算e（i）,l（i）：
设ai由弧表示，持续时间记为dut，则有下式成立
e（i）=ve（j）
l（i）=vl（k）-dut（）
（4）找出e（i）-l（i）=0的活动既是关键活动。
【答案】
顶点vevl
活动ell-e
V000
v122
v245
v31010
v477
v5910
v61414
a0000
a1044
a2011
a3297
a4220
a5451
a6770
a77103
a8451
a910100
a109101
关键路径为：
a0->a4->a6->a9
8．拓扑排序的结果不是唯一的，试写出下图任意2个不同的拓扑序列。
【解析】解题关键是弄清拓扑排序的步骤
（1）在AOV网中，选一个没有前驱的结点且输出；
（2）删除该顶点和以它为尾的弧；（3）重复上述步骤直至全部顶点均输出或不再有无前驱的顶点。
【答案】
（1）0132465
（2）0123465
9．给定带权有向图G和源点v1,利用迪杰斯特拉（Dijkstra）算法求从v1到其余各顶点的最短路径。
【解析】求解该题的关键是掌握迪杰斯特拉（Dijkstra）算法的设计原理----从一个顶点v到另一顶点vk的最短路径或者是（v,vk）或者是（v,vj,vk）,它的长度或者是从v到vk弧上的权值，或者是D[j]与vj到vk弧上的权值之和，其中D[j]是已经找到的从v到vj的最短路径。
【答案】S是已找到最短路径的终点的集合。
终点
从v1到各终点的D值和最短路径的求解
i=2
i=3
i=4
i=5
i=6
v2
5
（v1,v2）
5
（v1,v2）
v3
4
（v1,v3）
v4
32767
32767
32767
9
（v1,v2,v5,v4）
v5
32767
32767
6
（v1,v2,v5）
v6
32767
32767
12
（v1,v2,v6）
9
（v1,v2,v5,v6）
9
（v1,v2,v5,v6）
vj
v3
v2
v5
v4
v6
S
{v1,v3}
{v1,v2}
{v1,v2,v5}
{v1,v2,v5,v4}
{v1,v2,v5,v6}
10．利用Floyd算法求下图中各对顶点之间的路径。
【解析】Floyd算法是依次添加顶点来修改相应路径，也就是说,若（vi，．．．，vk）和（vk，．．．，vj）分别是从vi到vk和从vk到vj的中间顶点的序号不大于k-1的最短路径，则将（vi，．．．vk，．．．，vj）和已经得到的从vi到vj且中间顶点序号不大于k-１的最短路径相比较，其长度较短者便是从vi到vj的中间顶点的序号不大于k的最短路径。
经过n次比较后必求得vi到vj的最短路径，依次，可求得各对顶点间的最短路径。
求解的关键是求解如下的一个n阶方阵序列：
D（＿1），D（0），D
（1），．．．，D（k），D（n＿1）
其中
D（＿1）[i][j]=G．arcs[i][j]
D（k）=Min{D（k-1）[i][j]，D（k-1）[i][k]+D（k-1）[k][j]}0≤k≤n-1
【答案】
D
D（-1）
D（0）
D
（1）
D
（2）
0
1
2
0
1
2
0
1
2
0
1
2
0
0
1
7
0
1
7
0
1
4
0
1
4
1
∞
0
3
∞
0
3
∞
0
3
12
0
3
2
9
∞
0
9
10
0
9
10
0
9
10
0
P
P（-1）
P（0）
P
（1）
P
（2）
0
1
2
0
1
2
0
1
2
0
1
2
0
AC
AB
AC
AB
AC
ACB
AC
ACB
1
CB
CB
CB
CBA
CB
2
BA
BA
BAC
BA
BAC
BA
BAC
每对顶点之间的最短路径及长度总结如下：
顶点A到顶点C最短路径为：
A->C，长度为：
１
顶点A到顶点B最短路径为：
A->C->B，长度为：
4
顶点C到顶点A最短路径为：
C->B->A，长度为：
12
顶点C到顶点B最短路径为：
C->B，长度为：
3
顶点B到顶点A最短路径为：
B->A，长度为：
9
顶点B到顶点C最短路径为：
B->A->C，长度为：
10
8.4 应用题
1．顺序查找时间为O（n），二分法查找时间为O（log2n），散列法为O
（1），为什么有高效率的查找方法而低效率的方法不被放弃?
【答案】不同的查找方法适用的范围不同，高效率的查找方法并不是在所有情况下都比其他查找方法效率要高，而且也不是在所有情况下都可以采用。
2．对含有n个互不相同元素的集合，同时找最大元和最小元至少需进行多少次比较?
【答案】n-1次
【解析】设变量max和min用于存放最大元和最小元（的位置），第一次取两个元素进行比较，大的放入max，小的放入min。
从第2次开始，每次取一个元素先和max比较，如果大于max则以它替换max，并结束本次比较；若小于max则再与min相比较，在最好的情况下，比较下去都不用和min相比较，所以这种情况下，至少要进行n-1次比较就能找到最大元和最小元。
3．若对具有n个元素的有序的顺序表和无序的顺序表分别进行顺序查找，试在下述两种情况下分别讨论两者在等概率时的平均查找长度：
（1）查找不成功，即表中无关键字等于给定值K的记录；
（2）查找成功，即表中有关键字等于给定值K的记录。
【答案】
（1）不成功时需要n+1次比较
（2）成功时平均为（n+1）/2次
【解析】有序表和无序表顺序查找时，都需要进行n+1次比较才能确定查找失败。
因此平均查找长度都为n+1。
查找成功时，平均查找长度都为（n+1）/2，有序表和无序表也是一样的。
因为顺序查找与表的初始序列状态无关。
4．设有序表为（a,b,c,d,e,f,g,h,i,j,k,p,q），请分别画出对给定值a,g和n进行折半查找的过程。
【答案】
（1）查找a的过程如下（圆括号表示当前比较的关键字），经过三次比较，查找成功。
下标
1
2
3
4
5
6
7
8
9
10
11
12
13
区间
第一次比较
a
b
c
d
e
f
（g）
h
i
j
k
p
q
[a..q]
第二次比较
a
b
（c）
d
e
f
g
h
i
j
k
p
q
[a..f]
第三次比较
（a）
b
c
d
e
f
g
h
i
j
k
p
q
[a..b]
（2）g的查找过程如下，一次比较成功。
[abcdef（g）hijkpq]
（3）n的查找过程如下， 经过四次比较，查找失败。
下标
1
2
3
4
5
6
7
8
9
10
11
12
13
区间
升级会员 