首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。 【说明】对有向图进行拓扑排序的方法是: (1)初始时拓扑序列为空: (2)任意选择一个入度为0的顶点,将其放入拓扑序列中,同时从图中删除该顶点以及从该顶点出发的弧; (3)重复(2),
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。 【说明】对有向图进行拓扑排序的方法是: (1)初始时拓扑序列为空: (2)任意选择一个入度为0的顶点,将其放入拓扑序列中,同时从图中删除该顶点以及从该顶点出发的弧; (3)重复(2),
admin
2014-11-13
100
问题
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。
【说明】对有向图进行拓扑排序的方法是:
(1)初始时拓扑序列为空:
(2)任意选择一个入度为0的顶点,将其放入拓扑序列中,同时从图中删除该顶点以及从该顶点出发的弧;
(3)重复(2),直到不存在入度为0的顶点为止(若所有顶点都进入拓扑序列则完成拓扑排序,否则由于有向图中存在回路无法完成拓扑排序)。函数int*TopSoa(LinkedDigraphG)的功能是对有向图G中的顶点进行拓扑排序,返回拓扑序列中的顶点编号序列,若不能完成拓扑排序,则返回空指针。其中,图G中的顶点从1开始依次编号,顶点序列为v1,v2,…,vn,图G采用邻接表示,其数据类型定义如下:
#def ine NAXVNUM 50 /*最大顶点数*/
typedef structArcNode( /*表节点类型*/
int adjvex; /*邻接顶点编号*/
struct ArcNode*nextarc; /*指示下一个邻接顶点*/
}ArcNode:
typedef struct Adj List( /*头节点类型*/
char vdata; /*顶点的数据信息*/
ArcNode*firstarc; /*指向邻接表的第一个表节点*/
}Adj List;
typedef struct LinkedDigraph( /*图的类型*/
int n; /*图中顶点个数*/
AdjLiSt Vhead[MAXVNUM]; /*所有顶点的头节点数组*/
}LinkedDigraph;
例如,某有向图G如图15.3所示,其邻接表如图15-4所示。
函数T0pSon中用到了队列结构(Queue的定义省略),实现队列基本操作的函数原型如表15—2所示:
【C代码】
int *TopSort(LinkedDigraph G) {
ArcNode*P; /*临时指针,指示表节点*/
Queue Q;/*临时队列,保存入度为0的顶点编号*/
int k=0; /*临时变量,用作数组元素的下标*/
int j=0,W=0; /*临时变量,用作顶点编号*/
int*toporder,*inDegree;
toporder=(int*)malloc((G.n+1)*Si zeof(int)); /*存储拓扑序列中的顶点编号*/
inDegree=(int*)malloc((G.n+1)*sizeof(int)); /*存储图G中各顶点的入度*/
if(!inDegree I I!toporder)return NULL;
(1); /*构造一个空队列*/
for(j=1;J<=G.n;J++)( /*初始化*/
toporder[J]=0; inDegree[j]=0;
}
for(J=1;J<=G.n;J++) /*求图G中各项点的入度*/
for(P=G.Vhead[j].firstarc;P;P=p一>nextarc)
inDegree[p一>adjvex]+=1;
for(j=1;J<=G.n;j++) /*将图G中入度为0的顶点保存在队列中*/
i f(0==inDegree[j])EnQueue(&Q,j);
whi le(!IsEmpty(Q))(
(2) ; /*队头顶点出队列并用W保存该顶点的编号*/
toporder[k++]=W;
/*将顶点W的所有邻接顶点的入度减1(模拟删除顶点w及从该项点出发的弧的操作)*/
for(p=G.Vhead[w].firstarc;P;P=P一>nextarc)(
(3)一=1;
if(0==(4))EnQueue(&Q,P一>adjvex);
}/*for*/
}/*while*/
free(inDegree);
if( (5) )
return NULL;
return topOrder;
}/*TopSort*/
设某有向无环图的顶点个数为n、弧数为e,那么用邻接表存储该图时,实现上述拓扑排序算法的函数TopSo~的时间复杂度是(6)。若有向图采用邻接矩阵表示(例如,图15—3所示有向图的邻接矩阵如图15—5所示),且将函数TopSort中有关邻接表的操作修改为针对邻接矩阵的操作,那么对于有n个顶点、e条弧的有向无环图,实现上述拓扑排序算法的时间复杂度是(7)。
选项
答案
(6)0(n+e)(7)O(n
2
)
解析
以邻接表为存储结构时,计算各项点入度的时间复杂度为O(e),建立零入度顶点队列的时间复杂度为O(n)。在拓扑排序过程中, (图中无环情况下)每个顶点进出队列各1次,入度减1的操作在while循环中共执行e次,所以总的时间复杂度为O(n+e)。以邻接矩阵为存储结构时,计算各顶点入度时需要遍历整个矩阵,因此时间复杂度为O(n
2
),建立零入度顶点队列的时间复杂度为O(n)。在拓扑排序过程中, (图中无环情况下)每个顶点进出队列各1次,实现入度减1操作时需遍历每个顶点的行向量1遍(时间复杂度为O(n)),所以总的时间复杂度为O(n
2
)。
转载请注明原文地址:https://kaotiyun.com/show/YZDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
从下列选项中选取合适的答案分别填入图4-1中的(1)~(4)处。A.DES算法B.MD5算法C.会话密钥D.数字证书E.甲的公钥F.甲的私钥G.乙的公钥H.乙的私钥甲使用Out
阅读下列说明,回答问题1至问题6。[说明]某公司的业务员甲与客户乙通过Internet交换商业电子邮件(以下简称为“邮件”)。为保障邮件内容的安全,双方约定采用安全电子邮件技术对邮件内容进行加密和数字签名。安全电子邮件技术的实现原理如图4
启动init进程前,不需要经过______步骤。A.LIIO加载内核B.检测内存C.加载文件系统D.启动网络支持在系统控制台,______用Ctrl+Alt+Delete组合键来重新引导服务器。A.允许B
网络设计流程通常由以下五个阶段组成:A.确定网络物理结构B.确定网络逻辑结构C.对现有网络的体系结构进行分析D.安装和维护E.需求分析根据网络开发设计的过程,给出上述五个阶段的先后排序:(1)。Ca
阅读以下说明,回答问题1至问题6。【说明】某公司在WindowsServer2003中安装IIS6.0来配置Web服务器,域名为www.abc.com。
请阅读下列SwitchA的配置信息,并在(1)~(5)处解释该语句的作用。Switch>enable(进入特权模式)Switch#configterminal(进入配置模式)Switch(config)#hostnameSwi
DHCP允许服务器向客户端动态分配Ⅲ地址和配置信息。客户端可以从DHCP服务器获得(1)。(1)A.DHCP服务器的地址B.Web服务器的地址C.DNS服务器的地址邮件服务器的网络配置信息如图3-5所示。请在图3-6中为邮件服务器
该单位的公网IP地址范围是(1)到(2):其中该单位能够使用的有效公网地址有(3)个。为保证路由器的安全,网络管理员做了如下设置,请阅读下列三段路由配置信息,并在(4)~(6)处填写该段语句的作用。1.Router(Config)#noip
在控制面板的“添加/删除程序”对话框中选择(1),然后进入“应用程序服务器”选项,在(2)组件复选框中选择“文件传输协议(FTP)服务”,就可以在Windows2003中安装FTP服务。(1)A.更改或删除程序B.添加新程序C.添加/删除
在控制面板的“添加/删除程序”对话框中选择(1),然后进入“应用程序服务器”选项,在(2)组件复选框中选择“文件传输协议(FTP)服务”,就可以在Windows2003中安装FTP服务。(1)A.更改或删除程序B.添加新程序C.添加/删除
随机试题
Therearetworoomsinthehouse,______servesasakitchen.
Weallhaveoffensivebreathatonetimeoranother.Inmostcases,offensivebreathemanatesfrombacteriainthemouth,althou
一般英文文题以多少个词以内为宜()
某人2005年冠心病的若干危险因素的危险分值为:吸烟为1.2,缺乏体力活动为2.2,超重为1.6,饮酒为1.0,糖尿病史为1.0。其组合危险分值应为
患者气短自汗,呛咳少痰,口干咽燥,舌苔薄少津,脉虚数,治疗应首选
休克是一种
慢性阻塞性肺疾病患者,进行呼吸功能锻炼的方法是
视线诱导设施不包括()
关于营业税纳税义务发生时间的说法,正确的有()。(2010年真题)
每分肺泡通气量与肺血流量的比值称为通气/血流比值,它是衡量换气效率的指标。()
最新回复
(
0
)