答案 第七章 图

第七章图习题答案基础知识：7.1 在图7.23所示的各无向图中：(1)找出所有的简单环。

(2)哪些图是连通图?对非连通图给出其连通分量。

(3)哪些图是自由树(或森林)?答:(1)所有的简单环：(同一个环可以任一顶点作为起点)(a)1231(b)无(c)1231、2342、12341(d)无(2)连通图：(a)、(c)、(d)是连通图，(b)不是连通图，因为从1到2没有路径。

具体连通分量为：(3)自由树(森林)：自由树是指没有确定根的树，无回路的连通图称为自由树：(a)不是自由树，因为有回路。

(b)是自由森林，其两个连通分量为两棵自由树。

(c)不是自由树。

(d)是自由树。

7.2 在图7.24(下图)所示的有向图中：(1) 该图是强连通的吗? 若不是，则给出其强连通分量。

(2) 请给出所有的简单路径及有向环。

(3) 请给出每个顶点的度，入度和出度。

(4) 请给出其邻接表、邻接矩阵及逆邻接表。

答：(1)该图是强连通的，所谓强连通是指有向图中任意顶点都存在到其他各顶点的路径。

(2)简单路径是指在一条路径上只有起点和终点可以相同的路径：有v1v2、v2v3、v3v1、v1v4、v4v3、v1v2v3、v2v3v1、v3v1v2、v1v4v3、v4v3v1、v3v1v4、另包括所有有向环,有向环如下：v1v2v3v1、v1v4v3v1(这两个有向环可以任一顶点作为起点和终点)(3)每个顶点的度、入度和出度：D(v1)=3ID(v1)=1OD(v1)=2D(v2)=2 ID(v2)=1OD(v2)=1D(v3)=3 ID(v3)=2OD(v3)=1D(v4)=2 ID(v4)=1OD(v4)=1(4)邻接表：(注意边表中邻接点域的值是顶点的序号，这里顶点的序号是顶点的下标值-1) vertex firstedge next┌─┬─┐┌─┬─┐┌─┬─┐0│v1│─→│ 1│─→│ 3│∧│├─┼─┤├─┼─┤└─┴─┘1│v2│─→│ 2│∧│├─┼─┤├─┼─┤2│v3│─→│ 0│∧│├─┼─┤├─┼─┤3│v4│─→│ 2│∧│└─┴─┘└─┴─┘逆邻接表：┌─┬─┐┌─┬─┐0│v1│─→│ 2│∧│├─┼─┤├─┼─┤1│v2│─→│ 0│∧│├─┼─┤├─┼─┤┌─┬─┐2│v3│─→│ 1│─→│ 3│∧│├─┼─┤├─┼─┤└─┴─┘3│v4│─→│ 0│∧│└─┴─┘└─┴─┘邻接矩阵：0 1 0 10 0 1 01 0 0 00 0 1 07.3 假设图的顶点是A,B...，请根据下述的邻接矩阵画出相应的无向图或有向图。

第七章：图练习题第七章：图练习题⼀、选择题1、⼀个有n个顶点的⽆向图最多有（）条边。

A、nB、n(n-1)C、n(n-1)/2D、2n2、具有6个顶点的⽆向图⾄少有（）条边才能保证是⼀个连通图。

A、5B、6C、7D、83、具有n个顶点且每⼀对不同的顶点之间都有⼀条边的图被称为（）。

A、线性图B、⽆向完全图C、⽆向图D、简单图4、具有4个顶点的⽆向完全图有（）条边。

A、6B、12C、16D、205、G是⼀个⾮连通⽆向图，共有28条边，则该图⾄少有（）个顶点A、6B、7C、8D、96、存储稀疏图的数据结构常⽤的是（）。

A、邻接矩阵B、三元组C、邻接表D、⼗字链表7、对⼀个具有n个顶点的图，采⽤邻接矩阵表⽰则该矩阵的⼤⼩为（）。

A、nD、n28、设连通图G的顶点数为n，则G的⽣成树的边数为（）。

A、n-1B、nC、2nD、2n-19、n个顶点的⽆向图的邻接表中结点总数最多有（）个。

A、2nB、nC、n/2D、n(n-1)10、对于⼀个具有n个顶点和e条边的⽆向图，若采⽤邻接表表⽰，则表向量的⼤⼩为（），所有顶点邻接表的结点总数为（）。

A、nB、n+1C、n-1D、2nE、e/2F、eG、2eH、n+e11、在有向图的邻接表存储结构中，顶点v在表结点中出现的次数是（）。

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、acfdeb13、采⽤邻接表存储的图的深度和⼴度优先搜索遍历算法类似于⼆叉树的（）和（）。

A、中序遍历B、先序遍历14、已知⼀有向图的邻接表存储结构如下图所⽰，分别根据图的深度和⼴度优先搜索遍历算法，从顶点v1出发，得到的顶点序列分别为（）和（）。

第七章图一、选择题1．图中有关路径的定义是（ A ）。

【北方交通大学 2001 一、24 （2分）】A．由顶点和相邻顶点序偶构成的边所形成的序列 B．由不同顶点所形成的序列C．由不同边所形成的序列 D．上述定义都不是2．设无向图的顶点个数为n，则该图最多有（B ）条边。

A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．0 E．n2【清华大学 1998 一、5 （2分）】【西安电子科技大 1998 一、6 （2分）】【北京航空航天大学 1999 一、7 （2分）】3．一个n个顶点的连通无向图，其边的个数至少为（ A ）。

【浙江大学 1999 四、4 (4分)】A．n-1 B．n C．n+1 D．nlogn；4．要连通具有n个顶点的有向图，至少需要（B ）条边。

