下面关于Prim算法和Kmskal算法的时间复杂度正确的是( )。

admin2019-12-10 4

问题下面关于Prim算法和Kmskal算法的时间复杂度正确的是( )。

选项 A、Prim算法的时间复杂度与网中的边数有关，适合于稀疏图
B、Prim算法的时间复杂度与网中的边数无关，适合于稠密图
C、Kruskal算法的时间复杂度与网中的边数有关，适合于稠密图
D、Kruskal算法的时间复杂度与网中的边数无关，适合于稀疏图

答案B

解析 Prim算法的时间复杂度为O(n²)，与网中的边数无关，适合于稠密图；而Kruskal的算法复杂度为O(eloge)，与网中的边数有关，适合于稀疏图。

转载请注明原文地址:https://kaotiyun.com/show/Sh3i777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

某虚拟存储系统中有一个进程共有6页(0～5)，其中代码占3页(0～2)，数据占1页(3)，数据堆占1页(4)，用户栈占1页(5)。它们依次存放在外存的22，23，25，26存储块。当前，代码页已经分配在物理内存的66，67，87页，数据页为31，并已经进行
一个栈的入栈序列是1，2，3，4，5，则栈的不可能的输出序列是()。
有二个处理机P1和P2，它们各自有一个cache和主存，分别为C1、C2和M1、M2，其性能见下表：若两个处理机的指令系统相同，指令的执行时间与存储器的平均存取周期成正比，当执行某程序时，cache的命中率为70％，则P1处理机的速度比
设将n(n>1)个整数存放到一维数组R中。试设计一个在时间和空间两方面都尽可能高效的算法。将R中保存的序列循环左移p(0
假定一台计算机的显示存储器用DRAM芯片实现，若要求显示分辨率为1600×1200，颜色深度为24位，帧频为85Hz，显存总带宽的50％用来刷新屏幕，则需要的显存总带宽至少约为____。
某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作。若元素a、b、c、d、e依次入此队列后再进行出队操作，则不可能得到的出队序列是____。
某计算机处理器主频为50MHz，采用定时查询方式控制设备A的I／O，查询程序运行一次所用的时钟周期数至少为500。在设备A工作期间，为保证数据不丢失，每秒需对其查询至少200次，则CPU用于设备A的I／O的时间占整个CPU时间的百分比至少是____。
某计算机的CPU主频为500MHz，CPI为5(即执行每条指令平均需5个时钟周期)。假定某外设的数据传输率为0．5MB／s，采用中断方式与主机进行数据传送，以32位为传输单位，对应的中断服务程序包含18条指令，中断服务的其他开销相当于2条指令的执行时间。请
在下列事件中，哪个不是设备分配中应该考虑的问题()。

随机试题

在操作练习过程中，教师应当对学生的操作情况做出________，调整自己、提高操作能力。
下列关于招股说明书预先披露的说法中,正确的是()。
语言到底是什么?假如它仅仅是交流工具，地球人都讲英语也就谈不上有啥危险。然而语言还是文化最原始、最根本的成分，是文化的载体和源泉。任何一种语言中都蕴藏着那个民族的智慧、技艺、信仰、风俗等丰富的内涵，一旦消亡，人类就会丧失对理解、认识和更新自我而言“不可替代
名与字意义相反的例证是()。
要在报表每一页的顶部都有输出的信息，需要设置的是()。
Ibecameinterestedinwritingatanearlyage.Sowhenmyfourth-gradeteachertoldmeabouta【C1】______writer’sconferencew
Whomostlikelyisthespeaker?
ThefollowingispartofamemorandumfromthepresidentofHumanaUniversity."Lastyearthenumberofstudentswhoenrolledin
Inthepastoysterswereraisedinmuchthesamewayasdirtfarmersraisedtomatoes—bytransplantingthem.First,farmersselec
【B1】【B6】

最新回复(0)

下面关于Prim算法和Kmskal算法的时间复杂度正确的是( )。

计算机408

学硕统考专业

一个栈的入栈序列是1，2，3，4，5，则栈的不可能的输出序列是()。

设将n(n>1)个整数存放到一维数组R中。试设计一个在时间和空间两方面都尽可能高效的算法。将R中保存的序列循环左移p(0

假定一台计算机的显示存储器用DRAM芯片实现，若要求显示分辨率为1600×1200，颜色深度为24位，帧频为85Hz，显存总带宽的50％用来刷新屏幕，则需要的显存总带宽至少约为____。

某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作。若元素a、b、c、d、e依次入此队列后再进行出队操作，则不可能得到的出队序列是____。

在下列事件中，哪个不是设备分配中应该考虑的问题()。

在操作练习过程中，教师应当对学生的操作情况做出________，调整自己、提高操作能力。

下列关于招股说明书预先披露的说法中,正确的是()。

名与字意义相反的例证是()。

要在报表每一页的顶部都有输出的信息，需要设置的是()。

Ibecameinterestedinwritingatanearlyage.Sowhenmyfourth-gradeteachertoldmeabouta【C1】______writer’sconferencew

Whomostlikelyisthespeaker?

ThefollowingispartofamemorandumfromthepresidentofHumanaUniversity."Lastyearthenumberofstudentswhoenrolledin

Inthepastoysterswereraisedinmuchthesamewayasdirtfarmersraisedtomatoes—bytransplantingthem.First,farmersselec

【B1】【B6】