一、单项选择题

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为止。