【北京航空航天大学 2000 一、6(2分）】A．n-l B．n C．n+l D．2n5．n个结点的完全有向图含有边的数目（D ）。

【中山大学 1998 二、9 （2分）】A．n*n Ｂ．n（n＋１） C．n／2 D．n*（n－l）6．一个有n个结点的图，最少有（B）个连通分量，最多有（ D ）个连通分量。

A．0 B．1 C．n-1 D．n【北京邮电大学 2000 二、5 （20/8分）】7．在一个无向图中，所有顶点的度数之和等于所有边数（B ）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（ C ）倍。

【哈尔滨工业大学 2001 二、3 （2分）】A．1/2 B．2 C．1 D．48．用有向无环图描述表达式(A+B)*（（A+B）/A），至少需要顶点的数目为( A)。

【中山大学1999一、14】A．5 B．6 C．8 D．99．下列哪一种图的邻接矩阵是对称矩阵？（ B）【北方交通大学 2001 一、11 （2分）】A．有向图 B．无向图 C．AOV网 D．AOE网10. 下列说法不正确的是（ C ）。

【青岛大学 2002 二、9 （2分）】A．图的遍历是从给定的源点出发每一个顶点仅被访问一次 C．图的深度遍历不适用于有向图B．遍历的基本算法有两种：深度遍历和广度遍历 D．图的深度遍历是一个递归过程11．无向图G=(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 ）。

第七章图（参考答案）7．1（1）邻接矩阵中非零元素的个数的一半为无向图的边数；（2）A[i][j]= =0为顶点，I 和j无边，否则j和j有边相通；（3）任一顶点I的度是第I行非0元素的个数。

7．2（1）任一顶点间均有通路，故是强连通；（2）简单路径V4 V3 V1 V2;（3）0 1 ∞ 1∞ 0 1 ∞1 ∞ 0 ∞∞∞ 1 0邻接矩阵邻接表（2）从顶点4开始的DFS序列：V5,V3,V4,V6,V2,V1（3）从顶点4开始的BFS序列：V4,V5,V3,V6,V1,V27．4（1）①adjlisttp g; vtxptr i,j; //全程变量② void dfs(vtxptr x)//从顶点x开始深度优先遍历图g。

在遍历中若发现顶点j，则说明顶点i和j间有路径。

{ visited[x]=1; //置访问标记if (y= =j){ found=1;exit(0);}//有通路，退出else { p=g[x].firstarc;//找x的第一邻接点while (p!=null){ k=p->adjvex;if （!visited[k]）dfs(k);p=p->nextarc;//下一邻接点}}③ void connect_DFS (adjlisttp g)//基于图的深度优先遍历策略，本算法判断一邻接表为存储结构的图g种，是否存在顶点i //到顶点j的路径。

设 1<=i ,j<=n,i<>j.{ visited[1..n]=0;found=0;scanf (&i,&j);dfs (i);if (found) printf （” 顶点”,i,”和顶点”,j,”有路径”）；else printf （” 顶点”,i,”和顶点”,j,”无路径”）；}// void connect_DFS(2)宽度优先遍历全程变量，调用函数与（1）相同，下面仅写宽度优先遍历部分。

第七章 不完全竞争的市场1、根据图中线性需求曲线d 和相应的边际收益曲线MR ，试求：（1）A 点所对应的MR 值；（2）B 点所对应的MR 值。

解答：（1）根据需求的价格点弹性的几何意义，可得A 点的需求的价格弹性为：25)515(=-=d e 或者 2)23(2=-=d e 再根据公式)11(d e P MR -=，则A 点的MR 值为：MR=2×（2×1/2）=1 （2）与（1）类似，根据需求的价格点弹性的几何意义，可得B 点的需求的价格弹性为：21101015=-=d e 或者 21131=-=d e 再根据公式d e MR 11-=，则B 点的MR 值为：1)2111(1-=-⨯=MR 2、图7-19是某垄断厂商的长期成本曲线、需求曲线和收益曲线。

试在图中标出：（1）长期均衡点及相应的均衡价格和均衡产量；（2）长期均衡时代表最优生产规模的SAC 曲线和SMC 曲线；（3）长期均衡时的利润量。

解答：本题的作图结果下图所示：（1）长期均衡点为E 点，因为，在E 点有MR=LMC 。

由E 点出发，均衡价格为P 0，均衡数量为Q 0。

(2)长期均衡时代表最优生产规模的SAC 曲线和SMC 曲线如图所示。

在Q 0 的产量上，SAC 曲线和LAC 曲线相切；SMC 曲线和LMC 曲线相交，且同时与MR 曲线相交。

(3)长期均衡时的利润量有图中阴影部分的面积表示，即л=(AR(Q 0)-SAC(Q 0)Q 03、已知某垄断厂商的短期成本函数为30001461.023++-=Q Q Q STC ，反需求函数为P=150-3.25Q求：该垄断厂商的短期均衡产量与均衡价格。

解答：因为140123.02+-==Q Q dQ dSTC SMC且由225.3150)25.3150()(Q Q Q Q Q Q P TR -=-==得出MR=150-6.5Q根据利润最大化的原则MR=SMCQ Q Q 5.6150140123.02-=+-解得Q=20（负值舍去）以Q=20代人反需求函数，得P=150-3.25Q=85所以均衡产量为20 均衡价格为854、已知某垄断厂商的成本函数为236.02++=Q Q TC ，反需求函数为P=8-0.4Q 。

第七章：图练习题一、选择题1、一个有n个顶点的无向图最多有（）条边。

A、nB、n(n-1)C、n(n-1)/2D、2n2、具有6个顶点的无向图至少有（）条边才能保证是一个连通图。

A、5B、6C、7D、83、具有n个顶点且每一对不同的顶点之间都有一条边的图被称为（）。

A、线性图B、无向完全图C、无向图D、简单图4、具有4个顶点的无向完全图有（）条边。

A、6B、12C、16D、205、G是一个非连通无向图，共有28条边，则该图至少有（）个顶点A、6B、7C、8D、96、存储稀疏图的数据结构常用的是（）。

A、邻接矩阵B、三元组C、邻接表D、十字链表7、对一个具有n个顶点的图，采用邻接矩阵表示则该矩阵的大小为（）。

A、nB、(n-1)2C、(n+1)2D、n28、设连通图G的顶点数为n，则G的生成树的边数为（）。

A、n-1B、nC、2nD、2n-19、n个顶点的无向图的邻接表中结点总数最多有（）个。

A、2nB、nC、n/2D、n(n-1)10、对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表向量的大小为（），所有顶点邻接表的结点总数为（）。

A、nB、n+1C、n-1D、2nE、e/2F、eG、2eH、n+e11、在有向图的邻接表存储结构中，顶点v在表结点中出现的次数是（）。

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、acfdeb13、采用邻接表存储的图的深度和广度优先搜索遍历算法类似于二叉树的（）和（）。

A、中序遍历B、先序遍历C、后序遍历D、层次遍历14、已知一有向图的邻接表存储结构如下图所示，分别根据图的深度和广度优先搜索遍历算法，从顶点v1出发，得到的顶点序列分别为（）和（）。

第七章图一、选择题1、对于具有n个顶点的图，若采用邻接矩阵表示，则该矩阵的大小为（）。

A. nB. n2C. n-1D. (n-1)22、如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是（）。

A. 完全图B. 连通图C. 有回路D. 一棵树解析:在无向图中，如果从顶点v到顶点v1存在路径，则称v和v1是连通的。

完全图:若一个图的每一对不同顶点都恰有一条边相连。

3、关键路径是事件结点网络中（）。

A. 从源点到汇点的最长路径B. 从源点到汇点的最短路径C. 最长的回路D. 最短的回路4、下面（）可以判断出一个有向图中是否有环（回路）。

A. 广度优先遍历B. 拓扑排序C. 求最短路径D. 求关键路径5、带权有向图G用邻接矩阵A存储，则顶点i的入度等于A中（）。

A. 第i行非无穷的元素之和B. 第i列非无穷的元素个数之和C. 第i行非无穷且非0的元素个数D. 第i行与第i列非无穷且非0的元素之和6、采用邻接表存储的图，其深度优先遍历类似于二叉树的（）。

A. 中序遍历B. 先序遍历C. 后序遍历D. 按层次遍历7、无向图的邻接矩阵是一个（）。

A. 对称矩阵B. 零矩阵C. 上三角矩阵D. 对角矩阵8、当利用大小为N的数组存储循环队列时，该队列的最大长度是（）。

A. N-2B. N-1C. ND. N+1当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为?解析:n+1 因为队列的头指针指向的是第一个元素的前一个结点，而不是指向第一个元素，因此队列的头指针要占用一个结点长度，所以队列的长度就是n+1;9、邻接表是图的一种（）。

A. 顺序存储结构B.链式存储结构C. 索引存储结构D. 散列存储结构10、下面有向图所示的拓扑排序的结果序列是（）。

A. 125634B. 516234C. 123456D. 52164313256411、在无向图中定义顶点vi与vj之间的路径为从vi到vj的一个（）。

第七章 图一、单选题（ C ）1. 在一个图中，所有顶点的度数之和等于图的边数的 倍。

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

A ．1/2 B. 1 C. 2 D. 4 （B ）3. 有8个结点的无向图最多有 条边。

A ．14 B. 28 C. 56 D. 112 （ A ）一个n 个顶点的连通无向图，其边的个数至少为（ ）。

A ．n-1B ．nC ．n+1D ．nlogn ； （ C ）5. 有8个结点的有向完全图有 条边。

A ．14 B. 28 C. 56 D. 112 （B ）6. 用邻接表表示图进行广度优先遍历时，通常是采用 来实现算法的。

A ．栈 B. 队列 C. 树 D. 图 （ A ）7. 用邻接表表示图进行深度优先遍历时，通常是采用 来实现算法的。

A ．栈 B. 队列 C. 树 D. 图8. 下面关于求关键路径的说法不正确的是（ C ）。

A ．求关键路径是以拓扑排序为基础的B ．一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同C ．一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差D ．关键活动一定位于关键路径上9. 已知图的邻接矩阵如下，根据算法思想，则从顶点0出发，按深度优先遍历的结点序列是（ D ）A ． 0 2 4 3 1 5 6 B. 0 1 3 5 6 4 2 C. 0 4 2 3 1 6 5 D. 0 ⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡01000111011000010110101100110010001100100110111101 3 42 5 610、设数据结构A=(D，R)，其中D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，<3，4>，<4，1>，<4,2>}，则数据结构A是（C ）。

7-3 作图示连续梁的弯矩图及剪力图。

3232（g )32（h )（d)M P 图题７－3图(a)13P 32V 图（f )M 图（e )M 1图（c)（b)解：（１）选择基本结构，如（b ）图所示。

