19填空对于以下等价类，采用“加权合并规则”（也称“重量权衡合并规则”），进行并查运算，给出最后父节点索引序列。Forthefollowingequivalenceclass,pleaseuse”weightedunionrule”andUNION/FINDalgorithmtowritedownthefinalparentnodeindexsequence.8-93-27-45-96-18-67-32-58-0注意：当合并大小相同的两棵树的时候，将第二棵树的根指向第一棵树的根；根节点的索引是它本身；数字之间用空格隔开。Notice:Whenwejointwotreeswiththesamesize,welettherootofthesecondtreepointtotherootofthefirsttree.Theindexoftherootnodeisitself.Separatethenumberswithonlyonespaces.
1单选在一个无向图中，所有顶点的度数之和等于所有边数的()倍。Inaundirectedgraph,thesumofdegreesofallverticesisequaltotheamountofalledgestimes().
A.2
B.3
C.1/2
D.1
2单选在有向图G的拓扑序列中，若顶点在顶点之前，则下列情形不可能出现的是（）。InthetopologicalordersequencesofthedirectedgraphG,ifvertexViappearsbeforeVj,thentheimpossiblesituationofthefollowingis()
A.G中有一条从
到
的路径ThereisapathfromVjtoViintheG.
B.G中有一条从到的路径GcontainsapathfromVitoVj.
C.G中没有边(，)Gdoesn’tcontainedge(Vi,Vj)
D.G中有边(，)Gcontainsedge(Vi,Vj).
3单选当各边上的权值满足什么要求时，宽度优先搜索算法可用来解决单源最短路径问题？Whatrequirementdotheweightofedgesshouldsatisfiedtomakewidth-firstsearchalgorithmcansolvesinglesourceshortestpathproblem?
A.均互不相等Eachedgeisnotequaltoeachother.
B.不一定相等Nolimitation.
C.不一定相等（忽略该选项）
D.均相等Equal
4多选下面关于图的说法正确的有Therightstatementsofgraphsinthefollowingare:
A.将有向图的一个强连通分量中的边全部反向仍然是强连通分量。Reversionalltheedgesofastronglyconnectedcomponentofadirectedgraph,thenthesubgraphisstillastronglyconnectedcomponent.
B.对于一个连通图，一定存在一种给边添加方向的方案使得这个图变成强连通图。Foraconnectedgraph,theremustbeawayofdirectingalltheedgesoftheoriginalgraphtomakethegraphstronglyconnectedgraph.
C.对于无向图，所有结点的度数加起来一定是偶数。Asforundirectedgraphs,thesumofdegreesofallverticesisdefinitelyevennumber.
D.对于有向图，每个结点的出度必须要等于入度。Asfordirectedgraph,eachvertices’out-degreeisequaltoitsin-degree.
数据结构与算法
北京大学
军职在线答案
大学网课