数据结构与复习神卷 .pptVIP

习题课3;若采用邻接矩阵来存储简单有向图，则其某一个顶点i的入度等于该矩阵____。 A. 第i行中值为1的元素个数 B. 所有值为1的元素个数 C. 第i行及第i列中值为1的总个数 D. 第i列中值为1的元素个数; 设一个包含N个顶点、E条边的简单有向图采用邻接矩阵存储结构（矩阵元素A[i][j]等于1/0分别表示顶点i与顶点j之间有/无弧），则该矩阵的元素数目为__________, 其中非零元素数目为__________ 。 A. E2???? B. N2 ???? C. N2-E2???? D. N2+E2  A. N???? ? B. N+E ???? C. E ???? D. N–E; 采用邻接表表示一有向图，若图中某顶点的入度和出度分别为d1和d2，则该顶点对应的单链表的结点数为（ ） A.d1 B.d2 C.d1-d2 D.d1+d2; 求单源点最短路径的迪杰斯特拉(Dijkstra)算法是按____的顺序求源点到各顶点的最短路径的 A. 路径长度递减 B. 路径长度递增 C. 顶点编号递减 D. 顶点编号递增; kruskal算法的时间复杂度为（ ），它对（ ）图较为适合。 Prim算法的时间复杂度为（ ），它对（ ）图较为适合。 －O(eloge) (n是顶点数、e是边数) －边稀疏 －O(n*n) －边稠密 ; 求解每对结点之间的最短路径问题时，设有向图G=V,E共有n个结点，结点编号1～n，设C是G的成本邻接矩阵，用Dk(i,j)即为图G 中结点i到j并且不经过编号比k还大的结点的最短路径的长度（Dn(i,j)即为图G中结点i到j的最短路径长度），则求解该问题的递推关系式为______ A．Dk(i,j)=Dk-1(i,j)+C(i,j) B．Dk(i,j)= min{Dk-1(i,j),Dk-1(i,j)+C(i,j)} C．Dk(i,j)= Dk-1(i,k)+Dk-1(k,j) D．Dk(i,j)= min{Dk-1(i,j),Dk-1(i,k)+Dk-1(k,j)}　　; 有向图G=(V,A)，其中V={a,b,c,d,e}，A={a,b,a,c,d,c,d,e,b,e,c,e}，对该图进行拓扑排序，下面序列中哪一个不是拓扑序列 A.a,d,c,b,e B.d,a,b,c,e C.a,b,d,c,e D.a,b,c,e,d 试述一种判定有向图G中是否有圈（回路）的方法 －拓扑序列算法;; 拓扑排序是指有向图中的所有顶点排成一个线性序列的过程，若在有向图中从顶点vi到vj有一条路径，则在该线性序列中，顶点vi必然在顶点vj之前。因此，若不能得到全部顶点的拓扑排序序列，则说明该有向图一定_________。 A. 包含回路 B. 是强连通图 C. 是完全图 D. 是有向树 ;判断题 不是所有的AOV网都有一个拓扑序列 －正确 每个加权连通无向图的最小生成树都是惟一的 －错误 ; 拓扑序列是无环有向图中所有顶点的一个线性序列，图中任意路径中的各个顶点在该图的拓扑序列中保持先后关系，____为图中所示有向图的一个拓扑序列。 A. 1 2 3 4 5 6 7 B . 1 5 2 6 3 7 4 C. 5 1 2 6 3 4 7 D. 5 1 2 3 7 6 4; 一个加权连通无向图的最小生成树可以使用（ ）生成；一项过程完工所需的最少时间等于某个（ ） A.Hash算法 B.Dijkstra算法 C.Prim算法 D.Huffman算法 A.AOE网中源点到汇点事件最多的路径的长度 B.AOE网中源点到汇点的最长路径的长度 C.AOE网中源点到汇点的最短路径的长度 D.AOE网中源点到汇点活动最多的路径的长度; 在活动图中，结点表示项目中各个工作阶段的里程碑，连接各个结点的边表示活动，边上的数字表示活动持续的时间。在下面的活动图中，从 A 到 J 的关键路径是 __ (16) __ ，关键路径长度是 __(17) __ ，从 E 开始的活动启动的最早时间是 __(18) __ 。 ; 某工程计划图如下图所示，弧上的标记为作业编码及其需要的完成时间（天），作业E最迟应在第________天开始。 A. 7 B. 9 C. 12 D. 13; 某工程计划如下图所示，各个作业所需的天数如下表所示，设该工程从第 0 天工，则该工程的最短工期是 （）天，作业 J 最迟