CS220 PP Midterm Exam, November 14, 2019 1/6 Student ID No.: _______________ 姓名(汉语):
1. [60] What will DrRacket print in response to the following expressions? If an expression produces an error message, you may just write “error”; you don’t have to provide the exact text of the message. If the value of an expression is a procedure, just write “procedure”; you don’t have to show the form in which DrRacket print the procedure.
A. ((if(eq?’22)+-)321)
B. (car ((lambda (lst) (cdr lst)) ꞌ((1 2) (3 4))))
C. (define arg 5) (define local-arg 3) (define (proc arg)
(let ((arg 2) (local-arg arg))
(list arg local-arg)))
(proc 4)
D. (define q ꞌ(list list +)) ((cadr q) 3 4)
E. (map car ‘((Terry likes you) ((Oh!)) (police line)))
F. (define a 3) (define b 4) (define c 5)
(let ((a 5) (b c)) (* a b c))
G. (define xx 7)
(let ((xx xx)(y 13)
(f (lambda (y) (+ xx y))))
(f 25))
H. (define (cube x) (* x x x)) (define bop-funs
(lambda (bop)
(lambda (f) (lambda (x) (bop (f x))))))
(((bop-funs -) cube) 3)
CS220 PP Midterm Exam, November 14, 2019 2/6 Student ID No.: _______________ 姓名(汉语):
I. (define (foo func start sent) (cond ((null? sent) ‘yes)
((equal? (func start) (car sent))
(foo func (+ 1 start) (cdr sent)))
(else sent)))
(foo (lambda (x) (* 2 x)) 1 (list 2 4 8))
J. (define mat ‘((1 3 5) (7 9 11) (13 15 17))) (define (chop m) (map cdr (cdr m)))
(chop mat)
K. (define (inc x) (+ x 1))
(define (twice func) (lambda (x) (func (func x)))) (((twice twice) (twice inc)) 3)
L. (define * /) (define + -)
(* 12 (+ 6 2))
2. [20] Assuming that all primitive procedure used take constant time, write the order of growth in time for bar? and baz with respect to n. (n is the length of list sent.)
A. Θ( )
(define (bar? sent)
(cond ((empty? sent) #f)
((equal? (car sent) ‘hi) #t)
(else (bar? (cdr sent)))))
B. Θ( )
;; bar? is defined above in A.
(define (baz sent)
(cond ((empty? sent) 0)
((bar? sent) (+ 1 (baz (cdr sent))))
(else (baz (cdr sent)))))
CS220 PP Midterm Exam, November 14, 2019 3/6 Student ID No.: _______________ 姓名(汉语):
C. What is the result of the following expression?
(baz ‘(hi how are you? Say hi to me))
3. [20] Draw box-and-pointer diagrams that represent the results of a1. Then what is the output for the
expression b1? (What will be displayed?)
(define a1 (list 1 (list 2 3) (list 4)))
(define b1 (cons (cdr a1) (list ‘hello ‘world))) b1 _____________________________________________
4. [20] The following recursive procedure takes a list of integers and returns the number of elements that are even. It will generate linear recursive process.
(define (count-evens ints)
(cond ((null? ints) 0)
((even? (car ints)) (+ 1 (count-evens (cdr ints))))
(else (count-evens (cdr ints)))))
Rewrite this into a procedure that will generate linear iterative process by filling in the blanks.
a1
(define (count-evens-iter ints)
(define (helper input result)
(cond
(helper ints 0 ))
))
(A) (B) (C)
CS220 PP Midterm Exam, November 14, 2019 4/6 Student ID No.: _______________ 姓名(汉语):
5. [20] Write a procedure mpy-of-f-x-and-g-x that takes two numerical procedures f and g and a number x as inputs, and returns the product of applying f to x and g to x.
(mpy-of-f-x-and-g-x square cube -1) -1 ; why? (-1)2 * (-1)3 => -1
(mpy-of-f-x-and-g-x square cube 2) 32 ;why?(2)2*(2)3=>32
(define (mpy-of-f-x-and-g-x f g x)
Then generalize these examples so that the procedure you apply to the results of f and g is a parameter too. For example:
(combine-f-x-and-g-x * square cube 2)
32
(define (combine-f-x-and-g-x combiner f g x)
(A) You fill the rest of code here.
(B) You fill the rest of code here.
6. [20] Write a procedure diagonal that takes a list of sentences (a list of lists) as its argument. It should return a sentence (list) containing the first word of the first sentence, the second word of the second sentence, and so on. (Assume the sentences are long enough; don’t add error checks.)
> (diagonal ꞌ((she loves you)(tell me why)(I want to hold your hand))) ꞌ(she me to)
CS220 PP Midterm Exam, November 14, 2019 5/6 Student ID No.: _______________ 姓名(汉语):
; diagonal : list of lists -> list
; Given the list of sentences(list), pick the first word from the
; first sentence, the second word from the second sentence and so on. ; test:
;(diagonal ꞌ((I want) (You have a book) (He needs medicine to drink))) ; -> ꞌ(I have medicine)
; Your program must start with the following lines
(define (diagonal sentences)
(if (null? sentences)
)
7. [40] Ben is going to offer an abstract data type set. He will offer an abstract data set and the
following operations.
make-emptyset : aconstructorthatreturnsanemptyset
set-emtpy? : a predicate to test whether a set is empty or not
element-of-set? : (element-of-set? elm S) to determine whether elm is a member of a set S adjoin-set : (adjoin-set elm S) returns a set with original elements of S and an object elm diff–set : (diff-set S1 S2) a set whose elements are in set S1 but not in S2 (that is, S1-S2).
Notice that Ben does not include set operations union and intersection. For convenience, assume that all elements of a set are non-negative integers. For integer comparison, you can use primitive functions such as >, >=, <, and <= . Answer the following questions.
Ben represents a set as a sorted list. For example, the set {1 2 3} could be represented as the list (1 2 3), or the set {3 8 10 6} is (3 6 8 10). Followings are Ben’s implementation.
(define (make-emptyset) empty)
(define (set-empty? set) (empty? set))
(define (element-of-set? elm set) (... some implementation ...)) (define (adjoin-set elm set) (... some implementation ...)) (define (diff-set set1 set2) (... some implementation ...))
)
; You must fill in this part
CS220 PP Midterm Exam, November 14, 2019 6/6 Student ID No.: _______________ 姓名(汉语):
(a) Write a procedure (adjoin-set elm set). Your implementation must be as efficient as possible. If I can find faster implementation than yours, your score will be reduced. State the space and time complexity of your procedure in order notation: i.e., O(some function)
(b) Write a procedure (diff-set s1 s2). Your implementation must be as efficient as possible. If I can find faster implementation than yours, your score will be reduced. State the space and time complexity of your procedure in order notation: i.e., O(some function)
8. [20] We could implement a Scheme interpreter (for example, DrRacket) in two different evaluation methods: applicative order evaluation and normal order evaluation. Two different implementations may give different results for the following cases. What would a Scheme interpreter (DrRacket) print in response to the following expressions? If an expression produces an error message, you may just write “error”. If the value of an expression is a procedure, just write “procedure”. If a program does not terminate, write “loop”.
Given the following definition and expression:
(a) (b)
(define (mountain x) 'done)
(define (dew) (dew))
(mountain (dew))
in normal order evaluation? (A) in applicative order evaluation? (B)
(mountain dew)
in normal order evaluation? (C) in applicative order evaluation? (D)