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

admin2019-01-30 77

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

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

答案C

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

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

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

计算机408

学硕统考专业

相关试题推荐

“一战”后，协约国与奥地利签订的确认奥匈帝国解体的文件是()。
试述“轴心时代”(公元前8世纪至前3世纪)中国、印度、希腊三大古典文化系统之异同。
洋务派创办军事工业的方式是()。
系统阐明社会主义初级阶段理论是在()。
三个进程P1、P2、P3互斥使用一个包含N(N＞O)个单元的缓冲区。P1每次用produce()生成一个正整数并用put()送入缓冲区某一空单元中；P2每次用getodd()从该缓冲区中取出一个奇数并用countodd()统计奇数个数；P3每次用getev
图的D搜索类似于BFS，不同之处在于使用栈代替BFS中的队列，入／出队列的操作作为入／出栈的操作，即当一个顶点的所有邻接结点被搜索后，下一个搜索出发点应该是最近入栈(栈顶)的顶点。(1)用邻接表作为存储结构，写一个D搜索算法；(2)用D搜索方法
现有一个解决无向连通图的最小生成树的一种方法如下：将图中所有边按权重从大到小排序为(e1，e2．…，em)；i＝l；while(所剩边数>＝顶点数){从图中删去ei；若图不再连通，则恢复ei；i＝i＋l；
若浮点运算结果尾数不是规格化数，将进行结果规格化。结果规格化有左规和右规之分，下列操作中，属于结果规格化的操作是()。I．尾数左移1位，阶码加1Ⅱ．尾数左移1位，阶码减1Ⅲ．尾数右移1位，阶码加1Ⅳ．尾数右移1位，阶码减1
float类型(即lEEE754单精度浮点数格式)能表示的最大正整数是
若浮点运算结果尾数不是规格化数，将进行结果规格化。结果规格化有左规和右规之分，下列操作中，属于结果规格化的操作是()。I．尾数左移1位，阶码加1Ⅱ．尾数左移1位，阶码减1Ⅲ．尾数右移1位，阶码加11V．尾数右

随机试题

属于顺式作用元件的是
下列关于职业伤害安全事故处理的说法正确的是()。
经中国人民银行负责人批准，商业银行可采取临时冻结措施，但冻结时间不得超过(　　)小时。
小学生人格发展的主要任务为()。
代表心室复极的波是()。
A、 B、 C、 D、 A，那么下一项就应该为，因此选A。
(2015河北)一项工程由甲、乙、丙三个工程队共同完成需要22天，甲队工作效率是乙队的3/2倍，乙队3天的工作量是丙队2天工作量的2/3，三队同时开工，2天后，丙队被调往另一工地。那么甲、乙再干多少天才能完成该工程?
公司中有多个部门和多名职员，每个职员只能属于一个部门，一个部门可以有多名职员。则实体部门和职员间的联系是
就算你哭的声音______大，也不会有人同情。
A、InafruitshopB、InaclothingShopC、InabookshopD、InahospitalB问题是“对话发生在哪儿”选项A翻译为“水果店”；选项B翻译为“服装店”；选项C翻译为“书店”；选项D翻译为“在医

最新回复(0)

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

计算机408

学硕统考专业

“一战”后，协约国与奥地利签订的确认奥匈帝国解体的文件是()。

试述“轴心时代”(公元前8世纪至前3世纪)中国、印度、希腊三大古典文化系统之异同。

洋务派创办军事工业的方式是()。

系统阐明社会主义初级阶段理论是在()。

三个进程P1、P2、P3互斥使用一个包含N(N＞O)个单元的缓冲区。P1每次用produce()生成一个正整数并用put()送入缓冲区某一空单元中；P2每次用getodd()从该缓冲区中取出一个奇数并用countodd()统计奇数个数；P3每次用getev

现有一个解决无向连通图的最小生成树的一种方法如下：将图中所有边按权重从大到小排序为(e1，e2．…，em)；i＝l；while(所剩边数>＝顶点数){从图中删去ei；若图不再连通，则恢复ei；i＝i＋l；

float类型(即lEEE754单精度浮点数格式)能表示的最大正整数是

若浮点运算结果尾数不是规格化数，将进行结果规格化。结果规格化有左规和右规之分，下列操作中，属于结果规格化的操作是()。I．尾数左移1位，阶码加1Ⅱ．尾数左移1位，阶码减1Ⅲ．尾数右移1位，阶码加11V．尾数右

属于顺式作用元件的是

下列关于职业伤害安全事故处理的说法正确的是()。

经中国人民银行负责人批准，商业银行可采取临时冻结措施，但冻结时间不得超过( )小时。

小学生人格发展的主要任务为()。

代表心室复极的波是()。

A、 B、 C、 D、 A，那么下一项就应该为，因此选A。

(2015河北)一项工程由甲、乙、丙三个工程队共同完成需要22天，甲队工作效率是乙队的3/2倍，乙队3天的工作量是丙队2天工作量的2/3，三队同时开工，2天后，丙队被调往另一工地。那么甲、乙再干多少天才能完成该工程?

公司中有多个部门和多名职员，每个职员只能属于一个部门，一个部门可以有多名职员。则实体部门和职员间的联系是

就算你哭的声音______大，也不会有人同情。

A、InafruitshopB、InaclothingShopC、InabookshopD、InahospitalB问题是“对话发生在哪儿”选项A翻译为“水果店”；选项B翻译为“服装店”；选项C翻译为“书店”；选项D翻译为“在医

经中国人民银行负责人批准，商业银行可采取临时冻结措施，但冻结时间不得超过(　　)小时。