首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列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
72
问题
阅读下列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
软件设计师下午应用技术考试
软考中级
相关试题推荐
以下关于用例图的叙述中,不正确的是(44)。图书馆管理系统需求中包含“还书”用例和“到书通知”用例,对于“还书”用例,应先查询该书是否有人预定,若有则执行“到书通知”。“还书”用例和“到书通知”用例是(45)关系,以下用例图中,(46)是正确的。管理员处
以下关于用例图的叙述中,不正确的是(44)。图书馆管理系统需求中包含“还书”用例和“到书通知”用例,对于“还书”用例,应先查询该书是否有人预定,若有则执行“到书通知”。“还书”用例和“到书通知”用例是(45)关系,以下用例图中,(46)是正确的。管理员处
某软件项目的活动图如下图所示,其中顶点表示项目里程碑,连接顶点的边表示包含的活动,边上的数字表示活动的持续时间(天),则完成该项目的最少时间为(33)天。活动BC和BF分别最多可以晚开始(34)天而不会影响整个项目的进度。(33)
某开发小组欲开发一个软件系统,实现城市中不同图书馆的资源共享,包括实体资源和电子资源,共享规则可能在开发过程中有变化。客户希望开发小组能尽快提交可运行的软件,且可以接受多次交付。这种情况下最适宜采用(31)开发过程模型。主要是因为这种模型(32)。(
测试执行过程的阶段不包括______。
软件工程每一个阶段结束前,应该着重对可维护性进行复审。在系统设计阶段的复审期间,应该从(8)出发;评价软件的结构和过程。
()不是RISC的特点。
软件测试使用各种术语描述软件出现的问题,以下叙述正确的是______。A.软件错误(error)是指在软件生命周期内的不希望或不可接受的人为错误,其结果是导致软件故障的产生B.软件缺陷(defect)是存在于软件(文档、数据、程序)之中的那些不希望或不
根据你的网络工程经验,请用250字以内的文字简要描述该21层教学综合大楼网络层次结构设计的要点。(不要求画图)该21层教学综合大楼的部分网络拓扑结构如图1-22所示,其中L3_switch1、L3_switch2为该教学综合大楼的两台核心交换机;Swi
流程图中文件F的纪录格式设定为见表4形式: 其中的①、②应定义为何种数据项?简述处理2、处理3和处理4作何种处理,若有排序处理则需指明排序的键及序(升序或降序)。
随机试题
下列沟通方式中,属于正式沟通的是【】
2岁男孩,进食时哭闹不止,突然出现剧烈呛咳、喉鸣,呼吸困难,该患儿可能发生
与其他存款相比,下列有关存单的特点,说法不正确的是()。
甲将自己的私房一间出租给其同事乙居住,双方签订租赁协议,约定租期为2年,月租金l000元。其他事项未约定。在租赁期间,当事人以下行为合法的有()。
在选拔主管人员时,重点应放在候选人在实践中所表现出来的()。
下列文字中画横线部分存在错误的是()。古代的东西方商路主要有三条:一条是从中亚由陆路沿里海、波罗的海(A)到小亚细亚;一条是先由海路至波斯湾,然后经两河流域到地中海东岸(B)的叙利亚一带;第三条是先由海路至红海,然后再由陆路到埃及(C)的亚历山大
在平面直角坐标系中,如果点P(3a一9,1一a)在第三象限内,且横坐标纵坐标都是整数,则点P的坐标是:
()通过感觉寻求倾向测验对大量人类被试的研究发现,感觉寻求倾向是不受个体感觉形式制约的普遍的特质。
Youaregoingtoreadalistofheadingsandatextaboutsmartcardsandmobilephones.Choosethemostsuitableheadingfromt
《GB/T18905软件工程产品评价》标准中确定的通用评价过程包括:(55)。
最新回复
(
0
)