哈尔滨工程大学考研-数据结构-7.doc
《哈尔滨工程大学考研-数据结构-7.doc》由会员分享,可在线阅读,更多相关《哈尔滨工程大学考研-数据结构-7.doc(4页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、一 、判断题1求最小生成树的Prim算法在边较少、结点较多时效率较高。2图的最小生成树的形状可能不唯一。 3用邻接矩阵法存储一个图时,在不考虑压缩存储的情况下,所占用的存储空间大小只与图中结点个数有关,而与图的边数无关。4邻接表法只用于有向图的存储,邻接矩阵对于有向图和无向图的存储都适用。5任何有向网络(AOV-网络)拓扑排序的结果是唯一的。6有回路的图不能进行拓扑排序。7存储无向图的邻接矩阵是对称的,故只存储邻接矩阵的下(或上)三角部分即可。8用邻接矩阵A表示图,判定任意两个结点Vi和Vj之间是否有长度为m的路径相连,则只要检查Am的第i行第j列的元素是否为0即可。9 AOE网中一定只有一条
2、关键路径。10关键路径上活动的工期一定能够缩短整个工程的工期。二、选择题1N条边的无向图的邻接表的存储中,边表的个数有( )。A)N B)2N C)N/2 D)N*N2最短路径的生成算法可用( )。A)普里姆算法 B)克鲁斯卡尔算法 C)迪杰斯特拉算法 D)哈夫曼算法3有拓扑排序的图一定是( )。A)有环图 B)无向图 C)强连通图 D)有向无环图4图的邻接表如下图所示: vertex firstedgeV0 1 3 V1 0 2 3 V21 V3 0 1 (选择题5图) 5 点V0出发进行深度优先搜索,经历的结点顺序为( )。A)V0,V3,V2,V1 B)V0,V1,V2,V3 C)V0,
3、V2,V1,V3 D)V0,V1,V3,V26设有向图n个顶点和e条边,进行拓扑排序时,总的计算时间为( )。A)O (nlog2e) B)O (en ) C)O ( elog2n) D)O (n+e)7对于含有n个顶点e条边的无向连通图,利用Kruskal算法生成最小代价生成树其时间复杂度为( )。A)O (elog2e) B)O (en ) C)O ( elog2n) D)O (nlog2n)8关键路径是事件结点网络中( )。A)从源点到汇点的最长路径 B)从源点到汇点的最短路径 C)最长的回路 D)最短的回路9N个顶点的强连通图至少有(1)条边。(1)A)n B)n1 C)n1 D)n(
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 哈尔滨工程 大学 考研 数据结构
限制150内