Questions and Answers of Big Java, Enhanced Early Objects

A deque (double-ended queue) is a data structure with operations addFirst, remove- First, addLast, removeLast, and size. Implement a deque as a circular array, so that these operations have amortized
Implement a hash table with open addressing. When removing an element that is followed by other elements with the same hash code, replace it with the last such element and rehash the remaining
Modify Exercise ••• P16.14 to use quadratic probing. The ith index in the probing sequence is computed as (h + i2) % L.Data from exercise 16.14Implement a hash table with open addressing. When
Modify Exercise ••• P16.14 to use double hashing. The ith index in the probing sequence is computed as (h + i h2(k)) % L, where k is the original hash key before compression and h2 is a
Modify Exercise ••• P16.14 so that you mark removed elements with an “inactive”element. You can’t use null—that is already used for empty elements. Instead, declare a static
What are all possible shapes of trees of height h with one leaf? Of height 2 with k leaves?
Describe a recursive algorithm for finding the maximum number of siblings in a tree.
Describe a recursive algorithm for finding the total path length of a tree. The total path length is the sum of the lengths of all paths from the root to the leaves. (The length of a path is the
Show that a binary tree with l leaves has at least l – 1 interior nodes, and exactly l – 1 interior nodes if all of them have two children.
What is the difference between a binary tree and a binary search tree? Give examples of each.
What is the difference between a balanced tree and an unbalanced tree? Give examples of each.
The following elements are inserted into a binary search tree. Make a drawing that shows the resulting tree after each insertion.Adam Eve Romeo Juliet Tom Diana Harry
Insert the elements of Exercise • R17.7 in opposite order. Then determine how the BinarySearchTree.print method from Section 17.4.1 prints out both the tree from Exercise • R17.7 and this tree.
Consider the following tree. In which order are the nodes printed by the Binary-SearchTree.print method? The numbers identify the nodes. The data stored in the nodes is not shown. 1 8 6 10
Design an algorithm for finding the kth element (in sort order) of a binary search tree. How efficient is your algorithm?
Design an O(log(n)) algorithm for finding the kth element in a binary search tree, provided that each node has an instance variable containing the size of the subtree.Also describe how these instance
Design an algorithm for deciding whether two binary trees have the same shape. What is the running time of your algorithm?
Insert the following eleven words into a binary search tree:Mary had a little lamb. Its fleece was white as snow.Draw the resulting tree.
What is the result of printing the tree from Exercise • R17.13 using preorder, inorder, and postorder traversal?Data from exercise R17.13Insert the following eleven words into a binary search
Locate nodes with no children, one child, and two children in the tree of ExerciseR17.13 . For each of them, show the tree of size 10 that is obtained after removing the node.Data from exercise
Repeat Exercise • R17.13 for a red-black tree.Data from exercise R17.13 Insert the following eleven words into a binary search tree:Mary had a little lamb. Its fleece was white as snow.Draw the
Repeat Exercise •• R17.15 for a red-black tree.Data from exercise R17.15 Locate nodes with no children, one child, and two children in the tree of Exercise R17.13 . For each of them,
Show that a red-black tree with black height bh has at least 2bh –1 nodes. Look at the root. A black child has black height bh – 1. A red child must have two black children of black height bh –
Let rbts(bh) be the number of red-black trees with black height bh. Give a recursive formula for rbts(bh) in terms of rbts(bh – 1). How many red-black trees have heights 1, 2, and 3? Hint: Look at
What is the maximum number of nodes in a red-black tree with black height bh?
Show that any red-black tree must have fewer interior red nodes than it has black nodes.
Show that the “black root” rule for red-black trees is not essential. That is, if one allows trees with a red root, insertion and deletion still occur in O(log(n)) time.
Many textbooks use “dummy nodes”—black nodes with two null children—instead of regular null references in red-black trees. In this representation, all non-dummy nodes of a red-black tree have
Why does Figure 21 show all possible configurations of a double-red violation?Figure 21 13 722 13 5 t 13. t 12 t
Could a priority queue be implemented efficiently as a binary search tree? Give a detailed argument for your answer.•••
Will preorder, inorder, or postorder traversal print a heap in sorted order? Why or why not?
Prove that a heap of height h contains at least 2h–1 elements but less than 2h ele ments.
Suppose the heap nodes are stored in an array, starting with index 1. Prove that the child nodes of the heap node with index i have index 2 · i and 2 · i + 1, and the parent node of the heap node
Simulate the heapsort algorithm manually to sort the array 11 27 8 14 45 6 24 81 29 33 Show all steps.
Write a method that counts the number of all leaves in a tree.
Add a method countNodesWithOneChild to the BinaryTree class.
Add a method swapChildren that swaps all left and right children to the BinaryTree class.
Implement the animal guessing game described in Section 17.2.1. Start with the tree in Figure 4, but present the leaves as “Is it a(n) X?” If it wasn’t, ask the user what the animal was, and
Reimplement the addNode method of the Node class in BinarySearchTree as a static method of the BinarySearchTree class:If parent is null, return newNode. Otherwise, recursively add newNode to parent
Write a method of the BinarySearchTree class:that returns the smallest element of a tree. You will also need to add a method to the Node class. Comparable smallest()
Add methods: void preorder (Visitor v) void inorder (Visitor v) void postorder (Visitor v) to the BinaryTree class of Section 17.2.3.
Using a visitor, compute the average value of the elements in a binary tree filled with Integer objects.
Add a method void depthFirst(Visitor v) to the Tree class of Section 17.4. Keep visiting until the visit method returns false.
Implement an inorder method for the BinaryTree class of Section 17.2 so that it stops visiting when the visit method returns false. ( Have inorder return false when visit returns false.)
Write a method for the RedBlackTree class of Worked Example 17.2 that checks that the tree fulfills the rules for a red-black tree.Data from worked example 17.2 The code for fixing up a double-red
Modify the implementation of the MinHeap class so that the parent and child index positions and elements are computed directly, without calling helper methods.
Time the results of heapsort and merge sort. Which algorithm behaves better in practice?
A general tree (in which each node can have arbitrarily many children) can be implemented as a binary tree in this way: For each node with n children, use a chain of n binary nodes. Each left
A general tree in which all non-leaf nodes have null data can be implemented as a list of lists. For example, the treeis the list [[A, B], C, [D]].Using the list implementation from Section 16.1.8,
Continue Exercise •• E17.4 and write the tree to a file when the program exits. Load the file when the program starts again.Data from exercise E17.4Implement the animal guessing game described in
Change the BinarySearchTree.print method of Section 17.3.4 to print the tree as a tree shape. You can print the tree sideways. Extra credit if you instead display the tree with the root node centered
In the BinarySearchTree class of Section 17.3.4, modify the remove method so that a node with two chil dren is replaced by the largest child of the left subtree.
Reimplement the remove method in the RedBlackTree class of Worked Example 17.2 so that the node is first removed using the binary search tree removal algorithm, and the tree is rebalanced after
The ID3 algorithm describes how to build a decision tree for a given a set of sample facts. The tree asks the most important questions first. We have a set of criteria (such as “Is it a mammal?”)
Modify the expression evaluator from Section 13.5 to produce an expression tree. (Note that the resulting tree is a binary tree but not a binary search tree.) Then use postorder traversal to evaluate
Implement an iterator for the BinarySearchTree class that visits the nodes in sorted order. In the constructor, keep pushing left nodes on a stack until you reach null. In each call to next, deliver
Implement an iterator for the RedBlackTree class in Worked Example 17.2 that visits the nodes in sorted order. Take advantage of the parent links.Data from worked example 17.2.The code for fixing up
Modify the implementation of the MinHeap class in Section 17.6 so that the 0 element of the array is not wasted.
What is a type parameter?
What is the difference between a generic class and an ordinary class?
What is the difference between a generic class and a generic method?
Why is it necessary to provide type arguments when instantiating a generic class, but not when invoking an instantiation of a generic method?
Find an example of a non-static generic method in the standard Java library.
Find four examples of a generic class with two type parameters in the standard Java library.
Find an example of a generic class in the standard library that is not a collection class.
Why is a bound required for the type parameter T in the following method? int binarySearch (T[] a, T key)
Why is a bound not required for the type parameter E in the HashSet class?
What is an ArrayList>?
Explain the type bounds of the following method of the Collections class.Why doesn’t T extends Comparable or T extends Comparable suffice? public static
What happens when you pass an ArrayList to a method with an ArrayList parameter variable? Try it out and explain.
What happens when you pass an ArrayList to a method with an ArrayList parameter variable, and the method stores an object of type BankAccount into the array list? Try it out and explain.
What is the result of the following test?Try it out and explain. ArrayList accounts = new ArrayList (); if (accounts instanceof ArrayList ) .
The ArrayList class in the standard Java library must manage an array of objects of type E, yet it is not legal to construct a generic array of type E[] in Java. Locate the implementation of the
Modify the generic Pair class so that both values have the same type.
Add a method swap to the Pair class of Exercise • E18.1 that swaps the first and second elements of the pair.Data from exercise Modify the generic Pair class so that both values have the same
Implement a static generic method PairUtil.swap whose argument is a Pair object, using the generic class declared in Section 18.2. The method should return a new pair, with the first and second
Implement a static generic method that, given a Map, yields a List of the key/value pairs in the map.
Implement a generic version of the binary search algorithm.
Implement a generic version of the selection sort algorithm.
Implement a generic version of the merge sort algorithm. Your program should compile without warnings.
Implement a generic version of the LinkedList class of Section 16.1.
Turn the HashSet implementation of Section 16.4 into a generic class. Use an array list instead of an array to store the buckets.
Provide suitable hashCode and equals methods for the Pair class of Section 18.2 and implement a HashMap class, using a HashSet.
Implement a generic version of the permutation generator in Section 13.4. Generate all permutations of a List.
Write a generic static method print that prints the elements of any object that implements the Iterable interface. The elements should be separated by commas. Place your method into an appropriate
Turn the MinHeap class of Section 17.6 into a generic class. As with the TreeSet class of the standard library, allow a Comparator to compare elements. If no compara tor is supplied, assume that the
Make the Measurer interface from Section 10.4 into a generic interface. Provide a static method T max(T[] values, Measurer meas).
Provide a static method void append(ArrayLista, ArrayListb) that appends the elements of b to a.
Modify the method of Exercise • E18.15 so that the second array list can contain elements of a subclass. For example, if people is an ArrayList and students is an ArrayList, then append(people,
Modify the method of Exercise • E18.15 so that it leaves the first array list unchanged and returns a new array list containing the elements of both array lists.Data from exercise E8.15Provide a
Modify the method of Exercise •• E18.17 so that it receives and returns arrays, not array lists. Arrays.copyOf.Data from exercise E8.17Modify the method of Exercise • E18.15 so that it leaves
Provide a static method that reverses the elements of a generic array list.
Provide a static method that returns the reverse of a generic array list, without modifying the original list.
Provide a static method that checks whether a generic array list is a palindrome; that is, whether the values at index i and n - 1 - i are equal to each other, where n is the size of the array list.
Provide a static method that checks whether the elements of a generic array list are in increasing order. The elements must be comparable.
Write a static generic method PairUtil.minmax that computes the minimum and maximum elements of an array of type T and returns a pair containing the minimum and maximum value. Require that the array
Repeat Exercise •• P18.1 but require that the array elements implement the Comparable interface.Data from exercise P18.1 Write a static generic method PairUtil.minmax that computes the minimum
Repeat Exercise •• P18.2, but refine the bound of the type parameter to extend the generic Comparable type.Data from exercise P18.2 Repeat Exercise •• P18.1 but require that the array
Make the Measurable interface from Section 10.1.2 into a generic interface. Provide a static method that returns the largest element of an ArrayList, provided that the elements are instances of
Enhance Exercise •• P18.4 so that the elements of the ArrayList can implement Measurable for appropriate types U.Data from exercise P18.4 Make the Measurable interface from Section 10.1.2 into

Showing 100 - 200 of 791