CMSC132 Fall 2006 Midterm #1 – Key1. (13 pts) General Topics 1 point eacha. Abstraction and encapsulation help make programs run faster T or Fb. Run-time errors are easier to detect than logic errors T or Fc. Big-O notation indicates an upper bound on complexity T or Fd. Critical sections are usually found inside loops T or Fe. Best case analysis is more useful than worst case analysis T or Ff. Linear data structures are a type of collection T or Fg. Linked lists require more memory than arrays T or Fh. We insert A, B, C into a stack. The first element to be removed is C. T or Fi. We insert A, B, C into a queue. The first element to be removed is C. T or Fj. Recursive code always requires a base case T or Fk. Recursive code can always be rewritten as iterative code T or Fl. Maps may have more values than keys T or Fm. Maps may be implemented using arrays T or F2. (9 pts) Java constructs 1 point eacha. Java interfaces are examples of functional abstractions T or Fb. Java methods are examples of data abstractions T or Fc. Java throws exceptions for run-time errors T or F d. Java enumerations can grow in size during program execution T or Fe. Java Collections consist of both interfaces and classes T or Ff. Java Collections use the Comparable interface T or Fg. Generic classes help detect errors in Java programs T or Fh. If a.hashCode( ) == b.hashCode( ), then a.equals(b) == true T or Fi. If a.hashCode( ) != b.hashCode( ), then a.equals(b) == false T or F3. (7 pts) Complexity of Data Structures 1 point eachFor a data structure containing n elements a. Finding an element in a sorted array is O( log(n) )b. Finding an element in a sorted linked list is O( n )c. Finding an element in a hash table of size 5n is O( 1 )d. Inserting an element in an unsorted array (at beginning) is O( n )e. Inserting an element in an unsorted linked list (at beginning) is O( 1 )f. Inserting an element in a sorted linked list (keeping list sorted) is O( n )g. Inserting an element in a hash table of size 5n is O( 1 )14. (6 pts) Finding Critical Sections 2 points eachCalculate the asymptotic complexity of the code snippets below (using big-O notation) with respect to the problem size n: a. for (i = 0; i < n; i=i+9) { f(n) = O( n3)for (j = n-9; j > 99; j=j-9) { for (k = 9; k < n/9; k=k+1) {… } }}b. for (i = n-4; i < n+4; i=i+4) { f(n) = O( n ) for (j = i+4; j < n/4; j=j+4) { ... } for (j = 4; j < n; j=j+4) { ... }}c. for (i = 1; i < n; i=i*2) { f(n) = O( n log(n) ) for (j = n-1; j > i+3; j=j-1) { ... }}5. (12 pts) RecursionFor 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) { Returns result? T or F 1 point if (n > 1) If no result, why? return foo(n-2)+1;return 1;}b. int foo (int n) { Returns result? T or F 1 point if (n == 1) If no result, why? Misses base step of n=1 return 1; (goes from n=2 to n=0)return foo(n-2)+2; 2 points}2c. 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 Structuresa. 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; }}3Use the generic Node class to build a generic myQueue class that supports i. Constructor for empty myQueue( )ii. Enqueue( ) method for adding element to queueiii. Dequeue( ) method for removing element from queuepublic 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; }47. (18 pts) Maps & SetsThe class myZipMap uses a Java Map (Map<String, Set<Integer>>) to keep track of all thezip codes found in each city. City names are Strings, and zip codes are Integers. Anincomplete 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? 2 pointsCity names, which are of type Stringb. What are the values for this map, and what type do values have? 2 pointsSets of zip codes, which are of type Set<Integer>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 theZipNumber to the set of zip codes for the city. Hint: recall that the Java interface Maphas a Object put(Object k, Object v) method, and the interface Set has a booleanadd(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
View Full Document
Unlocking...