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

admin2019-08-15 89

问题假设有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

学硕统考专业

相关试题推荐

下列描述中，属于冯.诺依曼体系结构的特点是()。①采用流水线技术；②指令和数据均以二进制表示；③存储程序并且存储时不区别数据和指令。
就绪队列中有n个进程等待使用一个CPU，那么，如果采用不同的调用算法，就有()种调度顺序。
在一个双链表中，在*p结点之前插入*q结点的操作是()。
已知某CPU有16根地址线、8根数据线，并用MREQ作为访存控制信号(低电平有效)。现有下列存储芯片：1K×4位ROM、2K×4位ROM、4K×8位ROM、4K×8位RAM、8K×4位RAM、8K×8位RAM和非门、与非门、或非门若干，如下图所
快速排序最易发挥其长处的情况是()。
某模型机的通路结构如下图所示，用寄存器传送语句(如PC→MAR)，拟出下列指令从读取到执行的完整流程。(1)数据传送指令MOVX(R0)，Y(R1)，源和目的操作数地址均采用变址寻址，第1个参数X为源操作数的形式地址，第2个参数为目的操作数的形
有效容量为128KB的Cache，每块16字节，8路组相联。字节地址为1234567H的单元调入该Cache，其Tag应是()。
下列关于最小生成树的叙述中，正确的是I．最小生成树的代价唯一Ⅱ．权值最小的边一定会出现在所有的最小生成树中Ⅲ．使用普里姆(Prim)算法从不同顶点开始得到的最小生成树一定相同Ⅳ．使用普里姆算法和克鲁斯卡尔(Kruskal)算法得到的最小生成树总不相
假定一组元素序列为{38，42，55，15，23，44，34，74，45，26}，按次序插入每个元素生成一棵平衡二叉树，那么最后得到的平衡二叉树中度为2的结点个数为()。
假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间，例如，“loading”和“being”的存储映像如下图所示。设str1和str2分别指向两个单词所在单链表的头结点，链表结点结构为，请设计一个时间上尽可能高效的算

随机试题

在世界贸易组织框架下最惠国待遇可以允许一些小的国家获得大国间谈判成果产生的贸易利益，因此在世贸组织中，最惠国待遇是()
人体肠道菌群中99．9％是厌氧菌．大肠杆菌等仅占0．1％。()
临床上诊断劳力型心绞痛最重要的依据
仲裁裁决后，当事人就同一纠纷再申请仲裁或向法院起诉，仲裁委员会不受理，人民法院可以受理。（）
甲公司历年按10％计提盈余公积，2009～2012年有关投资业务如下。(1)甲公司2009年7月1日与A公司达成资产置换协议，甲公司以投资性房地产和无形资产换入A公司对乙公司的投资，该资产交换协议具有商业实质且换入和换出资产的公允价值能够可靠计量，甲公司
以学生实践活动为基本特征的练习法，属于()
【2010福建】个体身心发展具有不均衡性，因此教育要()。
“要给学生一杯水，教师要有一桶水。”这主要强调教师需要()。
按对外购同定资产价款处理方式的不同进行划分，增值税的类型分为()。
TheUnitedStatescountsitspopulationeverytenyears,andeachcensusrevealsthattheracialandethnicmixischangingdram

最新回复(0)

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

计算机408

学硕统考专业

下列描述中，属于冯.诺依曼体系结构的特点是()。①采用流水线技术；②指令和数据均以二进制表示；③存储程序并且存储时不区别数据和指令。

就绪队列中有n个进程等待使用一个CPU，那么，如果采用不同的调用算法，就有()种调度顺序。

在一个双链表中，在*p结点之前插入*q结点的操作是()。

已知某CPU有16根地址线、8根数据线，并用MREQ作为访存控制信号(低电平有效)。现有下列存储芯片：1K×4位ROM、2K×4位ROM、4K×8位ROM、4K×8位RAM、8K×4位RAM、8K×8位RAM和非门、与非门、或非门若干，如下图所

快速排序最易发挥其长处的情况是()。

有效容量为128KB的Cache，每块16字节，8路组相联。字节地址为1234567H的单元调入该Cache，其Tag应是()。

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

在世界贸易组织框架下最惠国待遇可以允许一些小的国家获得大国间谈判成果产生的贸易利益，因此在世贸组织中，最惠国待遇是()

人体肠道菌群中99．9％是厌氧菌．大肠杆菌等仅占0．1％。()

临床上诊断劳力型心绞痛最重要的依据

仲裁裁决后，当事人就同一纠纷再申请仲裁或向法院起诉，仲裁委员会不受理，人民法院可以受理。（）

以学生实践活动为基本特征的练习法，属于()

【2010福建】个体身心发展具有不均衡性，因此教育要()。

“要给学生一杯水，教师要有一桶水。”这主要强调教师需要()。

按对外购同定资产价款处理方式的不同进行划分，增值税的类型分为()。

TheUnitedStatescountsitspopulationeverytenyears,andeachcensusrevealsthattheracialandethnicmixischangingdram

在一个双链表中，在p结点之前插入q结点的操作是()。