- (2 pts) Is in ?
- (4 pts) Prove that
is in .
Specify values for , , and .
- (6 pts) Determine the complexity of the following algorithm and
express your answer in terms of big-O. Explain/show your work. You
may assume that the variable
`a`is an array containing at least`n`integer values.i=0; while (i<n && a[i]!=0) { for (j=0; j<5; j++) num= num+a[i]*j; i++; }

- (2 pts each) State (using ) the complexity of each of the
following operations:
- insert in an unordered, linked list-based list
- minimum in an ordered linked list-based list
- search in an ordered, array-based list
- delete in an ordered array-based list
- binary search tree delete
- binary search tree search

- (10 pts) Consider these growth functions: , , ,
, , , .
- Write them in order from slowest growing to fastest growing.
- Give the name for each type of growth function represented.

- (4 pts) Using words give a recursive explanation of how a binary search
works. NOTE: For it to be a recursive explanation you need to express your
answer in terms of itself and you need to identify a base condition.
- (4 pts) Explain the relationship between the number of nodes in a
binary search tree and the tree's height.
- Suppose a binary search tree will be used to store the following key
values: 10, 12, 20, 27, 32, 38, 45.
- (3 pts) Order the elements above so that if inserted into the tree using
a traditional binary search tree insert action it would produce
a worst-case unbalanced tree.
- (3 pts) Order the elements above so that if inserted into the tree using a traditional binary search tree insert action it would produce a complete tree.

- (3 pts) Order the elements above so that if inserted into the tree using
a traditional binary search tree insert action it would produce
a worst-case unbalanced tree.
- (8 pts) Suppose a binary search tree is implemented using the following
class:
class TreeNode { String word; int count; TreeNode left, right; };

Suppose a`MyTree`class has been built and is an implementation of a binary search tree that it has been used to track the number of times words in a document have been used. Assume the words are used as the ordering key. Write a method to be added to the`MyTree`class called`showLoners`that accepts no parameters and will alphabetically display all the words that appear only once. You may write additional helper methods as needed. - (6 pts) Briefly outline the steps (3 cases) to delete an element from
a binary search tree.
- (2 pts each) Use the diagram of the binary tree below to answer the
following questions:
- Is this tree a binary search tree?
- Show order of visits using a preorder traversal.
- Show order of visits using an inorder traversal.
- Show order of visits using a postorder traversal.