迪杰斯特拉(Dijkstra)算法按照路径长度递增的方式求解单源点最短路径问题，该算法运用了(62)算法策略。

admin2010-01-23 25

问题迪杰斯特拉(Dijkstra)算法按照路径长度递增的方式求解单源点最短路径问题，该算法运用了(62)算法策略。

选项 A、贪心
B、分治
C、动态规划
D、试探+回溯

答案A

解析本题考查最短路径问题。贪心算法通过一系列的选择得到问题的解。它所做出的每一次选择是当前状态下局部最优选择，即贪心选择。分治法的基本思想是把大问题分解成一些较小的问题，然后由小问题的解方便地构造出大问题的解。动态规划策略设计算法利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。回溯法也称为试探法，该方法首先暂时放弃关于问题规模大小的限制，并将问题的候选解按某种顺序逐一枚举和检验。迪杰斯特拉(Dijkstra)提出的按路径长度递增的次序产生最短路径的算法，其思想是把网中所有的顶点分成两个集合S和T，S集合的初态只包含顶点v0，T集合的初态为网中除v0之外的所有顶点。凡以v0为源点，已经确定了最短路径的终点并入S集合中；顶点集合T则是尚未确定最短路径的顶点的集合。按各顶点与v0间最短路径长度递增的次序，逐个把T集合中的顶点加入到S集合中去，使得从v0到S集合中各顶点的路径长度始终不大于从v0到T集合中各顶点的路径长度。从迪杰斯特拉算法求最短路径的过程可知，其算法策略属于贪心策略。

转载请注明原文地址:https://jikaoti.com/ti/zCa7FFFM

本试题收录于：软件设计师上午基础知识考试题库软考中级分类

软件设计师上午基础知识考试

软考中级

相关试题推荐

随机试题

最新回复(0)

迪杰斯特拉(Dijkstra)算法按照路径长度递增的方式求解单源点最短路径问题，该算法运用了(62)算法策略。

软件设计师上午基础知识考试

软考中级

在以太网的标准中，10BASE-T采用3类UTP，规定从收发站到有源集线器的距离不超过(163)米。100BASE-TX把数据传输速率提高了10倍，同时网络的覆盖范围(164)。假设tPHY表示工作站的物理层时延，C表示光速，S表示网段长度，tR表示中继器

FDDI是双环结构，其中一个为主环，一个为备用环，这样可以保证网络的可靠性。为了消除环网中的时钟偏移，FDDI使用了(171)方案，并规定进入站点缓冲器的数据时钟由输入信号的时钟确定，缓冲器的输出时钟信号由(172)确定。

请解释atm信元。请简述他们之间的通信过程。

阅读以下说明和交换机的配置信息，回答下面问题。【说明】某公司下设三个部门，为了便于管理，每个部门组成一个VLAN，公司网络结构如图2.8所示。[交换机Switch1的部分配置信息]Switch1(config)#fi

若某人持有盗版软件，但他本人确实不知道该软件是盗版的，则(15)承担侵权责任。

SNA(系统网络结构)：它是IBM公司1970年开发的大型，复杂，多功能网络结构，与SNA网的体系结构中的端用户相对应的是OSI的(22)层次。

在CPU中，__________可用于传送和暂存用户数据，为ALU执行算术逻辑运算提供工作区。(2008年下半年试题)

机器字长为n位的二进制数可以用补码来表示(1)个不同的有符号定点小数。

根据【说明】，将图6—1中的E1一E3填充完整。　　图6—1中缺少三条数据流，根据【说明】，分别指出这三条数据流的起点和终点。(注：数据流的起点和终点均采用图中的符号和描述)

胆郁痰扰证可见下列哪些症状

乙肝病毒存在的直接标志是

女性，29岁。G2P2，诊断为葡萄胎。查体：子宫如16周妊娠大小。肺部CT无异常。该患者治疗方法宜采用

特发性血小板减少性紫癜治疗首选

某载重汽车配司机1人，当年制度工作日为250天，年工作台班为230台班，人工日工资单价为50元，则该载重汽车的台班人工费为()元／台班。【2010年真题】

“不要将所有鸡蛋放在一个篮子里”这一投资格言说明的风险管理策略是()。

下列说法错误的是()。

下面句子中没有语病的是（）。

有以下程序#includeintf(intx);main(){inta,b=0;for(a=0;a＜3;a+=1){b+=f(A);putchar(’A’+b);}}intf(i

迪杰斯特拉(Dijkstra)算法按照路径长度递增的方式求解单源点最短路径问题，该算法运用了(62)算法策略。

软件设计师上午基础知识考试

软考中级

FDDI是双环结构，其中一个为主环，一个为备用环，这样可以保证网络的可靠性。为了消除环网中的时钟偏移，FDDI使用了(171)方案，并规定进入站点缓冲器的数据时钟由输入信号的时钟确定，缓冲器的输出时钟信号由(172)确定。

请解释atm信元。请简述他们之间的通信过程。

阅读以下说明和交换机的配置信息，回答下面问题。【说明】某公司下设三个部门，为了便于管理，每个部门组成一个VLAN，公司网络结构如图2.8所示。[交换机Switch1的部分配置信息]Switch1(config)#fi

若某人持有盗版软件，但他本人确实不知道该软件是盗版的，则(15)承担侵权责任。

SNA(系统网络结构)：它是IBM公司1970年开发的大型，复杂，多功能网络结构，与SNA网的体系结构中的端用户相对应的是OSI的(22)层次。

在CPU中，__________可用于传送和暂存用户数据，为ALU执行算术逻辑运算提供工作区。(2008年下半年试题)

机器字长为n位的二进制数可以用补码来表示(1)个不同的有符号定点小数。

根据【说明】，将图6—1中的E1一E3填充完整。 图6—1中缺少三条数据流，根据【说明】，分别指出这三条数据流的起点和终点。(注：数据流的起点和终点均采用图中的符号和描述)

胆郁痰扰证可见下列哪些症状

乙肝病毒存在的直接标志是

女性，29岁。G2P2，诊断为葡萄胎。查体：子宫如16周妊娠大小。肺部CT无异常。该患者治疗方法宜采用

特发性血小板减少性紫癜治疗首选

某载重汽车配司机1人，当年制度工作日为250天，年工作台班为230台班，人工日工资单价为50元，则该载重汽车的台班人工费为()元／台班。【2010年真题】

“不要将所有鸡蛋放在一个篮子里”这一投资格言说明的风险管理策略是()。

下列说法错误的是()。

下面句子中没有语病的是（）。

有以下程序#includeintf(intx);main(){inta,b=0;for(a=0;a＜3;a+=1){b+=f(A);putchar(’A’+b);}}intf(i

　　根据【说明】，将图6—1中的E1一E3填充完整。　　图6—1中缺少三条数据流，根据【说明】，分别指出这三条数据流的起点和终点。(注：数据流的起点和终点均采用图中的符号和描述)