Questions and Answers of Building Java Programs A Back to Basics Approach

Write a method in the HashIntSet class called toArray that returns the elements of the set as a filled array. The order of the elements in the array is not important as long as all elements from the
If separate chaining is used for collision resolution, and the same elements from the previous problem (35, 2, 15, 80, 42, 95, and 66) are added to a hash table of size 10, what is the final state of
Write a program that implements the “Huffman coding” compression algorithm using priority queues and binary trees. Huffman coding is an algorithm devised by David A. Huffman of MIT in 1952 for
Write a method in the HashIntSet class called retainAll that accepts another hash set as a parameter and removes all elements from this set that are not contained in the other set. For example, if
What is the final state of a hash table of size 10 after adding 35, 2, 15, 80, 42, 95, and 66? Assume that we are using the standard “mod” hash function shown in the chapter and linear probing
Modify the HeapIntPriorityQueue class written in this chapter to make it into a three-heap. A three-heap is similar to a binary heap, except that each node is considered to have three children rather
Write a method in the HashIntSet class called removeAll that accepts another hash set as a parameter and ensures that this set does not contain any of the elements from the other set. For example, if
The following statement is an incorrect attempt to resize a hash table to twice its current size. Why is this code incorrect? What is the proper way to enlarge a hash table?elementData =
Modify the HeapIntPriorityQueue class written in this chapter to make it configurable in ways similar to Java’s PriorityQueue class. Make it possible for the heap to be a min-heap or max-heap. (If
Write a method in the HashIntSet class called equals that accepts another hash set as a parameter and returns true if the two sets contain exactly the same elements. The internal hash table size and
How do you know when a hash table has become “full”? At what point does it become impossible to add further elements to a hash table of a given size? Does it depend on the collision resolution
Write a method in the HashIntSet class called containsAll that accepts another hash set as a parameter and returns true if your set contains every element from the other set. For example, if the set
Which of the following statements about hash tables is true?a. A hash table has O(log N) average time to add and search for elements.b. The higher a hash table’s load factor, the more quickly
Write a method in the HashIntSet class called addAll that accepts another hash set as a parameter and adds all of the elements from the other set into the current set. For example, if the set stores
Add an iterator to the HashSet class written in this chapter. To do this you will need to write an inner class that can iterate over the elements of the set, remembering its position as it moves
What is hashing, and why is hashing a good way of implementing a set?
What kind of changes would you make to add an iterator to our binary tree class?
What are some changes that need to be made to the tree class to convert it from storing integers to storing objects of type E?
Rewrite the min and max methods from Self-Check Problem 12 so that they will work on a binary search tree. The methods should take advantage of the fact that the tree is sorted and should not examine
Consider the following implementation of the contains method. How does it differ from the one we showed in Section 17.4 ? Is it better or worse, and why? private boolean contains (IntTreeNode root,
How many nodes at most would be examined in a call to contains on a perfect binary search tree of height N?
What is the x = change(x) pattern, and how is it used with binary trees?
Why does the add method of a binary search tree need to return the newly added/created node?
Write a method called matches that returns a count of the number of nodes in one tree that match nodes in another tree. A match is defined as a pair of nodes that are in the same position in the two
Draw the binary search tree that would result if the given elements were added to an empty binary search tree in the given order. Then write the elements of the tree in the order that they would be
Write a method called makePerfect that adds nodes until the binary tree is a perfect tree. A perfect binary tree is one where all leaves are at the same level. Another way of thinking of it is that
Draw the binary search tree that would result if the given elements were added to an empty binary search tree in the given order. Then write the elements of the tree in the order that they would be
Write a method called evenLevels that makes sure that all branches end on an even level. If a leaf node is on an odd level it should be removed from the tree. We will define the root as being on
Draw the binary search tree that would result if the given elements were added to an empty binary search tree in the given order. Then write the elements of the tree in the order that they would be
Write a method called inOrderList that returns a list containing the sequence of values obtained from an inorder traversal of your binary tree of integers. For example, if a variable t refers to
Draw the binary search tree that would result if the given elements were added to an empty binary search tree in the given order. Then write the elements of the tree in the order that they would be
Write a method called combineWith that accepts another binary tree of integers as a parameter and combines the two trees into a new third tree that is returned. The new tree’s structure should be a
What will be true about the results of an inorder traversal of a binary search tree?
Write a method called tighten that eliminates branch nodes that have only one child. Each such node should be replaced by its only child. (This can lead to multiple replacements because the child
Which of the following trees are valid binary search trees?a.b.c.d.e. - 5 1 -7
Write a method called trim that accepts minimum and maximum integers as parameters and removes from the tree any elements that are not within that range inclusive. For this method you should assume
What is the difference between a regular binary tree and a binary search tree?
Write a method called completeToLevel that accepts an integer as a parameter and that adds nodes to a tree to complete the first levels. A level is complete if every possible node at that level is
Write a method called countBranches that could be added to the IntTree class and that returns the total number of branch nodes in the tree. A branch node is any node that is not a leaf node.
Write a method called copy that returns a reference to a new IntTree that is an independent copy of the original tree. Do not change the original tree. Reference Tree #2 2 Reference Tree #1 1 7. 4 4
Write methods called min and max that could be added to the IntTree class and that return the smallest and largest values in the tree, respectively. For example, if a variable called tree stores the
Write a method called removeLeaves that removes the leaves from a tree. A leaf is a node that has empty left and right subtrees. If your method is called on an empty tree, the method does not change
Write a method called numberNodes that changes the data stored in a binary tree, assigning sequential integers starting with 1 to each node so that a preorder traversal will produce the numbers in
Write a method called size that could be added to the IntTree class and that returns the total number of nodes in the tree.
Write a method called doublePositives that doubles all data values greater than 0 in a binary tree of integers. Reference Tree #2 2 Reference Tree #1 1 7. 4 4 Reference Tree #3 2 3 8. 9. 3. 1.
Why do many recursive tree methods use a public/private pair? What is the difference between the header of the public method and that of the private method?
Write a method called equals that accepts another binary tree of integers as a parameter and compares the two trees to see whether they are equal to each other. For example, if variables of type
Write a method called printMirror that could be added to the IntTree class and that prints a backward inorder traversal of the tree. That is, for a given node, it examines the right subtree, then the
Write a toString method for a binary tree of integers. The method should return "empty" for an empty tree. For a leaf node, it should return the data in the node as a string. For a branch node, it
Write a method called printPostorder that could be added to the IntTree class and that prints a postorder traversal of the tree.
Write a method called isFull that returns true if a binary tree is full and false if it is not. A full binary tree is one in which every node has 0 or 2 children. For example, reference trees #1 and
What would happen if we removed the root != null test from the printPreorder method?
Write a method called printLeaves that prints to System.out the leaves of a binary tree from right to left. More specifically, the leaves should be printed in the reverse order that they would be
Write the elements of the given tree in the order in which they would be seen by a preorder, inorder, and postorder traversal. 7. 4 8 2. 3.
Write a program that evaluates numeric expressions using a binary expression tree. A leaf node represents an operand (a number). A branch node represents an operator; its two subtrees represent its
Write a method called printLevel that accepts an integer parameter n and prints the values at level n from left to right, one per line. We will use the convention that the overall root is at level 1,
Write the elements of the given tree in the order in which they would be seen by a preorder, inorder, and postorder traversal. 19 47 63 23 -2 94 55 28
Add an iterator to the search tree. Write a class called SearchTreeIterator that has the methods that follow for iterating over a binary tree. You will also need to modify the tree nodes to store
Write a method called countEvenBranches that returns the number of branch nodes in a binary tree that contain even numbers. A branch node has one or two children (i.e., it is not a leaf). For
Write the elements of the given tree in the order in which they would be seen by a preorder, inorder, and postorder traversal. 2 4 6.
The actual Set interface in the java.util package has several methods that are beyond those implemented by our search tree in this chapter. Write a version of SearchTree that adds some or all of
Write a method called depthSum that returns the sum of the values stored in a binary tree of integers weighted by the depth of each value. The method should return the value at the root, plus 2 times
a. How many levels does the given tree have?b. How many branches does it have, and which nodes are they?c. How many leaves does it have, and which nodes are they?d. Which node is the root of the
Write a program that performs Huffman encoding and compression using a binary tree. Huffman coding is an algorithm devised by David A. Huffman of MIT in 1952 for compressing text data to make a file
Draw a tree that has twice as many leaves as branches and one that has the same number of leaves as branches.
Write a program that encodes and decodes Morse code files using a binary tree. Morse code is a system that encodes the 26 English letters and 10 numeric digits into sequences of dots, dashes, and
How many roots can a tree have? Does a tree have more branches or leaves?
Implement a yes/no guessing game called 20 Questions using a binary tree. At the beginning of each round of the game, the human player thinks of an object. The computer tries to guess the object by
What state does the linked list iterator store? How does the iterator know if there are more elements left to examine?
Why is an iterator especially useful with linked lists?
What are some changes that need to be made to the linked list class to convert it from storing integers to storing objects of type E?
What are some advantages of creating an IntList interface and having both types of lists implement it?
Write methods called sum and average that return the sum of all values in the list and the average value as a real number, respectively. For example, if a variable called list stores [11, –7, 3,
What is the “inchworm approach”? What advantages does this approach have over other approaches for examining a linked list?
What are the four cases examined in the addSorted method?
In an array list, it is possible to overrun the capacity of the array, at which point the list must be resized to fit. Is resizing necessary on a linked list? What limits the number of elements that
When you add or remove the element found at index of a list, you must create a temporary current node reference and advance it through the list. At which index’s node should the loop stop, relative
An element can be inserted at or removed from the beginning, middle, or end of a linked list. Which of the three locations is the most computationally expensive, and why? How does this compare
What are the two ways to change the contents of a linked list?
Write a graphical program that shows a set of overlapping rectangular regions, each in a different random color. The regions are represented internally as a linked list. The regions have a
Modify the expression evaluator case study program from this chapter to make a new program that accepts as input a fully parenthesized infix expression and returns a string representing an equivalent
Perform a “Sort Detective” challenge to run several sorting algorithms without knowing which is which. Try to figure out which sorting algorithm is which on the basis of the runtime and
Suppose the following array has been declared:What indexes will be examined as the middle element by a binary search for each of the following target values? What value will be returned?a. 103b. 30c.
Write a method called stretch that takes an integer as a parameter and that increases a list of integers by a factor of by replacing each integer in the original list with copies of that integer. For
Write a method called stutter that doubles the size of a list by replacing every integer in the list with two of that integer. For example, suppose a variable list stores the values [1, 8, 19, 4, 17]
Write a method called switchPairs that switches the order of values in the list in a pairwise fashion. Your method should switch the order of the first two values, then switch the order of the next
Write a method called deleteBack that deletes the last value (the value at the back of the list) and returns the deleted value. If the list is empty, throw a NoSuchElementException.
list = new ListNode(4, list.next.next);Draw a picture of what the given linked nodes would look like after the given code executes. list 1 2 3
Write a method called hasTwoConsecutive that returns whether or not a list of integers has two adjacent numbers that are consecutive integers ( true if such a pair exists and false otherwise). For
list.next = new ListNode(3, list.next);Draw a picture of what the given linked nodes would look like after the given code executes. list 1
Write a method called countDuplicates that returns the number of duplicates in a sorted list. The list will be in sorted order, so all of the duplicates will be grouped together. For example, if a
list.next = new ListNode(3);Draw a picture of what the given linked nodes would look like after the given code executes. list 1
What happens if you or the client try to go past the last element in a linked list? Be specific.
Write a method called lastIndexOf that accepts an integer value as a parameter and that returns the index in the list of the last occurrence of that value, or −1 if the value is not found in the
“Assassin” is a real-life game in which a group of players all try individually to find and touch (or “kill”) one other player. You can use a linked list to represent this “kill ring” of
What value is stored as the next field of the last node of a list? What value will a node’s next field have if none is specified?
Write a method called isSorted that returns true if the list is in sorted (nondecreasing) order and returns false otherwise. An empty list is considered to be sorted.
The implementation of several methods is (or can be) the same between our ArrayList and LinkedList. Write a common abstract superclass called AbstractList that implements the common behavior and is
What is the difference between a linked node and a linked list? How are they related and connected?
Write a method called min that returns the minimum value in a list of integers. If the list is empty, it should throw a NoSuchElementException.

Showing 100 - 200 of 1041