CS W3139-02 Final Review Questions - Set 1
The following problems are final review questions from the second half of the
course. They are by no means an exhaustive list.
- Given a directed graph represented by the adjacency list
(assume a linked list representation) in figure 1:
Figure 1 |
| Adjacency List
|
| Node
| Pointers
|
| 1
| 2
| 3
| 5
| null
|
| 2
| 3
| 4
| null
|
|
| 3
| 2
| 4
| null
|
|
| 4
| null
|
|
|
|
| 5
| 2
| 3
| 4
| null
|
- Draw the graph.
- List the nodes in the order they would be visited using depth first
search with the adjacency list.
- List the nodes in the order they would be visited using breadth first
search with the adjacency list.
- Describe in English the steps involved in a topological sort of a directed
graph.
- Prove by induction that the number of arcs in a complete graph
of N nodes is ( N(N-1) ) / 2.
- Given N integers to sort, can you describe (in English) a method
that
would allow you to sort them and output the sorted list using a binary search
tree and standard binary tree operations? What is the Big Oh complexity of your
method?
- A multi-graph is a graph in which multiple edges are allowed between pairs of vertices (nodes). Define a Java data strcture that can be used to store an arbitrary multigraph.
- Is the array below max-heap ordered?
| Index
| 1
| 2
| 3
| 4
| 5
| 6
| 7
| 8
|
| Value
| 35
| 24
| 31
| 15
| 22
| 12
| 3
| 13
|
- Given an array A containing items 1 to N, write a boolean
function in
Java that returns
true or false depending upon
whether the array is heap ordered or not (assume min heap ordering).
- Solve the recurrence equation T(N) = N +2T( N/2 ) if T(1) = 1.
Name the algorithm we studied that fits this model.
- Analyze the running time of Selection Sort and show that it
is O(N^2).
[CS3139 Home]