## CSE 131 Module 9: ADT Representations

### Practice Problems

Directions: There will be two parts to the quiz, and you can do either one:
1. You will be asked to implement a method related to the work you did in Module 9.
2. You will be asked to carry out base conversions, similar to the ones below. Complete the table, doing all the calculations by hand. (Calculators will not be allowed for the quiz.) Be sure to double-check your calculations before you look at the solutions. The first one has been done for you. The last one is a little tricky.

The number...in base...equals the number...in base...
1012510
11102 10
29010 2
25510 2
255 10 4
2103 8
637 2
100000002 10
12810242

#### Solutions

Study problems related to Lab 9.

1. Consider implementing OrderedListMap using a doubly linked list with sentinals (dummy nodes) head and tail.
1. What property do you want head and tail to have with respect to a key of type K, so that there are no special cases for insertion or deletion?
2. Write a helper method that performs comparsion for a node (head, tail, or otherwise) and a key of type K. The method should model compareTo, but take in the aforementioned objects and take into account the relation between head, tail and any possible key value.
2. What are the advantages of implementing OrderedListMap with a CircularList?
3. Consider a binary search tree for Strings. Given the following String>s, what order of insertion of those strings creates
• a completely unbalanced tree?
• a balanced tree?
The strings are:
```"balloon"
"ellipse"
"eyeball"
"line"
"point"
"polynomial"
"robot"
"vector"
```