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

admin2019-01-30 61

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

学硕统考专业

相关试题推荐

阅读史料，回答以下问题：重庆中央党部，暨中央执监委员诸同志均鉴：今年4月，临时全国代表大会宣言，说明此次抗战之原因，曰：“自塘沽协定以来，吾人所以忍辱负重与倭国周旋，无非欲停止军事行动，采用和平方法，先谋北方各省之保全，再进而谋东北四省问题之合
战国初期，上党地区在下列哪一个国家的控制范围之内?()
洋务派创办军事工业的方式是()。
结合相关历史内容，评价罗斯福新政。
二次大战后，主要资本主义国家经历了增长时期，首先开始这个进程的国家是()。
西周的官僚制度已经相当完备，官僚机构庞杂，职官名目繁多。周王室的官僚机构分为两大系统，分别是()。
一棵：BS’r树共7个结点，值分别为1、2、3、4、5、6、7，形态为满二叉树，()不是插入序列。
浮点数加、减运算过程一般包括对阶、尾数运算、规格化、舍入和判溢出等步骤。设浮点数的阶码和尾数均采用补码表示，且位数分别为5位和7位(均含2位符号位)。若有两个数x=27×29／32，Y=25×5／8，则用浮点加法计算x+Y的最终结果是____。
问：下列IEEE单精度浮点数所表示的十进制数分别是多少?(1)1011110101000000000000000000000(2)010l0101011000000000000000000000(3
字长相同的两种浮点数，第一种阶码位数较多，尾数位数少，第二种阶码位数少，尾数位数多，阶的底数都是2，则()。

随机试题

北京明华中学学生发展中心的小刘老师负责向校本部及相关分校的学生家长传达有关学生儿童医保扣款方式更新的通知。该通知需要下发至每位学生，并请家长填写回执。参照“结果示例1．png,～结果示例4．png”按下列要求帮助小刘老师编排家长信及回执：在考生文件夹下
________账户核算企业发生的除营业利润以外的收益，主要包括与企业日常活动无关的政府补助、盘盈利得、捐赠利得(企业接受股东或股东的子公司直接或间接的捐赠，经济实质属于股东对企业的资本性投入的除外)等。企业发生营业外收入款项时，记入“营业外收入”账户的贷
为防止复发，关节内强直的患者术后开口练习的时间为
多发性骨髓瘤患者尿中主要出现
企业采用分期收款销售方式销售商品的收款期为3年，销售商品时，应作为确定商品销售收入金额的足()。
根据营业税法律制度的规定，下列关于营业税纳税地点的表述中，正确的有()。
从事软件开发的某有限责任公司召开股东会议，决定董事人选。下列人员中，不能担任公司董事的有()。
我国历史上第一个具有宪法性质的文件是()。
刑事责任是指
Thephenomenonthatwordsofdifferentmeaningsareidenticalinsoundiscalled

最新回复(0)

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

计算机408

学硕统考专业

战国初期，上党地区在下列哪一个国家的控制范围之内?()

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

结合相关历史内容，评价罗斯福新政。

二次大战后，主要资本主义国家经历了增长时期，首先开始这个进程的国家是()。

西周的官僚制度已经相当完备，官僚机构庞杂，职官名目繁多。周王室的官僚机构分为两大系统，分别是()。

一棵：BS’r树共7个结点，值分别为1、2、3、4、5、6、7，形态为满二叉树，()不是插入序列。

问：下列IEEE单精度浮点数所表示的十进制数分别是多少?(1)1011110101000000000000000000000(2)010l0101011000000000000000000000(3

字长相同的两种浮点数，第一种阶码位数较多，尾数位数少，第二种阶码位数少，尾数位数多，阶的底数都是2，则()。

为防止复发，关节内强直的患者术后开口练习的时间为

多发性骨髓瘤患者尿中主要出现

企业采用分期收款销售方式销售商品的收款期为3年，销售商品时，应作为确定商品销售收入金额的足()。

根据营业税法律制度的规定，下列关于营业税纳税地点的表述中，正确的有()。

从事软件开发的某有限责任公司召开股东会议，决定董事人选。下列人员中，不能担任公司董事的有()。

我国历史上第一个具有宪法性质的文件是()。

刑事责任是指

Thephenomenonthatwordsofdifferentmeaningsareidenticalinsoundiscalled