（２）画基本结构的荷载弯矩图、虚拟单位弯矩图，如（c ）、（d ）图示。

列力法方程如下：01111=∆+P x δ（3）求系数和自由项：EIlEI l 32311211=⨯⨯⨯=δ EI Pl l Pl EI P1621421121=⎥⎦⎤⎢⎣⎡⨯⨯⨯=∆ （4）求多余约束力323011111111Plx x PP -=∆-=→=∆+δδ（5）叠加法求最后弯矩值、画最后弯矩图。

如（e ）图示。

P M x M M +⋅=11)(323)323(111上拉PlPl M x M M P AB -=-⨯=+⋅= (6)切出AB 、BC 段，将弯矩以远端为中心从受拉边绕向受压边，剪力画成绕杆段的远端顺时针的正方向，内力、外力使各杆段平衡，受力如图（g ）、（h ）。

以各杆段的平衡求各杆端剪力。

AB 段处于平面任意力系作用，但没有水平荷载，无轴力。

⎪⎪⎩⎪⎪⎨⎧=+=-=--=→⎪⎩⎪⎨⎧=--=⋅--⋅-→==∑∑32133219232300232300P V P V P P P V V P V l P Pl l V Y M BA AB BA BA AB BA ABC 段处于平面力偶系作用而平衡，没有水平荷载，无轴力：32303230PV V l V Pl M CB BC BC ==→=⋅-→=∑。

7-5 作图示刚架的的弯矩图、剪力图、轴力图。

题7-5(a)图Pl 461P 11623211661P BC 11655N (h )19P解：（１）选择基本结例构，如（b ）图示。

（２）画基本结构的荷载弯矩图、虚拟单位弯矩图，如（c ）、（d ）、(e)图示。

列力法方程如下：⎩⎨⎧=∆+⋅+⋅=∆+⋅+⋅022221211212111P P x x x x δδδδ （3）求系数和自由项：232111522222216Pl Pl l Pl Pl l E I EI EI∆=-⨯⨯⨯⨯+⨯⨯=⋅32111211532222332296P l Pl l l Pl Pl l E I EI EI⎛⎫∆=-⨯⨯⨯⨯+⨯-⨯⨯=-⎪⋅⎝⎭32311117326l l l l E I EI EIδ=⨯⨯+⨯=⋅331221113()2224l l l l l E I EI EI δδ==-⨯⨯⨯-⨯=-⋅ 3333223223l l l l E I E I EI EIδ=++=⋅⋅（4）求多余约束力1211227353610()6496116351910()416232P P x x x P P x x x ⎧⎧⋅-⋅-==↑⎪⎪⎪⎪→⎨⎨⎪⎪-⋅+⋅+==→⎪⎪⎩⎩（5）叠加法求最后弯矩值、画最后弯矩图。

七、标准结构及标准零、组件7.1 螺纹∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙第77～77页习题7.2 螺纹连接和螺纹紧固件连接∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙第78～79页习题7.3 齿轮、键、销∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙第80～80页习题2345题号：题号：67891011121314题号：17.4 轴承和弹簧∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙第80～80页习题题号：1516171.已知下列螺纹代号，试识别其意义并填表。

2.根据给定的螺纹要素，标注螺纹的尺寸。

(1)普通螺纹，大径30mm，螺距1.5mm，单线，(2) 非螺纹密封的管螺纹，尺寸代号3/4。

右旋，中径及顶径公差代号6g，短旋合长度。

(3) 梯形螺纹，大径20mm，导程8mm，双线，右旋。

(4) 用螺纹密封的管螺纹，尺寸代号1/2。

3.将图中错处圈出，将正确的画在右边（包括尺寸）。

(1) M16(2) M24×1.5。

4.画出下列螺纹孔的两视图。

(1)M20。

孔为通孔，螺纹(2) M20。

孔为通孔，螺纹(3) M12×1.5。

螺纹盲孔，螺纹深攻到底，主、俯视图都全剖。

攻到30mm，主视图全剖。

18mm，钻孔深24mm，主视图全剖。

5.将下列两图的错处圈出，并将正确的画在下面。

(1) (2)6.将下图的错处圈出，并将正确的画在右面。

7.已知螺栓GB/T 5780 M16×L、垫圈GB/T 97.1 16、螺母GB/T 41 M16，板厚t1=t2=15mm。

用比例画法作螺栓连接的三视图（主视图全剖，俯、左视图画外形）。

第7章图二.判断题部分答案解释如下。

2. 不一定是连通图，可能有若干连通分量 11. 对称矩阵可存储上（下）三角矩阵14．只有有向完全图的邻接矩阵是对称的 16. 邻接矩阵中元素值可以存储权值21. 只有无向连通图才有生成树 22. 最小生成树不唯一，但最小生成树上权值之和相等26. 是自由树，即根结点不确定35. 对有向无环图，拓扑排序成功；否则，图中有环，不能说算法不适合。

42. AOV网是用顶点代表活动，弧表示活动间的优先关系的有向图,叫顶点表示活动的网。

45. 能求出关键路径的AOE网一定是有向无环图46. 只有该关键活动为各关键路径所共有，且减少它尚不能改变关键路径的前提下，才可缩短工期。

48．按着定义，AOE网中关键路径是从“源点”到“汇点”路径长度最长的路径。

自然，关键路径上活动的时间延长多少，整个工程的时间也就随之延长多少。

三．填空题1.有n个顶点，n-1条边的无向连通图2.有向图的极大强连通子图3. 生成树9. 2(n-1) 10. N-1 11. n-1 12. n 13. N-1 14. n15. N16. 3 17. 2（N-1） 18. 度出度 19. 第I列非零元素个数 20.n 2e21.(1)查找顶点的邻接点的过程 (2)O(n+e) (3)O(n+e) (4)访问顶点的顺序不同 (5)队列和栈22. 深度优先 23.宽度优先遍历 24.队列25.因未给出存储结构，答案不唯一。

本题按邻接表存储结构，邻接点按字典序排列。

25题（1） 25题（2） 26.普里姆（prim ）算法和克鲁斯卡尔（Kruskal ）算法 27.克鲁斯卡尔28.边稠密 边稀疏 29. O(eloge ） 边稀疏 30.O(n 2） O(eloge) 31.(1）（V i ，V j ）边上的权值 都大的数 （2）1 负值 （3）为负 边32.(1)n-1 (2)普里姆 (3)最小生成树 33.不存在环 34.递增 负值 35.16036.O(n 2） 37. 50，经过中间顶点④ 38. 75 39.O(n+e ）40.(1）活动 （2）活动间的优先关系 （3）事件 （4）活动 边上的权代表活动持续时间41.关键路径 42.（1）某项活动以自己为先决条件 （2）荒谬 （3）死循环 43.（1）零 （2）V k 度减1，若V k 入度己减到零，则V k 顶点入栈 （3）环44.（1）p<>nil (2)visited[v]=true (3)p=g[v].firstarc (4)p=p^.nextarc45.(1)g[0].vexdata=v (2)g[j].firstin (3)g[j].firstin (4)g[i].firstout (5)g[i].firstout (6)p^.vexj (7)g[i].firstout (8)p:=p^.nexti (9)p<>nil (10)p^.vexj=j(11)firstadj(g,v 0) (12)not visited[w] (13)nextadj(g,v 0,w)46.(1)0 (2)j (3)i (4)0 (5)indegree[i]==0 (6)[vex][i] (7)k==1 (8)indegree[i]==047.(1)p^.link:=ch[u ].head (2)ch[u ].head:=p (3)top<>0 (4)j:=top (5)top:=ch[j].count(6)t:=t^.link48.（1）V1 V4 V3 V6 V2 V5(尽管图以邻接表为存储结构，但因没规定邻接点的排列，所以结果是不唯一的。

第七章 图的基本概念一、 单项选择题1. 设V ＝{a,b,c,d},与V 能构成强连通图的边集E ＝(A ) (A) {<a,b>,<a,c>,<d,a>,<b,d>,<c,d>} (B) {<a,d>,<b,a>,<b,c>,<b,d>,<d,c>}(C) {<a,c>,<b,a>,<b,c>,<d,a>,<d,c>} (D) {<a,d>,<b,a>,<b,d>,<c,d>,<d,c>} 2. n 阶无向完全图K n 中的边数为（ A ）(A)2)1(-n n (B) 2)1(+n n (C) n (D)n(n+1) 3. 给定无向图G 图5－1所示，下面给出的顶点集子集中，不是点割集的为（A ） (A) {b,d} (B) {d} (C) {a,c} (D) {g,e} 4. 下列数组中，不能构成无向图的度数列的数组是( B ) (A) (1,1,1,2,3) (B) (1,2,3,4,5) (C) (2,2,2,2,2) (D) (1,3,3,3)5. 图 中 从v 1到v 3长度为3 的通路有（4）条。

A ． 0；B ． 1；C ． 2；D ． 3。

v 1到v 3长度为3 的通路: V 1V 3V 1V 3 ; V 1V 1V 1V 3 ; V 1V 4V 1V 3 ; V 1V 1V 4V 3 ; 6．给定无向图>=<E V G ,，如下图所示，下面哪个边集不是其边割集（ B ）。

A 、},,,{4341><><v v v v ；B 、},,,{6451><><v v v v ；C 、},,,{8474><><v v v v ；D 、},,,{3221><><v v v v。

⑴ 分析并回答下列问题：① 图中顶点的度之和与边数之和的关系?② 有向图中顶点的入度之和与出度之和的关系?③ 具有n 个顶点的无向图，至少应有多少条边才能确保是一个连通图? 若采用邻接矩阵表示，则该矩阵的大小是多少?④ 具有n 个顶点的有向图，至少应有多少条弧才能确保是强连通图的? 为什么?①在一个图中, 所有顶点的度数之后等于所有边数的2倍无向图中，顶点的度数之和是边数的两倍。

有向图中，任意一条边AB （A->B ）都会给A 提供一个出度，给B 提供一个入度，所以顶点的度之和 = 2 * 顶点入度之和 = 2*顶点出度之和 = 顶点入度之和+顶点出度之和=边数的两倍。

②对任意有向图顶点出度之和等于入度之和，且等于边的条数③至少应有n-1条边。

大小是n*n④ n 。

在有向图G 中，如果对于任何两个不相同的点a,b ，从a 到b 和从b 到a 都存在路径，则称G 是强连通图，强连通图必须从任何一点出发都可以回到原处,每个节点至少要一条出路。

⑵ 设一有向图G=(V,E)，其中V={a,b,c,d,e} ， E={<a,b>, <a,d>, <b,a>, <c,b>, <c,d>, <d,e>,<e,a>, <e,b>, <e,c>}① 请画出该有向图，并求各顶点的入度和出度。

② 分别画出有向图的正邻接链表和逆邻接链表。

有向图：a ：出度2，入度2b ：出度1，入度3c ：出度2，入度1d ：出度1，入度2e ：出度3，入度1 正邻接链表1234逆邻接链表1234⑶对图7-27所示的带权无向图。

① 写出相应的邻接矩阵表示。

② 写出相应的边表表示。

③ 求出各顶点的度。

邻接矩阵：∞ 9 6 3 ∞∞9 ∞∞ 5 8 ∞6 ∞∞ 2 9 53 5 2 ∞∞ 7∞ 8 9 ∞∞ 4∞∞ 5 7 4 ∞边表表示：12345123465顶点表0 1 90 2 60 3 31 3 51 4 82 3 2边表2 4 92 5 53 5 74 5 4各顶点的度：顶点1的度：3 顶点2的度：3 顶点3的度：4顶点4的度：4 顶点5的度：3 顶点6的度：3⑷已知有向图的逆邻接链表如图7-28所示。