Introduction to Java Programming

Introduction to Java Programming, Includes Data Structures, Eleventh Edition, Y. Daniel Liang

This quiz is for students to practice. A large number of additional quiz is available for instructors using Quiz Generator from the Instructor's Resource Website. Videos for Java, Python, and C++ can be found at https://yongdanielliang.github.io/revelvideos.html.

Chapter 29 Weighted Graphs and Applications

Section 29.2 Representing Weighted Graphs

29.1 True or False? The WeightedEdge class extends AbstractGraph.Edge.

A. True

B. False

29.2 A WeightedEdge object contains the public data fields _______.

A. u

B. v

C. weight

D. length

29.3 The adjacent edge for each vertex in the WeightedGraph class is stored in _________.

A. an ArrayList

B. a LinkedList

C. a PriorityQueue

D. a Stack

Section 29.3 The WeightedGraph Class

29.4 The WeightedGraph is a subtype of _________.

A. UnweightedGraph

B. AbstractGraph

C. Graph

D. WeightedEdge

29.5 The addEdge(u, v, w) method performs the following operations:

A. Invokes super.add(u, v) to add an edge.

B. Adds a weighed edge to the adjacent list for vertex u.

C. Adds a weighed edge to the adjacent list for vertex v.

Section 29.4 Minimum Spanning Trees

29.6 Suppose a weighted graph is created in the following code. What is total weight of a minimum spanning tree?

    Integer[] vertices = {0, 1, 2, 3, 4};

    int[][] edges = {
      {0, 1, 9}, {0, 2, 5},
      {1, 0, 9}, {1, 2, 6}, {1, 3, 4}, {1, 4, 7},
      {2, 0, 5}, {2, 1, 6}, {2, 3, 3},
      {3, 1, 4}, {3, 2, 3}, {3, 4, 1},
      {4, 1, 7}, {4, 3, 1}
    };

    WeightedGraph<Integer> graph1 =
      new WeightedGraph<>(vertices, edges);
    WeightedGraph<Integer>.MST tree1 = graph1.getMinimumSpanningTree();
    System.out.println("Total weight is " + tree1.getTotalWeight());

29.7 The MST class is subtype of __________.

A. BST

B. AVLTree

C. AbstractGraph.Tree

D. Tree

29.8 The getMinimumSpanningTree() method returns __________.

A. an ArrayList

B. a LinkedList

C. a queue

D. a MST

29.9 A graph may have several minimum spanning tree.

A. True

B. False

Section 29.5 Finding Shortest Paths

29.10 Suppose a weighted graph is created in the following code. What is the shortest path from vertex 4 to 0?

    Integer[] vertices = {0, 1, 2, 3, 4};

    int[][] edges = {
      {0, 1, 9}, {0, 2, 5},
      {1, 0, 9}, {1, 2, 6}, {1, 3, 4}, {1, 4, 7},
      {2, 0, 5}, {2, 1, 6}, {2, 3, 3},
      {3, 1, 4}, {3, 2, 3}, {3, 4, 1},
      {4, 1, 7}, {4, 3, 1}
    };

    WeightedGraph<Integer> graph1 =
      new WeightedGraph<>(vertices, edges);
    WeightedGraph<Integer>.ShortestPathTree tree1 =
      graph1.getShortestPath(graph1.getIndex(0));

    System.out.println("Shortest path from 4 to 0 is " +
      tree1.getPath(4));

29.11 The ShortestPathTree class is subtype of __________.

A. BST

B. AVLTree

C. AbstractGraph.Tree

D. Tree

29.12 The getShortestPath() method returns __________.

A. an ArrayList

B. a LinkedList

C. a ShortestPathTree

D. a MST

29.13 A ___________ of a graph is a subgraph that is a tree and connects all vertices in the graph.

A. spanning tree

B. shortest path