首页 课程 师资 教程 报名

2020年Java常见算法笔试题

  • 2020-03-18 10:36:18
  • 4097次 动力节点

      最小生成树算法

  连通图:在无向图G中,若从顶点i到顶点j有路径,则称顶点i和顶点j是连通的。若图G中任意两个顶点都连通,则称G为连通图。

  生成树:一个连通图的生成树是该连通图的一个极小连通子图,它含有全部顶点,但只有构成一个数的(n-1)条边。

  最小生成树:对于一个带权连通无向图G中的不同生成树,各树的边上的权值之和最小。构造最小生成树的准则有三条:

  必须只使用该图中的边来构造最小生成树。

  必须使用且仅使用(n-1)条边来连接图中的n个顶点。

  不能使用产生回路的边。

  Prim算法

  假设G=(V,E)是一个具有n个顶点的带权连通无向图,T(U,TE)是G的最小生成树,其中U是T的顶点集,TE是T的边集,则由G构造从起始顶点v出发的最小生成树T的步骤为:

  初始化U={v},以v到其他顶点的所有边为候选边(U中所有点到其他顶点的边)。

  重复以下步骤(n-1)次,使得其他(n-1)个顶点被加入到U中。

  从候选边中挑选权值最小的边加入TE,设该边在V-U(这里是集合减)中的顶点是k,将k加入U中。

  考察当前V-U中的所有顶点j,修改候选边,若边(k,j)的权值小于原来和顶点j关联的候选边,则用(k,j)取代后者作为候选边。

  Kruskal算法

  假设G=(V,E)是一个具有n个顶点的带权连通无向图,T(U,TE)是G的最小生成树,其中U是T的顶点集,TE是T的边集,则由G构造从起始顶点v出发的最小生成树T的步骤为:

  置U的初始值等于V(即包含G中的全部顶点),TE的初始值为空

  将图G中的边按权值从小到大的顺序依次选取,若选取的边未使生成树T形成回路,则加入TE,否则放弃,知道TE中包含(n-1)条边为止。

  Dijkstra——贪心算法

  从一个顶点到其余顶点的最短路径

  设G=(V,E)是一个带权有向图,把图中顶点集合V分成两组,第1组为已求出最短路径的顶点(用S表示,初始时S只有一个源点,以后每求得一条最短路径v,...k,就将k加到集合S中,直到全部顶点都加入S)。第2组为其余未确定最短路径的顶点集合(用U表示),按最短路径长度的递增次序把第2组的顶点加入S中。

  步骤:

  初始时,S只包含源点,即S={v},顶点v到自己的距离为0。U包含除v外的其他顶点,v到U中顶点i的距离为边上的权。

  从U中选取一个顶点u,顶点v到u的距离最小,然后把顶点u加入S中。

  以顶点u为新考虑的中间点,修改v到U中各个点的距离。

  重复以上步骤知道S包含所有顶点。

  ASL

  由于查找算法的主要运算是关键字的比较,所以通常把查找过程中对关键字的平均比较次数(平均查找长度)作为衡量一个查找算法效率的标准。ASL=∑(n,i=1)Pi*Ci,其中n为元素个数,Pi是查找第i个元素的概率,一般为Pi=1/n,Ci是找到第i个元素所需比较的次数。

  顺序查找

  原理是让关键字与队列中的数从最后一个开始逐个比较,直到找出与给定关键字相同的数为止,它的缺点是效率低下。时间复杂度o(n)。

2020年Java常见算法笔试题

    以上就是动力节点Java培训机构小编介绍的“2020年Java常见算法笔试题”的内容,希望对大家有帮助,如有疑问,请在线咨询,有专业老师随时为你服务。

选你想看

你适合学Java吗?4大专业测评方法

代码逻辑 吸收能力 技术学习能力 综合素质

先测评确定适合在学习

在线申请免费测试名额
价值1998元实验班免费学
姓名
手机
提交