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, cousin, 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 code or pseudocode for preOrderPrint, inOrderPrint and postOrderPrint.
  • What are the three cases you need to take into consideration when implementing the BST remove operation?
  • 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.
    • How is this code similar to the Binary Search Algorithm?


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 function 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 function in C++, this function 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?
  • 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.


Heaps

  • What is the Max Heap Property? How does it differ from the BST property?
  • What is the Big-O runtime of each of the heap algorithms we discussed in class?
  • Trace each step of the buildMaxHeap operation (diagram and array) on the following:

Diagram                    Array

                       

                        A = [4, 9, 7, 18, 2, 3]

1.






2.                        A = [ ___ , ___, ___, ___, ___, ___ ]   







           

3.                        A = [ ___ , ___, ___, ___, ___, ___ ]   







4.                        A = [ ___ , ___, ___, ___, ___, ___ ]   







  • Trace heapInsert on the below Max Heap and the value 35. Show diagram and array at each step below:


Diagram                    Array

                       

1.                        A = [21, 11, 13, 2, 9]







2.                        A = [ ___ , ___, ___, ___, ___, ___ ]   






           

3.                        A = [ ___ , ___, ___, ___, ___, ___  ]   







4.                        A = [ ___ , ___, ___, ___, ___, ___  ]   




  • Trace heapSort on the following heap. Show diagram and array at each step below:

Diagram                    Array

                       

1.                        A = [100, 90, 80, 70]







2.                        A = [ ___ , ___, ___, ___ ]   






           

3.                        A = [ ___ , ___, ___, ___ ]   







4.                        A = [ ___ , ___, ___, ___ ]   







5.                        A = [ ___ , ___, ___, ___ ]