Midterm 2 Practice Problems — CS 112, Boston University

pdf

School

Boston University *

*We aren’t endorsed by this school

Course

112

Subject

Computer Science

Date

Jan 9, 2024

Type

pdf

Pages

Uploaded by andrewleenyk

12/17/23, 8:17 PM Midterm 2 Practice Problems — CS 112, Boston University https://www.cs.bu.edu/courses/cs112/midterm_practice-2.html 1/10 Midterm 2 Practice Problems Solutions will be posted under Other Content on Blackboard as we get closer to the exam. These problems are not comprehensive, so make sure to review all of the relevant materials. Recursion 1. Consider the following method: What is returned by the call test(15, 4) ? How many times is the method called during the execution of test(15, 4) – including the initial call? 2. Write a recursive static method named sumReciprocals that takes as its only parameter an integer n that you can assume is positive, and that uses recursion (no loops!) to compute and return a ﬂoating-point value that is the sum of the reciprocals of the integers from 1 to n . For example, sumReciprocals(2) should return 1.5 , which is 1/1 + 1/2 , and sumReciprocals(4) should return approximately 2.0833 , which is 1/1 + 1/2 + 1/3 + 1/4 . 3. Write a recursive static method called removePadding() that takes a string s and that uses recursion to return a new string in which all leading and trailing spaces have been removed. For example, removePadding(" hello world ") should return "hello world" . Recursive Backtracking 1. A program for recursive backtracking includes a method similar to this one: public static int test( int a, int b) { if (a < b) { return 0 ; } else { return 1 + test(a-b, b); } public boolean key_function( int i) { if (i > imax) { return true; } for ( int alternative = 0 ; alternative < n; alternative++) {

12/17/23, 8:17 PM Midterm 2 Practice Problems — CS 112, Boston University https://www.cs.bu.edu/courses/cs112/midterm_practice-2.html 2/10 The blank should be replaced by: a. is_safe(i) b. apply_alt(alternative + 1) c. key_function(alternative + 1) d. key_function(i) e. key_function(i + 1) Big-Oh Questions 1-3 involve the following method: if (is_valid(alternative, i)) { apply_alt(alternative); if (_________________) { // what goes here? return true; } remove_alt(alternative); } } return false; } public static int mystery( int a[]) { int n = a.length; int result = 0 ; for ( int i = 1 ; i < n; i++) { int x = a[i]; // Question 2 int sum = 0 ; for ( int j = 0 ; j < 3 ; j++) { sum *= a[i]; // Question 3 } result += sum; int j = i; while (j > 0 ) { result += a[j]; // Question 4 j--; } }

12/17/23, 8:17 PM Midterm 2 Practice Problems — CS 112, Boston University https://www.cs.bu.edu/courses/cs112/midterm_practice-2.html 3/10 1. What is the big-O expression for the number of times that the line is executed? a. O ( n ) b. O ( n ²) c. O ( n log( n )) d. O (log( n )) e. O ( n !) 2. What is the big-O expression for the number of times that the line is executed? a. O ( n ) b. O ( n ²) c. O ( n log( n )) d. O (log( n )) e. O ( n !) 3. What is the big-O expression for the number of times that the line is executed? a. O ( n ) b. O ( n ²) c. O ( n log( n )) d. O (log( n )) e. O ( n !) Sorting return result; } int x = a[i]; sum *= a[i]; result += a[j];

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

12/17/23, 8:17 PM Midterm 2 Practice Problems — CS 112, Boston University https://www.cs.bu.edu/courses/cs112/midterm_practice-2.html 4/10 1. The following array is to be sorted using insertion sort: Which of the following shows the contents of the array at the end of one of the iterations of the algorithm? a. { 5, 10, 8, 35, 9, 29, 18} b. { 5, 8, 9, 35, 10, 29, 18} c. { 8, 9, 10, 35, 18, 29, 5} d. { 8, 10, 18, 35, 9, 29, 5} e. {10, 8, 18, 9, 29, 5, 35} 2. Here is an array that has just been partitioned by the first step of quicksort: Which of the following statements is correct? a. 5 could be the pivot, but 7 could not be. b. 7 could be the pivot, but 5 could not be. c. Neither 5 nor 7 could be the pivot. d. Either 5 or 7 could be the pivot. 3. The following array is to be sorted: Which of the algorithms that we discussed in lecture will cause the array to be ordered as follows at an intermediate stage in the sorting process? a. insertion sort b. bubble sort c. quicksort (with an initial pivot of 13) d. selection sort e. merge sort {18, 10, 8, 35, 9, 29, 5} {3, 0, 2, 4, 5, 8, 7, 6, 9} {19, 22, 11, 13, 53, 34, 25} {19, 11, 13, 22, 34, 25, 53}

