利用动态规划方法求解每对结点之间的最短路径问题(a11　pairs　shortest　path　problem)时，设有向图G=＜V，E＞共有n个结点，结点编号1～n，设C是G的成本邻接矩阵，用Dk(i，j)表示从i到j并且不经过编号比众还大的结点的最短路

admin2021-01-13 39

问题利用动态规划方法求解每对结点之间的最短路径问题(a11　pairs　shortest　path　problem)时，设有向图G=＜V，E＞共有n个结点，结点编号1～n，设C是G的成本邻接矩阵，用D^k(i，j)表示从i到j并且不经过编号比众还大的结点的最短路径的长度(Dⁿ(i，j即为图G中结点i到j的最短路径长度)，则求解该问题的递推关系式为(56)。

选项 A、D^k(i，j)；D^k-1(i，j)+C(i，j)
B、D^k(i，j)：min{D^k-1(i，j),D^k-1(i，j)+C(i，j)}
C、D^k(i，j)：D^k-1(i，k)+D^k-1(i，j)
D、D^k(i，j)；min{D^k-1(i，j),D^k-1(i，k)+D^k-1(k，j)}

答案D

解析设p^k(i，j)表示从i到j并且不经过编号比k还大的结点的最短路径，那么p^k(i，j)有以下两种可能：
①p^k(i，j)经过编号为k的结点，此时p^k(i，j)可以分为从i到k和从k到j的两段，易知产p^k(i，j)的长度为D^k-1(i，k)+D^k-1(k，j)。
②p^k(i，j)不经过编号为k的结点，此时产p^k(i，j)的长度为D^k-1(i，j)。

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

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

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

软考中级

相关试题推荐

随机试题

最新回复(0)

利用动态规划方法求解每对结点之间的最短路径问题(a11　pairs　shortest　path　problem)时，设有向图G=＜V，E＞共有n个结点，结点编号1～n，设C是G的成本邻接矩阵，用Dk(i，j)表示从i到j并且不经过编号比众还大的结点的最短路

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

软考中级

阅读以下函数说明和JaVa代码，将应填入(n)处的字句写在答题纸对应栏内。【说明】现有一个显示系统，要显示的图形有线Line、矩形Square，抽象出一+Shape类(接口)，有方法显示display()。需要新增图形Circle，又已知有类XXCir

阅读下列说明和图，回答问题1～问题3，将解答填入答题纸的对应栏内。【说明】Pay&Drive系统(开多少付多少)能够根据驾驶里程自动计算应付的费用。系统中存储了特定区域的道路交通网的信息。道路交通网由若干个路段(RoadSeg

容量为64块的Cache采用组相联方式映像，字块大小为128个字，每4块为一组。若主存容量为4096块，且以字编址，那么主存地址应为(7)位，主存区号应为(8)位。

关系R、S如下图所示，元组演算表达式{t|(u)(R(t)∧S(u)∧t[3]＞u[1])}的结果为(47)。

设阶码8位(最左一位为符号位)，用移码表示，尾数为24位(最左一位为符号位)，用规格化补码表示，则它所能表示的最大正数的阶码为(27)，尾数为(28)；绝对值最小的负数的阶码为(29)，尾数为(30)。

防火墙是一种常用的网络安全装置，它可以(63)。有多种实现防火墙的技术，如包过滤、代理服务器、双穴主机和屏蔽子网网关等，相对来说(64)功能较弱但实现也较简单。

公平理论

设备监理管理协调办公室的主要职责有(　　)。

根据我国《建筑法》的规定，实行监理的建筑工程，委托具有相应资质的工程监理单位进行监理的应是(　　)。

主副井贯通前，矿井的通风方式是利用()进行通风。

某市政工程公司购入一台设备，价款为20000元，增值税率17％，使用年限为5年，预计净残值率为5％。根据企业会计准则及其相关规定，在年数总和法下，该设备第三年的折旧额为()。

(　　)规定：“对会计人员的教育和培训工作应当加强”。

贷款人不享有先履行抗辩权的情况是()。

中国历史上记载最早的儿童识字课本是()

Whatistheconversationmainlyabout?

利用动态规划方法求解每对结点之间的最短路径问题(a11 pairs shortest path problem)时，设有向图G=＜V，E＞共有n个结点，结点编号1～n，设C是G的成本邻接矩阵，用Dk(i，j)表示从i到j并且不经过编号比众还大的结点的最短路

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

软考中级

阅读以下函数说明和JaVa代码，将应填入(n)处的字句写在答题纸对应栏内。【说明】现有一个显示系统，要显示的图形有线Line、矩形Square，抽象出一+Shape类(接口)，有方法显示display()。需要新增图形Circle，又已知有类XXCir

阅读下列说明和图，回答问题1～问题3，将解答填入答题纸的对应栏内。【说明】Pay&Drive系统(开多少付多少)能够根据驾驶里程自动计算应付的费用。系统中存储了特定区域的道路交通网的信息。道路交通网由若干个路段(RoadSeg

容量为64块的Cache采用组相联方式映像，字块大小为128个字，每4块为一组。若主存容量为4096块，且以字编址，那么主存地址应为(7)位，主存区号应为(8)位。

关系R、S如下图所示，元组演算表达式{t|(u)(R(t)∧S(u)∧t[3]＞u[1])}的结果为(47)。

设阶码8位(最左一位为符号位)，用移码表示，尾数为24位(最左一位为符号位)，用规格化补码表示，则它所能表示的最大正数的阶码为(27)，尾数为(28)；绝对值最小的负数的阶码为(29)，尾数为(30)。

防火墙是一种常用的网络安全装置，它可以(63)。有多种实现防火墙的技术，如包过滤、代理服务器、双穴主机和屏蔽子网网关等，相对来说(64)功能较弱但实现也较简单。

公平理论

设备监理管理协调办公室的主要职责有( )。

根据我国《建筑法》的规定，实行监理的建筑工程，委托具有相应资质的工程监理单位进行监理的应是( )。

主副井贯通前，矿井的通风方式是利用()进行通风。

某市政工程公司购入一台设备，价款为20000元，增值税率17％，使用年限为5年，预计净残值率为5％。根据企业会计准则及其相关规定，在年数总和法下，该设备第三年的折旧额为()。

( )规定：“对会计人员的教育和培训工作应当加强”。

贷款人不享有先履行抗辩权的情况是()。

中国历史上记载最早的儿童识字课本是()

Whatistheconversationmainlyabout?

利用动态规划方法求解每对结点之间的最短路径问题(a11　pairs　shortest　path　problem)时，设有向图G=＜V，E＞共有n个结点，结点编号1～n，设C是G的成本邻接矩阵，用Dk(i，j)表示从i到j并且不经过编号比众还大的结点的最短路

设备监理管理协调办公室的主要职责有(　　)。

根据我国《建筑法》的规定，实行监理的建筑工程，委托具有相应资质的工程监理单位进行监理的应是(　　)。

(　　)规定：“对会计人员的教育和培训工作应当加强”。