The second test will be given in class on Monday, April 15. It covers Section 9.4, Sections 10.1 through 10.4, and Sections 11.1 through 11.3. Note that sections 9.5 and 10.5 are not included. There will be no questions on JavaFX or GUI programming. There will be no questions that are specifically about earlier material; however, you should know that material and you might need to know it for some questions. (In particular, questions about the classes in the JFC might require some knowlege of the actual data structures that they use internally, which were covered in Chapter 9. Also, there could be questions about run time efficiency that use what you learned about that topic back in Chapter 8. And of course you need to know everything that you learned in CS 124.)
The format will be similar to the first test: There will be some definitions and essay-type questions. Some questions will ask you to write code segments or methods or possibly even complete classes. There might also be some questions that ask you to read some code and figure out what it does.
Here are some terms and ideas that you should be familiar with:
binary trees tree node: contains left and right child pointers root of a binary tree; leaf in a binary tree recursive structure of a binary tree: a tree is empty or consists of a root and two subtrees recursive processing of a binary tree traversals of a binary tree: preorder, postorder, and inorder traversal BST (Binary Sort Tree): inorder traversal visits nodes in increasing order inserting an item into a BST; searching for an item in a BST generic programming what problem is solved by generic programming? parameterized classes in Java, such as ArrayList<T> and HashMap<K,V> type parameters in parameterized classes the Java Collection Framework (JCF) working with generic lists, sets, and maps the JFC does not work with primitive types wrapper classes for primitive types: Integer, Double, Boolean, Character using wrapper classes with the JFC the class Object, the superclass for all classes methods in class Object that are often overridden: toString(), equals(x), hashCode() the interface Comparable<T> and its method compareTo(x) Collections: Lists and Sets using a "for-each loop"; example: for ( String str : strList )... using sets to store collections with no duplicates using TreeSet to store sets in increasing order, based on the compareTo() method implementing mathematical set operations with addAll(), removeAll, retainAll() using maps to associate values to keys hash tables and hash codes the structure of a hash table: an array of linked lists how hash codes are used run-time efficiencies of various operations comparing run times for operations on ArrayList and LinkedList find, insert, remove operations on TreeSets/TreeMaps run in time Θ(n*log(n)) find, insert, remove operations on HashSets/HashMops run in average time Θ(1) parameterized interfaces and classes in the JFC Collection<T>; methods: add(x), remove(x), contains(x), size(), clear(), isEmpty(), iterator(), addAll(collection), removeAll(collection), retainAll(collection) List<T>; extra methods: get(index), set(index,x), remove(index) ArrayList<T> LinkedList<T> Set<T> HashSet<T> TreeSet<T> Map<K,V>; methods: put(k,v), get(k), containsKey(k), keySet() HashMap<K,V> TreeMap<K,V> the stream API using lambda expressions with the stream API creating streams: collection.stream(), Arrays.stream(array), IntStream.range(n,m) intermediate operations: filter(p), map(f), mapToInt(f), mapToDouble(f) terminal operation: forEach(action), count(), sum() I/O streams for input and output files how I/O streams and files are abstractions and why that is important binary I/O streams versus character I/O streams character sets and character encoding; for example, ISO-8859-1, UTF-8, UTF-16 InputStream and OutputStream Reader and Writer IOExceptions PrintWriter: the methods print(), println(), printf(), checkError() files, directories, and file paths the File class; methods: exists(), length(), canRead(), canWrite(), isDirectory() FileReader and FileWriter; FileInputStream and FileOutputStream using a Scanner to read from a text file using a PrintWriter to write to a text file designing a format for a data file why use human readable (character) files?
1. (a) Suppose that the letters in the tree on the left below are printed out using a in-order traversal. List the letters in the order in which they are printed. (b) Place the letters A through K into the tree on the right below so that when the letters are printed by a post-order traversal of the tree the letters will be printed out in the order A B C D E F G H I J K
2. Suppose that binary trees of integers are implemented using the TreeNode data type shown below. Write a recursive method with a parameter of type TreeNode that returns the number of times that the number 17 occurs in the tree.
class TreeNode { int item; TreeNode left; TreeNode right; }
3. There are two Set classes in Java, TreeSet and HashSet. What's the difference? How do the run times of their operations compare? Why might you choose to use one rather than the other?
4. The Java Collection Framework uses parameterized types such as ArrayList<T> and TreeMap<K,V>. Discuss parameterized types: What can you do with them, and why do they exist in the Java langauge? What do parameters like the "T", "K", and "V" represent?
5. Suppose that a variable named words
is of type TreeSet<String>.
(a) Write a code segment that uses a "for-each"
loop to print out all the words in this set.
(b)The set is represented as a TreeSet rather than a HashSet. What consequence
does this have for the output in part (a)?
(c) Under what circumstances might you prefer to use a HashSet rather than
a TreeSet? Why?
6. Suppose that a variable named symTab is of type HashMap<String,Double>,
and that symTab is used to represent a symbol table that associates values to "variable" names.
(a) Write a Java statement that will associate the value 3.14 to a variable named pi.
(b) Write a Java statement that will print out the value associated to the variable named foo.
(c) Suppose that you want to add 1 to the value associated with the variable named count.
Write one or more Java statements that will do this. (You want to change the value that
is stored in the symbol table, not just compute the answer!)
7. A file named "data.dat" contains integers. Write a program that will read the integers from this file and create a new file named "result.dat" that contains the same integers, but sorted and with duplicates removed. You can do this using only the classes listed in the import statements shown below. You can use one big try..catch to handle errors.
import java.util.Scanner; import java.util.TreeSet; import java.io.File; import java.io.PrintWriter; public class Uniq { public static void main(String[] args) {
8. Write a Java code segment that will create a HashSet<Integer> that contains exactly 10 different numbers chosen at random from the range 0 t0 99. (Hint: In the end, the size of the set must be 10.)
9. Suppose that dictionary is a variable of type HashMap<String,String> in which the keys are words and the values are the definitions of the words. (a) The definition of the word "eschew" is "avoid rigorously." Write a Java statement that will add this definition to dictionary. (b) Write a code segment that will determine whether the word "obfuscation" has a definition in dictionary. If it does, the code segment should print the definition; if not, it should print out a message saying so.
10. Suppose that A and B are variables of type i>HashSet<Integer>. Write a code segment to find and print out how many integers are in the intersection of A and B.
11. Suppose that the variable grades is of type ArrayList<Student>, where Student is the class shown here:
class Student { String name; int homework; int midterm; int final; }
The following code segment was used to print the contents of the ArrayList, grades, to a file named "grades.dat":
try { PrintWriter out = new PrintWriter(new File("grades.dat)); out.println(grades.size()); for (int i = 0; i < grades.size(); i++) { Student std = grades.get(i); out.print(std.midterm + " "); out.print(std.final + " "); out.print(std.homework + " "); out.println(std.name); } out.flush(); out.close(); } catch (IOException e) { System.out.println( "Sorry, an error occurred while trying to write the file."); }Write a code segment that will read the file grades.dat and re-create the ArrayList grades exactly as it was before it was saved. You do not need to catch or report exceptions that occur.
12. Java has four basic abstract "I/O stream" classes that are used for input/output: InputStream, OutputStream, Reader, and Writer. State briefly what each of these clases is for. Then explain what it means that they are abstract classes and why it is so useful to have abstractions to represent I/O streams.