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

admin2022-06-07 43

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

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

答案B

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

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

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

计算机408

学硕统考专业

相关试题推荐

某双总线模型机如图8—3所示。双总线分别记为B1和B2；图8—3中连线的方向标明数据通路及流向，并注有相应的控制信号(微命令)；A、B、C、D为4个通用寄存器；X为暂存器；M为多路选择器，用于选择进入暂存器x的数据，存储器为双端口，分别面向总线B1和B2。
某字长为8bit的计算机中，x和y为无符号整数，已知x=68，y=80，x和y分别存放在寄存器A和B中。请回答下列问题(要求最终用十六进制表示二进制序列)。若x和y相减后的结果存放在寄存器D中，则寄存器D中的内容是什么?运算结果是否正确?此时，零标志Z
关于FTP的工作过程，下面说法错误的是()。
某机器采用16位单字长指令，采用定长操作码，地址码为5位，现已定义60条二地址指令，那么单地址指令最多有()条。
系统中有5个进程，每个进程的运行时间(单位：ms)、优先级和到达时刻，如下表所示：请给出当系统分别采用时间片轮转算法(时间片为Ires)、不可抢占优先级调度算法和抢占式优先级调度算法时，各进程的执行情况。
设将n(n，1)个整数存放到一维数组R中，试设计一个在时间和空间两方面尽可能有效的算法，将R中保有的序列循环左移P(0＜P＜n)个位置，即将R中的数据由(X1，X2，…，Xn)变换为(XP，XP+1，…，XN，X1，XP-1)，要求：(1)给出算
试编写一个建立带表头结点的双向循环链表的算法。
使用浏览器访问某大学Web网站主页时，不可能使用到的协议是_______。
某网络拓扑如图4-7所示，路由器R1通过接口E1、E2分别连接局域网1、局域网2，通过接口L0连接路由器R2，并通过路由器R2连接域名服务器与互联网。R1的L0接口的IP地址是202．118．2．1，R2的L0接口的IP地址是202．118．2．2，L1接
某计算机的主存地址空间大小为256MB，按字节编址。指令Cache和数据Cache分离，均有8个Cache行，每个Cache行大小为64B，数据Cache采用直接映射方式。现有两个功能相同的程序A和B，其伪代码如下：假定int类型数据用32位补码表示，

随机试题

胡旋舞的产生朝代是()
肌糖原分解不能直接补充血糖的原因是肌肉组织
《诸病源候论》的作者是
A．公正B．权利C．廉洁奉公D．医德评价E．医患关系属于医学伦理学基本原则的是
卫星天线的主要性能要求有()。
敷设仪表电缆时的环境温度要求塑料绝缘电缆不低于()℃，橡皮绝缘电缆不低于()℃。电缆电线敷设前，应进行外观检查和导通检查，并进行绝缘电阻测试。
关于国际税收抵免制度的说法，不正确的有()。
甲股份有限公司为上市公司(以下简称甲公司)，有关购入、持有和出售乙公司公司债券的资料如下：(1)甲公司本年1月1日，以1100万元(其中含交易费用60万元)的价款，从活跃市场购入乙公司当日发行的面值为1000万元、5年期的公司债券。该债券票面年利
【B1】【B4】
“布坎南式导语”(北大2010年研)

最新回复(0)

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

计算机408

学硕统考专业

关于FTP的工作过程，下面说法错误的是()。

某机器采用16位单字长指令，采用定长操作码，地址码为5位，现已定义60条二地址指令，那么单地址指令最多有()条。

系统中有5个进程，每个进程的运行时间(单位：ms)、优先级和到达时刻，如下表所示：请给出当系统分别采用时间片轮转算法(时间片为Ires)、不可抢占优先级调度算法和抢占式优先级调度算法时，各进程的执行情况。

设将n(n，1)个整数存放到一维数组R中，试设计一个在时间和空间两方面尽可能有效的算法，将R中保有的序列循环左移P(0＜P＜n)个位置，即将R中的数据由(X1，X2，…，Xn)变换为(XP，XP+1，…，XN，X1，XP-1)，要求：(1)给出算

试编写一个建立带表头结点的双向循环链表的算法。

使用浏览器访问某大学Web网站主页时，不可能使用到的协议是_______。

某网络拓扑如图4-7所示，路由器R1通过接口E1、E2分别连接局域网1、局域网2，通过接口L0连接路由器R2，并通过路由器R2连接域名服务器与互联网。R1的L0接口的IP地址是202．118．2．1，R2的L0接口的IP地址是202．118．2．2，L1接

某计算机的主存地址空间大小为256MB，按字节编址。指令Cache和数据Cache分离，均有8个Cache行，每个Cache行大小为64B，数据Cache采用直接映射方式。现有两个功能相同的程序A和B，其伪代码如下：假定int类型数据用32位补码表示，

胡旋舞的产生朝代是()

肌糖原分解不能直接补充血糖的原因是肌肉组织

《诸病源候论》的作者是

A．公正B．权利C．廉洁奉公D．医德评价E．医患关系属于医学伦理学基本原则的是

卫星天线的主要性能要求有()。

敷设仪表电缆时的环境温度要求塑料绝缘电缆不低于()℃，橡皮绝缘电缆不低于()℃。电缆电线敷设前，应进行外观检查和导通检查，并进行绝缘电阻测试。

关于国际税收抵免制度的说法，不正确的有()。

【B1】【B4】

“布坎南式导语”(北大2010年研)