Data structure with JAVA

Chapter : Symbol Table

Read Algorithms $3\mathrm{.}1,3\mathrm{.}5$ and $3\mathrm{.}2$

Recursion Supplement $($Optional$,$ but suggested$)$: Tracing Recursion. You do not need to hand in anything for this.

Do the following problems from the text. $($Hand in$.)$

$3\mathrm{.}1\mathrm{.}10$

Give a trace of the process of inserting the keys

E A S Y Q U E S T I O N

into an initially empty table using SequentialSearchST. How many

compares $($of keys$)$ are involved?

$3\mathrm{.}1\mathrm{.}11$

Give a trace of the process of inserting the keys

E A S Y Q U E S T I O N

into an initially empty table using BinarySearchST. How many

compares $($of keys$)$ are involved?

$3\mathrm{.}2\mathrm{.}1$

Draw the BST that results when you insert the keys

E A S Y Q U E S T I O N

in that order $($associating the value i with the ith key, as per

the convention in the text$)$ into an initially empty tree. How many

compares are needed to build the tree?

$3\mathrm{.}2\mathrm{.}2$

Inserting the keys in the order A X C S E R H into an

initially empty BST gives a worst$-$case tree where every node has one

null link, except one at the bottom, which has two null links. Give

five other orderings of these keys that produce worst$-$case trees.

You can also describe the constraints that produce this outcome

$---$ Things like "insert A first, insert B before C$,$ etc."

$3\mathrm{.}2\mathrm{.}3$

Give five orderings of the keys A X C S E R H that, when

inserted into an initially empty BST$,$ produce the best$-$case tree.

You can also describe the constraints that produce this outcome

$---$ Things like "insert A first, insert B before C$,$ etc."

$3\mathrm{.}2\mathrm{.}4$

Suppose that a certain BST has keys that are integers between

$1$ and $10,$ and we search for $5.$ Which sequence below cannot be the

sequence of keys examined?

a$.10,9,8,7,6,5$

b$.4,10,8,6,5$

c$.1,10,2,9,3,8,4,7,6,5$

d$.2,7,3,8,4,5$

e$.1,2,10,4,8,5$