Data Structures and Algorithms

Test 3 Study Guide

The tests in this course may contain any material covered in lecture up until this point, although much stronger emphasis will be placed on material for which you have received graded feedback. This page contains a collection of exercises that you may wish to complete to prepare yourself.

Lists

You should be able to describe the List ADT, describe several implementations of lists, and give code for methods of the lists we defined in lab.

1. Name three list implementations.
2. For each implementation, give the worst-case time complexity of inserting at front, inserting at back, retrieving an element, and finding the position of an element.
3. Define “amortized” time. Explain why adding an element to the end of an array list is amortized constant time. What is the worst-case non-amortized time of adding an element to the end of an array list?
4. Give an implementation of insert_at_front for a circular array list.

Trees

1. Define the following terms:
   • Tree
   • Node
   • Leaf
   • Height
   • Binary tree
   • Binary search tree
   • AVL tree
2. Draw a diagram showing the “rotate left” operation on binary trees. When is it impossible to rotate a binary tree to the left?
3. Write pseudocode for the AVL rebalancing algorithm.
4. Consider the following tree:

• Write the heights of each node for the tree above.
• Consider the addition of the value 8 to the above tree. Which nodes’ heights change?
• What will the tree look like after the value 8 is inserted?
• What will the tree look like after the value 3 is inserted to the original tree?
• What will the tree look like after the value 15 is inserted to the original tree?
• What will the tree look like after the value 5 is deleted from the original tree?
• What will the tree look like after the value 9 is deleted from the original tree?
• What will the tree look like after the value 6 is deleted from the original tree?