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:

• 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.

Graphs

Write the adjacency list representation of below graph in the format shown in class.

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.

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 Big-O runtime of DFS and BFS?

BFS: O (                    )

DFS: O (                    )

Ċ
Jennifer Parrish,
Mar 7, 2018, 12:33 PM