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

A)	ABCDEFJIHG	C)	ABCDEAGHIJFA	
B)	ABCDEAFJDIHBGFEJICHGA	D)	AEDCBGHIJFA	

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

	A)  ABCDEFGA    B)  ACBAEGFDEA    C)  ACBFGDEA    D)  ABCDGEF	

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

A)	ABCDEJHIGF	C)	ABCDEAFGHIJFA	
B)	AEDCBGIHJFA	D)	ABCDEAFGBGIDIHCHJEJFA	

4.	On the graph below, which routing is produced by using the nearest-neighbor algorithm to solve the traveling salesman problem?

	A)  ABCDA    B)  ABDCA    C)  ACBDA    D)  ABCD	

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

	A)  60    B)  54    C)  62    D)  66	

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

	A)  215    B)  220    C)  235    D)  295	

7.	Which path listed forms a Hamiltonian circuit on the graph below?

A)	ADCBFGHEA	C)	ABCDHGFEA	
B)	ABCDHGFE	D)	ABCDHGFEHDA	

8.	On a map there are roads from town A of length 10, 26, 12, and 50 miles. Using the nearest-neighbor algorithm for finding a Hamiltonian circuit starting at town A, which road would be traveled first?	
A)	road of length 10	C)	road of length 12	
B)	road of length 26	D)	road of length 50	

9.	For the traveling salesman problem (Hamiltonian circuit) applied to six cities, how many tours are possible?	
	A)  60    B)  120    C)  360    D)  720	

10.	For the traveling salesman problem (Hamiltonian circuit) applied to five cities, how many distinct tours are possible?	
	A)  120    B)  60    C)  24    D)  12	

11.	For the traveling salesman problem (Hamiltonian circuit) applied to four cities, how many distinct tours are possible?	
	A)  3    B)  6    C)  12    D)  24	

12.	For the traveling salesman problem applied to seven cities, how many distinct tours are possible?	
	A)  360    B)  720    C)  2520    D)  5040	

13.	On the graph below, which routing is produced by using the sorted-edges algorithm to solve the traveling salesman problem?

	A)  ABCDA    B)  ABDCA    C)  ACBDA    D)  ABCD	

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

	A)  40    B)  58    C)  60    D)  66	

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

	A)  220    B)  225    C)  235    D)  295	

16.	Use Kruskal's algorithm for minimum-cost spanning trees on the graph below. The cost of the tree found is:

	A)  5    B)  9    C)  12    D)  15	

17.	Use Kruskal's algorithm for minimum-cost spanning trees on the graph below. The cost of the tree found is:

	A)  23    B)  20    C)  16    D)  5	

18.	Use Kruskal's algorithm for minimum-cost spanning trees on the graph below. The cost of the tree found is:

	A)  20    B)  14    C)  19    D)  22	

19.	Use Kruskal's algorithm for minimum-cost spanning trees on the graph below. The cost of the tree found is:

	A)  47    B)  25    C)  22    D)  15	

20.	Use Kruskal's algorithm for minimum-cost spanning trees on the graph below. The cost of the tree found is:

	A)  22    B)  28    C)  32    D)  49	

21.	Given the order-requirement digraph for a collection of tasks shown below, the critical path would be:

	A)  T1, T2, T 3    B)  T4, T2, T 3    C)  T4, T3    D)  T4, T5, T 6	

22.	If the order-requirement digraph for a collection of tasks is shown below, then what is the minimum completion time for the collection of tasks?

	A)  64 minutes    B)  43 minutes    C)  36 minutes    D)  28 minutes	

23.	What is the earliest possible completion time for a job whose order-requirement is shown below?

	A)  10    B)  17    C)  40    D)  15	

24.	What is the earliest possible completion time for a job whose order-requirement digraph is shown below?

	A)  15    B)  22    C)  34    D)  19	

25.	What is the earliest possible completion time for a job whose order-requirement is shown below?

	A)  27    B)  17    C)  21    D)  48	

26.	The nearest-neighbor algorithm for solving the traveling salesman problem always gives optimal results.	
	A)  True    B)  False	

27.	The sorted-edges algorithm for solving the traveling salesman problem always gives optimal results.	
	A)  True    B)  False	

28.	Kruskal's algorithm for finding minimum-cost spanning trees always gives optimal results.	
	A)  True    B)  False	

29.	The nearest-neighbor algorithm for solving the traveling salesman problem always produces the same result as the sorted-edges algorithm.	
	A)  True    B)  False	

30.	The path produced by the nearest-neighbor algorithm when solving the traveling salesman problem may be dependent on the starting city.	
	A)  True    B)  False	

31.	The path produced by the sorted-edges algorithm when solving the traveling salesman problem may be dependent on the starting city.	
	A)  True    B)  False	

