数据结构章节测试课后答案2024春

第四章测试

1.以下说法，错误的是（ ）。
A:无向图是一个包含顶点和无向边的图结构 B:其他选项均不正确 C:加权无向图是一个包含顶点和加权有向边的图结构 D:有向图是一个包含顶点和有向边的图结构
答案:C
2.关于有向图的最短路径计算，正确的是（ ）。
A:拓扑排序算法不能处理存在回路的加权有向图 B:Bellman-Ford算法不能处理带有负权重回路的加权有向图 C:Dijkstra算法不能处理带有负权重的加权有向图 3.用于计算最短路径的Dijkstra和用于计算最小生成树的Prim算法是同一算法家族。（ ）
A:错 B:对 4.给定无向图的数据结构，进行插入和查找的操作，请根据要求填空。public class Graph {    private final int V;    private int E;private Bag<Integer>[] adj;}public class BreadthFirstPaths {    private static final int INFINITY = Integer.MAX_VALUE;    private boolean[] marked;  // marked[v] = is there an s-v path    private int[] edgeTo;      // edgeTo[v] = previous edge on shortest s-v path    private int[] distTo;      // distTo[v] = number of edges shortest s-v path     public BreadthFirstPaths(Graph G, int s) {        marked = new boolean[G.V()];        distTo = new int[G.V()];        edgeTo = new int[G.V()];        bfs(G, s);    }    // breadth-first search from a single source    private void bfs(Graph G, int s) {        Queue<Integer> q = new Queue<Integer>();        for (int v = 0; v < G.V(); v++)            distTo[v] = INFINITY;        distTo[s] = 0;        marked[s] = (    ？   );        q.enqueue(s);         while (!q.isEmpty()) {            int v = q.dequeue();            for (int w : G.adj(v)) {                if (!marked[w]) {                    edgeTo[w] = v;                    distTo[w] = distTo[v] + 1;                    marked[w] = true;                    q.enqueue(w);                }            }        }    }}
A:v B:false C:true D:null 5.给定如下的加权图的数据结构，完成最小生成树的延时prim方法的计算（prim方法）操作。public class Edge implements Comparable<Edge> {    private final int v;    private final int w;private final double weight;}public class EdgeWeightedGraph {    private final int V;    private int E;private Bag<Edge>[] adj;}public class LazyPrimMST {    private static final double FLOATING_POINT_EPSILON = 1E-12;     private double weight;       // total weight of MST    private Queue<Edge> mst;     // edges in the MST    private boolean[] marked;    // marked[v] = true iff v on tree    private MinPQ<Edge> pq;      // edges with one endpoint in tree     public LazyPrimMST(EdgeWeightedGraph G) {        mst = new Queue<Edge>();        pq = new MinPQ<Edge>();        marked = new boolean[G.V()];        for (int v = 0; v < G.V(); v++)     // run Prim from all vertices to            if (!marked[v]) prim(G, v);     // get a minimum spanning forest    }     // run Prim's algorithmprivate void prim(EdgeWeightedGraph G, int s) {   marked[s] = true;        for (Edge e : G.adj(s))            if (!marked[e.other(s)]) (    ？   );        while (!pq.isEmpty()) {                        // better to stop when mst has V-1 edges            Edge e = pq.delMin();                      // smallest edge on pq            int v = e.either(), w = e.other(v);        // two endpoints            if (marked[v] && marked[w]) continue;      // lazy, both v and w already scanned            mst.enqueue(e);                            // add e to MST            weight += e.weight();            if (!marked[v]) scan(G, v);               // v becomes part of tree            if (!marked[w]) scan(G, w);               // w becomes part of tree        }    }}
A:pq.insert(e) B:Pq.del(e) C:pq.insert(s) D:pq.delMin()