首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列函数说明和C++代码,将应填入(n)处的字句写在答题纸的对应栏内。 【说明】函数int Toplogical(LinkedWDigraph G)的功能是对图G中的顶点进行拓扑排序,并返回关键路径的长度。其中图G表示一个具有n个顶点的AOE一网
阅读下列函数说明和C++代码,将应填入(n)处的字句写在答题纸的对应栏内。 【说明】函数int Toplogical(LinkedWDigraph G)的功能是对图G中的顶点进行拓扑排序,并返回关键路径的长度。其中图G表示一个具有n个顶点的AOE一网
admin
2010-01-15
66
问题
阅读下列函数说明和C++代码,将应填入(n)处的字句写在答题纸的对应栏内。
【说明】函数int Toplogical(LinkedWDigraph G)的功能是对图G中的顶点进行拓扑排序,并返回关键路径的长度。其中图G表示一个具有n个顶点的AOE一网,图中顶点从1~n依次编号,图G的存储结构采用邻接表表示,其数据类型定义如下:
typedef struct Gnode{ /*邻接表的表结点类型*/
int adivex; /*邻接顶点编号*/
int weight; /*弧上的权值*/
bstmct Gonde*nextare; /*指示下一个弧的结点*/
}Gnode;
typedef struct Adjlist{ /*邻接表的头结点类型*/
char vdata; /*顶点的数据信息*/
struct Gnode*Firstadj; /*指向邻接表的第1个表结点*/
}Adjlist;
typedef struct LinkedWDigraph{ /*图的类型*/
int n, e; /*图中顶点个数和边数*/
struct Adjlist head; /*指向图中第1个顶点的邻接表的头结点*/
}LinkedWDigraph;
【函数】
int Toplogical(LinkedWDigraph G)
{ Gnode *p;
int j,w,top=0;
int *Stack,*ve,*indegree;
ve=(int *)mallloc(G.n+1)* sizeof(int)};
indegree=(int *)malloc((G.n+1)*sizeof(int));/*存储网中个顶点的入度*/
Stack=(int *)malloc((G.n+1)*sizeof(int)); /*存储入度为0的顶点的编号*/
if(!ve‖!indegree‖!Stack)
exit(0);
for(j=1;j<=G.n;j++){
ve[j]=0; indegree[j]=0;
}/*for*/
for(j=1;j<=G.n;j++){ /*求网中各顶点的入度*/
p=G.head[j].Firstadj;
while(p){
(1); p=p->nextarc;
}/*while*/
}/*for*/
for(i=1;j<=G.n;j++) /求网中入度为0的顶点并保存其编号*/
if(!indegree[j]) Stack[++top]=j;
while(top>0){
w=(2);
printf("%c", G.head[w].vdata);
p=G.head[w].Firstadj;
while(p){
(3);
if(!indegree[p->adjvex])
Stack[++top]=p->adjvex;
if( (4) )
ve[p->adjvex]=ve[w]+p->weight;
p=p->nextarc;
}/*while*/
return (5);
}/*Toplogical*/
选项
答案
(1)indegree[p->adjvex]++及其等价形式 (2)Stack[top-]及其等价形式 (3)indegree[p->adjvex]--及其等价形式 (4)ve[w]+p->weight>ve[p->adjvex]及其等价形式 (5)ve[w]及其等价形式
解析
(1)indegree[p->adjvex]++及其等价形式
此填空在for(j=1;j<=G.n;j++)中,求网中各顶点的入度。遍历邻接表G.head[j].Firstadj,将每个结点p->adjvex的入度indegree[p->adjvex]加1。邻接表是j的出度结点表。
(2)Stack[top-]及其等价形式
栈Stack中存放的是入度为0的结点号,此while循环中,w取栈顶值开始搜索打印这些结点。
(3)indegree[p->adjvex]--及其等价形式
由于p=G.head[w].Firstadj;因此while循环是遍历这个邻接链表,将每个结点的入度减1。将入度为0的结点号入栈Stack中。
(4)ve[w]+p->weight>ve[p->adjvex]及其等价形式
若ve[w]+p->weight大于ve[p->adjvex],则ve[w]+p->weight是最长路径,用ve[w]+p->weight取代ve[p->adjvex]。
(5)ve[w]及其等价形式
最终返回的是w结点的ve[w]值作为整个AOE—网的最长路径值。
转载请注明原文地址:https://kaotiyun.com/show/c0DZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
在WindowsXP操作系统中,用户利用“磁盘管理”程序可以对磁盘进行初始化、创建卷,(23)。通常将“C:\Windows\nyprogram.exe”文件设置成只读和隐藏属性,以便控制用户对该文件的访问,这一级安全管理称之为(24)安全管理。
在面向对象系统中,对象的属性是()。
()不属于程序的基本控制结构。
下图为某设计模式的类图,类State和Context的关系为(49),类(50)是客户使用的主要接口。(50)
软件设计阶段一般又可分为______。A.逻辑设计与功能设计B.概要设计与详细设计C.概念设计与物理设计D.模型设计与程序设计
某文件管理系统采用位示图(bitmap)记录磁盘的使用情况。如果系统的字长为32位,磁盘物理块的大小为4MB,物理块依次编号为:0、1、2、…,位示图字依次编号为:0、1、2、…,那么16385号物理块的使用情况在位示图中的第(24)个字中描述;如果磁盘的
假设系统中有三类互斥资源R1、R2和R3,可用资源数分别为10、5和3。在T0时刻系统中有P1、P2、P3、P4和P5五个进程,这些进程对资源的最大需求量和已分配资源数如下表所示,此时系统剩余的可用资源数分别为(22)。如果进程按(23)序列执行,那么系统
______不是正确的软件测试目的。A.尽最大的可能找出最多的错误B.设计一个好的测试用例对用户需求的覆盖度达到100%C.对软件质量进行度量和评估,以提高软件的质量D.发现开发所采用的软件过程的缺陷,进行软件过程改进
计算机各功能部件之间的合作关系如下图所示。假设图中虚线表示控制流,实线表示数据流,那么a、b和c分别表示(5)。
《GB/T18905软件工程产品评价》中确定的通用评价过程包括四个方面,其中有关“规定评价”部分包含的内容有(67)。
随机试题
异位妊娠时,子宫内假孕囊来自
汇率风险中,由于外汇汇率发生意外波动而引起企业未来收益发生变化的潜在风险指()
讨论f(x)=在X=1处的连续性.
Guest:Oh,it’steno’clock.Imustbeleavingnow.Host:______
下列为优先抢救的急症的是
患者,女,43岁。近3月来午后低热,剧烈咳嗽,痰中带血,进食少,乏力,消瘦,应用抗菌药及止咳化痰药物无效,X线检查未见异常,血沉未见增快,痰中找到结核菌,临床诊断为肺结核。是肝药酶强诱导剂,可加速多种药物的代谢如口服避孕药、维拉帕米、普罗帕酮、甲氧苄啶
下列属于水利水电工程施工现场一类负荷的是()。
中央各部门负责本部门所属各单位预算草案的审核,并汇总编制本部门的预算草案,于每年()前报财政部审核。
证券公司应当配备足够的具有期货从业人员资格的业务人员,也可以任用不具有期货从业人员资格的业务人员从事介绍业务,但是仅限于业务发展初期阶段。( )
在进行房地产产品定位时,可以运用菲利普.科特勒的产品三层次结构理论,将房地产产品看成由()三个层次组成的复合体。
最新回复
(
0
)