Data Structure Sample Questions

Algorithms

Graphs

1. Given a binary tree with pointers to objects stored in each node. Write an algorithm that prints out the objects in preorder, postorder, and inorder.
2. A topological sort of a directed graph generates an order v₁, v₂, v₃, v₄, ... of all vertices of a directed graph such that any edge goes from a lower-ordered vertex to a higher ordered one (i.e. v_i → v_j implies that i < j,) or declares that such a topological sort is impossible:
   1. Show that a topological sort is possible if and only if the the graph contains no cycles. (The ⇒ direction is simple, the other one is easiest done by induction on the number of vertices.!
   2. Assume that the graph is given in an adjacency list format. Give an algorithm that is linear in the number of edges and vertices.
   3. Prove that an algorithm for topological sort that runs on an adjacency matrix representation needs to look at least at half of the entries and has therefore runtime Θ (n²), where n is the number of vertices.
3. The reflexive, transitive closure of an acyclic digraph is a digraph obtained by (1) adding an edge to itself for all vertices, (2) adding an edge between u and v whenever there is a path between u and v.
   1. Given a digraph in adjacency list representation, give an effective algorith to compute the reflexive, transitive closure of the digraph (again in adjacency list representation) and determine its runtime in terms of number of edges and vertices.
   2. Given a digraph in adjacency matrix representation, find the reflexive, transitive closure in terms of matrix multiplication. Find the runtime of that algorithm.

Sorting

1. Write an algorithm that reverses the order of items in a single linked list.
2. Using divide and conquer, design an algorithm that determines the first and the second largest element in an array of 2**n elements. Give a recursion formula for the algorithm.
3. You are given the following pseudo-code:
   void sort(int * array, int length) {
   for(int j = lenght-2; j >= 0; j --) {
      for(int i = 0; i < j; i ++) {
         if(array[i+1] < array[i]) swap(i,i+1)
      }
   }
}
The input to sort are an array of length length and the length of the array. swap is a function that swaps two elements in the array.
   Determine the worst-case and the expected running times of the algorithm.
4. You are given the following algorithm in pseudo-code that sorts an array in place by repeatedly finding the maximum of the remaining unsorted elements.
   
   sort(int * array, int array_length)
{
for( int i = 0; i < array_length -2; i++) {
   int indexMax = i;
   for(int j=i+1; j < array_length - 1; j++)
   {
      if(array[indexMax] < array[j])
      {
         indexMax = j;
      }
   }
   swap(array, i, max);
}

Give the number of comparisons of array elements. Prove your result by induction on n, the number of elements in the array. (Here, assume that the swap function swaps the two array elements given by the next two parameters.)

Data Structures

1. An AVL tree is a binary tree such that the height of the left subtree and the right subtree at any node differ by at most one. (If there is no left / right subtree, then its height is deemed to be -1.) Show that an AVL tree of height h has at most 2**(h+1)-1 vertices and give a recursion for the minimum number of vertices in an AVL tree.

NP Completeness

1. Show that the problem of finding a Hamiltonian path in a graph is NP.
2. Conclude the following proof that the Hamiltonian circuit problem for directed graphs is polynomial transformable to the Hamiltonian circuit problem for directed graphs.
   Let G = (V,E) be a directed graph. We define an undirected graph H = (U,F). Let U be V x {0,1,2}. That is, U is the set of vertices of G together with an index 0, 1, or 2. We write [v,i] for a vertex in U, where v is in V and index i is 0, 1, or 2. The set F of edges consists exactly of the edges
        ([v,0],[v,1]) for all vertices v in V
        ([v,1],[v,2]) for all vertices v in V
        ([v,2],[w,0]) if and only if (v,w) is in E, that is, is an edge in G.