数据结构与算法习题及答案

内容发布更新时间 : 2024/11/15 21:51:35星期一 下面是文章的全部内容请认真阅读。

精心整理

cout<data;

DoubleTraverse(T->lchild); cout<data;

DoubleTraverse(T->rchild); } }

（5）计算二叉树最大的宽度（二叉树的最大宽度是指二叉树所有层中结点个数的最大值）。

[题目分析]求二叉树高度的算法见上题。求最大宽度可采用层次遍历的方法，记下各层结点数，每层遍历完毕，若结点数大于原先最大宽度，则修改最大宽度。

intWidth(BiTreebt)//求二叉树bt的最大宽度

{if(bt==null)return(0);//空二叉树宽度为0 else {BiTreeQ[];//Q是队列，元素为二叉树结点指针，容量足够大 front=1;rear=1;last=1;//front队头指针,rear队尾指针,last同层最右结点在队列中的位置 temp=0;maxw=0;//temp记局部宽度,maxw记最大宽度 Q[rear]=bt;//根结点入队列 while(front<=last) {p=Q[front++];temp++;//同层元素数加1 if(p->lchild!=null)Q[++rear]=p->lchild;//左子女入队 if(p->rchild!=null)Q[++rear]=p->rchild;//右子女入队 if(front>last)//一层结束， {last=rear; if(temp>maxw)maxw=temp;//last指向下层最右元素,更新当前最大宽度 temp=0; }//if }//while return(maxw); }//结束width （6）用按层次顺序遍历二叉树的方法，统计树中具有度为1的结点数目。 intLevel(BiTreebt)//层次遍历二叉树，并统计度为1的结点的个数 {intnum=0;//num统计度为1的结点的个数 if(bt){QueueInit(Q);QueueIn(Q,bt)；//Q是以二叉树结点指针为元素的队列 while(!QueueEmpty(Q)) {p=QueueOut(Q);printf(p->data);//出队,访问结点 if(p->lchild&&!p->rchild||!p->lchild&&p->rchild)num++;//度为1的结点 if(p->lchild)QueueIn(Q,p->lchild);//非空左子女入队 if(p->rchild)QueueIn(Q,p->rchild);//非空右子女入队 }}//if(bt)

return(num);}//返回度为1的结点的个数

（7）求任意二叉树中第一条最长的路径长度，并输出此路径上各结点的值。

[题目分析]因为后序遍历栈中保留当前结点的祖先的信息，用一变量保存栈的最高栈顶指针，每当退栈时，栈顶指针高于保存最高栈顶指针的值时，则将该栈倒入辅助栈中，辅助栈始终保存最长路径长度上的结点，直至后序遍历完毕，则辅助栈中内容即为所求。

voidLongestPath(BiTreebt)//求二叉树中的第一条最长路径长度