12/17/23, 8:17 PM Midterm 2 Practice Problems — CS 112, Boston University https://www.cs.bu.edu/courses/cs112/midterm_practice-2.html 5/10 4. Through experiment, you determine that selection sort performs 5000 comparisons when sorting a array of some size k . If you doubled the size of the array to 2 k , approximately how many comparisons would you expect it to perform? a. 5000 b. 10000 c. 20000 d. 40000 e. it would depend on the contents of the array 5. Through experiment, you determine that selection sort performs 5000 moves when sorting a array of some size k . If you doubled the size of the array to 2 k , approximately how many moves would you expect it to perform? a. 5000 b. 10000 c. 20000 d. 40000 e. it would depend on the contents of the array 6. The following array is to be sorted: a. During the execution of quicksort, what would the array look like after the first call to the partition() method? b. During the execution of quicksort, what would the array look like after the second call to the partition() method? c. After the initial pass of bubble sort, how would the array be ordered? d. Ignore this question: Assume that the initial phase of Shell sort uses an increment of 3. At the end of that phase, how would the array be ordered? e. After three passes of selection sort, how would the array be ordered? f. After four passes of insertion sort, how would the array be ordered? g. During the execution of mergesort, what would the array look like after the third call to the merge() method? Linked Lists {17, 53, 71, 36, 46, 41, 23, 12}

12/17/23, 8:17 PM Midterm 2 Practice Problems — CS 112, Boston University https://www.cs.bu.edu/courses/cs112/midterm_practice-2.html 6/10 Questions 1 and 2 involve linked lists of integers that are constructed from nodes whose class definition begins as follows: 1. You want to add a method to the Node class that takes two parameters: a reference to the first node in a linked list (or null if the list is empty) an integer x The method should insert a node containing x at the front of the list, and it should return a reference to the new front of the list. Which of these methods does this correctly? option I: option II: option III: public class Node { private int val; private Node next; public Node() { this .val = 0 ; this .next = null; } ... } public static Node insertFront(Node first, int x) { first = new Node(); first.val = x; first.next = first; return first; } public static Node insertFront(Node first, int x) { Node n = new Node(); n.val = x; n.next = first; return n; }

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

12/17/23, 8:17 PM Midterm 2 Practice Problems — CS 112, Boston University https://www.cs.bu.edu/courses/cs112/midterm_practice-2.html 7/10 a. only I b. only II c. only III d. I and II, but not III e. II and III, but not I 2. The intent of the method below is to delete the last node in the linked list to which the parameter first refers: Which of the following describes the subset of linked lists for which this method works correctly? a. no linked lists b. all nonempty linked lists c. all linked lists with more than one node d. the empty list and all linked lists with more than one node e. all linked lists 3. A doubly linked list is constructed from nodes that are instances of the following class: public static Node insertFront(Node first, int x) { Node n = new Node(); first = n; n.val = x; n.next = first; return first; } public static void removeLast(Node first) { Node p = first; Node q = p.next; while (q.next != null) { p = q; q = q.next; } p.next = null; } public class DNode { private char ch; private DNode next;

12/17/23, 8:17 PM Midterm 2 Practice Problems — CS 112, Boston University https://www.cs.bu.edu/courses/cs112/midterm_practice-2.html 8/10 The next field holds a reference to the next node in the linked list, and the prev field holds a reference to the previous node in the linked list. Below is a list of three of these nodes, along with two reference variables, n and p , that refer to specific nodes in the list: Which of the following expressions does not refer to the third node in the list? a. p.next b. n.next.next c. p.prev.next d. p.prev.next.next e. n.next.next.prev.next 4. The diagram below suggests how we could implement a linked list in which we maintain a reference to both the first and last nodes in the linked list: Which of the following operations would be ineﬃcient to carry out when there are a large number of elements in the linked list? a. insertion at the end to which front refers b. insertion at the end to which rear refers private DNode prev; }

12/17/23, 8:17 PM Midterm 2 Practice Problems — CS 112, Boston University https://www.cs.bu.edu/courses/cs112/midterm_practice-2.html 9/10 c. deletion from the end to which front refers d. deletion from the end to which rear refers 5. The diagram below shows a linked list of characters that is constructed from instances of the StringNode class from lecture: In addition, we have included two variables that each store a reference to one of the nodes in the linked list, along with the memory address of each node. You should assume that the ch field has the same address as the node itself, and that the address of the next field is 2 bytes after the beginning of the node. a. What is the memory address of the field given by the expression head.next.next ? b. What is the value of the expression head.next.next ? c. Write one or more lines of code that remove the node containing the character 's' from the list. d. Modify the diagram to reﬂect the results of executing the following lines on the original version of the list (before the 's' was removed): 6. This question involves linked lists of integers that are constructed from nodes of the following class: a. Write a static method named numEvenRec() that takes a reference to the first node in a linked list of integers and uses recursion to determine and return the number of even values in the list. q = q.next; q.next = head; public class Node { private int val; private Node next; }

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

12/17/23, 8:17 PM Midterm 2 Practice Problems — CS 112, Boston University https://www.cs.bu.edu/courses/cs112/midterm_practice-2.html 10/10 b. Write a static method named numEvenIter() that takes a reference to the first node in a linked list of integers and uses iteration to determine and return the number of even values in the list. 7. Write a static method called everyOther() that is a member of the StringNode class. It should take a reference to the first node in a linked-list string, and it should create and return a reference to a new linked-list string that contains every other character from the original string. The original linked list should not be modified. You may use either recursion or iteration.

Midterm 2 Practice Problems — CS 112, Boston University

Related Documents