简答题
计算机
2013-09-26
带权图(权值非负,表示边连接的两顶点间的距离)的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假定从初始顶点到目标顶点之间存在路径,现有一种解决该问题的方法:
①设最短路径初始时仅包含初始顶点,令当前顶点u为初始顶点;
②选择离u最近且尚未在最短路径中的一个顶点v,加入到最短路径中,修改当前顶点u=v;
③重复步骤②,直到u是目标顶点时为止。
请问上述方法能否求得最短路径?若该方法可行,请证明之;否则,请举例说明。
参考答案
暂无
答案解析
该方法求得的路径不一定是最短路径。例如,对于下图所示的带权图,如果按照题中的原则,
从A到C的最短路径为A→B→C,事实上其最短路径为 A→D→C。

从A到C的最短路径为A→B→C,事实上其最短路径为 A→D→C。

你可能感兴趣的试题
3
某计算机字长16位,采用16位定长指令字结构,部分数据通路结构如图所示。图中所有控制信号为1时表示有效、为0时表示无效。例如控制信号MDRinE为1表示允许数据从DB打入MDR,MDRin为1表示允许数据从内总线打入MDR。假设MAR的输出一直处于使能状态。加法指令“ADD(R1),R0”的功能为(R0)+((R1))→(R1),即将R0中的数据与R1的内容所指主存单元的数据相加,并将结果送入R1的内容所指主存单元中保存。

数据通路结构

数据通路结构
下表给出了上述指令取值和译码阶段每个节拍(时钟周期)的功能和有效控制信号,请按表中描述方式用表格列出指令执行阶段每个节拍的功能和有效控制信号。
功能和控制信号
|
时钟 |
功能 |
有效控制信号 |
|
C1 |
MAR←(PC) |
PCout,MARin |
|
C2 |
MDR←M(MAR) |
MemR,MDRinE |
|
C3 |
IR←(MDR) |
MDRout,IRin |
|
C4 |
指令译码 |
无 |
假设该链表只给出了头指针list。在不改变链表的前提下,请设计一个尽可能高效的算法,查找链表中倒数第k个位置上的结点(k为正整数)。若查找成功,算法输出该结点的data值,并返回1;否则,只返回0。要求: