10填空请使用Kruskal算法求出下图的最小生成树，依次写出每次被选择的合法的合并代价最小的边的编号（如果同时存在多条边满足要求，选择编号最小的）。顶点a到顶点b(a<b)之间的边编号为ab，例如图中权值为1的边编号为02。(不同编号之间用一个空格分隔）PleaseuseKruskalalgorithmtothefollowinggraphandfindtheminimumspanningtree,andwritethenumberofthevalidvertexwithminimummergingcostinturn(iftherearemanyverticessatisfyrequirement,choosethevertexwithminimumnumber).Thenumberoftheedgeconnectingvertexaandvertexbisab.Liketheedgewithweight1inthegraph,itsnumberis02(differentnumbersseparatedbyablankspace).
11填空请使用Prim算法从结点0出发求下图的最小生成树，依次写出每次被加入到最小生成树中边的编号（如果同时存在多条边满足要求，选择编号最小的）。顶点a到顶点b(a<b)之间的边编号为ab，例如图中权值为1的边编号为02。(不同编号之间用一个空格分隔）Pleaseuseprimalgorithmstartingfromvertex0tofindtheminimumspanningtreeofthefollowinggraph,writethenumberoftheedgeaddedintotheminimumspanningtreeinturn((iftherearemanyverticessatisfyrequirement,choosethevertexwithminimumnumber).Thenumberoftheedgeconnectingvertexaandvertexbisab.Liketheedgewithweight1inthegraph,itsnumberis02(differentnumbersseparatedbyablankspace).
12填空题图为一无向图,分别写出从顶点1出发,按深度优先搜索遍历算法得到的顶点序列,和按广度优先搜索遍历算法得到的顶点序列
1单选对初始状态为递增的表按递增顺序排序，最省时间的是（）算法
A.快速排序
B.插入排序
C.堆排序
D.归并排序
2单选大部分排序算法是通过不断交换记录来减小序列中的逆置数，从而实现排序。假设有n个记录，那么交换序列中两个不同的记录，最多能减少()个逆置？
A.2n-1
B.n-1
C.n+1
D.2n-3
数据结构与算法
北京大学
军职在线答案
大学网课