一、单项选择题
1、数据结构是研究数据的______以及它们之间的相互关系。
A.理想结构,物理结构
B.理想结构,抽象结构
C.物理结构,逻辑结构
D.抽象结构,逻辑结构
2、线性表的链接实现有利于______运算。
A.插入
B.读表元素
C.查找
D.定位
3、从一个长度为n的顺序表中删除第i个元素(1≤i≤n)时,需向前移动______个元素。
A.n-i
B.n-i+1
C.n-i-1
D.i
4、具有n个顶点的完全有向图的边数为______。
A.n(n-1)/2
……此处隐藏20938个字…… "951" src="/d/file/p/2024/12-06/7e4f332148fc2bb978b03406e12838de.jpeg" width="693" />
[考点] 本题考查Dijkstra算法的设计。
[解析] Dijkstra算法用来求某源点到其余各顶点的最短路径,主要特点是从起始点开始,采用贪心算法的策略,每次遍历到始点距离最近且未访问过的顶点的邻接点,直到扩展到终点为止。该算法要求图中不存在负权边。Dijkstra算法步骤如下:G={V,E}
① 初始时令S={V0},T=V-S={其余顶点},V0与T中各顶点若存在弧,d(V0,Vi)为弧上的权值。若不存在,d(V0,Vi)为∞。
② 从T中选取一个与S中顶点有关联边且权值最小的顶点W,加入到S中。
③ 对其余T中顶点的距离值进行修改:若加进W作中间顶点,从V0到Vi的距离值缩短,则修改此距离值重复上述步骤②、③,直到S中包含所有顶点,即W=Vi为止。