ImageVerifierCode 换一换
格式:DOC , 页数:7 ,大小:56KB ,
资源ID:2667200      下载积分:6 金币
验证码下载
登录下载
邮箱/手机:
图形码:
验证码: 获取验证码
温馨提示:
支付成功后,系统会自动生成账号(用户名为邮箱或者手机号,密码是验证码),方便下次登录下载和查询订单;
特别说明:
请自助下载,系统不会自动发送文件的哦; 如果您已付费,想二次下载,请登录后访问:我的下载记录
支付方式: 支付宝    微信支付   
验证码:   换一换

开通VIP
 

温馨提示:由于个人手机设置不同,如果发现不能下载,请复制以下地址【https://www.zixin.com.cn/docdown/2667200.html】到电脑端继续下载(重复下载【60天内】不扣币)。

已注册用户请登录:
账号:
密码:
验证码:   换一换
  忘记密码?
三方登录: 微信登录   QQ登录  

开通VIP折扣优惠下载文档

            查看会员权益                  [ 下载后找不到文档?]

填表反馈(24小时):  下载求助     关注领币    退款申请

开具发票请登录PC端进行申请


权利声明

1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,个别因单元格分列造成显示页码不一将协商解决,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前可先查看【教您几个在下载文档中可以更好的避免被坑】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时联系平台进行协调解决,联系【微信客服】、【QQ客服】,若有其他问题请点击或扫码反馈【服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【版权申诉】”,意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4009-655-100;投诉/维权电话:18658249818。

注意事项

本文(数据结构图测验.doc)为本站上传会员【快乐****生活】主动上传,咨信网仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知咨信网(发送邮件至1219186828@qq.com、拔打电话4009-655-100或【 微信客服】、【 QQ客服】),核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
温馨提示:如果因为网速或其他原因下载失败请重新下载,重复下载【60天内】不扣币。 服务填表

数据结构图测验.doc

1、图练习: 1.图中有关路径的定义是( )。 A.由顶点和相邻顶点序偶构成的边所形成的序列 B.由不同顶点所形成的序列 C.由不同边所形成的序列 D.上述定义都不是 2.设无向图的顶点个数为n,则该图最多有( )条边。 A.n-1 B.n(n-1)/2 C. n(n+1)/2 D.0 E.n2 3.一个n个顶点的连通无向图,其边的个数至少为( )。 A.n-1 B.n C.n+1 D.nlogn; 4.要连通具有n

2、个顶点的有向图,至少需要( )条边。 A.n-l B.n C.n+l D.2n 5.n个结点的完全有向图含有边的数目(   )。 A.n*n B.n(n+1) C.n/2 D.n*(n-l) 6.一个有n个结点的图,最少有( )个连通分量,最多有( )个连通分量。 A.0 B.1 C.n-1 D.n 7.在一个无向图中,所有顶点的度数之和等于所有边数( )倍,在一个

3、有向图中,所有顶点的入度之和等于所有顶点出度之和的( )倍。 A.1/2 B.2 C.1 D.4 8. 下列说法不正确的是( )。 A.图的遍历是从给定的源点出发每一个顶点仅被访问一次 C.图的深度遍历不适用于有向图 B.遍历的基本算法有两种:深度遍历和广度遍历 D.图的深度遍历是一个递归过程 9.无向图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)},对该图进行深度优先遍历,得到的顶

4、点序列正确的是( )。 A.a,b,e,c,d,f B.a,c,f,e,b,d C.a,e,b,c,f,d D.a,e,d,f,c,b 10. 关键路径是事件结点网络中( )。 A.从源点到汇点的最长路径 B.从源点到汇点的最短路径 C.最长回路 D.最短回路 1.A 2.B 3.A 4.B 5.D 6.1B 6.2D 7.1B 7.2C 8C 9D 10A 二、判断题 1

5、树中的结点和图中的顶点就是指数据结构中的数据元素。( ) 2.在n个结点的无向图中,若边数大于n-1,则该图必是连通图。( ) 3.对有n个顶点的无向图,其边数e与各顶点度数间满足下列等式e=。( ) 4. 有e条边的无向图,在邻接表中有e个结点。( ) 5. 有向图中顶点V的度等于其邻接矩阵中第V行中的1的个数。( ) 6.强连通图的各顶点间均可达。( ) 7.邻接多重表是无向图和有向图的链式存储结构。( ) 8. 十字链表是无向图的一种存储结构。( ) 9.用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关。( )

6、10.有n个顶点的无向图, 采用邻接矩阵表示, 图中的边数等于邻接矩阵中非零元素之和的一半。( ) 11. 有向图的邻接矩阵是对称的。( ) 12.无向图的邻接矩阵一定是对称矩阵,有向图的邻接矩阵一定是非对称矩阵。( ) 13. 邻接矩阵适用于有向图和无向图的存储,但不能存储带权的有向图和无向图,而只能使用邻接表存储形式来存储它。( ) 14. 用邻接矩阵存储一个图时,在不考虑压缩存储的情况下,所占用的存储空间大小与图中结点个数有关,而与图的边数无关。( ) 15. 广度遍历生成树描述了从起点到

7、各顶点的最短路径。( ) 16.任何无向图都存在生成树。( ) 17. 不同的求最小生成树的方法最后得到的生成树是相同的.( ) 18.带权无向图的最小生成树必是唯一的。( ) 19. 最小代价生成树是唯一的。( ) 20.一个网(带权图)都有唯一的最小生成树。( ) 21.连通图上各边权值均不相同,则该图的最小生成树是唯一的。( ) 22.带权的连通无向图的最小(代价)生成树(支撑树)是唯一的。( ) 23.带权的连通无向图的最小代价生成树是唯一的。( ) 24. 最小生成树问题是构造连通网的最小代价生成树。( )

8、 1.√ 2. × 3.× 4.× 5.× 6.√ 7× 8× 9.× 10. √ 11× 12. × 13. × 14. √ 15.× 16.× 17.× 18.× 19.× 20.× 21.√ 22. × 23× 24√ 三、填空题 1.判断一个无向图是一棵树的条件是______。 2.有向图G的强连通分量是指______。 3.一个连通图的______是一个极小连通子图。 4.具有10个顶点的无向图,边的总数最多为______。 5.若用n表示图中顶点数目,则有__

9、条边的无向图成为完全图。 6. 设无向图 G 有n 个顶点和e 条边,每个顶点Vi 的度为di(1<=i<=n〉,则e=______ 7.G是一个非连通无向图,共有28条边,则该图至少有______个顶点。 8. 在有n个顶点的有向图中,若要使任意两点间可以互相到达,则至少需要______条弧。 9.在有n个顶点的有向图中,每个顶点的度最大可达______。 10.设G为具有N个顶点的无向连通图,则G中至少有______条边。 11.n个顶点的连通无向图,其边的条数至少为______。 12.如果含n个顶点的图形形成一个环,则它有______棵生成树。 13.N个顶点

10、的连通图的生成树含有______条边。 14.构造n个结点的强连通图,至少有______条弧。 15.有N个顶点的有向图,至少需要量______条弧 才能保证是连通的。 16.右图中的强连通分量的个数为( )个。 17.N个顶点的连通图用邻接矩阵表示时,该矩阵 至少有_______个非零元素。 18.在图G的邻接表表示中,每个顶点邻接表中所含的结点数,对于无向图来说等于该顶点的______;对于有向图来说等于该顶点的______。 19. 在有向图的邻接矩阵表示中,计算第I个顶点入度的方法是______。 20. 对于一个具有n个顶点e条边的无向图的邻接表的表示,则表

11、头向量大小为______,邻接表的边结点个数为______。 21. 已知一无向图G=(V,E),其中V={a,b,c,d,e } E={(a,b),(a,d),(a,c),(d,c),(b,e)}现用某一种图遍历方法从顶点a开始遍历图,得到的序列为abecd,则采用的是______遍历方法。 答案: 1.有n个顶点,n-1条边的无向连通图 2.有向图的极大强连通子图 3. 生成树 4. 45 5. n(n-1)/2 6 . 7. 9 8. n 9. 2

12、n-1) 10. N-1 11. n-1 12. n 13. N-1 14. n 15. N 16. 3 17. 2(N-1) 18. 度 出度 19. 第I列非零元素个数 20.n 2e 22. 深度优先 23.宽度优先遍历 四、 应用题 1.(1).如果G1是一个具有n个顶点的连通无向图,那么G1最多有多少条边?G1最少有多少条边? (2).如果G2是一个具有n个顶点的强连通有向图,那么G2最多有多少条边?G2最少有多少条边

13、 (3).如果G3是一个具有n个顶点的弱连通有向图,那么G3最多有多少条边?G3最少有多少条边? 2.n个顶点的无向连通图最少有多少条边?n个顶点的有向连通图最少有多少条边? 3. 首先将如下图所示的无向图给出其存储结构的邻接链表表示,然后写出对其分别进行深度,广度优先遍历的结果。 3 10 5 7 8 4 2 1 6 9 3 6 7 5 8 9 4 2 1

14、 4.给出图G: (1).画出G的邻接表表示图; (2).根据你画出的邻接表,以顶点①为根,画出G的深度优先生成树和广度优先生成树。 5.对一个图进行遍历可以得到不同的遍历序列,那么导致得到的遍历序列不唯一的因素有哪些? 6.考虑下图: (1)从顶点A出发,求它的深度优先生成树 (2)从顶点E出发,求它的广度优先生成树 (3)根据普利姆(Prim) 算法,求它的最小生成树 从A点开始 (4)根据kruskal 算法,求它的最小生成树 7.考虑下图: (1)从顶点A出发,求它的深度优先生成树 (2)从顶点E出发,求它的广度优先生成树 (3

15、根据普利姆(Prim) 算法,求它的最小生成树 从1点开始 (4)根据kruskal 算法,求它的最小生成树 答案: 1.(1)G1最多n(n-1)/2条边,最少n-1条边 (2) G2最多n(n-1)条边,最少n条边 (3) G3最多n(n-1)条边,最少n-1条边 (注:弱连通有向图指把有向图看作无向图时,仍是连通的) 2.n-1,n 3.深度优先遍历序列:125967384 宽度优先遍历序列:123456789 注:(1)邻接表不唯一,这里顶点的邻接点按升序排列 (2)在邻接表确定后,深度优先和宽度优先遍历序列唯一 (3)这里的遍历,均从顶点1开始 4.略 5.遍历不唯一的因素有:开始遍历的顶点不同;存储结构不同;在邻接表情况下邻接点的顺序不同。 6.设该图用邻接表存储结构存储,顶点的邻接点按顶点编号升序排列 (1)ABGFDEC (2)EACFBDG 7.略 7 / 7

移动网页_全站_页脚广告1

关于我们      便捷服务       自信AI       AI导航        抽奖活动

©2010-2025 宁波自信网络信息技术有限公司  版权所有

客服电话:4009-655-100  投诉/维权电话:18658249818

gongan.png浙公网安备33021202000488号   

icp.png浙ICP备2021020529号-1  |  浙B2-20240490  

关注我们 :微信公众号    抖音    微博    LOFTER 

客服