Question 1

In which of the diagrams below do the wiggly edges represent spanning trees? 
A) I only
B) II only
C) Both I and II
D) Neither I nor II

Accepted Answer

The answer of In which of the diagrams below do...

Question 2

Which of the following describes a Hamiltonian circuit for the graph below? 
A) ABFEDCBA
B) ABCFEA
C) ABCFBAEDA
D) ABCFEDA

Accepted Answer

The answer of Which of the following describes a Hamiltonian...

Question 3

For the graph below, what is the cost of the Hamiltonian circuit obtained by using the sorted-edges algorithm? 
A) 16
B) 17
C) 18
D) 19

Accepted Answer

The answer of For the graph below, what is the...

Question 4

Suppose a college campus decides to install its own phone lines connecting all of the buildings so that calls may be relayed through one or more buildings before reaching their destination. Which technique is most likely to be useful in solving this problem?
A) Finding an Euler circuit on a graph
B) Applying the nearest-neighbor algorithm for the traveling salesman problem.
C) Applying Kruskal's algorithm for finding a minimum-cost spanning tree for a graph
D) None of these techniques is likely to apply

Accepted Answer

Kruskal's algorithm for finding a minimum-cost spanning tree for a graph would be useful in solving this problem because it would help to find the most efficient way to connect all the buildings with minimum cost. This algorithm is commonly used in network design problems.

Question 5

A connected graph G has 32 vertices. How many vertices does a spanning tree of G have?
A) 30
B) 31
C) 32
D) 33

Accepted Answer

A spanning tree of a graph G is a subgraph that includes all of the vertices of G and is a tree. Since a tree with n vertices has exactly n-1 edges, and the question asks for the number of vertices, the spanning tree of a graph with 32 vertices also has 32 vertices.

Question 6

Given the two graphs shown below, which one represents a tree? 
A) I only
B) II only
C) Both I and II
D) Neither I nor II

Accepted Answer

The answer of Given the two graphs shown below, which...

Question 7

Suppose a maintenance worker needs to empty garbage dumpsters from five locations on the grounds of a park in the most efficient way possible. Which technique is most likely to be useful in solving this problem?
A) Finding an Euler circuit on a graph
B) Applying the nearest-neighbor algorithm for the traveling salesman problem
C) Applying Kruskal's algorithm for finding a minimum-cost spanning tree for a graph
D) None of these techniques is likely to apply

Accepted Answer

The problem of emptying garbage dumpsters from multiple locations is similar to the traveling salesman problem, where a salesman needs to visit multiple cities in the most efficient way possible. The nearest-neighbor algorithm is a commonly used heuristic for solving the traveling salesman problem and can be applied in this scenario to find the most efficient route for the maintenance worker to take. The other techniques mentioned (finding an Euler circuit and Kruskal's algorithm) are not relevant to this particular problem.

Question 8

The graph below shows the cost (in hundreds of dollars) of installing telephone wires between the workspaces in an office complex. Use Kruskal's algorithm for minimum-cost spanning trees to find the cost for establishing this phone network. 
A) $2100
B) $2400
C) $2900
D) $6200

Accepted Answer

The answer of The graph below shows the cost (in...

Question 9

A college student has six pairs of pants, eight T-shirts, three sweatshirts, and two pairs of tennis shoes. If an outfit consists of pants, a T-shirt, a sweatshirt, and a pair of tennis shoes, how many different outfits can the student wear before repeating one?
A) 19
B) 124
C) 288
D) 328

Accepted Answer

The number of outfits can be found by multiplying the number of options for each clothing item:
6 (pants) x 8 (T-shirts) x 3 (sweatshirts) x 2 (tennis shoes) = 288
Therefore, the student can wear 288 different outfits before repeating one.

Question 10

Given the two graphs shown below, which one represents a tree? 
A) I only
B) II only
C) Both I and II
D) Neither I nor II

Accepted Answer

The answer of Given the two graphs shown below, which...

Question 11

For the graph below, what is the cost of the Hamiltonian circuit obtained by using the nearest-neighbor algorithm, starting at B? 
A) 16
B) 17
C) 18
D) 19

Accepted Answer

The answer of For the graph below, what is the...

Question 12

For a connected graph of 18 vertices, every possible spanning tree has exactly 17 edges.

Accepted Answer

In any connected graph, a spanning tree will have exactly one less edge than the number of vertices, so for a graph with 18 vertices, every possible spanning tree will have 17 edges.

Question 13

For the graph below, what is the cost of the Hamiltonian circuit obtained by using the nearest-neighbor algorithm, starting at A? 
A) 16
B) 17
C) 18
D) 19

Accepted Answer

The answer of For the graph below, what is the...

Question 14

An online banking service requires its customers to select a password that is four characters long. The password is case-sensitive, so upper-case letters are considered to be different than lower-case letters. The first character of the password must be an upper-case letter and the second character must be a digit. The remaining two characters may each be a digit, an uppercase letter, or a lowercase letter. What is the number of possible passwords?
A) 175,760
B) 336,960
C) 999,440
D) 1,406,080

Accepted Answer

The answer of An online banking service requires its customers...

Question 15

There are 3, 4, and 3 distinct paths from the city A to B, B to C, and C to D, respectively. Starting from the city A, you are planning to travel those cities in the order B, C, and D. How many different travel routes are possible?
A) 10
B) 24
C) 36
D) 72

Accepted Answer

There are 3 possible paths from A to B, 4 possible paths from B to C, and 3 possible paths from C to D. Thus, the total number of travel routes from A to D passing through B and C is 3 x 4 x 3 = 36.

