Midterm 2 Review Guide
Note: Solutions Attached Below as a PDF for Graph Questions
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 BigO runtime 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 BigO 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 BigO runtime for the the hash table operations? Explain.
Graphs
Write the adjacency list representation of below graph in the format shown in class.
image source
Trace DFS on the above graph
Vertex  Adj []
 Color[]
 Discovery_Time[]
 Finish_Time[]
 Parent[]
 1       2       3       4       5       6      
Then, draw the DFS Forest
Now, trace BFS on the above Graph.
Vertex  Adj []
 Color[]
 Distance[]
 Parent[]
 1      2      3      4      5      6     
Queue:
Also Draw the BFS Tree. How do the tracings for BFS and DFS differ?
Write the adjacency list representation of below graph in the format shown in class.
Image source
Trace DFS on the above graph
Vertex  Adj []
 Color[]
 Discovery_Time[]
 Finish_Time[]
 Parent[]
 0       1       2       3       4       5       6       7       8       9       10      
Then, draw the DFS Forest
Next, trace BFS on the above graph.
Vertex  Adj []
 Color[]
 Distance[]
 Parent[]
 0
     1      2      3      4      5      6      7      8      9      10     
Queue:
Also Draw the BFS Tree. How do the tracings for BFS and DFS differ?
What is the BigO runtime of DFS and BFS?
BFS: O ( )
DFS: O ( ) 
Updating...
Ċ Jennifer Parrish, Mar 7, 2018, 12:33 PM
