CS302 Midterm Exam #2 - April 14, 2026

James S. Plank

The exam featured a lot of "bank" questions -- this is an example exam.

Questions 1 and 2 are "what is your username" and "if you have comments, put them here." So we start with question 3.

Questions 3-12

These came from a bank and were in random order. 2.5 points each:

Key=Selection: What is the Big-O running time of doing selection sort on an arbitrary vector of n values?
Key=Heap: What is the Big-O running time of doing heapsort on an arbitrary vector of n values?
Key=Merge: What is the Big-O running time of doing mergesort on an arbitrary vector of n values?
Key=Bucket: What is the Big-O running time of doing bucket/insertion sort on a vector of n uniformly distributed values?
Key=DFS: Given a graph with V nodes, E edges and one connected component, what is the big-O running time of doing a depth-first search on the graph?
Key=Dijkstra: Given a connected, directed graph with V nodes and E edges, where each edge has a weight between 1 and 100, what is the big-O running time of finding the shortest path from a given node to every other node on the graph?
Key=BFS: Given a connected, directed graph with V nodes and E edges, where each edge has a weight of 1, what is the big-O running time of finding the shortest path from a given node to every other node on the graph?
Key=Adjacency-Lists: Given a graph with V nodes and E edges, where each node has on average V/2 incident edges, what is the big-O of how much space is consumed when adjacency lists are use to store the graph? Your big-O equation should only have V in it.

Key=Inheritance: In the following code, an "Item" is either an interface or uses inheritance. Which is it? Answer "Can't determine" if you can't determine.

int main()
{
  Item *i;
  string s;

  cin >> s;
  if (s == "D") {
    i = new Dog;
  } else {
    i = new Koozie;
  }
  printf("%d\n", i->price());
  printf("%.2lf\n", i->expenses);
  return 0;
}

Key=Maxflow: What is the maximum flow of this graph?

   20       25
S -----> A-----> B 
 \       |       |
  \      | 17    | 10   
25 \     |       |
    \    v       v
     --> C ----> T
            28

Questions 13-15

These came from a bank and were in random order. 3 points each:

Key=Insertion: I have a program that takes 1 second to read 1,000,000 values from a file, and 20 seconds to sort them with insertion sort. The values are completely random. How many seconds do we expected it to take the program to read 4,000,000 values from a file and sort them with insertion sort?
Key=Quicksort: I have a program that takes 1 second to read 1,000,000 values from a file, and 20 seconds to sort them with quicksort. The values are completely random, meaning quicksort runs with its average-time behavior. How many seconds do we expected it to take the program to read 4,000,000 values from a file and sort them with quicksort?
Key=DFS-Adjmatrix: I have a program that reads in a graph, stores it with an adjacency matrix and then performs a depth-first search on it. This processs takes 4 seconds when the graph has 1024 nodes and is connected. How many seconds do we expected it to take when the graph has 4096 nodes and is connected?

Question 16

This came from a bank, and is worth 24 points.

You are sorting the following string: using bubble sort. What is the string after one pass of the algorithm?

IKDPQHEXMC

Put your answer here: _______

You are sorting the following string: using selection sort. What is the string after two passes of the algorithm?

MFQLJCWBRI

Put your answer here: _______

You are sorting the following string: using insertion sort. What is the string after four passes of the algorithm?

WRKSIJLMGC

Put your answer here: _______

You are sorting the following string: using merge sort. What is the string right before the final merge?

YMLCHKVANF

Put your answer here: _______

You are sorting the following string, using quicksort and the median-of-three pivot selection algorithm. What is the pivot?

ISHAVWGLQ

Put your answer here: _______

You are sorting the following string, using quicksort and the median-of-three pivot selection algorithm. What is the pivot?

HGITUNMPW

Put your answer here: _______

You are sorting the following string, using quicksort and the median-of-three pivot selection algorithm. What is the pivot?

NAETWRLQC

Put your answer here: _______

You are sorting the following string using quicksort. You will use a pivot of P. Your first step is to partition characters 1 through 9 of the vector, leaving the pivot in character 0. Show me the string when you're done with this step (include all 10 characters of the string).

PPSFPHPTQB

Put your answer here: _______

You are sorting the following string using quicksort. You will use a pivot of Q. Your first step is to partition characters 1 through 9 of the vector, leaving the pivot in character 0. Show me the string when you're done with this step (include all 10 characters of the string).

QXIUYMRPAW

Put your answer here: _______

Question 17

This came from a bank, and is worth 15 points.

