习题12(图的应用)
- 格式:doc
- 大小:274.00 KB
- 文档页数:3
二年级数学上册期末复习18道图形应用题专项练习题
1、
学校合唱队现在有多少人?
答:学校合唱队现在有()人。
2、小云和爸爸、妈妈、爷爷、奶奶一起去公园玩,爸爸拿30元买门票够吗?
3、
(1)男生种了多少棵树苗?
(2)男生和女生一共种了多少棵树苗?
4、有3个老师和32个学生,8顶帐篷能住下吗?
5
、小兔子拔萝卜。
(1) 一共有多少根萝卜?
(2)剩下的比运走的少多少根?
6、租6条船能坐下吗?
7、母鸡有52只,公鸡比母鸡少37只,公鸡有多少只?
我们班共有45人。
还剩28根。
已经运走了37根。
限乘8人
8、看图填上合适的数和运算符号。
答:一共有个。
9、10年以后父亲比女儿大多少岁?10
两只小兔一共拔了多少个萝卜?
11、小华、小亮和小兰三人跳绳。
我跳了24下我比小华少跳6下我比小华多跳12下
小华小亮小兰
他们三人共跳了多少下?
我今年41岁。
我今年13岁。
我拔了28个萝卜。
我拔了16个萝卜。
12、从宁波到北京有几种走法?
13、每两个队踢一场,一共要踢多少场?
14、6串一共有几个西红柿?
15、6张这样的桌子可以坐多少人?
16、
17、一间屋里有6只小狗6间屋里一共有多少只小狗?
18、教室里有4行双人课桌,每行 6张,一共有多少张课桌?。
二年级数学上册期末复习图形应用题专项练习题
1、
(1)12个面包,每盒放()个,可以放()盒。
□÷□=□
(2)()个面包,平均放在()个盒里,每盒放()个。
□÷□=□
(3)每盒放()个面包,可以放()盒,一共有()个。
□÷□=□
2、
铅笔2元一枝放大镜15元一个笔记本19元一本尺4元一副(1)买一枝铅笔,一个放大镜和一本笔记本,一共需要多少元?(2)买4副尺和1枝铅笔,20元够吗?
(3)你能提出一个用乘法解决的问题吗?
3、
5元 3元 4元
(1)买5枝钢笔要多少钱?
(2)买4本笔记本要多少钱?
(3)买4个茶杯需要多少钱?
(4)买一枝钢笔和一个茶杯需要多少钱?
4、
3元 5元 3元 24元 ( )元
(1)4个 要用多少元?
(2)一个 比一个 多27元,一个 要多少元?
□○□=□(元)
□○□=□(元) □○□=□(元) □○□=□
(元)
5、
格尺
1元 6角6元5角
(1)明明买6个闹钟花多少钱?
(2)红红买5本练习本花多少钱?
(3)请你再提出一个数学问题并解答。
6、卡车面包车大客车
45辆 36辆 12辆
(1)卡车比面包车多多少辆?(4分)
○ = ()答:卡车比面包车多()辆。
(2)面包车和大客车一共有多少辆?(4分)
○ = ()答:面包车和大客车共()辆。
(3)大客车比卡车少多少辆?(4分)
○ = ()答:大客车比卡车少()辆。
图论及其应用习题答案图论及其应用习题答案图论是数学的一个分支,研究的是图的性质和图之间的关系。
图是由节点和边组成的,节点表示对象,边表示对象之间的关系。
图论在计算机科学、电子工程、物理学等领域有着广泛的应用。
下面是一些图论习题的解答,希望对读者有所帮助。
1. 问题:给定一个无向图G,求图中的最大连通子图的节点数。
解答:最大连通子图的节点数等于图中的连通分量个数。
连通分量是指在图中,任意两个节点之间存在路径相连。
我们可以使用深度优先搜索(DFS)或广度优先搜索(BFS)来遍历图,统计连通分量的个数。
2. 问题:给定一个有向图G,判断是否存在从节点A到节点B的路径。
解答:我们可以使用深度优先搜索(DFS)或广度优先搜索(BFS)来遍历图,查找从节点A到节点B的路径。
如果能够找到一条路径,则存在从节点A到节点B的路径;否则,不存在。
3. 问题:给定一个有向图G,判断是否存在环。
解答:我们可以使用深度优先搜索(DFS)或广度优先搜索(BFS)来遍历图,同时记录遍历过程中的访问状态。
如果在搜索过程中遇到已经访问过的节点,则存在环;否则,不存在。
4. 问题:给定一个加权无向图G,求图中的最小生成树。
解答:最小生成树是指在无向图中,选择一部分边,使得这些边连接了图中的所有节点,并且总权重最小。
我们可以使用Prim算法或Kruskal算法来求解最小生成树。
5. 问题:给定一个有向图G,求图中的拓扑排序。
解答:拓扑排序是指将有向图中的节点线性排序,使得对于任意一条有向边(u, v),节点u在排序中出现在节点v之前。
我们可以使用深度优先搜索(DFS)或广度优先搜索(BFS)来遍历图,同时记录节点的访问顺序,得到拓扑排序。
6. 问题:给定一个加权有向图G和两个节点A、B,求从节点A到节点B的最短路径。
解答:我们可以使用Dijkstra算法或Bellman-Ford算法来求解从节点A到节点B的最短路径。
这些算法会根据边的权重来计算最短路径。
二年级数学下册期末图形应用题专项练习题1、下面是丁冬调查的本班同学最喜欢阅读的课外书的情况。
正正正正正正(1)把记录的结果填在下表中。
(2)最喜欢阅读( )的人数最多。
(3)最喜欢阅读( )和( )的人数一样多。
(4)如果丁冬所在的班级要采购新图书,你有什么建议?2、明明统计了自己这学期所用的作业本情况。
1.把统计的数据填在下表中。
2.根据统计的数据涂一涂。
(每个代表2本)3.明明这学期一共用了多少本作业本?4.大笔记和大方格的总本数比田字格少多少本?3、儿童节那天,爷爷、奶奶带着欢欢去公园,欢欢看见很多小朋友手里都拿着气球,非常漂亮。
她把气球的个数记录下来,并按颜色加以区分。
正正正正(1)把记录的结果填在下表中。
(2)欢欢一共记录了多少个气球?(3)红气球比粉气球少多少个?4、下面是实验小学三、四年级订阅报刊的情况。
《小学生数学报》《新语文学习报》《新希望英语报》三年级15份32份四年级18份27份52份(1)三年级这三种报刊一共订了60份,《新希望英语报》订了多少份?(2)四年级订《新希望英语报》的份数比《小学生数学报》和《新语文学习报》的总和多几份?5、4.下表是宿迁市第一实验小学学生三月份做好事的情况统计表。
(1)()年级做的好事最多,()年级做的好事最少,相差()件。
(2)()年级和()年级做的好事最接近。
(3)算一算,一年级和六年级一共做了多少件好事?(4)算一算,一年级、二年级、三年级一共做了多少件好事?6、明明在班级进行调查,得到如下数据:他们班不会游泳和不会溜冰的各有多少人?7、下面是二(1)班同学“五一”假期旅游的情况。
(1)根据上表涂色。
(每个代表1人) 二(1)班同学“五一”假期旅游的情况(2)去丹东的同学比去青岛的同学多几人?(3)请你再提出一个数学问题并解答。
8、新星小学二年级同学喜欢看的图书情况如下表。
(1)喜欢看《少儿百科》和《笑话》的同学比喜欢看《故事大王》的同学少多少人?(2)把《漫画》平均分给二年级的9个班,每班可以分几本?。
小学数学图形20道应用题专项练习题1、小红串珠子,按2个红珠子、3个黄珠子和4个绿珠子的顺序,一共串了81颗珠子。
(1)第81颗珠子是什么颜色的?(2)这时小红分别用了多少颗红珠子?多少颗黄珠子?多少颗绿珠子?2、有24个桃子,请你分一分。
(1)如果平均分给8只小猴,每只小猴分几个桃子?(2)你还想平均分给几只小猴,每只小猴分几个桃子?(请解答)3、小明一家用40元钱买票够吗?4、(1)芳芳的钱正好够买5辆玩具汽车,芳芳有多少元钱?(2)买1双鞋的钱,正好买5个皮球。
1个皮球几元钱?(3)丽丽有29元钱,买一个皮球后,剩下的钱可以买几个闹钟?5、一本书共100页。
还要读几天?6、两只猴子一共采了多少个香蕉?列式计算。
7、每人折的纸鹤同样多,他们一共折了多少只?8、公共汽车上原有36人,到中山路站时有4人下车,有13人上车。
9、一本书共100页。
还要读几天?10、每人折的纸鹤同样多,他们一共折了多少只?11、在一个长30 m,宽14 m的长方形草坪上有两条相交的小路,那么草坪的面积是多少平方米?12、学校食堂有100 kg油,共装了32个瓶子(如下图),并且每个瓶子都装满了。
请问大、小油瓶各多少个?13、据调查,一个儿童一天大约要喝2千克水。
一个没有关紧的水龙头一个星期流失的水可以供几个儿童喝一天?14、如图,教室窗户上的一块长方形玻璃被打碎了。
15、16、光明小学三年级去植树。
17、张老师带了100元钱,需要买5个球,有几种买法?请分别写在下面。
18、19、下图中长方形地的长增加到56米,宽不变,扩建后的面积是多少?20、这本书我多少天能看完?足 球 28元篮 球 18元保康药店益智口服液每瓶25元,买4瓶送1瓶一次买4瓶,每瓶便宜多少钱?28米252平方米这本书共有126页,我每天看14页!。
平衡方程及其应用一、 填空题:1.物体的平衡是指物体相对于地面__________或作________运动的状态。
2.平面汇交力系平衡的必要与充分条件是:_____。
该力系中各力构成的力多边形____。
平面汇交力系的特点为__________________。
其平衡的充分必要条件为_________________________________。
3.平面任意力系平衡方程,⎪⎩⎪⎨⎧===000BA m m X ∑∑∑的附加条件是_______________而⎪⎩⎪⎨⎧===000CB A m m m ∑∑∑的附加条件是_____________________________。
4.写出平面力偶系的平衡方程:_________________________。
5、平面平行力系的平衡方程:∑=0)F (M A,∑=0)F (M B,其附加条件是A 、B 连线与各力作用线__________。
6..题12图示刚体上某平面A 、B 、C 、D 处作用有大小相等的四个力,四边形边长均相等,该平面力系处于___________状态。
7.平面一般力系向平面内一点简化为一个力R ’和一个力偶M 。
,这个力称原力系的_____,这个力偶称为原力系对简化中点O 的_______。
平面一般力系平衡的充要条件为_____________________________。
8.当平面任意力系的主矢和对任一点的主矩均等于零时,则该力系为_________力系。
二、选择题1.某简支梁AB受载荷如图所示,现分别用R A、R B表示支座A、B处的约束反力,则它们的关系为( )。
A.R A<R BB.R A>R BC.R A=R BD.无法比较2.图示平面机构,正方形平板与直角弯杆ABC在C处铰接。
平板在板面内受矩为M=8N·m的力偶作用,若不计平板与弯杆的重量,则当系统平衡时,直角弯杆对板的约束反力大小为( )A.2NB.4NC.22ND.42N3.三直角折杆AB、BC、BD连接如题3图示,不计自重。
一次函数图象性质应用(习题)➢复习巩固1.一次函数y=mx+2 与正比例函数y=2mx(m 为常数,且m≠0)在同一平面直角坐标系中的图象可能是()A.B.C.D.2.在同一坐标系中,函数y=-ax 与y =2x -a 的图象大致是3()A.B.C.D.3.两条直线y1=ax+b 与y2=bx+a 在同一平面直角坐标系中的图象可能是()A.B.C.D.4.已知一次函数y=kx+b 与正比例函数y=kbx,它们在同一平面直角坐标系中的图象可能是()A.B.C.D.15.函数y=mx-n 与正比例函数y=mnx(m,n 为常数,且mn≠0)在同一平面直角坐标系中的图象中,一定不正确的是()A.B.C.D.6. 已知点(-2,y1),(1,y2)在直线y=5x+3 上,则y1,y2 的大小关系是.7. 若A(-4,y1),B(2,y2),C(3,y3)三点都在直线y=(-k2-4)x-k上,则下列结论正确的是()A.y1>y2>y3 B.y1>y3>y2C.y3>y1>y2 D.y2>y3>y18. 若A(x1,-3),B(x2,2)是直线y=-2x+k 上的两点,则x1,x2的大小关系是.9.若一次函数y=kx+b的图象过第一、三、四象限,点A(-1,y1),B(3,y2)在其图象上,则y1,y2的大小关系是.10.若A(-2,y1),B(1,y2)在一次函数y=kx-1的图象上,且y1>y2,则一次函数y=kx-1的图象不经过第象限.11.一次函数y=kx+b的图象如图所示,则方程kx+b=3的解为.第11 题图第12 题图12.一次函数y=k1x+b1的图象l1与y=k2x+b2的图象l2相交于点P,则关于x的方程k1x+b1=k2x+b2的解是.2⎩⎨2x -y =-n⎨⎪13.如图,直线y=x+1与直线y=mx-n相交于点M(1,b),则关于x,⎧x +1 =yy的方程组⎨mx -y =n的解为.⎧x -3 -y = 0 ⎧x =-514.已知方程组⎨2x + 2 -y = 0的解为⎨y =-8,则直线y=x-3与⎩⎩y=2x+2交点的坐标为.15.已知一次函数y1=2x+m与y2=2x+n(m≠n)的图象如图所示,则关于x,y的二元一次方程组⎧2x -y =-m的解的个数为⎩()A.0 个B.1 个C.2 个D.无数个⎧5x + 6 y = 1616.若关于x,y的方程组⎪6x +⎩ 5⎧4x + 5 y = 7y = 4m有无穷多组解,则关于x,y的方程组⎨⎩10mx + 7 y =11的解为.3⎩ ⎨ 【参考答案】 ➢ 复习巩固1. C2. A3. D4. A5. A6. y 2 > y 17. A8. x 1 > x 29. y 2 > y 110. 一11. x =212. x =-2 13. ⎧x = 1⎨ y = 214. (-5,-8)15. A ⎧x = 116. ⎪ 2 ⎪⎩ y = 14。
《自动控制原理》习题习题11有一水位控制装置如图所示。
试分析它的控制原理,指出它是开环控制系统闭环控制系统?说出它的被控量,输入量及扰动量是什么?绘制出其系统图。
2 某生产机械的恒速控制系统原理如图所示。
系统中除速度反馈外,还设置了电流正反馈以补偿负载变化的影响。
试标出各点信号的正负号并画出框图。
3图示为温度控制系统的原理图。
指出系统的输入量和被控量,并画出系统框图。
4.自动驾驶器用控制系统将汽车的速度限制在允许范围内。
画出方块图说明此反馈系统。
5.双输入控制系统的一个常见例子是由冷热两个阀门的家用沐浴器。
目标是同时控制水温和流量,画出此闭环系统的方块图,你愿意让别人给你开环控制的沐浴器吗?6.开环控制系统和闭环控制系统各有什么优缺点?7.反馈控制系统的动态特性有哪几种类型?生产过程希望的动态过程特性是什么?习题21 试分别写出图示各无源网络的传递函数。
习题1图2 求图示各机械运动系统的传递函数。
(1)求图a的=?(2)求图b的=?(3) 求图c的=?习题2图3 试分别写出图中各有源网络的传递函数U2(s)/ U1(s)。
习题3图4交流伺服电动机的原理线路和转矩-转速特性曲线如图所示。
图中,u为控制电压.T为电动机的输出转矩。
N为电动机的转矩。
由图可T与n、u呈非线性。
设在某平衡状态附近用增量化表示的转矩与转速、控制电压关系方程为k n、k c为与平衡状态有关的值,可由转矩-转速特性曲线求得。
设折合到电动机的总转动惯量为J,粘滞摩擦系数为f,略去其他负载力矩,试写出交流伺服电动机的方程式并求输入为u c,输出为转角θ和转速为n时交流伺服电动机的传递函数。
习题4图5图示一个转速控制系统,输入量是电压V,输出量是负载的转速 ,画出系统的结构图,并写出其输入输出间的数学表达式。
习题5图6 已知一系统由如下方程组组成,试绘制系统框图,求出闭环传递函数。
7 系统的微分方程组如下:其中K0,K1,K2,T均为正常数。
习题12(图的应用)一、选择题1、下面( B )方法可以判断出一个有向图是否有环。
A)深度优先遍历 B)拓扑排序 C)求最短路径 D)求关键路径2、在图采用邻接表存储时,求最小生成树的 Prim 算法的时间复杂度为( C )A)O(n) B)O(n+e) C)O(n*n) D)O(n*n*n) 3、在用邻接表表示图时,拓扑排序算法时间复杂度为( B )A)O(n) B)O(n+e) C)O(n*n) D)O(n*n*n) 4、求解最短路径的Floyd算法的时间复杂度为( D )A)O(n) B)O(n+e) C)O(n*n) D)O(n*n*n) 5、下面( A )算法适合构造一个稠密图G的最小生成树。
A) Prim算法 B)Kruskal算法 C)Floyd算法 D)Dijkstra算法6、最小生成树指的是( C )A)由连通网所得到的边数最少的生成树 B)由连通网所得到的顶点相对较少的生成树C)连通网中所有生成树中权值之和为最小的树 D)连通网的极小连通子图7、关键路径是事件结点网络中( A )A)从源点到汇点的最长路径 B)从源点到汇点的最短路径 C)最长回路 D)最短回路8、下列关于AOE网的叙述中,不正确的是( B )A)关键活动不按期完成就会影响整个工程的完成时间B)任何一个关键活动提前完成,那么整个工程将会提前完成C)所有的关键活动提前完成,那么整个工程将会提前完成D)某些关键活动提前完成,那么整个工程将会提前完成9、求图中一个顶点到其它各个顶点最短路径的算法是( C )A)Kruskal算法 B)Prim算法 C)Dijkstra算法 D)Floyd算法10、下面关于求关键路径的说法不正确的是( C )A)求关键路径是以拓扑排序为基础的B)事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同C)事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差D)关键活动一定位于关键路径上11、下面叙述中不正确的是( D )(1) 求源点到其余顶点的Dijkstra最短路径算法中弧上权不能为负的原因是在实际应用中无意义;(2) 利用Dijkstra求每一对不同顶点之间的最短路径的算法时间是O(n3);(图用邻接矩阵表示)(3) Floyd求每对不同顶点对的算法中允许弧上的权为负,但不能有权和为负的回路。
习题12(图的应用)
一、选择题
1、下面( B )方法可以判断出一个有向图是否有环。
A)深度优先遍历 B)拓扑排序 C)求最短路径 D)求关键路径2、在图采用邻接表存储时,求最小生成树的 Prim 算法的时间复杂度为( C )
A)O(n) B)O(n+e) C)O(n*n) D)O(n*n*n) 3、在用邻接表表示图时,拓扑排序算法时间复杂度为( B )
A)O(n) B)O(n+e) C)O(n*n) D)O(n*n*n) 4、求解最短路径的Floyd算法的时间复杂度为( D )
A)O(n) B)O(n+e) C)O(n*n) D)O(n*n*n) 5、下面( A )算法适合构造一个稠密图G的最小生成树。
A) Prim算法 B)Kruskal算法 C)Floyd算法 D)Dijkstra算法6、最小生成树指的是( C )
A)由连通网所得到的边数最少的生成树 B)由连通网所得到的顶点相对较少的生成树C)连通网中所有生成树中权值之和为最小的树 D)连通网的极小连通子图
7、关键路径是事件结点网络中( A )
A)从源点到汇点的最长路径 B)从源点到汇点的最短路径 C)最长回路 D)最短回路8、下列关于AOE网的叙述中,不正确的是( B )
A)关键活动不按期完成就会影响整个工程的完成时间
B)任何一个关键活动提前完成,那么整个工程将会提前完成
C)所有的关键活动提前完成,那么整个工程将会提前完成
D)某些关键活动提前完成,那么整个工程将会提前完成
9、求图中一个顶点到其它各个顶点最短路径的算法是( C )
A)Kruskal算法 B)Prim算法 C)Dijkstra算法 D)Floyd算法
10、下面关于求关键路径的说法不正确的是( C )
A)求关键路径是以拓扑排序为基础的
B)事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同
C)事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差
D)关键活动一定位于关键路径上
11、下面叙述中不正确的是( D )
(1) 求源点到其余顶点的Dijkstra最短路径算法中弧上权不能为负的原因是在实际应用中无意义;
(2) 利用Dijkstra求每一对不同顶点之间的最短路径的算法时间是O(n3);(图用邻接矩阵表示)
(3) Floyd求每对不同顶点对的算法中允许弧上的权为负,但不能有权和为负的回路。
A)(1),(2),(3) B)(1) C)(1),(3) D)(2),(3)
12、已知有向图G=(V,E),其中V={V1,V2,V3,V4,V5,V6,V7},
E={<V1,V2>,<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,<V6,V7>},G的拓扑序列是( A )A)V1V3V4V6V2V5V7 B)V1V3V2V6V4V5V7 C)V1V3V4V5V2V6V7 D)V1V2V5V3V4V6V7 13、在有向图G的拓扑序列中,若顶点Vi在顶点Vj之前,则下列情形不可能出现的是( D )
A)存在弧<Vi,Vj> B)有一条从Vi到Vj的路径
C)不存在弧<Vi,Vj> D)有一条从Vj到Vi的路径
14、下面关于有向图的运算的叙述中,哪个(些)是正确的( D )
Ⅰ.求有向图结点的拓扑序列,其结果必定是惟一的。
Ⅱ.求两个指定结点间的最短路径,其结果必定是惟一的。
Ⅲ.求事件结点网络的关键路径,其结果必定是惟一的。
A)只有Ⅰ B)Ⅰ和Ⅱ C)都正确 D)都不正确
二、填空题
1、Prim算法的时间复杂度是(o(n*n) ),适用于求(稠密)图的最小生成树;kruskal
算法的时间复杂度是( O(eloge)),适用于求(稀疏)图的最小生成树。
2、实现构造最小生成树的Prim算法需附设一个(辅助数组),用来记录(从U到v-u具体最小代价的
边),在(辅助数组)中存在一个分量,它包括( 2 )个域。
3、拓扑排序是从每个集合上的一个(偏序)得到该集合上的一个(全序)。
4、有向图G可拓扑排序的判别条件是(不存在环)。
5、设有向图有n个顶点和e条边,进行拓扑排序时,时间复杂度为( O(n+e))。
6、已知有向图G=(V,E),其中V={V1,V2,V3,V4},E={<V1,V2>,<V1,V3>,<V3,V2>,<V2,V4>,<V3,
V4>},图G的拓扑序列是( V1,V3,V2,V4)。
7、AOE网为边表示活动的网,是一个带权的(有向无环图),其长度最长的路径称为(关键路径)。
8、在AOE网中,从源点到汇点路径上各活动时间总和最长的路径称为(关键路径)。
9、AOV网中,结点表示(活动),边表示(活动时间的优先关系)。
AOE网中,结点表示(事
件),边表示(活动)。
10、在 AOV网中,存在环意味着(某项活动应以自己为先决条件),这是(荒谬)的;对程序
的数据流图来说,它表明存在(死循环)。
11、求最短路径的Dijkstra算法的时间复杂度为( O(n*n) )。
12、Dijkstra提出的求最短路径方法,引进一个辅助向量dist,它的每个分量dist[I]表示当前所找到的
从(源点)到每个(终点)的最短路径的(长度)。
13、求从某源点到其余各顶点的Dijkstra算法在图的顶点数为10,用邻接矩阵表示图时计算时间约为10ms,
则在图的顶点数为40,计算时间约为( 160 )ms。
14、 Dijkstra最短路径算法从源点到其余各顶点的最短路径的路径长度按(严格递增)次序依
次产生,该算法弧上的权出现(权值为负)情况时,不能正确产生最短路径。
三、应用题
1、利用Dijkstra算法求图1中从顶点a到其他个顶点间的最短路径,写出执行算法过程中各步的状态。
2、对图2所示的AOE-网,求每个活动的最早开始时间和最迟开始时间,并确定关键活动及整个工程的最早结束时间。
图1 图2
3、按Kruthkal算法写出求图3最小生成树的过程。
按Prim算法写出求图4最小生成树的过程。
图3 图4
4、求出图5中顶点1到其余各顶点的最短路径长度,写出所有拓扑有序序列,并指出应用拓扑排序算法得到
的是哪一个?
5、求出图6所示AOE 网的关键路径(要求写出各条弧代表的活动的最早、最迟开始时间)。
图5 图6
6、下表给出了某工程各工序之间的优先关系和各工序所需时间。
(1)画出相应的AOE 网。
(2)列出各事件的最早发生时间,最迟发生时间。
(3)找出关键路径并指明完成该工程所需最短时间。
7、下图是带权的有向图G 的邻接表表示法,其中出边表中的每个结点均含有三个字段,依次为边的另一个顶点在顶点表中的序号、边上的权值和指向下一个边结点的指针。
求:
(1)以V1出发深度遍历图所得结点序列; (2)以V1出发广度遍历图所得结点序列;
(3)从V1到V8的最短路径; (4)从V1到V8的关键路径; (7)写出至少2个拓扑序列。
四、算法设计题
2、设计算法,求出无向连通图中距离顶点V0的最短路径长度(最短路径长度以边数为单位计算)为K 的所有的结点,要求尽可能地节省时间。
5、有向图G 采用邻接表存储结构,试编写一算法判断图G 是否存在回路,若存在回路,则输出“Error ”的信息,否则输出“OK ”的信息,并输出图G 的一个拓扑序列。