CMSC132 Spring 2007 Midterm 1 Key 1 5 pts a b c d e Object Oriented Programming and Java Procedural abstraction makes it clear what algorithm is used by a program Java interfaces are examples of data abstraction Java requires a list of all possible values for an enumerated type Using Java generics can cause more errors to appear during compilation The Java Comparator interface supports generics T or F T or F T or F T or F T or F 2 6 pts Testing Program Correctness a Compile time errors may cause exceptions to be thrown in Java b An interactive debugger can display the value of variables in a program c Breakpoints mark where run time errors may occur in a program d Empirical testing will find all run time errors in a program e Integration testing tests individual classes f Test coverage measures whether code is executed by some test case T or F T or F T or F T or F T or F T or F 3 13 pts Algorithmic Complexity a Asymptotic complexity is more accurate than benchmarking b Worst case analysis is more useful than best case analysis c Critical sections are never found outside loops d O n is more complex than O log n e O n log n is more complex than O n2 T or F T or F T or F T or F T or F 2 pts each Give the complexity of an algorithm for problem size n whose running time f g h i Triples when n triples Quadruples when n doubles Is unchanged when n triples Increases by 3 when n triples O O O O n n2 1 log n 4 4 pts Critical Sections Calculate the asymptotic complexity of the code snippets below using big O notation with respect to the problem size n a for i 1 i n i i 2 for k 1 k 1000 k k 2 f n O log n b for i n i 0 i i 1 for j 2 j n 2 j j 2 f n O n2 1 5 4 pts Recursion 2 pts each For each of the following codes describe whether the function foo n will return 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 if n 0 return 1 foo n 1 return 0 foo 4 4 If no result explain why b int foo int n return foo n 1 foo n 2 foo 4 no result If no result explain why no base case 6 10 pts Data Structures a Data structures differ mainly in the amount of storage required b A queue is a restricted version of a list c Elements are removed from a stack in reverse order of insertion d Sets may contain duplicate elements e Maps may contain more keys than values f A key may be used to retrieve multiple values from a map g Removing a key from a map also removes its associated value h Collisions may cause run time errors in open addressing hash tables i Markers are needed for previously filled hash locations for open addressing j In Java if a equals b is false then a hashCode b hashCode is true 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 7 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 b A linked list with 16 elements 1 2 4 8 c A sorted linked list with 16 elements 1 2 4 8 d A chained hash table of size 8 with 16 elements 1 2 4 8 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 th g Deleting the 5 element in an array is O h Deleting the 5th element in a linked list is O 2 1 n n 1 16 16 16 16 8 26 pts Generic Programming Data Structures You are asked to count the number of times each String occurs in an array You realize you can build a map from Strings to Integers to keep count of the number of occurrences for each word You start writing a class implementing the map using linked lists with an extra key field per node a 4 pts Using your knowledge of generic programming modify the MyListMap class so it supports generics e g MyListMap String Integer public class MyLinkedMap K V private class Node K key V val Node next Node head public V get K key public V put K key V val b 12 pts Implement the put method for the MyListMap class using only a linked list formed from the inner Node class public V put K key V val Node n head while n null if n key equals key V oldVal n val n val val return oldVal n n next n new Node n key key n val val n next head head n return null 3 c 10 pts Implement the following countStrings method so that it returns a map from Strings to 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 public static Map String Integer count String strs MyLinkedMap String Integer cmap new MyLinkedMap String Integer for String s strs Integer i cmap get s if i null cmap put s 1 else count put s i 1 return cmap Honors Section Credit is given only for Honors Section students 9 14 pts Honors a An n2 algorithm can require O n3 steps to solve b A polynomial time algorithm is one that can be solved in O nk steps T or F T or F 2 pts each Give the complexity of an algorithm for problem size n whose running time c Triples when n increases by 1 O 3n 2 pts Calculate the asymptotic complexity of the code snippets below using big O notation with respect to the problem size n d for i n i 0 i i 1 for j 2 j i j j 2 e for i 3 i n i i 2 for k 2 k n k k 3 f n O n2 f n O log log n 2 pts each What is the average of comparisons needed to find an element in the following …
View Full Document
Unlocking...