数据结构习题课第8、7、6章(网上的答案有些有问题的)

第8章图

8.2对于如图8.33所示的无向图，试给出：

m图中每个顶点的度；

(2)该图的邻接矩阵；

(3)该图的邻接表；

(4)该图的连通分量。

图8.33无向图

(1)D(V0)=2；D(VI)=2；D(V2)=3；D(V3)=3；D(V4)=2；D(V5)=1；

D(V6)=1.

'0101000'

'0101000'

1010000

1010000

0101100

0101100

1010100

⑵邻接矩阵1010100

0011000

0011000

0000001

0000001

0000010

0000010

veV-

(3)邻接表

(4)连通分量

©—©

8.5图&35所示的是某个无向图的邻接表，试:

(1)画出此图；

(2)写出从顶点A开始的DFS遍历结果；

(3)写出从顶点A开始的BFS遍历结果。

图8.35题8.5的邻接表

实用文档.

(2)

从顶点A开始的DFS遍历，深度优先遍历的根本思想：对于给定的图

G=(V,E),首先将V中每一个顶点都标记为未被访问，然后，选取一个源点yeV

将v标记为被访问，再递归地用深度优先搜索方法，依次搜索v的所有邻接点

w.假设w未曾访问过，那么以w为新的出发点继续深度优先搜索遍历，如果从v

出发所有路的顶点都已被访问过，那么结束。

A,B,C,F,E,G,D

从顶点A开始的BFS遍历，根本思想：对于给定的图G=(V,E),从图中某未访

问过的顶点vi出发：

1)访问顶点vi；

2)访问vi的所有未被访问的邻接点wl,w2，…wk；

3)依次从这些邻接点出发，访问它们的所有未被访问的邻接点；依此类推，直

到图中所有访问过的顶点的邻接点都被访问；

A,B,C,D,F,E,G

8.8对如图8.36所示的连通图，分别用Prim和Kruskal算法构造其最小生成

树。

图8.36无向连通网

解：(1)Prime算法的根本思路、步骤P167

Prim算法的根本步骤如下：

(1)初始化：U={uO},TREE={};

(2)如果U=V(G),那么输出最小生成树T,并结束算法；

(3)在所有两栖边中找一条权最小的边(u,v)1假设候选两栖边中的最小边不

止一条，可任选其中的一条)，将边(u,v)参加到边集TREE中，并将顶点v

并入集合U中。

(4)由于新顶点的参加，U的状态发生变化，需要对U与V-U之间的两栖边进

行调整。

(5)转步骤⑵

实用文档.

Prim算法构造最小生成树过程

(2)采用Kruskal算法求解最小生成树时首先要对边进行由小到大进行排序，

此题对边进行排序的结果是：(D,F)1、(C,F)2、此F)3、(A,C)4、此G)4、

(D.E)4、(D,B)4、(C,D)5、(E.G)5、(A,D)6、(D,G)6、(A,B)7。根据

8.9对于如图8.37所示的有向网，用Dijkstra方法求从顶点A到图中其他顶

点的最短路径，并写出执行算法过程中距离向量d与路径向量p的状态变化情

况。

实用文档.

图8.37有向网

解：

Dijkstra算法的根本思想：

把图中所有顶点分成两组，第一组包括已确定最短路径的顶点，初始时只含有

一个源点，记为集合S；第二组包括尚未确定最短路径的顶点，记为V-S。按最

短路径长度递增的顺序逐个把V-S中的顶点加到S中去，直至从vO出发可以到

达的所有顶点都包括到S中。在这个过程中，总保持从vO到第一组（S）各顶点

的最短路径都不大于从vO到第二组（V-S）的任何顶点的最短路径长度，第二组

的顶点对应的距离值是从vO到此顶点的只包括第一组（S）的顶点为中间顶点的

最短路径长度。对于S中任意一点j,vO到j的路径长度皆小于vO到［V-S）中

任意一点的路径长度。

距,向量d路径向量p

循环集合SV

01234560123456

初始化{A}-0480015288400-100-I0

1{AD}3048co152848380-10033

2{ADE}40486115284838040033

3{ADG}604S6115284838040033

4{ADGB}10486015284838010033

