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.
Name three list implementations.
For each implementation, give the worst-case time complexity of inserting at front, inserting at back, and retrieving an element.
How does a CircularArrayList avoid moving each element in its array when insertAtFront is called?
(Singly-)LinkedList, ArrayList, CircularArrayList. You may also distinguish between a singly-linked list and a doubly-linked list.
insertAtFront
insertAtBack
get
LinkedList
\(O(1)\)
\(O(n)\)
\(O(n)\)
ArrayList
\(O(n)\)
\(O(1)\) amortized
\(O(1)\)
CircularArrayList
\(O(1)\) amortized
\(O(1)\) amortized
\(O(1)\)
A CircularArrayList maintains a field (e.g. startIndex) which tracks the position of list index 0 inside of the array. When a new element is added to the front of the list, that start index is decreased (and, if necessary, changed to point to the last element of the array) and the new element is added there. When get is called, it uses this start index to determine where the requested list element is in the array.
Trees
Define the following terms with respect to tree data structures:
Leaf
Height
Binary tree
Binary search tree
AVL tree
Max heap
Draw a diagram showing the “rotate left” operation on binary trees. When is it impossible to rotate a binary tree to the left?
Write pseudocode for the AVL rebalancing algorithm.
Is the following statement true or false? If true, give a justification. If false, give a counterexample. “All BSTs are heaps.”
Consider the following tree:
Write the heights of each node for the tree above.
Consider the addition of the value 1 to the above tree. Which nodes’ heights change?
What will the tree look like after the value 1 is inserted?
What will the tree look like after the value 15 is inserted into 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?
A leaf is a node in a tree that has no children.
The height of a tree is the number of levels below the root; or the number of edges in the longest path from the root to a leaf; or one less than the number of levels in the tree.
A binary tree is a tree for which each node has at most one left child and at most one right child.
A binary search tree is a binary tree in which, for each node, all data in the left subtree are less than the node’s datum and all data in the right subtree are greater than the node’s datum.
An AVL tree is a binary search tree in which, for every node, the height of the left subtree and the height of the right subtree differ by no more than one.
A max heap is a complete binary tree in which every node’s datum is greater than or equal to the data in its children.
It is only possible to perform left rotation if the root has a right child; a binary tree with no right child of the root cannot be left-rotated.
The statement that “all BSTs are heaps” is false. The following BST shows this:
This binary tree is a BST because 3 < 4 (left subtree data are smaller) and 5 > 4 (right subtree data are larger). But it is not a max heap because 4 < 5 and, in a max heap, all parents must have a datum greater than or equal to the data of their children.
Showing the heights above each node:
Showing the insertion of 1 into the tree and the changed heights as bold.
Inserting 15 into the original tree. Note that a rebalancing is necessary because 17 was out of balance after the 15 was added.
Removing 5 from the original tree. No rebalancing is necessary.