32.	The minimum-cost spanning tree produced by applying Kruskal's algorithm will always contain the lowest cost edge of the graph.	
	A)  True    B)  False	

33.	The minimum-cost spanning tree produced by applying Kruskal's algorithm may contain the most expensive edge of the graph.	
	A)  True    B)  False	

34.	A heuristic algorithm will always produce optimal results.	
	A)  True    B)  False	

35.	A heuristic algorithm may produce optimal results.	
	A)  True    B)  False	

36.	When Kruskal's algorithm is used to find a minimum-cost spanning tree on a graph, which of the following is false?	
A)	Circuits are not permitted in the tree.	
B)	The tree contains the edge of the graph of minimum cost.	
C)	The tree is not necessarily connected.	
D)	The tree may contain the edge of the highest cost.	

37.	A spanning tree of a graph must contain every edge of the graph.	
	A)  True    B)  False	

38.	A digraph is a graph with exactly two vertices.	
	A)  True    B)  False	

39.	Suppose an architect needs to design an intercom system for a large office building. The technique most likely to be useful in solving this problem is	
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.	

40.	Suppose a veteran is planning a visit to all the war memorials in Washington D.C. The technique most likely to be useful in solving this problem is	
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.	

41.	Suppose an employee of a power company needs to read the electricity meters outside of each house along the streets in a residential area. The technique most likely to be useful in solving this problem is	
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.	

42.	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. The technique most likely to be useful in solving this problem is	
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.	

43.	Suppose a college campus decides to install its own phone lines connecting all of the  buildings where calls may be relayed through one or more buildings before reaching their destination. The technique most likely to be useful in solving this problem is	
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.	

44.	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. The technique most likely to be useful in solving this problem is	
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.	

45.	Suppose a maintenance worker needs to empty garbage dumpsters from five locations on the grounds of a park in the most efficient way possible. The technique most likely to be useful in solving this problem is	
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.	

46.	Phyllis has her office in Middletown 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 will 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	

47.	The graph below shows the cost of installing telephone wires (in hundreds of dollars) between the work spaces 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	

48.	A local cafeteria offers a choice of 5 meats, 6 vegetables, and 3 salads. A complete dinner includes 1 meat, 1 vegetable, and 1 salad. How many different dinners can be created?	
	A)  14    B)  45    C)  90    D)  120	

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

50.	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	

51.	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	

52.	In which of the diagrams below do the wiggled edges represent spanning trees?

	A)  I only    B)  II only    C)  Both I and II    D)  Neither I nor II	

53.	In which of the diagrams below do the wiggled edges represent spanning trees?

	A)  I only    B)  II only    C)  Both I and II    D)  Neither I nor II	

54.	For the graph below, which routing is produced by using the nearest-neighbor algorithm to solve the traveling salesman problem?

	A)  ABCEDA    B)  ABEDCA    C)  ADCEBA    D)  ABCED	

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

	A)  25    B)  28    C)  29    D)  35	

56.	A college student has six pairs of pants, eight tee shirts, three sweatshirts and two pairs of tennis shoes. If an outfit consists of pants, a tee 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	

57.	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 upper-case letter or a lower-case letter. What is the number of possible passwords?	
	A)  175,760    B)  336,960    C)  999,440    D)  1,406,080	

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

59.	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	

60.	For the graph below, which routing is produced by using the sorted-edges algorithm to solve the traveling salesman problem?

	A)  ACBEDA    B)  ABCEDA    C)  ABEDCA    D)  ADCEBA	

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

	A)  23    B)  29    C)  33    D)  41	

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

	A)  ABFEDCBA    B)  ABCFEA    C)  ABCFBAEDA    D)  ABCFEDA	

63.	Use Kruskal's algorithm for minimum-cost spanning trees on the graph below. What is the cost of the tree found?

	A)  27    B)  31    C)  36    D)  39	

Answer Key

1.	D	
2.	C	
3.	B	
4.	B	
5.	D	
6.	B	
7.	C	
8.	A	
9.	B	
10.	C	
11.	B	
12.	B	
13.	A	
14.	D	
15.	C	
16.	B	
17.	C	
18.	B	
19.	C	
20.	B	
21.	D	
22.	B	
23.	B	
24.	D	
25.	A	
26.	B	
27.	B	
28.	A	
29.	B	
30.	A	
31.	B	
32.	A	
33.	A	
34.	B	
35.	A	
36.	C	
37.	B	
38.	B	
39.	C	
40.	B	
41.	A	
42.	B	
43.	C	
44.	A	
45.	B	
46.	C	
47.	B	
48.	C	
49.	C	
50.	B	
51.	A	
52.	B	
53.	A	
54.	B	
55.	C	
56.	C	
57.	C	
58.	B	
59.	C	
60.	A	
61.	B	
62.	D	
63.	C