Question 16

In which of the diagrams below do the wiggly edges represent spanning trees? 
A) I only
B) II only
C) Both I and II
D) Neither I nor II

Accepted Answer

The answer of In which of the diagrams below do...

Question 17

Suppose that after a storm an inspection needs to be made of the sewers along the streets in a small village to make sure local flooding is not due to clogging. Which technique is most likely to be useful in solving this problem?
A) Finding an Euler circuit on a graph
B) Applying the nearest-neighbor algorithm for the traveling salesman problem
C) Applying Kruskal's algorithm for finding a minimum-cost spanning tree for a graph
D) None of these techniques is likely to apply

Accepted Answer

Finding an Euler circuit on a graph is most useful for this scenario because it allows for the inspection of every edge (in this case, every street or sewer segment) without repeating any, ensuring a thorough and efficient inspection route.

Question 18

Suppose a pizza delivery person needs to take pizzas to 10 houses in different neighborhoods and then return to pick up the next set to be delivered. Which technique is most likely to be useful in solving this problem?
A) Finding an Euler circuit on a graph
B) Applying the nearest-neighbor algorithm for the traveling salesman problem
C) Applying Kruskal's algorithm for finding a minimum-cost spanning tree for a graph
D) None of these techniques is likely to apply

Accepted Answer

The nearest-neighbor algorithm for the traveling salesman problem is a technique that can be used to solve this problem. This algorithm involves starting at a random house, then finding the nearest house and delivering the pizza there. The delivery person then moves on to the nearest house that has not yet been visited and repeats this process until all houses have been visited. This method allows the delivery person to take an efficient route and return to the starting point after delivering all the pizzas.

Question 19

Phyllis has her office in Middleton and must visit four clients, each in a different city. The graph below shows each city and the distances between each pair of cities. How many miles would Phyllis travel if she chooses the Hamiltonian circuit for her trip by using the sorted-edges algorithm? 
A) 265 miles
B) 300 miles
C) 285 miles
D) 345 miles

Accepted Answer

Using the sorted-edges algorithm, the Hamiltonian circuit would be: 
Middleton -> Eland -> Mellen -> Ogema -> Prentice -> Middleton 
The total distance traveled would be: 
Middleton to Eland: 60 
Eland to Mellen: 70 
Mellen to Ogema: 55 
Ogema to Prentice: 80 
Prentice to Middleton: 20 
Total distance = 60 + 70 + 55 + 80 + 20 = 285 miles. Therefore, the answer is C.

Question 20

Kris has three pairs of pants of different colors, five shirts of different colors, and two pairs of shoes. How many different outfits can Kris create?
A) 2
B) 10
C) 30
D) 50

Accepted Answer

To find the total number of outfit combinations, we need to multiply the number of options for each item of clothing. 
Therefore, the total number of outfits that Kris can create is 3 (pants) x 5 (shirts) x 2 (shoes) = 30. Therefore, the best choice is C.

Quiz 2: Business Efficiency

In which of the diagrams below do the wiggly edges represent spanning trees?

Which of the following describes a Hamiltonian circuit for the graph below?

For the graph below, what is the cost of the Hamiltonian circuit obtained by using the sorted-edges algorithm?

Suppose a college campus decides to install its own phone lines connecting all of the buildings so that calls may be relayed through one or more buildings before reaching their destination. Which technique is most likely to be useful in solving this problem?

A connected graph G has 32 vertices. How many vertices does a spanning tree of G have?

Given the two graphs shown below, which one represents a tree?

Suppose a maintenance worker needs to empty garbage dumpsters from five locations on the grounds of a park in the most efficient way possible. Which technique is most likely to be useful in solving this problem?

The graph below shows the cost (in hundreds of dollars) of installing telephone wires between the workspaces in an office complex. Use Kruskal's algorithm for minimum-cost spanning trees to find the cost for establishing this phone network.

A college student has six pairs of pants, eight T-shirts, three sweatshirts, and two pairs of tennis shoes. If an outfit consists of pants, a T-shirt, a sweatshirt, and a pair of tennis shoes, how many different outfits can the student wear before repeating one?

Given the two graphs shown below, which one represents a tree?

For the graph below, what is the cost of the Hamiltonian circuit obtained by using the nearest-neighbor algorithm, starting at B?

For a connected graph of 18 vertices, every possible spanning tree has exactly 17 edges.

For the graph below, what is the cost of the Hamiltonian circuit obtained by using the nearest-neighbor algorithm, starting at A?

There are 3, 4, and 3 distinct paths from the city A to B, B to C, and C to D, respectively. Starting from the city A, you are planning to travel those cities in the order B, C, and D. How many different travel routes are possible?

In which of the diagrams below do the wiggly edges represent spanning trees?

Suppose that after a storm an inspection needs to be made of the sewers along the streets in a small village to make sure local flooding is not due to clogging. Which technique is most likely to be useful in solving this problem?

Suppose a pizza delivery person needs to take pizzas to 10 houses in different neighborhoods and then return to pick up the next set to be delivered. Which technique is most likely to be useful in solving this problem?

Phyllis has her office in Middleton and must visit four clients, each in a different city. The graph below shows each city and the distances between each pair of cities. How many miles would Phyllis travel if she chooses the Hamiltonian circuit for her trip by using the sorted-edges algorithm?

Kris has three pairs of pants of different colors, five shirts of different colors, and two pairs of shoes. How many different outfits can Kris create?