CSCI 2320 Data StructureQuiz 3 Oct/20/2008Name:__________________Question 1(a.) Construct the AVL tree by giving the following sequence of integers: 20,40,10,18,5(b.) Draw the AVL tree in (a.) after insert the element 55 and 2 (c.) Draw the AVL tree in (b.) after insert the element 1 (It is better you draw both the tree before and after the rotation) (d.) Draw the AVL tree in (c.) after delete the element 20 (Substitute with the smallest number in right side of child) (e.) Draw the AVL tree in (d.) after insert the element 20Question 2.1Hash function: h(k)=k mod 8Use Linear Probing: h(k, i ) = (h(k) + i ) mod m. where m=8Finish the table:Action 0 1 2 3 4 5 6 7 # probeStore 8 8 1Store 20 8 20 1Store 16 8 16 20 2Store 17 8 16 17 20 2Store 80 8 16 17 80 20 4Delete 8 +- 16 17 80 20 1Store 79 +- 16 17 80 20 79 1Store 31 31 16 17 80 20 79 2Delete 80 31 16 17 +- 20 79 4Question 2.2Hash function: h(k)=k mod 8Use Quadratic Probing: h(k, i ) = (h(k) + c1i + c2i2) mod m where c1=0 c2=1 m=8Finish the table:Action 0 1 2 3 4 5 6 7 # probeStore 8 8 1Store 79 8 79 1Store 16 8 16 79 2Store 17 8 16 17 79 2Store 80 8 16 17 80 79 3Delete 8 +- 16 17 80 79 1Store 63 63 16 17 80 79 2Store 31 63 16 17 31 80 79 3Delete 80 63 16 17 31 +- 79
View Full Document
Unlocking...