cs110_sample_written_exam2

CS110 Written Exam 2 Sample Name: Instructions 1. Write your name at the top of the first page and your initials at the bottom of every page. 2. When you are done, return the exam with all the pages, arranged in ascending order. Do not staple the exam. 3. This is a closed-book exam. No form of communication is permitted (eg, talking, texting, etc.), except with the course staff. 4. No electronic devices are permitted. 5. There are 25 multiple-choice questions in this exam, each worth 3 points. 6. The answer to each question must be marked with a pencil as shown in the following example. It will be considered incorrect otherwise. Example. What is Albert Einstein’s miracle year? A 1879 B 1900 C 1905 D 1917 E 1955 7. You may use the blank spaces for any scratch work. 8. Discussing the exam contents with anyone who has not taken the exam is a violation of the academic honesty code. Problem 1. If s is a string object, s.replace(u, v) returns a string with all occurrences of u in s replaced with v , and s.find(u) returns the lowest index in s where u is found, or -1 . For example, ’abba’.replace(’b’, ’a’) returns ’aaaa’ , ’abba’.find(’b’) returns 1 , and ’abba’.find(’z’) returns -1 . Consider the following functions: def f(x, y, z): return x.replace(y, z) def g(x, y= ’abcdr ’ ): z = 0 for v in y: z += x.find(v) return z a. What does f(’abracadabra’, ’abcdr’[1], ’vwxyz’[4]) return? A ’ayracadayra’ B ’zbrzczdzbrz’ C ’azracadabra’ D ’abwacadabwa’ E ’azracadazra’ Initials: 1 / 8

CS110 Written Exam 2 Sample b. What does g(’abracadabra’) return? A 15 B 11 C 13 D 14 E 12 c. What does g(’abracadabra’, ’parrot’[2:4]) return? A 4 B 2 C 1 D 3 E 0 d. What does g(f(’abracadabra’, ’abcdr’[3], ’vwxyz’[4])) return? A 7 B 1 C 6 D 2 E 4 Problem 2. Consider the following functions: def f(x): st = SymbolTable () for v in x: if v in st: st[v] += 1 else : st[v] = 1 return st def g(x): return sum (f(x). values ()) def h(x): y = f(x) z = max (y.values ()) for v in y.keys (): if y[v] == z: return v return -1 Initials: 2 / 8

CS110 Written Exam 2 Sample quadratic.Quadratic Quadratic(a, b, c) constructs a quadratic function q given the values of the coefficients a , b , and c q.coeffs() returns the coefficients of q as a tuple q[x] returns the value of q evaluated at x (eg, x 2 + 2 x + 3 evaluates to 6 at x = 1) q.root1() returns the first root - b + √ b 2 - 4 ac 2 a of q q.root2() returns the second root - b - √ b 2 - 4 ac 2 a of q p == q returns True if p and q represent the same quadratic function (ie, their coefficients are the same), and False otherwise p + q returns a Quadratic object representing sum of quadratic functions p and q (eg, if p = - x 2 + 2 x + 3 and q = 2 x 2 - 4 x - 2, then p + q = x 2 - 2 x + 1) str(p) returns a string representation of q (eg, "1x^2 + 2x + 3" ) Now consider the quadratic function q = x 2 - 7 x + 12. a. How do you create a Quadratic object to represent q ? A q = Quadratic([1, -7, 12]) B q = Quadratic(1, 12, -7) C q = Quadratic([1, 12, -7]) D q = [1, -7, 12] E q = Quadratic(1, -7, 12) b. What is the value of the expression max(q.coeffs()) ? A 1 B 12 C 7 D -7 E 6 c. What is the value of the expression q[5] ? A 12 B 1 C -10 D -7 E 2 Initials: 4 / 8

CS110 Written Exam 2 Sample d. What does the expression q[5] translate to internally? A __getitem__(q, 5) B q.__getitem__(self, 5) C Quadratic.__getitem__(q, 5) D q.__getitem__(5) E __getitem__(self, 5) e. Which of the following is a root of q ? A 5 B 7 C 3 D 9 E 1 f. If u and v are Quadratic objects, what does the expression u == v translate to internally? A u.__eq__(v) B u.__eq__(self, v) C __eq__(self, u, v) D __eq__(u, v) E Quadratic.__eq__(u, v) g. If u , v , and w are Quadratic objects, what does the expression u + v + w translate to internally? A u.__add__(v.__add__(w)) B Quadratic.__add__(u, v, w) C (__add__(u, v)).__add__(w) D (u.__add__(v)).__add__(w) E __add__(u, v, w) h. What is the expression for computing the sum of the two roots of q ? A root1(q) + root2(q) B root(q, 1) + root(q, 2) C q.root(1, 2) D q.root(1) + q.root(2) E q.root1() + q.root2() Problem 4. Consider sorting the following array of strings a using insertion sort (shown below), by making the call sort(a) : Initials: 5 / 8

CS110 Written Exam 2 Sample A 576 B 1536 C 192 D 768 E 384 b. What is the running time classification for the program? A Linear B Logarithmic C Quadratic D Linearithmic E Cubic Problem 6. Suppose that a minus sign in the input indicates pop the stack and write the return value to standard output, and any other string indicates push the string onto the stack. Further suppose that following input is processed: A B - C D - E F G - - H I J - - - K L - M N O - a. What is the fifth string in standard output? A J B G C I D F E H b. What are the contents (top to bottom) left on the stack? A A C E K M N B N M K E C A C M K E C A N D C E K M N A E K E C A N M Problem 7. Suppose that a minus sign in the input indicates dequeue the queue and write the return value to standard output, and any other string indicates enqueue the string into the queue. Further suppose that following input is processed: A B - C D - E F G - - H I J - - - K L - M N O - Initials: 7 / 8

CS110 Written Exam 2 Sample a. What is the last string in standard output? A J B G C F D I E H b. What are the contents (front to back) left on the queue? A O N M L K J B M K E C A N C J K L M N O D C E K M N A E K E C A N M Answers Problem 1. E, C, A, C Problem 2. E, D, B, C Problem 3. E, B, E, D, C, A, D, E Problem 4. D, E, A Problem 5. D, C Problem 6. A, B Problem 7. D, C Initials: 8 / 8