CMSC132 Spring 2007Midterm #1First Name: _______________________Last Name: _______________________Student ID: _______________________Section time _________ TA Name: _________________I pledge on my honor that I have not given or received any unauthorized assistance on this examination.Your signature: _____________________________________________________________General Rules (Read):- This exam is closed book and closed notes.- If you have a question, please raise your hand.- Total point value is 80 points. - Answer True/False questions by circling the T or F at the end of the question.o Correct answers to True/False questions receive 1 point each (+1pt)o Unanswered (blank) True/False questions receive 0 points eacho Incorrect answers to True/False questions are penalized 1 point each (-1pt)- Answer essay questions concisely using 1-2 sentences. Longer answers are discouraged.- PUNT RULE: For essay/coding questions, you may write PUNT, and you will get ¼ of thepoints for the question (rounded down). You are encouraged to punt rather than waste yourtime writing down semi-random verbiage in hopes of getting partial credit.- WRITE NEATLY. If we cannot understand your answer, you will receive 0 credit.- Honors section questions only count for credit for students in the honors section.1Grader Use Only:#1 OOP (5)#2 Testing (6)#3 Complexity (13)#4 Critical Section (4)#5 Recursion (4)#6 Data Structures (10)#7 Operations (12)#8 Generics & Data Structs (26)Total (80)Honors (12)1. (5 pts) Object-Oriented Programming and Javaa. Procedural abstraction makes it clear what algorithm is used by a program T or Fb. Java interfaces are examples of data abstraction T or Fc. Java requires a list of all possible values for an enumerated type T or Fd. Using Java generics can cause more errors to appear during compilation T or Fe. The Java Comparator interface supports generics T or F2. (6 pts) Testing & Program Correctnessa. Compile-time errors may cause exceptions to be thrown in Java T or Fb. An interactive debugger can display the value of variables in a program T or Fc. Breakpoints mark where run-time errors may occur in a program T or Fd. Empirical testing will find all run-time errors in a program T or Fe. Integration testing tests individual classes T or Ff. Test coverage measures whether code is executed by some test case T or F3. (13 pts) Algorithmic Complexitya. Asymptotic complexity is more accurate than benchmarking T or Fb. Worst case analysis is more useful than best case analysis T or Fc. Critical sections are never found outside loops T or Fd. O(n) is more complex than O( log(n) ) T or Fe. O(n log(n) ) is more complex than O(n2) T or F(2 pts each) Give the complexity of an algorithm for problem size n whose running time: f. Triples when n triples O( )g. Quadruples when n doubles O( )h. Is unchanged when n triples O( )i. Increases by 3 when n triples O( )4. (4 pts) Critical SectionsCalculate the asymptotic complexity of the code snippets below (using big-O notation) withrespect to the problem size n: a. for (i = 1; i < n; i=i*2) { f(n) = O( ) for (k = 1; k < 1000; k=k+2) {… }}b. for (i = n; i > 0; i=i-1) { f(n) = O( ) for (j = 2; j < n-2; j=j+2) { ... }}25. (4 pts) Recursion(2 pts each) For each of the following codes, describe whether the function foo(n) willreturn a result when it is invoked as foo(4). If it returns a result, what is the value returned?If no result is returned, explain why.a. int foo (int n) { foo(4) = if (n > 0) If no result, explain why return 1+foo(n-1);return 0;}b. int foo (int n) { foo(4) = return foo(n-1) + foo(n-2); If no result, explain why}6. (10 pts) Data Structuresa. Data structures differ mainly in the amount of storage required T or Fb. A queue is a restricted version of a list T or Fc. Elements are removed from a stack in reverse order of insertion T or Fd. Sets may contain duplicate elements T or Fe. Maps may contain more keys than values T or Ff. A key may be used to retrieve multiple values from a map T or Fg. Removing a key from a map also removes its associated value T or Fh. Collisions may cause run-time errors in open addressing hash tables T or Fi. Markers are needed for previously-filled hash locations for open addressing T or Fj. In Java, if a.equals(b) is false, then a.hashCode( ) != b.hashCode( ) is true T or F7. (12 pts) Operations on Data Structures(2 pts each) What is the average # of comparisons needed to find an element k in the following data structure, assuming k is stored in the data structure? Circle the closest value:a. A sorted array with 16 elements (using binary search) 1 2 4 8 16b. A linked list with 16 elements 1 2 4 8 16c. A sorted linked list with 16 elements 1 2 4 8 16d. A chained hash table of size 8 with 16 elements 1 2 4 8 16(1 pt each) For a data structure containing n elements, the complexity of:e. Finding the 5th element in an array is O( )f. Finding the (n-5)th element in a linked list is O( )g. Deleting the 5th element in an array is O( )h. Deleting the 5th element in a linked list is O( )38. (26 pts) Generic Programming & Data StructuresYou are asked to count the number of times each String occurs in an array. You realize youcan build a map from Strings to Integers to keep count of the number of occurrences foreach word. You start writing a class implementing the map, using linked lists with an extrakey field per node:public class MyListMap { private class Node {Object k; // key Object v; // valueNode next; } private Node head; public Object get(Object key) { ... } // returns value for key (or null) public Object put(Object key, Object value) { ... } // returns previous value for key} // (or null if no previous value)a. (4 pts) Using your knowledge of generic programming, modify the MyListMap classso it supports generics (e.g., MyListMap<String,Integer>).b. (12 pts) Implement the put( ) method for the MyListMap class, using only a linked listformed from the inner Node class. c. (10 pts) Implement the following count( ) method so that it returns a map from Stringsto Integers that counts the number of times each string occurs in the String array strs.You must iterate through the Strings in the strs array using the enhanced Java for loop.You must create a MyListMap object using generics and use only its get( ) and put( )methods to count strings.// returns map of string countspublic static MyListMap<String,Integer> count(String[ ] strs) { ... }45Honors
View Full Document
Unlocking...