Midterm 2 Review Guide


Trees, Binary Trees, Binary Search Trees

  • How is a Tree different from the linear data structures we have seen so far in this class?
  • What is a Binary Tree?
  • How do you determine if a Binary Tree is balanced?
  • How do you define a Binary Search Tree ADT?
  • How is a BST a recursive structure?
Given the tree below:

Image source.

  • Label the root, leaves, and interior nodes, and give one example of a child, parent, sibling, descendant, and ancestor relationship.
  • What are the height and depth of the nodes 12, 54, and 50?
  • Is the above tree a binary tree? Why or why not?
  • Is the above tree a BST? Why or why not?
  • What is the Big-O run-time of search, insert and delete operations on a BST in best, average and worst case?
  • Trace recursive tree traversals inOrder, preOrder, postOrder on the above BST.
  • Write the preOrderPrint, inOrderPrint and postOrderPrint helper methods.
  • Trace the remove operation on node 76. Then remove 12. Finally, remove 17. For each node you remove, draw your steps and the resulting tree after the element has been removed.
  • What are the three cases you need to take into consideration when implementing the BST remove operation?
    • How do you write the Java code to handle each of these three operations?
  • How do you write the remove wrapper method?
  • How do you write the copy constructor method as an adaptation of preOrderPrint provided in class?
  • Write insert and search for a BST.
    • How are these operations similar to the binary search algorithm?
  • Draw the BST that results from inserting the following values: 55, 90, 32, 16, 7, 101, 68, 42, 89, 112.
  • Write the helper and wrapper function for BST insert.


Hash Tables

  • What is a Hash Table?
  • What are the advantages of using a Hash Table over other ADTs we have studied?
    • Arrays
    • Linked Lists (and other linear structures)
    • Binary Search Trees
  • What is a hashing algorithm?
    • How do you write a good hashing algorithm?
  • True or False: A method that returns a random number between 0 and the size of the table -1 would be a good hash function.
  • Write the hash function defined in class.
  • True or False: When implementing a hash method in Java, this method is likely to return a String if the data being stored in the table is String data?
  • What is linear probing?
  • What is separate chaining?
  • How are linear probing and separate chaining different?
  • How do you search for an element in a Hash Table?
  • How do you insert a new element into a Hash Table?
  • How do you remove an element from a Hash Table?
  • How do you print a Hash Table (2 ways?)
  • What is the Big-O runtime of the hash table operations insert, search and remove in the best, worst and average case?
  • What is the load factor?
  • What is the rule of thumb for selecting a table size, and how does this rule of thumb, along with the concept of the load factor, contribute to creating an efficient Big-O runtime for the the hash table operations? Explain.



Graph Basics

  • Write the adjacency list representation of below graph in the format shown in class.
  • Is the below Graph cyclic or acyclic. If there is a cycle, list the cycle.
  • Is the below Graph directed or undirected?
  • Is the below graph a DAG?
  • Is the below graph connected of disconnected? If it is connected, is it weakly or strongly connected?





  • Write the adjacency list representation of below graph in the format shown in class.
  • Is the below Graph cyclic or acyclic. If there is a cycle, list the cycle.Is the below Graph directed or undirected?
  • Is the below graph a DAG?
  • Is the below graph connected of disconnected? If it is connected, is it weakly or strongly connected?




graph with two components