Sample 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, 25, 28, 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 and the remove method for a 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.