首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。 【说明】对有向图进行拓扑排序的方法是: (1)初始时拓扑序列为空: (2)任意选择一个入度为0的顶点,将其放入拓扑序列中,同时从图中删除该顶点以及从该顶点出发的弧; (3)重复(2),
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。 【说明】对有向图进行拓扑排序的方法是: (1)初始时拓扑序列为空: (2)任意选择一个入度为0的顶点,将其放入拓扑序列中,同时从图中删除该顶点以及从该顶点出发的弧; (3)重复(2),
admin
2014-11-13
25
问题
阅读下列说明和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*/
对于图15—3所示的有向图G,写出函数TopSoa执行后得到的拓扑序列。若将函数T0pSort中的队列改为栈,写出函数TopSon执行后得到的拓扑序列。
选项
答案
队列方式:v1 v2 v5 v4 v3 v7 v6 或者1 2 5 4 3 7 6栈方式:v1 v2 v5 v4 v7 v3 v6 或者1 2 5 4 7 3 6
解析
使用栈和队列的差别在于拓扑序列中顶点的排列次序可能不同。对于本题中的有向图,在使用队列的方式下:
(1)开始时仅顶点v1的入度为0,因此顶点v1入队;
(2)对头顶点v1出队,并进入拓扑序列,然后删除从顶点v1出发的弧后,仅使顶点v2的入度为0,因此顶点v2入队;
(3)队头顶点v1出队,并进入拓扑序列,然后删除从顶点v2出发的弧后,仅使顶点v5的入度为i,因此顶点v5入队;
(4)队头顶点v5出队,并进入拓扑序列,然后删除从顶点v5出发的弧后,仅使顶点v4的入度为0,因此顶点v4入队;
(5)队头顶点v4出队,并进入拓扑序列,然后删除从顶点v4出发的弧后,仅使顶点v3和v的入度为0,因此顶点v3和v7依次入队;
(6)队头顶点v3出队,并进入拓扑序列,然后删除从顶点v3出发的弧后,没有产生新的入度为0的顶点;
(7)队头顶点v7出队,并进入拓扑序列,然后删除从顶点v7出发的弧后,使顶点v6的入度为0,因此顶点v6入队;
(8)队头顶点v6出队,并进入拓扑序列,然后删除从顶点v6出发的弧后,没有产生新的入度为0的顶点,队列已空,因此结束拓扑排序过程,得到的拓扑序列为v1 v2 v5 v4 v3 v7 v6。使用栈保存入度为0的顶点时,前4步都是一样的,因为每次仅有一个元素进栈,因此出栈序列与入栈序列一致。到第5步时,v3和v7依次入栈后,出栈时的次序为v7和v3,因此得到的拓扑序列为v1 v2 v5 v4 v7 v3 v6。
转载请注明原文地址:https://kaotiyun.com/show/iZDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
阅读下列说明,回答问题1至问题6。[说明]某公司的业务员甲与客户乙通过Internet交换商业电子邮件(以下简称为“邮件”)。为保障邮件内容的安全,双方约定采用安全电子邮件技术对邮件内容进行加密和数字签名。安全电子邮件技术的实现原理如图4
启动init进程前,不需要经过______步骤。A.LIIO加载内核B.检测内存C.加载文件系统D.启动网络支持root用户执行psaux|grepinit命令,得到init的PID是______。A.0
阅读以下说明,回答问题1至问题8。[说明]Linux系统开机引导时首先启动内核,由内核检查和初始化硬件设备,载入设备的驱动程序模块,安装root文件系统,然后内核将启动一个名为init的进程。在init运行完成并启动其他必要的后续进程后,
销售部的网络号是(1),广播地址是(2):技术部的网络号是(3),广播地址是(4);每个子网可用的IP地址有(5)个。在网关计算机上使用以下路由命令创建两个默认的路由:routeadd-net192.168.1.0255.255.2
完成下列命令行,对网络接口进行地址初始化配置。firewall(config)#ipaddressinside(1)(2)firewall(config)#ipaddressoutside(3)(4)以下命令针对网络服务的端口配
完成下列命令行,对网络接口进行地址初始化配置。firewall(config)#ipaddressinside(1)(2)firewall(config)#ipaddressoutside(3)(4)管道命令的作用是允许数据流从
DHCP允许服务器向客户端动态分配Ⅲ地址和配置信息。客户端可以从DHCP服务器获得(1)。(1)A.DHCP服务器的地址B.Web服务器的地址C.DNS服务器的地址通常采用IP地址与MAC地址绑定的策略为某些设备保留固定的IP地址
阅读以下说明,回答问题1至问题4。【说明】2007年春,ARP木马大范围流行。木马发作时,计算机网络连接正常却无法打开网页。由于ARP木马发出大量欺骗数据包,导致网络用户上网不稳定,甚至网络短时瘫痪。
在控制面板的“添加/删除程序”对话框中选择(1),然后进入“应用程序服务器”选项,在(2)组件复选框中选择“文件传输协议(FTP)服务”,就可以在Windows2003中安装FTP服务。(1)A.更改或删除程序B.添加新程序C.添加/删除
在控制面板的“添加/删除程序”对话框中选择(1),然后进入“应用程序服务器”选项,在(2)组件复选框中选择“文件传输协议(FTP)服务”,就可以在Windows2003中安装FTP服务。(1)A.更改或删除程序B.添加新程序C.添加/删除
随机试题
只要社会主义物质文明建设搞好了,社会主义精神文明建设就自然搞好了。
香豆素类成分的荧光与结构的关系是
下列各项中,不能作为法律关系客体的是()。
关于胜任特征,下列说法错误的是()。
如图,玻璃管内封闭了一段气体,气柱长度为l,管内外水银面高度差为h,若温度保持不变。把玻璃管稍向上提起一段距离,则()。
幼儿自言自语的形式主要有_______、_______两种。
Studythefollowingpicturecarefullyandwriteanessayinnolessthan160—200words.Youressaymustbewrittenclearlyandy
根据信息系统的定义,构成信息系统的核心要素不包括________________。
Weareluckytohavethemostup—to—dateequipmentinourlaboratory,withwhichwecancompleteourresearchintime.
A、Challengesfromabroad.B、Lackofconstantupgrading.C、Competitionofthesametrade.D、Somecountries’slowingeconomies.D录
最新回复
(
0
)