This preview shows page 1-2 out of 6 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 6 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 6 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 6 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Sample midterm 3 #1Problem 1 (box and pointer).What will the Scheme interpreter print in response to the last expression in each of thefollowing sequences of expressions? Also, draw a “box and pointer” diagram for the resultof each printed expression. If any expression results in an error, circle the expressionthat gives the error message. Hint: It’ll be a lot easier if you draw the box and pointerdiagram first!(let ((x (list 1 2 3)))(set-car! x (list ’a ’b ’c))(set-car! (cdar x) ’d)x)(define x 3)(define m (list x 4 5))(set! x 6)m(define x (list 1 ’(2 3) 4))(define y (cdr x))(set-car! y 5)x(let ((x (list 1 2 3)))(set-cdr! (cdr x) x)x)178Problem 2 (Assignment, State, and Environments).Suppose we want to write a procedure prev that takes as its arg ument a procedure procof one argument. Prev returns a new procedure that returns the value returned by theprevious call to proc. The new procedure should return #f the first time it is called. Forexample:> (define slow-square (prev square))> (slow-square 3)#f> (slow-square 4)9> (slow-square 5)16Which of the fol lowing definitions implements prev correctly? Pick only one.______ (define (prev proc)(let ((old-result #f))(lambda (x)(let ((return-value old-result))(set! old-result (proc x))return-value))))______ (define prev(let ((old-result #f))(lambda (proc)(lambda (x)(let ((return-value old-result))(set! old-result (proc x))return-value)))))______ (define (prev proc)(lambda (x)(let ((old-result #f))(let ((return-value old-result))(set! old-result (proc x))return-value))))______ (define (prev)(let ((old-result #f))(lambda (proc)(lambda (x)(let ((return-value old-result))(set! old-result (proc x))return-value)))))179Problem 3 (Drawing environment diagrams).Draw the environment diagram resulting from evaluating the following expressions, andshow the result printed by the last expression where indicated.> (define x 4)> (define (baz x)(define (* a b) (+ a b))(lambda (y) (* x y)))> (define foo (baz (* 3 10)))> (foo (* 2 x))Problem 4 (List mutation).Write make-alist!, a procedure that takes as its argument a list of alternating keys andvalues, like this:(color orange zip 94720 name wakko)and changes it, by mutation, into an association list, like this:((color . orange) (zip . 94720) (name . wakko))You may assume that the argument list has an even number of elements. The result of yourprocedure requires exactly a s many pairs as the argument, so you will work by rearrangingthe pairs in the argument it self. Do not allocate any new pairs in your solution!180Problem 5 (Vectors).Suppose there are N students taking a midterm. Suppose we have a vector of size N,and each element of the vector represents one student’s score on the midterm. Write aprocedure (histogram scores) that takes this vector of midterm scores and computesa histo gram vector. That is, the resulting vector should be of size M+1, where M is themaximum score on the midterm (it’s M+1 because scores of zero are possible), and elementnumber I of the resulting vector is the number of students who got score I on the midterm.For example:> (histogram (vector 3 2 2 3 2))#(0 0 3 2) ;; no students got 0 points, no students got 1 point,;; 3 students got 2 points, and 2 students got 3 points.> (histogram (vector 0 1 0 2))#(2 1 1) ;; 2 students got 0 points, 1 student got 1 point,;; and 1 student got 2 points.Do not use list->vector or vector->list.Note: You may assume that you have a procedure vector-max that takes a vector ofnumbers as argument, and returns the largest number in the vector.Problem 6 (Concurrency).Choose the answer which best describes each of the following:(a) You and a friend decide to have lunch at a rather popular Berkel ey resturant. Sincethere is a lo ng line at the service counter, each group of people entering t he restaurantdecide to have someone grab a table while someone else waits in the line to order the food.This sounds l ike a good idea, so yo ur friend sits down at the last free table while you get inline. Unfortunately, the resturant stops ta king o rders when there are no ta bles available,and you have t o wait in line for the people ahead of you. This i s an example ofincorrect answerdeadlockinefficency (too much serialization)unfairnessnone of the above (correct parallelism)181(b) After you finally get to eat lunch, you a nd your friend decide to go to the library towork on a joint paper. The library has a policy that students who enter the library mustopen their backpacks to show that they are not bringing food into the l ibrary. They haveseveral employees doing backpack inspection, so there are several lines for people waitingto be inspected. However, today there was a bomb threat, and so the inspectors also use ahandheld metal detector to examine the backpacks. Although there are several inspectors,the library only has one metal detector. This is an example ofincorrect answerdeadlockinefficency (too much serialization)unfairnessnone of the above (correct parallelism)(c)While you are working on the paper, your friend decides to do some research for yourpaper and leaves for a few hours while you continue writing. This is an example ofincorrect answerdeadlockinefficency (too much serialization)unfairnessnone of the above (correct parallelism)182Problem 7 (Streams).In weaving, a hori zontal thread is pulled through a bunch of vertical threads. The hori-zontal thread passes over some of the vertical ones, and under others. The choice of overor under determines the patt ern of the weave.We will represent a pattern a s a list of the words OVER and UNDER, repeated as needed.Here’s an example:(OVER OVER UNDER OVER UNDER UNDER)The pattern may be of any length (it depends on the desired width of the woven cloth),but it must contain at least one OVER a nd at least one UNDER.Write a Scheme expression to compute the (infinite) stream of all possible


View Full Document

Berkeley COMPSCI 61A - Midterm

Documents in this Course
Lecture 1

Lecture 1

68 pages

Midterm

Midterm

5 pages

Midterm

Midterm

6 pages

Lecture 35

Lecture 35

250 pages

Lecture 14

Lecture 14

125 pages

Lecture 2

Lecture 2

159 pages

Lecture 6

Lecture 6

113 pages

Lecture 3

Lecture 3

162 pages

Homework

Homework

25 pages

Lecture 13

Lecture 13

117 pages

Lecture 29

Lecture 29

104 pages

Lecture 11

Lecture 11

173 pages

Lecture 7

Lecture 7

104 pages

Midterm

Midterm

6 pages

Lecture 8

Lecture 8

108 pages

Lab 4

Lab 4

4 pages

Lecture 7

Lecture 7

52 pages

Lecture 20

Lecture 20

129 pages

Lecture 15

Lecture 15

132 pages

Lecture 9

Lecture 9

95 pages

Lecture 30

Lecture 30

108 pages

Lecture 17

Lecture 17

106 pages

Load more
Download Midterm
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Midterm and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Midterm 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?