计算机考研专业课复习科目包括数据结构、操作系统、计算机组成原理、计算机网络四门课程。其中数据结构这一科目兼具理论与实践，要求同学们在复习过程中不仅要对教材的基本概念进行记忆，同时还要结合知识点掌握相应的实际操作知识。为帮助同学们在计算机专业课复习上卓有成效，中公考研将为同学们整理全面的考点梳理，今天为大家带来的是数据结构的相关内容，请同学们适当参考，结合自身实际在全面复习的基础上进行重点理解记忆。

　　两种求最小生成树的算法(Prim和Kruskal)

　　Prim算法中有双重循环，外层是求n-1条边内层是在closedge[v].lowcost 中求最小值和并列的求得当前加入点对closedge[]的影响。所以他的时间复杂度是O( )，它与途中边的数目没有关系，所以比较适合用在边比较稠密的图中。(顶点数相同，不管边数，都相同)

　　Kruskal和他相对应，他的时间复杂度为O(eloge)，与图中的结点数目无关，至于边的个数有关。所以适合用在稀疏图中。(边数一定，不管顶点数，复杂度都相同)

　　求最小生成树的普里姆(Prim)算法中边上的权不可以为负，

　　typedef struct {

　　VertexType adjvex;

　　VRType lowcost;

　　}closedge[MAX_VERTEX_NUM];

　　假设cost(u,w)表示边(u,w)上的权值，则对于集合 V-U 中每个顶点 w，

　　closedge[LocateVex(G, w)].lowcost = Min{cost(u,w)|u∈U}

　　void MiniSpanTree_PRIM( MGraph G, VertexType u,SqList& MSTree)

　　{

　　// G 为数组存储表示的连通网，按普里姆算法从顶点 u 出发构

　　k = LocateVex ( G, u );

　　for ( j=0; j

　　if (j!=k) closedge[j] = { u, G.arcs[k][j].adj };//{adjvex,lowcost}

　　closedge[k].lowcost = 0; 　　　 // 初始状态，U={u}

　　for (i=1; i

　　{　 k = minimum(closedge);　　　　// 求出T的下一个结点(图中第k顶点)

　　// 此时closedge[k].lowcost =

　　// Min{ closedge[vi].lowcost | closedge[vi].lowcost>0, vi∈V-U }

　　printf(closedge[k].adkvex, G.vexs[k]); //输出生成编

　　closedge[k].lowcost = 0; 　　　// 第 k 顶点并入U集

　　for (j=0; j

　　if (G.arcs[k][j].adj < closedge[j].lowcost) //新顶点并入U后重新选最小边

　　closedge[j] = { G.vexs[k], G.arcs[k][j].adj };

　　} // for

　　} // MiniSpanTree