{BiTreep=bt,l[],s[];//l,s是栈，元素是二叉树结点指针，l中保留当前最长路径中的结点 inti，top=0,tag[],longest=0; 精心整理

精心整理

while(p||top>0)

{while(p){s[++top]=p；tag[top]=0;p=p->Lc;}//沿左分枝向下 if(tag[top]==1)//当前结点的右分枝已遍历

{if(!s[top]->Lc&&!s[top]->Rc)//只有到叶子结点时，才查看路径长度

if(top>longest){for(i=1;i<=top;i++)l[i]=s[i];longest=top;top--;}

//保留当前最长路径到l栈，记住最高栈顶指针，退栈 }

elseif(top>0){tag[top]=1;p=s[top].Rc;}//沿右子分枝向下 }//while(p!=null||top>0) }//结束LongestPath

（8）输出二叉树中从每个叶子结点到根结点的路径。

[题目分析]采用先序遍历的递归方法，当找到叶子结点*b时，由于*b叶子结点尚未添加到path中，因此在输出路径时还需输出b->data值。对应的递归算法如下： voidAllPath(BTNode*b,ElemTypepath[],intpathlen) { inti;

if(b!=NULL) {

if(b->lchild==NULL&&b->rchild==NULL)//*b为叶子结点 {

cout<<\到根结点路径:\for(i=pathlen-1;i>=0;i--) cout<

path[pathlen]=b->data;//将当前结点放入路径中 pathlen++;//路径长度增1 AllPath(b->lchild,path,pathlen);//递归扫描左子树 AllPath(b->rchild,path,pathlen);//递归扫描右子树 pathlen--;//恢复环境 } } }

第6章 图

1．选择题

（1）在一个图中，所有顶点的度数之和等于图的边数的（）倍。 A．1/2B．1 C．2D．4

（2）在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。 A．1/2B．1 C．2D．4

（3）具有n个顶点的有向图最多有（）条边。 精心整理

精心整理

A．nB．n(n-1)C．n(n+1)D．n2

（4）n个顶点的连通图用邻接距阵表示时，该距阵至少有（）个非零元素。 A．nB．2(n-1)C．n/2D．n2

（5）G是一个非连通无向图，共有28条边，则该图至少有（）个顶点。 A．7B．8 C．9D．10

（6）若从无向图的任意一个顶点出发进行一次深度优先搜索可以访问图中所有的顶点，则该图一定是（）图。

A．非连通B．连通C．强连通D．有向

（7）下面（ ）算法适合构造一个稠密图G的最小生成树。 A．Prim算法B．Kruskal算法C．Floyd算法D．Dijkstra算法

（8）用邻接表表示图进行广度优先遍历时，通常借助（）来实现算法。 A．栈B.队列C.树D．图 （9）用邻接表表示图进行深度优先遍历时，通常借助（）来实现算法。 A．栈B.队列C.树D．图 （10）深度优先遍历类似于二叉树的（）。 A．先序遍历B．中序遍历C．后序遍历D．层次遍历 （11）广度优先遍历类似于二叉树的（）。 A．先序遍历B．中序遍历C．后序遍历D．层次遍历 （12）图的BFS生成树的树高比DFS生成树的树高（）。 A．小B．相等C．小或相等D．大或相等 （13）已知图的邻接矩阵如图6.25所示，则从顶点0出发按深度优先遍历的结果是（）。 ?0?1??1??1?1??0??111110011000010010011101?01??00??10?10??01?10??0011000A．0243156 B．0136542 C．0134256 D．0361542 图6.25邻接矩阵 （14）已知图的邻接表如图6.26所示，则从顶点0出发按广度优先遍历的结果是（），按深度优先遍历的结果是（）。 A．0132B．0231 C．0321D．0123 图6.26邻接表

（15）下面（）方法可以判断出一个有向图是否有环。

A．深度优先遍历B．拓扑排序C．求最短路径D．求关键路径 2．应用题

（1）已知如图6.27所示的有向图，请给出： ①每个顶点的入度和出度； ②邻接矩阵； ③邻接表； ④逆邻接表。 精心整理

精心整理

（2）已知如图6.28所示的无向网，请给出： ①邻接矩阵； ②邻接表； ③最小生成树 a b c d e f g h → b 4 → c 3 → a 4 → c 5 → a 3 → b 5 → b 5 → c 5 → b 9 → d 7 → d 6 → e 3 → d 5 → f 2 → c 5 → d 4 5 5 7 3 2 6 6 → d → d → e → f → g → h → g → e → h → f ^ ^ ^ ^ 9 ^ 5 ^

图6.27有向

图 6.28无向 6 → g 5 → h 4^ （3）已知图的邻接矩阵如6.29所示。试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。 （4）有向网如图6.30所示，试用迪杰斯特拉算法求出从顶点a到其他各顶点间的最短路径，完成表6.9。

图6.30有向网 图6.29邻接矩阵 D 终点 b c d e f g S 终点集 {a,c} {a,c,f} {a,c,f,e} {a,c,f,e,d} {a,c,f,e,d,g} {a,c,f,e,d,g,b} 15 (a,b) 2 (a,c) 12 (a,d) ∞ 15 (a,b) 15 (a,b) 15 (a,b) 15 (a,b) 15 (a,b) i=1 i=2 i=3 i=4 i=5 i=6 12 (a,d) 10 (a,c,e) 6 (a,c,f) ∞ 11 (a,c,f,d) 10 (a,c,e) 11 (a,c,f,d) 16 (a,c,f,g) 14 (a,c,f,d,g) ∞ 16 (a,c,f,g) ∞ （5）试对图6.31所示的AOE-网：

①求这个工程最早可能在什么时间结束； 精心整理