Popular in Course
verified elite notetaker
Popular in ComputerScienence
This 11 page Bundle was uploaded by Dustin Luu on Monday August 18, 2014. The Bundle belongs to a course at a university taught by a professor in Fall. Since its upload, it has received 312 views.
Reviews for 187-midterm1-v1-SOLUTIONS.pdf
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 08/18/14
CMPSCI 187 Midterm 1 March 4 2014 89 Points 75 Minutes 11IPages SOLUTIONS PJanux StudentIIL Discussion Time TA Name Probk nz 32 33 34 Tbtal hdaxhnunr 4 4 4 12 Score I True False 2 points each Use opscan A True B False 1 10 11 12 13 14 15 16 The item that has been in a stack the longest is always at the top FALSE bottom Thrown exceptions are always fatal ie the program will stop running FALSE They can be caught and handled A class that implements an interface can include methods that are not required by the interface TRUE Constructors are classi ed as observer methods FALSE The base case does not exist or is not reached when there is in nite recursion TRUE Generics are used in Java because their use allows for greater code re use TRUE Abstraction is used to expose the internal complexity of a software module FALSE Abstraction is used to hide the internal complexity of a software module Observer methods return information about the state of an object TRUE A node in a linked list is linked together using a reference to another node of a different type FALSE A node in a linked list is linked together using a referene to another node of the same type Linked lists are typically used to implement unbounded data structures TRUE A linked list is terminated by the last node whose link references a negative integer FALSE A linked list is terminated by the last node whose link references null A NullPointerException is thrown by Java whenever a null valued reference variable is passed to a method FALSE The exception is thrown when a null valued reference variable is used as if it referred to an object instance instead Eg you attempt to access a eld or method speci ed by the variable s type References pointers links addresses and objects are all terms that refer to the same thing FALSE The rst four are the same Objects are what they refer to Reference variables require more space to store than variables of a primitive type because they hold objects FALSE Reference variables hold references to objects which aren t different in size than most primitive types Imagine your professor gives a programming assignment that will be graded solely based on the Big O time complexity of the single method you re asked to write Your solution loops 10 times over an array of length n and does little else Your friend found a solution that loops over the same array just 2 times Your friend s grade should be better than yours FALSE They are both On where n is the length of the array For a non empty stack top returns the value of the most recent item popped from the stack FALSE II Multiple Choice 3 points each Use opscan 17 Imagine you are given two interfaces F00 and Bar where Bar extends Foo Suppose Foo declares meth ods flip flop fro and Bar declares methods bring back brush brace You are writing a new class that implements Bar Assuming your class de nition compiles properly how many methods will need to be implemented A exactly 3 B exactly 4 C 4 or more D exactly 7 E 7 or more lt CORRECT ANSWER 18 In the linked list version of the stack class which operations will require On time for a stack containing 77 elements A isempty B peek C pop D push E None of the above lt CORRECT ANSWER 19 Consider the following operations on an object k where k is a reference to a non null object of type NodeltStringgt ksetLinkkgetLink Which of the following is true after executing the above statement A k links to the same node it linked to before lt CORRECT ANSWER B It throws an Array0ut0fBoundsExcept ion C k now links to the next node in the linked list D It throws a NullPointerException E None of the above 20 A stack is what type of data structure a First in rst out b Last in last out c First in last out lt CORRECT ANSWER 21 The length of the following array is int array new int 5 4 5 lt CORRECT ANSWER 6 22 In terms of the number of elements 77 in the list what is the Big O running time of a method that inserts an element at the end of a linked list that only has a reference to its rst element the head A 01 B Ol0gn C On lt CORRECT ANSWER D On2 E None of the above 23 Imagine you are using a stack to evaluate an arithmetic post x expression So far you have evaluated this part of the expression 2 2 3 9 2 4 8 Which of the following illustrates the state of the stack at this point in the evaluation A bottom 2 5 9 lt CORRECT ANSWER B bottom 2 5 7 C bottom 2 D bottom 2239248 E None of the above 24 Which of the post x expressions below is equivalent to this in x expression 1 X 2 y 3 z A1x2y3zlt CORRECTANSWER B1x2y3z C1x2y3 D1x2yz E None of the above N 00 25 Which Java keyword is used to specify that a method may raise an exception A catch B try C throw D throws lt CORRECT ANSWER E None of the above 26 Which expression below describes the number of stars printed when we call fun5 public static void funint n int i 0 if n gt 1 return funn1 for i O i lt n i Systemoutprintlnquot quot IX 0 I3 1 C123 D1234 E 1 2 3 4 5 lt CORRECT ANSWER 27 Consider the implementation of a linked list with a recursive implementation of its remove method Which conditions must this recursive method check as base cases A check for empty list B check for matching node and list length C empty list and list length D check for end of list and matching node lt CORRECT ANSWER E None of the above 28 Assume you are given a standard NodeltTgt type Given a variable A that is a reference to the Node at the start of this linked list shown below what does mystery1 A return 2 gt 4 gt 6 gt 8 gt 10 gt null public int mysteryint v NodeltTgt n ifn null return v return mysteryv2 ngetNext IX 1 I3 8 C 16 D 32 lt CORRECT ANSWER E None of the above 29 Consider the following method public String gnirtsString s if sequalsquotquot return s else return gnirtsssubstring1 scharAtO How many recursive calls does the gnirts method perform if it is invoked with the string quotracecarquot as its argurnent Note The substring method works like this quotunhappyquot substring2 returns quothappyquot IX 7 I3 1 CD 6 D 8 lt CORRECT ANSWER E None of the above 30 If n gt 0 how many times will biPower be called in order to evaluate biPower n including the initial call public int biPowerint n if n 1 return 2 else return 2 biPowern 1 IX 2n B n lt CORRECT ANSWER CD 2 I7z 1 31 What is the result of executing the main function below public static void fooint i throws RuntimeException Systemoutprintquot1quot if 1 lt 0 throw new RuntimeExceptionquot2quot Systemoutprintquot3quot public static void mainString args try Systemoutprintquot4quot foo1 Systemoutprintquot5quot catchRuntimeException e Systemoutprint egetMessage ystemoutprintquot6quot IX 412 B 4126 lt CORRECT ANSWER 3 41236 I 41235 E 41256 III Short Answer 4 points each Write your answer on the exam pages 32 Consider a generic Stack implementation to which you are adding the following method mysteriously named mystery public void mysteryint k T elem StackltTgt hold new StackltTgt for int i0 i lt k1 i holdpushthistop thispop thispop thispushT while holdisEmpty thispushholdtop holdpop Suppose you have a stack yourStack of characters that looks like this Bottom X T G S C a Draw the stack that results from calling yourStackmystery3 quotVquot Bottom X T V S C b What would be an appropriate name for the mystery function ReplaceAtPosition 33 Consider the following subroutine static void printStuffint level if level 0 Systemoutprintquotquot else Systemoutprintquotquot printStufflevel 1 Systemoutprintquotquot printStufflevel 1 Systemoutprintlnquotquot Show the output that would be produced by each of the following subroutine calls 0 printStuffO o printStuff1 o printStuff2 0 printStuff3 lllllll The solution above received full credit however since the last print statement of the method is println and not print the correct answers for printStuff2 and printStuff3 are the following for which we offered one point extra credit 0 printStuff2 l l l o printStuff3 l l l l l l l 34 Consider the following Java interface for a stack and the sequence of statements that use it public interface StackltTgt void pushT element void pop T peek StackltIntegergt k new StackImp1ltIntegergt StackltIntegergt j new StackImp1ltIntegergt StackltIntegergt i new StackImp1ltIntegergt push3 push6 push9 push2 push4 push6 push12 k push15 push2 1 3 int result kpeek kpop WLL 39 39 Wlt U W W W State the Value of result and draw pictures of the nal states of the stack objects created resultis 2 i j and k are references to the same stack with nal contents l30tt07n 3 6 9 12 15 The stack originally referenced as j had nal contents of l30tt0nz 2 4 6 although it is not longer referenced at the end of the program Drawing this latter stack was not required for credit You may NOT leave the exam early Please remain quietly at your seat 10 Extra work space you may remove this page from the exam You may NOT leave the exam early Please remain quietly at your seat 11
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'