Grader Use Only 1 2 3 4 5 6 7 Total CMSC132 Summer 2007 Midterm 1 6 6 8 15 15 25 25 100 First Name Last Name Student ID 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 Total point value is 100 points Answer essay questions concisely using 1 or 2 sentences Longer answers are not necessary and are discouraged WRITE NEATLY If we cannot understand your answer we will not grade it i e 0 credit 1 Problem 1 6 pts Testing a 2 pts What is clear box testing Briefly explain b 2 pts What is black box testing Briefly explain c 2 pts What is regression testing Briefly explain Problem 2 6 pts Hashing a 2 pts Name two hashing approaches discussed in class b 2 pts When defining a hashCode for a class could two objects have the same hash code Briefly explain c 2 pts Describe the Java hashCode contract Problem 3 8 pts Big O 2 a 6 pts Calculate the asymptotic complexity of the code snippets below using big O notation with respect to the problem size n i for int i 0 i n i for int k 0 k 20 k f n O ii for int i 0 i n 2 i for int j 1 j n j j 2 f n O iii for int i 1 i 100 i f n O b 2 pts List the following big O expressions in order of asymptotic complexity with the lowest complexity first O nlog n O 1 O log n Problem 4 15 pts Java Language Features 3 O 2n O n3 a b 2 pts Which Java language construct supports procedural abstraction 2 pts Assume that class B extends class A Is the following assignment VALID or INVALID List A k new List B c 2 pts Assume that class B extends a class A Is the following assignment VALID or INVALID A k new B d 2 pts What method must be defined for a class that implements the Iterable interface e 2 pts An inner class has access to the private fields of the enclosing class True or False f g 2 pts A code segment involving a loop could potentially have an infinite number of flow paths True or False 3 pts Rewrite the following loop using the new for loop construct String members Mary John Peter for int i 0 i members length i System out println members i 4 Problem 5 15 pts Recursion 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 5 Problem 6 25 pts Java Collections Framework The Course class keeps track of students registered to different sections of a course The class uses a HashMap to map a section number to a set of students registered in that section public class Course private Map Integer Set String allSections MAP DEFINITION HERE public void addStudent Integer sectionNumber String name You must implement this method public boolean removeStudent String name You must implement this method What You Must Implement 1 Provide a map definition that uses hashing This definition would appear where you see the comments MAP DEFINITION HERE above 2 Implement the addStudent method This method adds a student to the set associated with the specified section number If there is not set associated with the section one will be added to the map 3 Implement the removeStudent method The method will return true if the specified student is found in the map and it is removed from the map Otherwise the method will return false If after removing the student the corresponding section is empty then the section must be removed from the map The following are map methods that you may find helpful for this problem V get Object key Returns the value to which this map maps the specified key V put K key V value Associates the specified value with the specified key in this map Set K keySet Returns a set view of the keys contained in this map boolean isEmpty Returns true if this map contains no key value mappings The following are set methods that you may find helpful for this problem boolean contains Object o Returns true if this set contains the specified element boolean add E o Adds the specified element to this set if it is not already present V remove Object key Removes the mapping for this key from this map if it is present boolean isEmpty Returns true if this set contains no elements 6 Use the next page to provide your answers There is another problem on the reverse side 7 Problem 7 25 pts Linked Lists Implement the methods below based on the following Java class definitions public class MyLinkedList T private class Node E private E data private Node E next private Node T head a Define a constructor for the MyLinkedList class that creates an empty list b Define a non static method named addAtEnd that has the following signature public void addAtEnd T element The method adds the element to the end of the list c Define a non static method named printReverse that has the following signature public void printReverse The method prints the element in reverse order You may add an auxiliary method You can use the rest of this page and the next one to provide your answers 8 9 10
View Full Document
Unlocking...