CMSC132 Practice Problems Midterm 1 Problem 1 Files Scanner and Generics in Java A Files Scanner a Files may be viewed as streams when opened using either the FileReader and FileInputStream classes What is the difference between the two types of streams b What is the motivation for using the Scanner class to process text input c Write code to show how the scanner may be used to read in a series of alternating numbers ints and names Strings from a text file starting with a number class Scanner Scanner boolean hasNext String next int nextInt String nextLine myFileReader try BufferedReader f new BufferedReader new FileReader filename insert code to read in numbers and names from file catch IOException e System out println e getMessage B Generics a What is the motivation for using generic types b Classes in the Java Collection Framework support generic types in Java 1 5 Show how to modify the following code to declare a LinkedList class for Strings using generics then add get a String object from the list previously LinkedList myList new LinkedList myList add new String test String s String myList get 0 1 Problem 2 Algorithmic Complexity C Algorithmic complexity a What is algorithmic complexity b List 2 reasons benchmarking is better than analyzing complexity c What is the difference between best case worst case and average case d What is a recurrence relation D Big O notation and complexity a What does the Big O notation represent b Why are O 2n 4 and O n considered equivalent c Why are O n2 and O n not considered equivalent d What are some simple rules for calculating Big O notation e Sort the following complexity categories from least to most complex i Constant O 1 ii Cubic O n3 iii Exponential O 2n iv Linear O n v Logarithmic O log n vi Quadratic O n2 f How are the following complexity categories similar O n2 O n4 O n3 O n12 O n99 E Calculating Big O functions What is the asymptotic complexity of the function f below using big O notation when the complexity of f and g are as shown f n g n h n a b c d h n n 1 g n 2n h n 3n g n 4n2 h n log n g n 5 h n 8 n g n 2n n f n O f n O f n O f n O 2 F Finding critical regions 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 f n O b for i 1 i n i i 2 f n O c for i 0 i n i for j 1 j n j j 2 f n O d for i 0 i n 2 i for j 0 j 100 j j 2 for k 1 k 3 n k f n O e for i 0 i n i i 2 for j 1 j n j f n O f for i 0 i n 2 i for j 0 j n j j 2 for k 1 k 5000 k k 5 for j 0 j n j j 1 f n O 3 Problem 3 Recursive Algorithms G Recursion a Describe the difference between an iterative and recursive algorithm b What are the 2 main parts of a recursive algorithm c Name 4 requirements for recursive algorithms to work correctly d Name 2 advantages 2 disadvantages of recursive algorithms H Legality of recursive code For each of the following codes describe what result is returned when foo n is invoked If no result is returned explain why I a int foo int n return foo n 1 foo n b int foo int n if n 1 return 1 return foo n 1 foo n c int foo int n if n 1 return 1 return 1 foo n 1 foo n d int foo int n if n 1 return 1 return foo n foo n e int foo int n if n 1 return 1 return foo n 1 f n 1 foo n Writing recursive code you may use helper functions a Write a recursive function to search an unsorted array for a number k public static boolean findNum int k int array b Write a recursive function to calculate the sum of an array of ints public static int sumArray int array c Write a recursive function to determine whether an array of ints is sorted ascending public static boolean sortedArray int array 4 Problem 4 Linear Data Structures J Taxonomy properties a Describe the main difference between linear and hierarchical data structures b Describe the main difference between a linked list and an array c Describe the main difference between a queue and a stack d Describe a circular linked list K Given the following Java class definition for a singly linked list Class Node int myValue Node next Class LinkList Node head first node in list Node find int k void insertHead Node n void insertTail Node n void removeTail Write the following code a b c d e f find k Find a node with myValue k in a linked list insertHead n Insert node n at the head of a linked list insertTail n Insert a node n at the tail of a linked list removeTail Delete the node at the tail of a linked list Which 2 methods in the LinkList class can be used to implement a queue Which 2 methods in the LinkList class can be used to implement a stack 5 Problem 5 Maps Hashing L Sets maps a What is the difference between a set and a map b What is the difference between a map and a hash table c How are maps useful d Given the following TreeMap API show how to write code to construct a TreeMap storing String objects for actor names with movie titles The TreeMap should allow movie names to be used to look up lead actor names assuming each move has a single leading actor public class TreeMap TreeMap Object get Object key Object put Object key Object value Object remove Object key TreeMap myDB new TreeMap void addMovie String leadActor String movie write code to add leading actor name for movie to TreeMap String findLeadActor String movie write code to find String for leading actor name for movie M Hashing a What is a hash function b What is a desirable property of hash functions c What is a perfect hash function d What is a collision e What is the relationship between the hashCode and equals methods in Java 6
View Full Document
Unlocking...