首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列C++程序和程序说明,将应填入(n)处的字句写在对应栏内。 【说明】[程序6说明]单源最短路径的分支限界算法。 const int MAXNUM=29999; #include<iostream> #include<vector> #include
阅读下列C++程序和程序说明,将应填入(n)处的字句写在对应栏内。 【说明】[程序6说明]单源最短路径的分支限界算法。 const int MAXNUM=29999; #include<iostream> #include<vector> #include
admin
2009-02-15
79
问题
阅读下列C++程序和程序说明,将应填入(n)处的字句写在对应栏内。
【说明】[程序6说明]单源最短路径的分支限界算法。
const int MAXNUM=29999;
#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
using namespace std;
template <class VertexType,class EdgeType>
class MinNode { //程序中使用的最小化堆的结点说明
friend class Graph<VertexType,EdgeType>
public:
MinNode (int nl, EdgeType length1)
{ VexNum=nl;
length=length1;
}
bool operator>(const MinNode<VertexType,EdgeType>&p)const
{ return (1)>p.length;
}
private:
int VexNum;
//记录源点序号,序号数组p及distance下标相一致。源点为初始扩展顶点
EdgeType length;
//记录源点到本顶点的当前最短路径的长度,源点到自身的长度为0
}
template<class VertexType,classEdgeType>
void Graph<VertexType,EdgeType>:: shortestpath(VertexType start) {
int j,k,source;//source 记录源点的序号。
EdgeType*distance=(2);
int*p=new int[MaxNumVertex];
vector<MinNode<VertexType,EdgeType> >H;
for(source=0;source<MaxNumVertex;source++)
{ if(NodeList[source]==start)break;}
if (source>=MaxNumVertex){cout<<”This is error!”<<end1;return;}
MinNode<VertexType,Edge Type>(3);
for(k=0;k<MaxNumVertex;k++)
{ distance[k]:MAXXUM; //记录源点到本顶点k的最终的最短路径的长度
p[k]=source; //记录最短路径上的本顶点的直接前驱顶点的序号
}
distance[source]=0;p[source]=-1;//m 是源点,前一顶点不存在
vector<MinNode<VertexType, EdgeType>>::iterator q;
while(1){
for(j=0;j<MaxNumVertex;j++)
if((AdjMatrix[E.VexNum* MaxNumVertex+j]<MAXNUM)
&&((4)<distance[j]))
{ distance[j]=E.length+AdjMatrix[E.VexNum* MaxNumVertex+j];
p[j]=E. VexNum; //记录顶点j的前一顶点
MinNode<VertexType, EdgeType>(5);
H.push_ back(N);
push_heap(H. begin(),H.end(),greater<MinNode<VertexType,
EdgeType>>());
}
if(H.empty()=true)break; //若优先队列为空,那么算法结束
else{
pop_ heap(H.begin(),H. end(),greater<MinNode<VertexType,
EdgeType>>());
q=H.end()-1; //从最小化堆中取路径最短的顶点
E=*q;
H.pop_ back(); //删除从最小化堆中“挤”出的顶点
}
} //end while
for(k=0;k<MaxNumVertex;k++){
cout<<"Shorstest path from vertex"<<k<<"is"<<distance[k]<<end1;
j=k;cout<<"All vertices are:";
while(j!=source){cout<<j<<"->";j=p[j];}
cout<<source<<”.”<<end1;
} //打印顶点的最短路径长度和至源点的最短路径上经过的顶点序列
return;
}
选项
答案
(1)this->length或(*this).length (2)new EdgeType[MaxNumVertex] (3)E(source,0) (4)E.length+ AdjMatrix [E. VcxNum* MaxNumVertex+j] (5)N(j,distance[j])
解析
(1)this->length或(*this).length
操作符,的成员函数,比较两个对象的最短路径的长度length,大于则返回真(1)。
(2)new EdgeType[MaxNumVertex]
动态申请EdgeType类的对象数组distance,长度为MaxNumVertex,存放最短路径的长度。
(3)E(source,0)
定义最小化堆模板类MinNode<VertexType, EdgeType>的对象E(source,0)。
(4)E.length+ AdjMatrix [E. VcxNum* MaxNumVertex+j]
若E.length+ AdjMatrix [E.VexNum*MaxNumVertex+j]小于distance[j],则distance[j]取这个更小值。
(5)N(j,distance[j])
定义最小化堆模板类MinNode<VertexType,EdgeType>的对象N(j,distance[j])。
转载请注明原文地址:https://kaotiyun.com/show/GgDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
根据ANSI/IEEE829标准,以下(37)属于《测试程序说明》中程序步骤的内容。 ①启动 ②目的 ③日志 ④设置
以下属于影响软件可靠性因素的是()。①软件运行剖面②软件规模③软件内部结构④软件的开发方法和开发环境⑤软件的可靠性投入
如果在查找路由表时发现有多个选项匹配,那么应该根据___________(25)原则进行选择。假设路由表有4个表项如下所示,那么与地址139.17.179.92匹配的表项是____________(26)。(26)
在WindowsXP操作系统中,用户利用“磁盘管理”程序可以对磁盘进行初始化、创建卷,(23)。通常将“C:\Windows\nyprogram.exe”文件设置成只读和隐藏属性,以便控制用户对该文件的访问,这一级安全管理称之为(24)安全管理。
以下用例图中,A1和A2为(47)。A1和A2的关系为(48)。(48)
系统交付后,修改原来打印时总是遗漏最后一行记录的问题,该行为属于______维护。
某汽车维修公司有部门、员工和顾客等实体,各实体对应的关系模式如下:部门(部门代码,部门名称,电话)员工(员工代码,姓名,部门代码)顾客(顾客号,姓名,年龄,性别)维修(顾客号,故障情况,维修日期,员工代码)假设每个部门允许有多部电话,则电话属性为
在引入自动化测试工具以前,手工测试遇到的问题包括()。①工作量和时间耗费过于庞大②衡量软件测试工作进展困难③长时间运行的可靠性测试问题④对并发用户进行模拟的问题⑤确定系统的性能瓶颈问题⑥软件测试过程的管
阅读以下说明和交换机的配置信息,回答问题1至问题3,将解答填入答题纸的对应栏内。[说明]某公司设3个部门,为了便于管理,每个部门组成1个VLAN,公司网络结构如图9-4所示。[交换机Switch1的部分配置信息]Switch
填充流程图中①的判断条件。写出子程序A的功能,并顺序写出实现该功能的操作
随机试题
罢免村民委员会成员须经()
由枯枝落叶→真菌→花鼠组成的食物链属于捕食食物链。()
男,56岁,进食哽噎感,胸骨后异物感1个月,食管钡透见食管下段黏膜紊乱、断裂、管壁僵硬。该病人最可能的诊断为
以下哪种细胞不是牙周膜中的细胞成分
多个基金共用一个基金合同,子基金独立运作,子基金之间可以进行相互转换的基金是()。
若旅游团乘火车离开,要求导游人员带团提前1小时抵达车站。
韩愈,字退之,昌黎人。父仲卿,无名位。愈生三岁而孤,养于从父兄。愈自以孤子,幼刻苦学儒,不俟奖励。……洎举进士,投文于公卿间,故相郑余庆颇为之延誉,由是知名于时。寻登进士第。宰相董晋出镇大梁,辟为巡官。府除,徐州张建封又请为其宾佐。愈发言真率,无
甲某于2000年多次盗割在使用中的铁路专用电话线,致使数辆列车延误,造成严重后果,甲的行为构成:()
【2011年第55题】有医学研究显示,行为痴呆症患者大脑组织中往往含有过量的铝,同时有化学研究表明,一种硅化合物可以吸收铝,陈医生据此认为,可以用这种硅化合物治疗行为痴呆症。以下哪项是陈医生最可能依赖的假设?
NarcoticAddiction(麻醉品依赖)Heroin(海洛因)addictiontodayisfoundchieflyamongyoungpeopleinghettoareas(贫农区),ofthemore
最新回复
(
0
)