## CSE 131 Module 9: ADT Representations

### Practice Problems

**Directions:**
There will be two parts to the quiz, and you can do either one:
- You will be asked to implement a method related to the work you
did in Module 9.
- 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... |

101 | 2 | 5 | 10 |

1110 | 2 | | 10 |

290 | 10 | | 2 |

255 | 10 | | 2 |

255 | 10 | | 4 |

210 | 3 | | 8 |

63 | 7 | | 2 |

10000000 | 2 | | 10 |

128 | 10 | 242 | |

Study problems related to Lab 9.

- Consider implementing
`OrderedListMap` using a doubly linked
list with sentinals (dummy nodes) `head` and `tail`.
- 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?
- 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.

- What are the advantages of implementing
`OrderedListMap` with
a `CircularList`?
- Consider a binary search tree for
`String`s. 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"

#### Solution not yet available.