Multiple Choices (10 points, 1 point each)

1. A graph that has values associated with its edges is called a weighted graph. The graph can be either directed or undirected. The weights can represent thing(s) like:

A. the cost of traversing the edge B. the length of the edge

C. the time needed to traverse the edge D. all of the above

2. In an undirected graph with n vertices, the maximum number of edges is:

A. n² B. n(n-1)/2 C. n(n+1)/2 D. n(n-1)

3. In an adjacency list of undirected graph with n vertices and e edges, the number of edge node is:

A. n B. e C. 2*e D. n*e

4. In the adjacency list of a directed graph, the times vertex v_i appears in the list is:

A. the degree of vertex v_i B. the in-degree of vertex v_i

C. the out-degree of vertex v_i D. the number of edges attached to vertex v_i

5. Which of the following is useful in traversing a given graph by breadth first search?

A. list B. stack C. queue D. set

6. Assuming graph G with n vertices and e edges, and using the adjacency list as the storage structure, when we execute depth-first search, the time complexity is:

A. O(e) B. O(n+e) C. O(log(n*e)) D. O(n*e)

7. When traversing graph, in the following sequence: from A to all of As adjacency nodes B_i to all of B_is adjacency nodes, such traversal method is:

A. depth-first traversal B. breadth-first traversal

C. preorder traversal D. postorder traversal

8. A spanning tree of a connected undirected graph is a:

A. minimal connected subgraph that includes all of the vertices of this graph

B. minimal subgraph that includes all of the vertices of this graph

C. significantly connected subgraph that includes all of the vertices of this graph

D. significantly subgraph that includes all of the vertices of this graph

9. Which is wrong in the following statements?

A. Each vertex is visited only once during graph traversal.

B. There are two methods, depth-first search and breadth-first search, to traverse a graph.

C. Depth-first search of a graph isnt fit to a directed graph.

D. Depth-first search of a graph is a recursive process.

10. How many minimum-cost spanning trees are there for a connected undirected graph with n vertices and e edges?

A. must be only one B. n-1 C. n-e D. not sure