Friday, April 13, 2018

Data Structures Exam Questions: Trees, Heaps, and Graphs


  1. If you want to access each node in a binary tree in sorted order, how would you go about doing this?  Describe the procedure.
  2. Draw the resulting binary tree if the following values are added (as ordered below).   Is this tree complete? 56, 43, 60, 67, 80, 31, 12, 54, 65, 57, 50, 59
    1. What nodes could you add to make this tree complete?
  3. How many nodes are in a full tree if the tree’s height is 11?  How many nodes are leaf nodes?
  4. What is the computational complexity of retrieving a value from a full tree?
  5. Describe the worst case for retrieval from a binary tree that is NOT full.
  6. Identify each the steps involved in removing the value “88” from the tree below.
  7. Write the code for the method public void add(Comparable value) in a Tree object.  State any assumptions made.
  8. Assume you are building a map with a tree as its backing structure.  Implement the get(Comparable key) method below.  State any assumptions made (beyond the get and set methods available within the TreeNode object).
  9. If the root is removed from this heap, what does the resulting heap look like?  Be sure to show each of the steps in removing the root.
  10. Perform a heap sort on the heap above (prior to removing the root).  Show the array after each swap.
  11. Explain the difference between weighted and unweighted graphs.  Give an example of each.
  12. Draw the undirected graph represented by the following list of edges: AB, AC, CD, DE, EA
    1. Assuming that neighbors would be visited in alphabetical order, how would you determine the shortest path from B to D?  Describe the operations step-by-step, including the structures you would use.
  13. When you are simply printing the values in a binary tree, you can apply a simple recursive algorithm. The same procedure can’t be performed when building an iterator to return every node one-by-one.  Why not? How would an iterator that returns the nodes one-by-one work?
  14. Explain why a heap is usually a better approach than a sorted list for implementing a priority queue.
  15. If you are removing a value from a tree and the node has two children, how can you remove this node?  Explain the steps necessary.
  16. What nodes, and in what order, could you add to a binary tree that holds the following nodes (in order) to make it complete? 31, 24, 39, 36, 50, 6, 32
  17. Why is it easy to represent a heap in an array, but much more of a challenge to represent a binary tree in an array?
  18. Write code to traverse a Binary Tree and output nodes in order.
  19. What is one benefit of using a Set created from a Binary Tree instead of a Hash Table?  What are two drawbacks?
  20. In a heap, given a value’s index, where can its parent be found?
  21. In a heap, given a value’s index, where can its children be found?
  22. For the following undirected Graph, if you travel the nodes in order of lowest cost to highest cost, what is the depth first search path from A to G? Explain your steps.
  23. For the following undirected, unweighted Graph, if you visit neighbors in alphabetical order using a breadth first search, in what order do you visit each node if you travel from A to G?  Show your queue. What is the shortest path?
  24. If a directed Graph has 12 nodes and 77 edges, how would you represent it?   Why?
  25. What is one key question we should consider when we are deciding how to model a Graph?
  26. Explain the difference between a directed Graph and an undirected Graph, and give an example of each.
  27. Assuming a TreeNode with the following methods, implement a put() method for the TreeMap. [constructor] TreeNode(String key, User value) boolean hasLeft() boolean hasRight() String getKey() TreeNode getLeft() TreeNode getRight() void setLeft(TreeNode node) void setRight(TreeNode node) void set(String key, User value)
  28. implement the add method for a MinHeap.
    1. Implement a remove method for the MinHeap.
  29. Assuming that you have a well implemented Queue and Map, explain the steps involved in finding the shortest path from A to F in the undirected, unweighted graph below.

Thursday, April 12, 2018

Data Structures: Removing from a Heap and Heapsort

Think about this MaxHeap:

0
1
2
3
4
5
6
23
12
19
7
10
18
14

Children in a heap are found with this formula:
Left child: 2i + 1
Right child: 2i + 2

Parents are found with this formula:
Parent: (i - 1) / 2

If we have a maxheap, the children are smaller than the parents.  If we have a minheap, the children are larger than the parents. This is a maxheap, so all parents are larger than their children.

To add to a maxheap, we put the new value at the next available position in the array then swap up.  In the file for your assignment, we call this process reheapUp.

If we add the value 20 to the maxheap above, we get this:
0
1
2
3
4
5
6
7
23
12
19
7
10
18
14
20

We swap 20 (index 7) with its parent, if the parent is smaller.  The parent value is 7 (index 3) so we swap up.
0
1
2
3
4
5
6
7
23
12
19
20
10
18
14
7

We swap 20 (index 3) with its parent, if the parent is smaller.  The parent value is 12 (index 1) so we swap up.
0
1
2
3
4
5
6
7
23
20
19
12
10
18
14
7

We swap 20 (index 1) with its parent, if the parent is smaller.  Here it’s not so we’re done.

To remove from the maxheap, we could just remove the top element and swap elements upward.  However, this would leave a gap. This is no good because heaps should be complete. In the heap at the top of the page, we’d take off 23 (index 0), put 19 into the empty spot (into index 0 from index 2), then put 18 into the empty spot (into index 2 from index 5).  What do we put into index 5? We can’t just move an adjacent value into that spot because it might not result in a valid maxheap.

We’ll prevent this problem by swapping the first & last elements in our maxheap.

To remove 23, we swap index 0 and 7.  We also decrement “nextPosition” so that while 23 is still in our array, it isn’t part of our maxheap.
0
1
2
3
4
5
6
7
7
20
19
12
10
18
14
23

This is not a valid heap (because 7 is smaller than both of its children: 20 and 19), so as long as it’s not valid, we swap the element with the larger of its two children.  Here we swap 7 and 20:
0
1
2
3
4
5
6
7
20
7
19
12
10
18
14
23

It’s still not valid (7 < 12 and 7 < 10) so we swap 7 and 12:
0
1
2
3
4
5
6
7
20
12
19
7
10
18
14
23

Now 7 is at index 3; it doesn’t have any children.  This process of moving an invalid top value from the top to closer to the bottom is handled in the code in the reheapDown method.

Notice now that 23 - the largest thing that was in our maxheap - is now in the last index.  If we were to remove 20, we’d swap 20 (index 0) with 14 (index 6), then swap 14 (index 0) with 19 (index 2), then swap 14 (index 2) with 18 (index 5).  Our new maxheap would look like this:
0
1
2
3
4
5
6
7
19
12
18
7
10
14
20
23

Notice now that the end of our array seems to be sorted.

This is the way the heapsort algorithm works - it’s basically just removing a bunch of things from our maxheap.

So, to complete a heapsort, first we create a maxheap from our array:

MaxHeap heap = new MaxHeap(array);

Then, all we have to do is remove everything from it.  The remove() method takes care of all of the sorting and your original array should now be sorted.