5{ADGBF}50485715284838050033

6{ADGBFC}20485715284838050033

（后面四行需要在集合S加上E）

从表中可以看出源点A到其它各顶点的最短距离及路径为:

AfB：48路径：A-*B

A-C：57路径：A-D-F—C

A-D：15路径：A-D

A—E：28路径：A—E

A-F：48路径：AfDfF

A-G：38路径：A-D-G

实用文档.

8.10试写出如图8.38所示的A0V网的4个不同的拓扑序列。

实用文档.

图8.38题8.10的AOV网

(这里也有点问题，等待老师再次讲解)

解：拓扑排序过程：

1)输入A0V网络。令n为顶点个数。

2)在A0V网络中选一个没有直接前驱(入度为0)的顶点，并输出之；

3)从图中删去该顶点，同时删去所有它发出的有向边；

4)重复以上(2)、(3)步，直到

全部顶点均已输出，拓扑有序序列形成，拓扑排序完成；

图8.38所示的AOV网的4个不同的拓扑序列为：

(1)ABDCEFGIH

(2)ABDECFGIH

(3)DABCEFGIH

(4)DAECBFGIH

8.11计算如图8.39所示的A0E网中各顶点所表示的事件的发生时间ve(j),

vl(j),各边所表示的活动的开始时间e(i),l(i),并找出其关键路径。

图8.39题8.10的A0E网

解：

(1)：e(i)：表示活动ai的最早开始时间。

1(i)：表示活动最迟开始时间的向量。

关键活动特征：e(i)=1(i)

1(j)-e(j)的值表示完成活动aj的时间余量，提前完成非关键活动并不

实用文档.

能提高整个工程的进度。

实用文档.

事件可能的最早开始时间ve(i)：对于某一事件vi,它可能的最早发生时间

事件允许的最晚发生时间vl(i)：对于某一事件vi,它允许的最晚发生时间是

在保证按时完成整个工程的前提下，该事件最晚必须发生的时间

ye(0)=0；

<匕,匕〉持续的时间｝

