CSC115 Fundamentals of Programming II | Java代写 | midterms代考 | UVic维多利亚大学

Page 1 of 11
CSC 115
Midterm Exam #2:
Sections: A01 and A02
Monday, June 29th, 2020
Name:__________________________________________________(please print clearly!)
UVic ID number:_______________________________________________
Signature:_______________________________________________________
Exam duration: 60 minutes
Instructor: Anthony Estey
Students must check the number of pages in this examination paper before
beginning to write, and report any discrepancy immediately.
 We will not answer questions during the exam. If you feel there is an error or
ambiguity, write your assumption and answer the question based on that assumption.
 Answer all questions on this exam paper.
 The exam is closed book. No books or notes are permitted.
No electronic devices of any type are permitted.
 The marks assigned to each question and to each part of a question are printed within
brackets. Partial marks are available.
 There are eleven (11) pages in this document, including this cover page.
 Page 11 is left blank for scratch work. If you write an answer on that page, clearly
indicate this for the grader under the corresponding question.
 Clearly indicate only one answer to be graded. Questions with more than one answer
will be given a zero grade.
 It is strongly recommended that you read the entire exam through from beginning to
end before beginning to answer the questions.
 Please have your ID card available on the desk.
Page 2 of 11
Part 1: Linked Lists (14 marks)

1. Examine the following Nodes linked together, with Node pointers head, a, and b:
   Write code to update next reference arrows to the following:
   a) Write your code to in the box below:
   b) In the second diagram, what is the order the nodes are visited, beginning at head
   and traversing through the other nodes until the end of the sequence?
   Page 3 of 11
2. Implement the addFront method for a singly-linked list with the Node class defined
   below, in which Nodes only have a reference to the PREVIOUS Node in the list.
   In the LinkedList class implementation, shown below, there is only a tail reference
   variable. Note: there is NO HEAD reference variable.
   a) Based on these restrictions, complete the implementation for the addFront method.
   (more space on next page)
   Page 4 of 11
   b) What is the growth rate of the addFront method in Big-Oh terms? Assume 𝑛
   represents the number of elements in the list. Circle one answer
   𝑂(1)
   𝑂(log 𝑛)
   𝑂(𝑛)
   𝑂(𝑛
   2
   )
   𝑂(𝑛
   3
   )
   Page 5 of 11
   Part 2: Recursion (7 marks)
3. Complete a RECURSIVE implementation of the getPosition method for a doublylinked list with the Node class defined below:
   For this question the LinkedList class has head and tail references.
   ( The problem description is continued on the next page. )
   Page 6 of 11
   The getPosition method is given a node from the linked list, and returns the
   number of places from the front of the list the node is positioned. For example:
   Example 1: when Node 𝑛 shown below is passed to getPosition, 0 is returned:
   Example 2: when Node 𝑛 shown below is passed to getPosition, 3 is returned:
   public int getPosition (Node n) {
   }
   Page 7 of 11
   Part 3: Stacks (9 marks)
4. For this question you will work with an instance of the IntegerStack class, which is
   an implementation of the Stack interface shown below:
   You will receive marks for:

• returning the right value representing the number negative integers counted
  (focus on this first)
• maintaining the order and contents of the stack (when the value is returned, s
  should contain the same number of elements, in the same order, as it did originally).
  You are allowed to create any other variables, including another MT2Stack, in your
  implementation.
  Assume all of the methods specified in the Stack Interface have been implemented
  correctly in the IntegerStack class. There is no isFull method as the implementation
  allows for an unlimited number of elements to be inserted.
  Complete the implementation of the countNegatives method specified below, which
  takes a reference to an IntegerStack as a parameter and returns a count of the number
  of negative numbers found in the stack.
  Note: The countNegatives method is a static method defined in a DIFFERENT class than
  IntegerStack.java.
  Page 8 of 11
  Similar to Assignment 4, you can use any of the Stack methods on the IntegerStack
  variable s, (ie. s.push(x) or s.pop()). You may create any other variables, including
  another IntegerStack, in your implementation of the countNegatives method.
  You will receive marks for the following:
• returning the correct value representing the number negative integers found in the
  given stack (focus on this first)
• maintaining the order and number of elements in the stack when the value is
  returned (when the result is returned, the stack referenced by s should contain the
  same number of elements, in the same order, as it did originally).
  public static int countNegatives (IntegerStack s) {
  }
  Page 9 of 11
  Part 4: Exceptions (10 marks)

1. Carefully examine the following three methods, defined below:
   For this question you will be determining if different outputs are possible by calling
   method1 with different input values for x, y, and z.
   For example, your answer might be: method1(1, 2, 3);
   Page 10 of 11
   a) Is it possible to call method1 and produce only output “Caught A in method1”?
   If so, provide an example method1 call, if not, simply write no.
   b) Is it possible to call method1 and produce only output “Caught B in method1”?
   If so, provide an example method1 call, if not, simply write no.
   c) Is it possible to call method1 and produce only output “Caught C in method1”?
   If so, provide an example method1 call, if not, simply write no.
   d) Is it possible to call method1 and produce only output “Caught B in method2”?
   If so, provide an example method1 call, if not, simply write no.
   e) Is it possible to call method1 and have it complete execution without any exceptions
   being thrown? If so, provide an example method1 call, if not, simply write no.
   f) Is it possible to call method1 and have ExceptionA, ExceptionB, or ExceptionC be
   thrown and never caught? If so, provide an example method1 call, if not, write no.
   g) Is it possible to call method1 and produce output: “Caught A in method1” followed
   by “Caught B in method1”. If so, provide an example method1 call, if not, write no.
   h) Is it possible to call method1 and produce output: “Caught B in method2” followed
   by “Caught B in method1”. If so, provide an example method1 call, if not, write no.
   i) Is it possible to call method1 and produce output: “Caught B in method2” followed
   by “Caught C in method1”. If so, provide an example method1 call, if not, write no.
   j) Is it possible to call method1 and produce output: “Caught C in method1” followed
   by “Caught B in method1”. If so, provide an example method1 call, if not, write no.
   Page 11 of 11
   … Left blank for scratch work…
   END OF EXAM
   Question Value Mark
   Part 1 14
   Part 2 7
   Part 3 9
   Part 4 10
   Total 40

https://heat.csc.uvic.ca/coview/course/2019091/CSC115