CMSC 132 Fall 2007 Midterm 1 Key Problem 1 12 pts Java Language Features a 10 pts True or False 1pt each Assume A B are Java classes where B extends A 1 2 3 4 5 6 7 8 9 10 A v new B is a valid Java statement B v new A is a valid Java statement int v new Integer 1 is a valid Java statement Integer v 1 is a valid Java statement ArrayList int v is a valid Java statement ArrayList Integer v is a valid Java statement ArrayList A v new ArrayList A is a valid Java statement ArrayList A v new ArrayList B is a valid Java statement Instance variables should be declared private to enforce encapsulation Package scope for a method is declared using the package keyword T T T T T T T T T T F F F F F F F F F F b 2 pts Define an enumerated type Season representing 4 seasons Summer Fall Winter Spring enum Season Summer Fall Winter Spring Problem 2 12 pts Program Correctness and Exceptions a 2 pts True or False 1pt each 1 A piece of code is covered if it is executed by a test case during testing 2 A set of tests providing 100 test coverage with no errors proves code is correct T F T F b 6 pts Fill in the blank 2pts each 1 Name the hardest type of error to debug Logic 2 Name a Java checked exception Exception IoException ClassNotFoundException 3 Name a Java unchecked exception RuntimeException ArithmeticE NullPointerE c 4 pt The method bar can throw an exception Modify the method foo so it returns 1 if an exception is thrown by bar public int foo int x try for int i x i 2000 i bar i catch Exception e return 1 return 0 1 Problem 3 14 pts Algorithmic Complexity a 8 pts Calculate the asymptotic complexity of the code snippets below using big O notation with respect to the problem size n 1 for int i 1 i n i i i n 2 f n O n 2 for i 1 i n 3 i for k 1 k n 2 k for m n m n 100 m s s 10 f n O n2 3 for int i n 2 i n i for int j 1 j n j j 2 f n O n log n 4 n2 log n 100n f n O n2 log n b 2 pts List the following big O expressions in order of asymptotic complexity lowest complexity first O nlog n O 1 O log n O 2n O n3 O 1 O log n O nlog n O n3 O 2n c 4 pts Assume you are playing the number guessing game where you are trying to guess a number x between 1 and n For each number guessed the answer may be correct too high or too low Consider a game where x 30 and n 64 1 2 3 4 List your first 3 guesses using a linear search algorithm List your first 3 guesses using a binary search algorithm List the worst case value for x using a linear search algorithm List the best case value for x using a binary search algorithm 2 1 2 3 32 16 24 64 32 Problem 4 12 pts Hashing a 4 pts Hash tables Assuming the following hash values are computed for the keys A B C D and E H A 4 H B 3 H C 3 H D 3 H E 0 Rewrite the following two hash tables to illustrate the state of each table after A B C D and E have been inserted in the table in the specified order Open addressing Chaining bucket hashing 0 D 0 E 1 E 1 2 2 3 B 3 B 4 A 4 A 5 C 5 C D b 4 pts Load factor 1 2 3 4 The load factor for a hash table is calculated as A search in an open addressing hash table with load factor 0 10 is A search in an open addressing hash table with load factor 1 00 is A search in an chaining bucket hash table with load factor 1 00 is keys table size O 1 O n O 1 c 4 pts Java hashCode 1 The default Object hashCode and equals methods satisfy the Java Hash Code contract T F 2 Comparing the hashCode values of two objects answers whether 2 objects are equal T F 3 The Java hash code contract requires that the hashCode method guarantees the following if a equals b is true then a hashCode b hashCode 3 Problem 5 24 pts Linear Data Structures a 4 pts Convert the class MyLinkedList into a class that supports generic programming b 10 pts Define a constructor that constructs a MyLinkedList using elements in an ArrayList You must use only the enhanced for loop to access elements of the ArrayList c 10 pts Define a public method named shiftLeft for the MyLinkedList class that moves the first element of the list to the end of the list causing the list to shift left by one element public class MyLinkedList T private class Node private T data private Node next public Node T data this data data next null private Node head null public MyLinkedList ArrayList T aList Node n tail null for T elem aList n new Node elem if head null head n else tail next n tail n public void shiftLeft if head null return Node n head while n next null n n next n next head Node oldHead head head head next oldHead next null public void shiftLeft2 if head null return if head next null return Node oldHead head head head next oldHead next null Node n head while n next null n n next n next oldHead 4 Problem 6 26 pts Sets and Maps You are asked to use the HashSet and HashMap classes to implement a TVPrograms class 1 2 pts Implement a constructor for TVPrograms that creates an empty showChannelMap 2 10 pts Implement a addChannelToShow method that stores information a specified show is running on a specified channel Note you must handle the case where a show is added for the first time 3 2 pts Implement a channelsInShow method that returns set of channels running specified show 4 12 pts Implement a showsInChannel method that returns set of shows running on specified channel public class TVPrograms private Map String Set Integer showChannelMap 2 pts constructor 1 pt use HashMap 1 pt rest public TVPrograms showChannelMap new HashMap String Set Integer public void addChannelToShow String showName int channel Set Integer channelSet if channelSet showChannelMap get showName null channelSet new HashSet Integer showChannelMap put showName channelSet channelSet add channel public Set Integer channelsInShow String showName return showChannelMap get showName public Set String showsInChannel int channel Set String showsInChannel new HashSet String for String show showChannelMap keySet if showChannelMap get show contains channel showsInChannel add show return showsInChannel 5 15 pts Honors …
View Full Document
Unlocking...