Data Structure!!!!!!!!!!!

12 points 1. Tree traversals. a. (4pts) Give the sequence of letters from an inorder traversal of this binary tree: q / \ e r / \ / \ c d n s \ / / \ a g t w Give the sequence of letters from these traversals of the tree below: b. (4 pts) a preorder traversal c. (4 pts) a postorder traversal q / | \ e f r / | /|\ | \ d n g h j s t 4 points 2. Use the stack-based algorithm for converting a postfix expression into an expression tree for the postfix expression: abc*+ghk+m*/* Illustrate each step. 4 points 3. Use your expression tree to find the expression in prefix notation. 10 points 4. Draw an AVL tree for the following values inserted in this order. Illustrate the tree for each rotation that occurs: 83 12 62 55 32 68 74 10 points 5. Draw an AVL tree for the following values inserted in this order. Illustrate the tree for each rotation that occurs: 50 26 65 13 16 28 11 20 52 35 30 10 points 6. For the splay tree shown below, show how an access of node 55 is performed. Illustrate the tree for each operation that occurs: 10 \ 20 / \ 15 30 / \ 25 40 / \ 35 50 \ 60 / 55 10 points 7. For the splay tree shown below, show how an access of node 40 is performed. Illustrate the tree for each operation that occurs: 90 / \ 30 95 / \ 20 70 / /\ 10 60 80 / 45 / \ 40 50 10 points 8. For the B+-tree where M=3 and L=5 shown below, show how an insert of value 80 is handled. Resolve overflows by splitting. || 12 || 50 || / | \ / | \ 2 12 50 5 18 65 7 20 70 9 21 72 10 24 78 10 points 9. For the B+-tree where M=3 and L=5 shown below, show how an insert of value 77 is handled. Use the method of splitting the node rather than redistributing between siblings. || 24 || 75 || / | \ / | \ / | \ || 10 || 16 || || 41 || 50 || || 84 || 90 || | / \ / | \ | \ \ / | | | | \ | | | 2 10 16 24 41 50 75 84 90 5 11 18 26 42 65 78 86 92 7 14 20 30 45 70 79 87 93 9 47 72 80 81 10 points 10. A B+-tree is to be stored on disk whose block size is 2048 bytes. The data records to be stored are 64 bytes, and their key is 24 bytes. Determine the values for M and L for the B+-tree. Assume pointers are 4 bytes each. 10 points 11. For the problem above, in the worst case, how many levels are needed to store 16,000,000 records?