CMSC 132 Final Exam Sample Problems Spring 2017 Notes This is not intended to be an exhaustive review of all of the problems that might appear on your cid 12 nal exam Instead it is a selection of problems that we have either done in class or on previous exams that require additional attention For example I didn t include any speci cid 12 c question on Dijsktra s algorithm use the slides that have been done so well by others and that are available to you on Elms for that topic Please use these in the spirit in which they are o ered Try them cid 12 rst in earnest Answers may be provided later 1 Using only the de cid 12 nitions provided by the References and standard Java statements write the recursive function append that takes two SLists and returns a new SList that contains the elements from both lists in their original order For example append 1 2 3 2 3 5 should return 1 2 3 2 3 5 If either list is empty the other list is returned unmodi cid 12 ed Your implementation must be recursive and should be contained in one method public static T SList T append LinkedList T list Solution public static T LinkedList T append SList T list1 SList T list2 if isEmpty list1 return list2 else return cons first list1 append rest list1 list2 1 2 Study the following class de cid 12 nition public class Item private String itemName private float unitCost private boolean isAvailable Two Items are equal only when their itemName and unitCosts properties are equal a Override the hashCode method for the Item class Solution public int hashCode int hash 0 hash this itemName hashCode new Float this unitCost hashCode return hash b The class WishList looks like public class WishList implements Iterable Item private List Item items Two WishLists are equal when the contain the same Items in the same order Override the hashCode method for the WishList class Solution Note that any reasonable positive prime number will work here public int hashCode int hash 0 int exponent 0 for Item anItem items return hash hash anItem hashCode Math pow 13 exponent Page 2 3 Examine the undirected graph below and use it to answer the following questions a Give the list of vertices encountered in an ordered Breath First traversal of the graph starting from vertex B b Give the list of vertices encountered in an ordered Depth First traversal of the graph starting from vertex B a B A C D E G F b B A C D E F G c Express the graph used in the this question formally i e as a set of Vertices and a set of Edges Solution The G V E be de cid 12 ned as the set of vertices V fA B C D E F Gg and the set of edges fe1 A B e2 A C e3 A D e4 D E e5 D G e6 E F e7 F G g Note the by convention vertices and edges are listed in their natural ordering but this is not a requirement Page 3 4 Given any 2 BinaryTrees tree 1 and tree 2 write the sameShape predicate that returns true if and only if tree 1 and tree 2 have the same shape i e each may be superimposed on the other with no apparent di erences othen that the labeling of their nodes public static T boolean sameShape BinaryTree T tree 1 BinaryTree T tree 2 Solution public static T boolean sameShape BinaryTree T tree 1 BinaryTree T tree 2 if isEmpty tree 1 isEmpty tree 2 return true else if isEmpty tree 1 isEmpty tree 2 return sameShape getLeft tree 1 getLeft tree 2 sameShape getRight tree 1 getRight tree 2 else return false Page 4 Instructions De nitionsforCMSC132Final Nouseoftry catchstatementsisallowedinanycodewritteninresponsetoanyquestiononthisexam Forrecursivemethods UseonlythestructuresprovidedintheReferencesprovidedinthisdocument Donotuseanyexternaldata structures suchasArrayLists Stacks etc withtheintentofremovingrecursionfromanyrecursivemethodthatyouwrite Noquestionthatrequiresarecursiveimplementationwillallowtheexplicituseofanyiterativestatement Noauxiliaryorhelpermethodsshouldberequiredtorespondtoanyoftheprogrammingquestionsonthisexam Graphsearchingquestionsassumethatthenaturalorderingofverticeswillbeusedintheexpansionofadjacencies Inthecaseofnumbers assume0 1 2 andinthecaseofliteralsorStrings assumethenormalrulesofEnglish a b c Allowedde nitionsfordata structuresusedonthisexam LinkedListsUsethefollowingde nitionforquestionsregardinglinked lists Note Allofthesemethodsarestatic acceptingSList T sandelementsofanyobjecttype T publicstatic T booleanisEmpty SList T lst publicstatic T Tfirst SList T lst publicstatic T SList T rest SList T lst publicstatic T SList T cons Titem SList T lst MethodSignatureDescriptionbooleanisEmpty lst Returnstrueiflstisempty Tfirst lst Returnsthevalueofthe rstelementinlst Note itisanerrortocallthisfunctiononanemptylist SListrest lst Returnsthe tail aSListoftheelementsafterthe rstelementinalinkedlist Note callingthisfunctiononanemptylistscausesanerror SListcons ele lst ReturnsanewSListthatistheresultofaddingtheeleasits rstelement elementsarekeptintheiroriginalorder Table1 LinkedListOperations Alllinkedlistoperatorsaretransparent returningcopies 1 BinaryTreesUsethefollowingde nitionforquestionsregardingBinaryTrees publicclassBTree T publicbooleanisEmpty publicTgetValue publicbooleanisLeaf publicBTree T getLeft publicBTree T getRight MethodSignatureDescriptionbooleanisEmpty ReturnstrueifthisBTreeisempty TgetValue ReturnsthevalueonthisBTreeobject note anerrorresultsifthistreeisempty booleanisLeaf Returnstrueonlyifthistreeisa leaf hasemptyleftandrightsubtrees Note anerrorresultsifthismethodiscalledonanemptytree BTree T getLeft Returnstheleftchild Note callingthisonanemptytreethrowsanerror BTree T getRight Returnstherightchild Note callingthisonanemptytreethrowsanerror Table2 BinaryTreeOperationsOrderingRelationsUnlesstoldotherwise assumethatanyreferencestoBinarySearchTreesareorderedsuchthattheirleftcontainselementslessthanorequaltotheroot andtherightcontainselementsgreaterthantheroot AllheapsareMax Heaps unlesstoldotherwise Providedmethods classes etc AssumethatallmethodsworkasdescribedwhenansweringanyquestionsregardingLinked ListsorBinaryTreesonthisexam Donotassumethatanyothermethodsexistunlessyoude nedthem usingthesemethods Donotaddanypropertiestotheseclassde nitions 2
View Full Document
Unlocking...