假设有n个顶点e条边的有向图用邻接表表示，则删除与某个顶点v相关的所有边的时间复杂度为( )。

admin2019-08-15 98

问题假设有n个顶点e条边的有向图用邻接表表示，则删除与某个顶点v相关的所有边的时间复杂度为( )。

选项 A、0(n)
B、0(e)
C、0(n+e)
D、0(ne)

答案C

解析删除与某顶点v相关的所有边的过程如下：先删除下标为v的顶点表结点的单链表，出边数最多为n一1，对应时间复杂度为O(n)，再扫描所有边表结点，删除所有的入边，对应时间复杂度为O(e)。故总的时间复杂度为O(n+e)。

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

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

计算机408

学硕统考专业

相关试题推荐

北宋在统一南方割据势力的过程中特设()，把征南所得的财富统一存放，以作日后恢复幽燕之费。
(1)以太网采用了曼彻斯特编码，一个比特的数据需要两个信号来传输，那么为了达到100Mbps的数据传送速率，需要线路达到200Mbps的带宽。(2)以太网的最小帧长度是64字节，那么发送一个最小帧需要的时间T1=64×8／(100×106)，
假设某计算机的存储系统由Cache和主存组成j某程序执行过程中访存1000次，其中访问Cache缺失(未命中)50次，则Cache的命中率是()。
一个客户机利用FTP协议从服务器上下载文件，如下图所示为整个过程中协议交换的过程，请回答如下问题：(1)该协议层图中第四层协议是什么?(2)如果FTP客户端采用了LIST命令来获得FTP服务器上的文件列表，该列表采用什么端口传输?
给定页面请求序列RS=cadbebabcd，页框为4，起始为空，写出LRU页面置换过程。
下图是三个计算机局域网A，B和C，分别包含10台，8台和5台计算机，通过路由器互联，并通过该路由器接口d联入因特网。路由器各端口名分别为a、b、c和d(假设端口d接入IP地址为61．60．21．80的互联网地址)。LANA和LANB公用一个C类IP地址
网络拓扑结构如下图所示，与C相连接的节点B，E，D的权值分别是6，5，3。如果C收到的三张矢量表分别为：试根据距离矢量路由算法给出C所构造的路由表，并给出计算过程，路由表结构如下表所示。
若对n阶对称矩阵A[1．．n，1．．n]以行序为主序方式下将其下三角的元素(包括主对角线上的所有元素)依次存放于一维数组B[1．．n(n＋1)／2]中，则在B中确定aij(i
在下面的应用中，通常使用栈的是()。　Ⅰ递归调用Ⅱ括号匹配Ⅲ表达式求值
假定一组元素序列为{38，42，55，15，23，44，34，74，45，26}，按次序插入每个元素生成一棵平衡二叉树，那么最后得到的平衡二叉树中度为2的结点个数为()。

随机试题

简述芭蕾舞剧的含义，并举出三部芭蕾舞剧。
化疗病人需要进行保护性隔离的白细胞计数为（　　）。
下列制剂检查正确的是
男性，34岁，诊断为细菌性痢疾，遵医嘱行保留灌肠。为提高治疗效果，患者最好采取
关于细胞凋亡坏死(固缩坏死)，下列叙述中哪一项不正确
下列病变中显示为前牙针形高密度影像的是
A．《国家非处方药目录》B．《基本医疗保险药品目录》中的“甲类目录”C．《基本医疗保险药品目录》中的“乙类目录”D．《国家基本药物目录》可供临床治疗选择使用，疗效好，同类药品中价格略高的药品，纳入
在一个研讨班上，学员对假、劣药情形、使用法律和法律责任展开了讨论。讨论的情形主要包括四个：一是采用多加矫味剂生产儿童退热药；二是多加药用淀粉少用主药生产降压药；三是部分药品超过有效期；四是某抗菌药物的外包装上标示的适应证与批准的药品说明书中适应证表述不一致
以下哪一项情形不发生诉讼时效中止?()
我国也是世界上最早的一部教育专著是【】

最新回复(0)

假设有n个顶点e条边的有向图用邻接表表示，则删除与某个顶点v相关的所有边的时间复杂度为( )。

计算机408

学硕统考专业

北宋在统一南方割据势力的过程中特设()，把征南所得的财富统一存放，以作日后恢复幽燕之费。

(1)以太网采用了曼彻斯特编码，一个比特的数据需要两个信号来传输，那么为了达到100Mbps的数据传送速率，需要线路达到200Mbps的带宽。(2)以太网的最小帧长度是64字节，那么发送一个最小帧需要的时间T1=64×8／(100×106)，

假设某计算机的存储系统由Cache和主存组成j某程序执行过程中访存1000次，其中访问Cache缺失(未命中)50次，则Cache的命中率是()。

给定页面请求序列RS=cadbebabcd，页框为4，起始为空，写出LRU页面置换过程。

网络拓扑结构如下图所示，与C相连接的节点B，E，D的权值分别是6，5，3。如果C收到的三张矢量表分别为：试根据距离矢量路由算法给出C所构造的路由表，并给出计算过程，路由表结构如下表所示。

若对n阶对称矩阵A[1．．n，1．．n]以行序为主序方式下将其下三角的元素(包括主对角线上的所有元素)依次存放于一维数组B[1．．n(n＋1)／2]中，则在B中确定aij(i

在下面的应用中，通常使用栈的是()。 Ⅰ递归调用Ⅱ括号匹配Ⅲ表达式求值

假定一组元素序列为{38，42，55，15，23，44，34，74，45，26}，按次序插入每个元素生成一棵平衡二叉树，那么最后得到的平衡二叉树中度为2的结点个数为()。

简述芭蕾舞剧的含义，并举出三部芭蕾舞剧。

化疗病人需要进行保护性隔离的白细胞计数为（ ）。

下列制剂检查正确的是

男性，34岁，诊断为细菌性痢疾，遵医嘱行保留灌肠。为提高治疗效果，患者最好采取

关于细胞凋亡坏死(固缩坏死)，下列叙述中哪一项不正确

下列病变中显示为前牙针形高密度影像的是

A．《国家非处方药目录》B．《基本医疗保险药品目录》中的“甲类目录”C．《基本医疗保险药品目录》中的“乙类目录”D．《国家基本药物目录》可供临床治疗选择使用，疗效好，同类药品中价格略高的药品，纳入

以下哪一项情形不发生诉讼时效中止?()

我国也是世界上最早的一部教育专著是【】

在下面的应用中，通常使用栈的是()。　Ⅰ递归调用Ⅱ括号匹配Ⅲ表达式求值

化疗病人需要进行保护性隔离的白细胞计数为（　　）。