[Solved] CMSC204-Exam2-

1. Given a binary search tree class (BST) with the following denition: 1public class BST<T extends Comparable> {3Node<T> root; int count; 5 private class Node<T extends Comparable> { 7T value; Node left; 9Node right;11public Node(T value) { this.value = value; 13left = right = null; } 15}}Assume that there are standard implementations of: public BST(); // Default constructor creates an empty BST 2public boolean insert(T data); // Inserts a node containing data into BST, // returns TRUE on success 4public T delete(T data); // Removes a node containing data from BST, // returns data 6public boolean contains(T data); // Returns TRUE if data is in the BSTImplement the following methods: (a) [8 points] public int countLeaves(); returns the number of leaves in the BST (b) [8 points] void printSingleBranches(); outputs all nodes with exactly one (1) child, in ascending order (c) [8 points] void reverseOrder(); outputs all the nodes in the tree in descending order 2. Given the following hashing class that implements linear probing, with dummy values inserted for removed entries: 1public class LinearHash {3String []table; // Hash Table Entries int used; // Count of used entries 5int probeDist; // Probing distance (default: 1)Assume that there are standard implementations of: 1public HashTable(int size, int probDist); // Constructor for HashTable with size entries // and probing distance probDist 3public HashTable(int size); // Constructor for HashTable with size entries // and probing distance: 1 5Implement the following methods:public double load(); returns the current load factor for the table. (b) [7 points] public int insert(String value); adds value to the table, returns the index (c) [7 points] public int find (String value); returns the index of value in the table (d) [7 points] public String delete(String value); removes value from the table, and returns it. Note: delete() should place a dummy value of into the table to represent a removed entry. insert() and find() should also do the right thing with the dummy values. 3. [9 points] Implement the following static method that utilizes the Set Interface: 1public static Set intersection(Set a, Set b);This method should return a Set that contains only those Objects that appear in both Set a and Set b. The returned Set must only meet the Set Interface. Your implementation is free to use classes included in the base Java SDK, but not from other packages and libraries. 4. You have been asked to design and implement a (mini) spell checker application. Your application will need to process a le of correctly spelled words, and another le which is the document (text le for our case) that you want to perform spelling check. For this problem only you may utilize any data structures available from the Java Platform API (such as list, map, etc.) (a) [8 points] In a paragraph or two, discuss how you would solve this program. In particular, explain the data structure(s) that you are planning to use, and why its your best choice(s). (b) [18 points] Provide a Java implementation that will: 1. Read a le, called wordlist.txt of correctly spelled words; one word per line, all words will be lowercase. 2. Process the input.txt le; this is the le that you want to spell check. Assume the entire le will be lowercase, without any punctuation, but multiple words may appear on each line. 3. Identify and display all of the misspell words in input le; A word is misspelled if it does not exist in the wordlist.txt le. 4. In the event a le cannot be found (ie. FileNotFoundException), your code should print a meaningful error along with the name of the oending le. Your program should then exit cleanly (eg. no stack trace printed) 5. Given the following sequence of integers: 67, 89, 100, 83, 50, 55, 42, 95, 22, 66 (a) [5 points] Show the binary search tree built from this sequence of integers. (b) [3 points] Show the pre-order traversal (c) [3 points] Show the in-order traversal (d) [3 points] Show the post-order traversal (e) [6 points] Represent (show) the tree if stored as an array representation 6. Determine the algorithmic complexity of the following methods: (a) [3 points] public static void recurse1(long n) { 2if (n > 0) recurse1(n-1); 4}/86 points

(b) public static void recurse2(long n) { 2for (long i = 0; i < n; i++) { 4recurse2(n-1); } 6}(c) public static void recurse3(long n) { 2if (n > 0) { recurse3(n-1); 4recurse3(n-1); } 6}7. Given the following min-heap in array form:2 19 25 38 55 60 40 53 80 87 85(a) Add the value 23 to the heap, and then show the new min-heap in array representation. (b) [6 points] Remove the value 19 from the heap you created in question 7a, , and then show the new min-heap in array representation. 8. [12 points] Assume the BST class from question 1 contains a boolean equals(BST b) method which will return true if in-order traversals of the trees are the same. Create a int hashcode() method that generates hashcodes that conform to the Java hashcode contract. Feel free to create any support methods you need to complete the problem.