树、图习题及答案

1、、选择题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 一个具有1025个结点的二叉树的高 h为(C )A. 11 B . 10 C . 11至1025之间 D . 10至1024之间文档来自于网 络搜索3 二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK；中序遍历：HFIEJKG。该二叉树根的右子树的根是：(C )文档来自于网络搜索A、E B 、F C 、G D 、H4 引入二叉线索树的

2、目的是( A )A.加快查找结点的前驱或后继的速度B 为了能在二叉树中方便的进行插入与删除C.为了能方便的找到双亲D 使二叉树的遍历结果唯一5 设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1, M2和M3与森林F对应的二叉树根结点的右子树上的结点个数是(D )。文档来自于网络搜索A. M1B . M1+M2 C . M3 D . M2+M36 有n个叶子的哈夫曼树的结点总数为( D )。A.不确定B.2nC.2n+1D.2n-1文档来自于网络搜索7一个有n个结点的图，最少有(B :)个连通分量，最多有(D )个连通分量。A. 0B.1C.n-1D. n文档来自于网络搜索8无向图G

3、=(V,E),其中：V=a,b,c,d,e,f,E=(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)，对该图进行深度优先遍历，得到的顶点序列正确的选项是( D )。文档来自于网络搜索A. a,b,e,c,d,f B.a,c,f,e,b,d Ca,e,b,c,f,d D.a,e,d,f,c,b 文是(A )。文档来自于网络搜索A. V1,V3,V4,V6,V2,V5,V7C. V1,V3,V4,V5,V2,V6,V7二、填空题1 8层完全二叉树至少有7。文档来自于网络搜索档来自于网络搜索9 有向图 G=(V,E)，其中 V=V1,V2,V3,V4,V5,V6,V

4、7,E=<V1,V2>,<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,<V6,V7>,G 的拓扑序列B. V1,V 3,V 2,V 6,V4,V5,V7文档来自于网络搜索D. V1,V2,V5,V3,V4,V6,V7文档来自于网络搜索128个结点，拥有 100个结点的完全二叉树的最大层数为2 设有N个结点的完全二叉树顺序存放在向量A1:N中，其下标值最大的分支结点为N2 _。文档来自于网络搜索3 有数据 WG=7 19,

5、2, 6, 32, 3, 21, 10，那么所建 Huffman树的树高是 6 ，带权 路径长度 WPL为261 o文档来自于网络搜索4 G是一个非连通无向图，共有28条边，那么该图至少有 9个顶点。5 为了实现图的广度优先搜索，除了一个标志数组标志已访问的图的结点外， 还需 队列存放被访问的结点以实现遍历。文档来自于网络搜索6 Prim (普里姆)算法适用于求 _边稠密的网的最小生成树; kruskal (克鲁斯卡尔)算 法适用于求_边稀疏_的网的最小生成树。文档来自于网络搜索三、算法题1 将二叉树bt中每一个结点的左右子树互换的C语言算法如下，其中 ADDQ(Q,bt),DELQ(Q),E

6、MPTY(Q)分别为进队，出队和判别队列是否为空的函数，请填写算法 中得空白处，完成其功能。文档来自于网络搜索typedef struct nodeint data ; struct node *lchild, *rchild; bt no de;void EXCHANGE®node *bt)bt node *p, *q;if (bt)ADDQ(Q,bt);while(!EMPTY(Q) p=DELQ(Q);q=(1) p_>rchild _ 一； p->rchild=(2)(3)p->lchild _ _=q;if(p->lchild) ADDQ(Q,p-&

7、gt;lchild) ;if(p->rchild) (5)A 2 二叉树采用二叉链表存储，试设计一个算法计算一棵给定二叉树的叶子结点数。答：int leafs ( bitree t) int nu mleft ,nu mright;If ( t = NULL ) return 0;Else if ( t -> lchild = NuLL && t -> rchild = NuLL ) return 1;文档来自于网络搜索Else nu mleft = leafs ( t -> lchild );nu mright = leafs ( t -> rc

8、hild );Retur n ( nu mleft + nu mright ); /else / leafs3 二叉树采用二叉链表存储，试设计一个算法计算二叉树的深度。答： int depth ( bitree t) if ( !t ) depthval = 0;Else depthleft = depth ( t -> lchild );Depthright = depth ( t -> rchild );Depthval = 1 + ( depthleft > depthright ? depthleft : depthright );文档来自于网络搜索 / elseRe

9、tut n depthval; / depth4 二叉树采用二叉链表存储，试写出对二叉树的先序遍历非递归算法。答: void pretraverse ( bitree t ) in itstack ( s );If ( t ) push ( s , t );While ( ! stackempty ( s ) pop ( s , p )；Visit ( p -> data );If ( p -> rchild != NuLL ) push ( s , p -> rchild );文档来自于网络搜索If ( p -> lchild ) push ( s , p ->

10、 lchild ); / while/ if / pretraverse5试写出用普里姆(Prim )算法和克鲁斯卡尔(Kruskal )算法构造下列图的一棵最小支撑(或生成)树的过程。文档来自于网络搜索6 AOE网中顶点v1、a2、a3、a4、a5、a6、a7、发生时间、各事件的最晚发生时间4动的松弛时间，分别填表。用顶7其中：a1 = 3, a2= 6, a3= 2,自于网络搜索v3、V4、v2示出关键2小v6和v7分别表示7个事件，有向线段 a1、个活动，请分别计算出各事件的最早 各活动的最晚开始时间、各活 出关键活动。文档来自于网络搜索6a4= 4, a5Q 2, a6= 1, a7= 3, a8= 1, a9= 3, a10= 4 文档来事件V1V2V3V4V5V6V7最早发生时间ve03267510最晚发生时间vl03367610活动a1a 2a 3a 4a 5a 6a 7a 8a 9a 10最早开始时间e0003322675最晚开始时间10013453676松弛时间1 e0010131001关键活动：a1 a2 a4 a8 a9文档来自于网络搜索关键路径：v1 v2 v5 v7 和 v1 v4 v5 v77求解下面有向图的有关问题。(1) 判断此有向图是否有强联通分量？