y8(i)=max{ve(J)+活动(1<Z<H-1)

jeP(i)

集合p(i)

e(k)=ye(i)；

I(k)=yt(j)-ten(<Vj,y>)；

求每一个顶点i的最晚允许发生时间M(i)可以沿

图中的汇点开始，按图中的逆拓扑序逐个递推出每

个顶点的M(i)o

可以得出:

实用文档.

顶点VeV|活动e11-e关键活动

Voj0▲0a。i0i00

V1j6j6aij0111

:5

V2|4a2।6；60(

V3j1313|41

V；22522a41

44fP

V52525a513130

2613152

22220

a7

第7章二叉树

7.1选择题。

(1)前序遍历和中序遍历结果相同的二叉树为(F)；前序遍历和后序遍历结

果相同的二叉树为(B)。

A.一般二叉树B.只有根结点的二叉树

C.根结点无左孩子的二叉树D.根结点无右孩子的二叉树

E.所有结点只有左子树的二叉树F.所有结点只有右子树的二叉树。

(2)以下有关二叉树的说法正确的选项是(B

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

C.二叉树中至少有一个结点的度为2D.二叉树中任一个结点的度均为2

(3)一棵完全二叉树上有1001个结点，其中叶子结点的个数为(D

A.250B.500C.254D.501

注：1023为深度是10的满二叉树，有512个叶子结点，1001比1023少22个节

点。所以有512-22+22/2=501片叶子

(4)一棵完全二叉树有999个结点，它的深度为(B)。

A.9B.10C.11D.12

(5)一棵具有5层的满二叉树所包含的结点个数为(B

A.15B.31C.63D.32

7.2用一维数组存放完全二叉树：ABCDEFGHI,那么后序遍历该二叉树的结点序

列为(HIDEBFGCA)。

实用文档.

7.10一棵二叉树的中序遍历的结果为ABCEFGHD，后序遍历的结果为

ABFHGEDC,试画出此二叉树。

解：

7.11一棵二叉树的前序遍历的结果为ABCDEF,中序遍历的结果为CBAEDF，试画

出此二叉树

7.14试编写一个函数，将一棵给定二叉树中所有结点的左、右子女互换。

解：

ttinclude"bintree.h〃

voidchange(bintreet)

{bintreep;

if(t)

(

p=t->lchild;

t->lchild=t->rchiId;

t->rchild=p;

change(t->lchild);

change(t->rchiId);

}

实用文档.

intmainO

{bintreet;

creat(&t);/*建立二叉树t的存储结构*/

preorder(t);

change(t);

printf(〃\n〃)；

preorder(t);

)

7.18假设二叉树采用链式方式存储，root为其根结点，p指向二叉树中的任意

一个结点，编写一个求从根结点到P所指结点之间路径长度的函数。

解：在后序遍历非递归算法中，当访问的结点为p时，其祖先点正好全部在栈

中，此时栈中结点的个数就是根结点到p所指结点之间路径长度。

#include<stdio.h>

#include<stdlib.h>

typedefchardatatype;

typedefstructnode/*二叉树结点定义*/

{datatypedata;

structnode*lchild,*rchild;

}bintnode;

typedefbintnode*bintree;

typedefstructstack

(

bintreedata[100];

inttag[100];

inttop;

}seqstack;

voidcreat(bintree*t);

/*函数Depth,功能：求根结点到x的路径长度*/

intDepth(bintreet,datatypex)

(

seqstacks;

inti=0,j;

s.top=0;

while(t||s.top!=0)

(

while(t)

{

s.data[s.top]=t;

s.tag[s.top]=0;

s.top++;

t=t->lchild;

)

while(s.top>0&&s,tag[s.top-1])

实用文档.

s.top——;

t=s.data[s.top];

if(t->data==x)returns.top;//此时栈中的结点都是x的祖先结点

)

if(s.top>0)

{

t=s.data[s.top-1];

s.tag[s.top-l]=l;

t=t->rchild;

)

elset=NULL;

第6章树

6.1树最适合用来表示具有(有序)性和(层次)性的数据。

6.2在选择存储结构时，既要考虑数据值本身的存储，还需要考虑(数据间关

系)

的存储。

6.3对于一棵具有n个结点的树，该树中所有结点的度数之和为(n-1)。

6.4一棵树如图6.11所示，试答复以下问题：

图6.11一棵树

(1)树中哪个结点为根结点？哪些结点为叶子结点？

答：A是根结点；E,G,H,I,C,J,K,L为叶结点。

(2)结点B的双亲为哪个结点？其子女为哪些结点？

答：B的双亲结点是A,其子女结点为E和F。

(3)哪些结点为结点I的祖先？哪些结点为结点B的子孙？

答：F,B,A是结点I的祖先结点；E,F,G,H,：［是B的子孙结点。

(4)哪些结点为结点D的兄弟？哪些结点为结点K的兄弟？

答：B,C,L是结点D的兄弟结点，J是结点K的兄弟结点。

(5)结点J的层次为多少？树的高度为多少？

答：结点J的层次为3,树的高度为4。

(6)结点A、C的度分别为多少？树的度为多少？

实用文档.

答：结点A的度为4,结点C的度是0,树的度是4。

(7)以结点B为根的子树的高度为多少？

答：以结点B为根的子树的高度是3。

(8)试给出该树的括号表示及层号表示形式。

答：该树的括号表示为：A(B(E,F(G,H,I)),C,D(J,K),L),该树的层

号

表示为：10A,20B,30E,30F,40G,40H,401,20C,20D,25J,25K,20L

6.5试写出图6.11所示树的前序遍历、后序遍历和层次遍历的结果。

图6.11一棵树

答：前序遍历：ABEFGHICDJKL

后序遍历：EGHIFBCJKDLA

层次遍历：ABCDLEFJKGHI

6.9假设树采用指针方式的孩子表示法表示，试编写一个非递归函数，实现树的

后序遍历算法。

答：

#include"tree.h"

intPostOrderByStack(TreeNode*root)

{

TreeNode*temp;

TreeNode*stack[MAXLEN];

//childSeq表示当前打印到了此树第几个孩子，

inttop,childSeq[MAXLEN];

inti;

top=-1;〃初始化空栈

temp=root;

while(1)

{

while(temp!=NULL)

(

for(i=0;i<MAXN;i++)

{