Due in 24 hours theoretical assignment for Data Structures and algorithms, 

 

1.(1 pt) Draw a binary tree T that simultaneously satisfies the following:Each internal node of T stores a single character.A preorder traversal of T yields A B C D E F G H IAn inorder traversal of T yields C B E D A H G F I2.In this question you will sort an array using in-place heapsort (parts a) and b)) and practice insertions on a heap in part c).a)(4 pt) Build a max-heap using the bottom-up heap construction, in place, in the following array. Show the array after each call to procedure “down-heap”:Index i012345678A[i]53171084196229b)(4 pt) After the max-heap is constructed, do the second stage of heapsort, showing the array after each of the 8 remove-max operations, specifying which part of the array is the heap and which part is the sorted sequence.c)(4 pt) Go back to the original array given in part a). Build a max-heap by successively inserting A[0],A[1],…, A[8] in this order into an initially empty heap stored in an array B. Show B after each of the 9 insertion.3.(2 pt) Insert the following keys into an initially empty binary search tree in the given order and show the final tree:  32, 29, 88, 44, 54, 76, 824.Given the following binary search tree:1

Attachments:

• 1494488745-A3.docx