资源描述：
《数据结构复习神卷》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、习题课3图、查找、内部排序若采用邻接矩阵来存储简单有向图，则其某一个顶点i的入度等于该矩阵____。A.第i行中值为1的元素个数B.所有值为1的元素个数C.第i行及第i列中值为1的总个数D.第i列中值为1的元素个数由邻接矩阵的定义可知，对于无向图，其邻接矩阵第i行元素的和即为顶点i的度，对于有向图，其邻接矩阵的第i行元素之和为顶点i的出度，而邻接矩阵的第i列元素之和为顶点i的入度设一个包含N个顶点、E条边的简单有向图采用邻接矩阵存储结构（矩阵元素A[i][j]等于1/0分别表示顶点i与顶点j之间有/无弧），则该矩阵的元素数目为_
2、_________,其中非零元素数目为__________。A.E2B.N2C.N2-E2D.N2+E2A.N B.N+E C.E D.N–E采用邻接表表示一有向图，若图中某顶点的入度和出度分别为d1和d2，则该顶点对应的单链表的结点数为（）A.d1B.d2C.d1-d2D.d1+d2求单源点最短路径的迪杰斯特拉(Dijkstra)算法是按____的顺序求源点到各顶点的最短路径的A.路径长度递减B.路径长度递增C.顶点编号递减D.顶点编号递增kruskal算法的时间复杂度为（），它对（）图较为适合。Prim算
3、法的时间复杂度为（），它对（）图较为适合。－O(eloge)(n是顶点数、e是边数)－边稀疏－O(n*n)－边稠密求解每对结点之间的最短路径问题时，设有向图G=共有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．
4、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.a,d,c,b,eB.d,a,b,c,eC.a,b,d,c,eD.a,b,c,e,d试述一种判定有向图G中是否有圈（回路）的方法－拓扑序列算法对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向
5、量的大小为__。A、nB、n+1C、n-1D、n+e拓扑排序是指有向图中的所有顶点排成一个线性序列的过程，若在有向图中从顶点vi到vj有一条路径，则在该线性序列中，顶点vi必然在顶点vj之前。因此，若不能得到全部顶点的拓扑排序序列，则说明该有向图一定_________。A.包含回路B.是强连通图C.是完全图D.是有向树判断题不是所有的AOV网都有一个拓扑序列－正确每个加权连通无向图的最小生成树都是惟一的－错误拓扑序列是无环有向图中所有顶点的一个线性序列，图中任意路径中的各个顶点在该图的拓扑序列中保持先后关系，____为图中所示有
6、向图的一个拓扑序列。A.1234567B.1526374C.5126347D.51237641234567一个加权连通无向图的最小生成树可以使用（）生成；一项过程完工所需的最少时间等于某个（）A.Hash算法B.Dijkstra算法C.Prim算法D.Huffman算法A.AOE网中源点到汇点事件最多的路径的长度B.AOE网中源点到汇点的最长路径的长度C.AOE网中源点到汇点的最短路径的长度D.AOE网中源点到汇点活动最多的路径的长度在活动图中，结点表示项目中各个工作阶段的里程碑，连接各个结点的边表示活动，边上的数字表示活动持续
7、的时间。在下面的活动图中，从A到J的关键路径是__(16)__，关键路径长度是__(17)__，从E开始的活动启动的最早时间是__(18)__。A.ABEGJB.ADFHJC.ACFGJD.ADFIJA.22B.49C.19D.35A.10B.12C.13D.15某工程计划图如下图所示，弧上的标记为作业编码及其需要的完成时间（天），作业E最迟应在第________天开始。A.7B.9C.12D.13某工程计划如下图所示，各个作业所需的天数如下表所示，设该工程从第0天工，则该工程的最短工期是（）天，作业J最迟应在第（）天开工A.1
8、7B.18C.19D.20A.11B.13C.14D.16在11个元素的有序表A[1..11]中进行折半查找([(low+high)/2])，查找元素A[11]时，被比较的元素的下标依次是__________。A.6，8，10，11B.6，9，10，11C.6，
