Feaculty of Computer Science and Engineering Department of Computer Scienc Tutorial 4 Questions

Tham khảo tài liệu feaculty of computer science and engineering department of computer scienc tutorial 4 questions, công nghệ thông tin, kỹ thuật lập trình phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả
Nội dung trích xuất từ tài liệu:
Feaculty of Computer Science and Engineering Department of Computer Scienc Tutorial 4 Questions Faculty of Computer Science and Engineering Department of Computer Science DATA STRUCTURES & ALGORITHMS Tutorial 4 Questions AVL Tree and HeapPart 1. AVL TreeRequired QuestionsQuestion 1.For each of the following key sequences determining the AVL tree obtained when the keys are insertedone-by-one in the order given into an initially empty tree: a) 1, 2, 3, 4, 5, 6, 7. b) 4, 2, 1, 3, 6, 5, 7. c) 1, 6, 7, 2, 4, 3, 5. 45, 9, 2, 17, 84, 92, 71, 18, 30, 62, 55, 20, 27 d)Question 2.For each of the AVL trees obtained in Question 1 determine the tree obtained when the root is withdrawn.Question 3.Write a global function in pseudo code to generate an AVL tree from an input list by insert elements in thelist into an initial empty AVL. Refer to Question 1 for an example.algorithm generateAVLfromList (val list ) This algorithm generate a AVL from the input list Pre Post the AVL is built by inserting elements in the list into an initial empty tree one-by-one from the beginning of the list. Return the AVLend generateAVLfromListQuestion 4.Devise an algorithm to test whether a given binary search tree is AVL balanced.algorithm testAVL (val tree ) Pre Post. Return true if tree is an AVL, otherwise return falseend testAVLAdvanced QuestionsQuestion 5.Devise an algorithm to merge the contents of two binary search trees into one. What is the running time ofyour algorithm? 1/ 3 Faculty of Computer Science and Engineering Department of Computer ScienceQuestion 6.Suggest a data structure that supports the following operation and given time complexities: Operation Complexity Init Init the DS with n real numbers (unordered) O(nlogn) Insert(x) Insert x to the DS O(logn) findMin Return the value of the minimal element O(logn) findMax Return the value of the maximal element O(logn) findMed Return the value of the median element O(1) DelMin Remove the minimal element O(logn) DelMax Remove the maximal element O(logn) DelMed Remove the median element O(logn)Part 2. HeapRequired QuestionsQuestion 7.Show the heap (tree) you will have after inserting the following values: a) 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 b) 8, 4, 3, 6, 11, 9, 10, 10, 9 c) 3, 1, 4, 1, 5, 9, 2, 6, 5, 4 d) 2, 7, 1, 8, 2, 8, 1, 8, 2 e) 45, 9, 2, 17, 84, 92, 71, 18, 30, 62, 55, 20, 27Question 8.Show the heap (tree) you will have after removing (from 1-3 times) the root element of the tree generatedin the all cases of the previous question.Advanced QuestionsQuestion 9.The following class definition will be used for the problem that follow:public class BinaryTree { private class Node { E data; Node left, right; } Node root;} 2/ 3 Faculty of Computer Science and Engineering Department of Computer ScienceWrite a recursive method called isCompleteBinaryTree() that returns true if the binary tree represents acomplete binary tree (one that satisfies the shape property for heaps).Notice that the tree might not be a complete tree. 3/ 3