[SOLVED] CSE 101 Introduction to Data Structures and Algorithms Midterm 1 Review Problems

CSE 101

Midterm 1 Review Problems

1.   Using only the List ADT operations defined in the project description for pa1, write a client function with the heading

bool isPalindrome(List L)

Your function will return true if the integer sequence represented by L isa palindrome (i.e. is identical to its own reversal), and will return false ifL is not a palindrome.

2.   Using only the List ADT operations defined in the project description for pa1, write a client function with the heading

void Replace(List L, int x, int y)

Your function will replace all occurrences of x in L with y.  If x is not in L, your function will make no changes to the integer sequence in L.

3.   Run the BFS algorithm on the digraph pictured below, with vertex 4 as the source.  Fill in the table giving the adjacency list representation, colors, distances from the source, and parents in the BFS tree. List the discovered vertices in the order that they enter the queue.  Draw the resulting BFS tree.

4.   Given a connected (undirected) graph G , the diameter of G is the maximum possible distance between any two vertices x andyin G , i.e.

diameter(G) = max{ δ(x, y) | x, y ∈ V(G) }

Using only the Graph ADT functions defined in the project description for pa2, write a client function with the heading

int diameter(Graph G)

Your function will compute and return the diameter of its input graph G.

5.   Run the DFS algorithm on the digraph pictured below.  Process vertices in the main loop of DFS() by increasing vertex label. Process vertices in the for loop of Visit() by increasing vertex label. As vertices finish, push them onto a stack.  Fill in the table below giving the adjacency list representation, discover times, finish times and parents in the DFS forest.  Draw the resulting DFS forest, and show the state of the stack when DFS is complete.  Classify all edges as of type tree, back forward or cross.  Determine whether the graph is acyclic.  If it is acyclic, determine a topological sort of the vertices, and determine the number of distinct topological sorts.  If it is not acyclic, list all directed cycles.