CMSC132 Fall 2006 Midterm 1 Key 1 13 pts General Topics a b c d e f g h i j k l m 1 point each Abstraction and encapsulation help make programs run faster Run time errors are easier to detect than logic errors Big O notation indicates an upper bound on complexity Critical sections are usually found inside loops Best case analysis is more useful than worst case analysis Linear data structures are a type of collection Linked lists require more memory than arrays We insert A B C into a stack The first element to be removed is C We insert A B C into a queue The first element to be removed is C Recursive code always requires a base case Recursive code can always be rewritten as iterative code Maps may have more values than keys Maps may be implemented using arrays 2 9 pts Java constructs a b c d e f g h i T or F T or F T or F T or F T or F T or F T or F T or F T or F T or F T or F T or F T or F 1 point each Java interfaces are examples of functional abstractions Java methods are examples of data abstractions Java throws exceptions for run time errors Java enumerations can grow in size during program execution Java Collections consist of both interfaces and classes Java Collections use the Comparable interface Generic classes help detect errors in Java programs If a hashCode b hashCode then a equals b true If a hashCode b hashCode then a equals b false 3 7 pts Complexity of Data Structures T or F T or F T or F T or F T or F T or F T or F T or F T or F 1 point each For a data structure containing n elements a Finding an element in a sorted array is b Finding an element in a sorted linked list is c Finding an element in a hash table of size 5n is d Inserting an element in an unsorted array at beginning is e Inserting an element in an unsorted linked list at beginning is f Inserting an element in a sorted linked list keeping list sorted is g Inserting an element in a hash table of size 5n is 1 O O O O O O O log n n 1 n 1 n 1 4 6 pts Finding Critical Sections 2 points each Calculate the asymptotic complexity of the code snippets below using big O notation with respect to the problem size n 5 a for i 0 i n i i 9 for j n 9 j 99 j j 9 for k 9 k n 9 k k 1 f n O n3 b for i n 4 i n 4 i i 4 for j i 4 j n 4 j j 4 for j 4 j n j j 4 f n O n c for i 1 i n i i 2 for j n 1 j i 3 j j 1 f n O n log n 12 pts Recursion For each of the following codes describe whether the function foo n will return a result when it is invoked as foo 100 If no result is returned explain why a int foo int n if n 1 return foo n 2 1 return 1 Returns result If no result why T or F b int foo int n if n 1 return 1 return foo n 2 2 Returns result If no result why T or F 1 point Misses base step of n 1 goes from n 2 to n 0 2 points 2 1 point c Write a recursive function to compare two array of ints returning true if the arrays have the same elements and in the same order Assume neither a nor b are null The static method sameArray has the following prototype public static boolean sameArray int a int b Feel free to add an auxiliary method Non recursive solutions will receive no credit public static boolean sameArray int a int b if a length b length return false return sameA a b 0 public static boolean sameA int a int b int k if a length k return true else if a k b k return false return sameA a b k 1 6 15 pts Generic Classes Linked Data Structures a Given the following Node class for Objects convert it into a generic Node class e g a class that can support generic programming such as Node String Node Integer public class Node public Object data public Node next Node Object o data o next null public class Node T public T data public Node T next Node T val data val next null 3 Use the generic Node class to build a generic myQueue class that supports i Constructor for empty myQueue ii Enqueue method for adding element to queue iii Dequeue method for removing element from queue public class myQueue T Node T head Node T tail myQueue head null tail null public void enqueue T val Node T n new Node T val if head null head n tail n else tail next n tail n public T dequeue if head null return null T ret head data if tail head tail head next head head next return ret 4 7 18 pts Maps Sets The class myZipMap uses a Java Map Map String Set Integer to keep track of all the zip codes found in each city City names are Strings and zip codes are Integers An incomplete implementation is presented public class myZipMap Map String Set Integer cityZips a What are the keys for this map and what type do keys have City names which are of type String 2 points b What are the values for this map and what type do values have Sets of zip codes which are of type Set Integer 2 points c Implement a constructor which defines an empty myZipMap 2 points myZipMap cityZips new HashMap String Set Integer d Implement a void add String CityName Integer ZipNumber method that adds the ZipNumber to the set of zip codes for the city Hint recall that the Java interface Map has a Object put Object k Object v method and the interface Set has a boolean add Object o method void add String CityName Integer ZipNumber Set Integer s cityZips get CityName if s null s new HashSet Integer cityZips put CityName s s add ZipNumber e Implement a void printCityZips String CityName method that prints all of the city s zip codes Hint recall that the Java interface Map has a Object get Object k method and use a Java enhanced for loop void printCityZips String CityName Set Integer s cityZips get CityName if s null for Integer i s System out println i 5 Honors Section Credit is given only for Honors Section students 8 20 pts Honors a Expected cost is usually smaller than average cost b Amortized cost is usually smaller than …
View Full Document
Unlocking...