The following defines the adjacency lists for an undirected graph. How many connected components are in the graph? __________

  A    { }
  B    { F, I }
  C    { I }
  D    { E }
  E    { D }
  F    { B, J }
  G    { L }
  H    { K }
  I    { B, C }
  J    { F }
  K    { H }
  L    { G }

The following defines the adjacency matrix for an undirected graph, where 'X' denotes an edge and '.' denotes no edge.

    A B C D E F G H I J
A | . X . . . . . . . .
B | X . X . . X . . . X
C | . X . X . . . . . .
D | . . X . X . . . X X
E | . . . X . . . . . .
F | . X . . . . . . . .
G | . . . . . . . . . X
H | . . . . . . . . X .
I | . . . X . . . X . .
J | . X . X . . X . . .

Let's suppose you perform a standard recursive DFS on this graph starting from node A. And suppose you print a node's id when you set its visited field to true. Please enter the id's of the nodes in the order in which they are printed, as a single string (like "ABCDEFGHIJ"). __________

The following defines the adjacency lists for an undirected graph.

  A    { B }
  B    { A, C, F, J }
  C    { B, D }
  D    { C, E, I, J }
  E    { D }
  F    { B }
  G    { J }
  H    { I }
  I    { D, H }
  J    { B, D, G }

Let's suppose you perform a standard breadth-first search on this graph starting from node A. When you're done, you will have two vectors -- path_lengths contains the shortest path lengths from node A to each node, and backedges contains the back edge for each node, as calculated in the breadth-first search.

Please enter the path_length for node J __________
Please enter the path_length for node I __________

Please enter the backedge for node J __________
Please enter the backedge for node D __________

Just specify an edge by the two nodes it connects -- for example, an edge from node A to node B should be specified as AB.

Question 18

This came from a bank and is worth 16 points.

We are working on a directed graph defined by the following adjacency matrix:

       A   B   C   D   E   F   G   H   I   J
     --- --- --- --- --- --- --- --- --- ---
A |   --  92  --  79  --  --  --  45  99  66
B |   37  --  17  93  --  64  --  --  --  --
C |   85  --  -- 100  --  --  --   5  82  33
D |   36  10  21  --  --  62  18  --  38  45
E |   --  61  81  45  --  75  72  --  --  54
F |   --  86  23  25  19  --  --  81  44  72
G |    6  60  62  --  13  24  --  --  88  48
H |   --  --   2  --  --  --  --  --  --  17
I |   --  --  --  --  --  89  --  85  --  --
J |   --  52  14  --  --  --  --  --  24  --

We are running Dijsktra's shortest path algorithm on this graph, starting from node A. When we do this, we process the multimap in the following order:

Node A    Distance 0
Node H    Distance 45
Node C    Distance 47
Node J    Distance 62
Node D    Distance 79
Node I    Distance 86
Node B    Distance 89
Node G    Distance 97
Node E    Distance 110
Node F    Distance 121

After we process node A, the distances vector is:


                 Distances
   A   B   C   D   E   F   G   H   I   J
   0  92   -  79   -   -   -  45  99  66

As we process the nodes after node A, there are four times when we set a distance from '-' to a number, and four times when we change a distance from one number to another. In the four boxes below, enter the nodes whose distances are set, in the order in which they are set. Enter the answer as "Node-distance" -- for example, if your answer is node A with a distance of 5, then answer "A-5".

[A1]
[A2]
[A3]
[A4]

In the four boxes below, enter the nodes whose distances are changed. You can specify these in any order. Enter the answer as "Node-newdistance" -- for example, if your answer is node A with a new distance of 5, then your answer should be "A-5".

[C1]
[C2]
[C3]
[C4]

Question 19

You are representing a directed graph where the number of nodes is n, and n is at most 32. Nodes are numbered from 0 to n-1. You are storing a the graph using an adjacency matrix, where each row of the matrix is a single integer, and we are using the bits of that integer to store edges. For example, suppose the graph is the following:

0 <---- 1 <----> 2 ----> 3

Then the adjacency matrix is a vector of four integers -- { 0x0, 0x5, 0xa, 0x0 }.

Implement a depth-first search that has the following prototype:

void dfs(int node, vector <int> &am, int &visited);

You'll call it with am being the adjacency matrix, and visited being zero. You'll set a node as being visited by setting the node's bit in visited. When you do that, print the id of the node. For example, the following procedure call:

dfs(1, { 0x0, 0x5, 0xa, 0x0 }, 0);

will print:

Remember to set the formatting below to "preformatted", and you can resize it to make it bigger.