首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
以下有关拓扑排序的说法中,错误的是( )。 Ⅰ.如果某有向图存在环路,则该有向图一定不存在拓扑排序 Ⅱ.在拓扑排序算法中,既可以使用栈,也可以使用队列 Ⅲ.若有向图的拓扑有序序列唯一,则图中每个顶点的入度和出度最多为1
以下有关拓扑排序的说法中,错误的是( )。 Ⅰ.如果某有向图存在环路,则该有向图一定不存在拓扑排序 Ⅱ.在拓扑排序算法中,既可以使用栈,也可以使用队列 Ⅲ.若有向图的拓扑有序序列唯一,则图中每个顶点的入度和出度最多为1
admin
2022-06-07
26
问题
以下有关拓扑排序的说法中,错误的是( )。
Ⅰ.如果某有向图存在环路,则该有向图一定不存在拓扑排序
Ⅱ.在拓扑排序算法中,既可以使用栈,也可以使用队列
Ⅲ.若有向图的拓扑有序序列唯一,则图中每个顶点的入度和出度最多为1
选项
A、仅Ⅰ、Ⅲ
B、仅Ⅱ、Ⅲ
C、仅Ⅱ
D、仅Ⅲ
答案
D
解析
Ⅰ:如果一个有向图存在环路,则肯定不会存在拓扑排序,因为该环路找不到入度为0的结点,拓扑排序自然也就进行不下去了,故Ⅰ正确。
Ⅱ:使用栈来表示拓扑排序的序列,最后的出栈序列是逆拓扑排序,只需逆转过来即可,只是效率比较低;使用队列时,出队序列就是拓扑排序序列,故使用栈和队列都是可以的,只是效率不等而已,故Ⅱ正确。
Ⅲ: —个反例如图8—9所示。该图的拓扑有序序列是唯一的,但各个顶点的入度和出度可以超出1,故Ⅲ错误。
转载请注明原文地址:https://kaotiyun.com/show/jt3i777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
某机字长32位,主存容量1MB,按字编址,块长512B,Cache共可存放16个块,采用直接映射方式,则Cache~1电址长度为()。
已知有向图G=(V,A),其中V={a,b,c,d,e},A={,,,,,},对该图进行拓扑排序,下面序列中不是拓扑排序的是().,
大部分文件系统以硬盘作为文件存储器。某一个文件系统中,其磁盘物理块的大小为512B,有一个文件,包含了590个逻辑记录,每个记录占255B;其中,为检索方便,采用成组法存储,在每个物理块上只存放2个记录。文件A在该文件目录中的位置如下图5—2所示。此
设有4台主机A、B、C和D都处在同一物理网络中,它们的IP地址分别为192.155.28.112、192.155.28.120、192.155.28.135和192.155.28.202,子网掩码都是255.255.255.224,请回答:若不改变主机
设有一个双向链表h,每个结点中除有prior、data和next共3个域外,还有一个访问频度域freq,在链表被起用之前,每个结点中的freq域的值均被初始化为零。每当进行LocateNode(h,x)运算时,令元素值为x的结点中freq域的值加1,并调整
偏移寻址通过将某个寄存器内容与一个形式地址相加而生成有效地址。下列寻址方式中,不属于偏移寻址方式的是____。
用户程序发出磁盘I/O请求后,系统的正确处理流程是____。
假如一个FCB块的大小是64字节。盘块的大小为1KB,则在每个盘块中能存放的最大FCB数是()。
下列网络设备中,能够抑制广播风暴的是_______。Ⅰ.中继器Ⅱ.集线器Ⅲ.网桥Ⅳ.路由器
队尾已到达一维数组的最高下标,不能再插入元素,然而队中元素个数小于队列的长度,这种现象称作()。
随机试题
城邦民主制
CanalsexistedinEgyptthousandsofyearsago.ThegreatcanalatBabylonwasbuiltabout2000B.C..TheGrandCanalofChina,
关于皮肤吸收的途径下列叙述错误的是
A.银翘散B.附子汤C.葛根芩连汤D.生脉散合复脉汤E.血府逐瘀汤合生脉散病毒性心肌炎气阴两虚证的用方是
喷锚暗挖法二次衬砌施工最佳时机是()。
《出境货物报检单》的“合同、信用证订立的检验检疫条款或特殊要求”内容由检验检疫机构受理报检人员填写。 ( )
(2012年)2011年1月1日某有限责任公司向银行借款2800万元,期限1年;同时公司接受张某投资,约定张某于4月1日和7月1日各投入400万元I张某仅于10月1日投入600万元。同时银行贷款年利率为7%。该公司2011年企业所得税前可以扣除的利息费用为
商品销售结构分析可以有区别地对商品加以管理,其主要措施有()。
下图是我国海拔3800米某内陆湖泊的水位变化情况。据此回答问题。读某大洋等温线分布图,假定①②等温线的弯曲是由洋流影响所致,则()。
中国历史上最早的专职警察机构是清朝的()。
最新回复
(
0
)