Final Exam

CS 152 -- Spring 2008

Mark your answers on a 882-E form, not on this document, as only the 882-E form will be used for scoring. At the conclusion of the exam you will keep the exam question sheets.

On the 882-E form, in the boxes provided in the margin, be sure to write the following:

Your full name for NAME
CS 152 for SUBJECT
FIN-SPRING-2008 for TEST NO.

[Note]Note

For the Scheme questions below, assume x, y, z have no previous definitions.

.1. What kind of programming language is Scheme?

A) Non-linear

B) Object-oriented

C) Procedural

D) Declarative

E) Functional

.2. Scheme uses which of the following?

A) Anonymous variables

B) Anonymous functions

C) Anonymous classes

D) All of the above

E) None of the above

.3. A Scheme compiler will optimize Tail Recursive functions into:

A) Strongly-typed lambda expressions

B) Iteration

C) A-Lists

D) All of the above

E) None of the above

.4. Which of the following Scheme expressions evaluate without error?:

A) (list 1 2 3)

B) (list x y z)

C) (1 2 3)

D) All of the above

E) None of the above

.5. Which of the following Scheme expressions evaluate without error?:

A) (1 2 +)

B) (1 + 2)

C) + 1 2

D) All of the above

E) None of the above

.6. Which of the following Scheme expressions evaluate without error?:

A) (if x #t #f)

B) (if #t 0 y)

C) (if #f 0 z)

D) All of the above

E) None of the above

.7. Which of the following Scheme expressions evaluate without error?:

A) (lambda (f) (lambda (x) (f x x)))

B) ((lambda (y) (+ y 1)) 2)

C) (lambda (z) (+ z 1))

D) All of the above

E) None of the above

.8. Which of the following Scheme expressions evaluate without error?:

A) (quote a)

B) (quasiquote a)

C) (quasiquote (unquote (quote a)))

D) All of the above

E) None of the above

.9. Which of the following evaluates to 0 when entered at a Scheme prompt?:

A) (cadr (quote ((0 1) (2 3))))

B) (caar (quote ((0 1) (2 3))))

C) (cdar (quote ((0 1) (2 3))))

D) All of the above

E) None of the above

.10. Which of the following evaluates to 0 when entered at a Scheme prompt?:

A) (cdr (cons 1 0))

B) (cadr (list 1 0))

C) (car (reverse (list 1 0)))

D) All of the above

E) None of the above

.11. Which of the following evaluates to 0 when entered at a Scheme prompt?:

A) ((lambda () 0))

B) ((lambda (x) 1) 0)

C) ((lambda (x y) 2) 1 0)

D) All of the above

E) None of the above

.12. Which of the following evaluates to 0 when entered at a Scheme prompt?:

A) (car (car (cdr (list (cons 3 (cons 2 ())) (cons 1 (cons 0 ()))))))

B) (car (car (cdr (cdr (list (cons 3 (cons 2 ())) (cons 1 (cons 0 ())))))))

C) (car (cdr (car (cdr (list (cons 3 (cons 2 ())) (cons 1 (cons 0 ())))))))

D) All of the above

E) None of the above

.13. Which of the following evaluates to 0 when entered at a Scheme prompt?:

A) (+ 0)

B) (+ 1 -1)

C) (* 0)

D) All of the above

E) None of the above

.14. Which of the following Scheme expressions evaluates #t?:

A) (list? (cons () ()))

B) (list? (cons (car '(0 1)) (cdr '(0 1))))

C) (list? (cons (cdr '(0 1)) (car '(0 1))))

D) All of the above

E) None of the above

.15. Which of the following Scheme expressions evaluates #t?:

A) (if #t #f #t)

B) (if #f #t #f)

C) (or #f #t z y x)

D) All of the above

E) None of the above

.16. Which of the following Scheme expressions evaluates #t?:

A) (eq? '((3 2) (1 0)) '((3 2) (1 0)))

B) (equal? '((3 2) (1 0)) '((3 2) (1 0)))

C) (list? '((3 2) (1 0)) '((3 2) (1 0)))

D) All of the above

E) None of the above

.17. Which of the following Scheme expressions evaluates #t?:

A) (eq? 2 (length '((3 2) (1 0))))

B) (eq? 2 (length (cons (cons 3 (cons 2 ())) (cons 1 (cons 0 ())))))

C) (eq? 2 (length (append '(3 2) '(1 0))))

D) All of the above

E) None of the above

.18. Consider the following Scheme program.


(define (foo x)
  (define (bar x) (and (list? x) (eq? 2 (length x))))
  (if (null? x) #t
    (and (bar (car x)) (foo (cdr x)))))

Which of the following Scheme expressions evaluates #t?:

A) (foo '((0 1) (2 3)))

B) (foo '(0 1))

C) (foo (list (cons 0 1) (cons 2 3)))

D) All of the above

E) None of the above

.19. A "binding":

A) Allocates a memory entity for a variable or object

B) Associates a name to an entity

C) Represents the rest of the computation given a particular point in the computation

D) Is an abstraction binding a function to its extent

E) None of the above

.20. A "continuation":

A) Allocates a memory entity for a variable or object

B) Associates a name to an entity

C) Represents the rest of the computation given a point in the computation

D) Is an abstraction binding a function to its extent

E) None of the above

.21. "Lambda":"

A) Is an anonymous function

B) Defines a function that can be the return result of a procedure/function

C) Is supported by Scheme, JavaScript

D) All of the above

E) None of the above

.22. "Anonymous Classes":

A) Are not supported by Java

B) Are definable by lambda expressions

C) Bind names to class definitions

D) All of the above

E) None of the above

.23. Which of the following is most likely used in an implementation of BASH's scoping semantics?:

A) A Stack of Activation Records

B) An A-list (Association List)

C) A Hash Table

D) Closures

E) None of the Above

.24. Which of the following is most likely used in an implementation of emacs-lisp's scoping semantics?:

A) A Stack of Activation Records

B) An A-list (Association List)

C) A Hash Table

D) Closures

E) None of the Above

.25. Consider the following code fragment written in a Scheme-like syntax:


(define x 1)           ;; binds x to 1

(define (f)
   x)                  ;; returns value of x

(define (g)
  (let ((x 2))         ;; binds x to 2
    (f) ))             ;; calls function f and returns its result

Consider what function g returns under two situations:

  1. lexical scope and dynamic extent semantics
  2. indefinite scope and dynamic extent semantics

A) g returns 1 under either of these semantics

B) g returns 2 under either of these semantics

C) g returns 1 using lexical scope (and dynamic extent) semantics

D) g returns 2 using lexical scope (and dynamic extent) semantics

E) None of the above

.26. Consider the following JavaScript program:


outer = function (x) {
    inner = function (y) {
      x = x + y;
      return x;
    };
    return inner;
};

afunc = outer(5);
afunc(3);
afunc(2);

The last call, afunc(2), returns 10 because JavaScript uses:

A) A-Lists

B) Continuations

C) Closures

D) Stop and Copy

E) Generation Scavenging

.27. Prolog has its roots in which branch of mathematics?:

A) Algebra

B) Combinatorics

C) Graph Theory

D) Logic

E) None of the above

.28. Prolog variables:

A) May start with a capital letter

B) May start with an underscore

C) May get bound during unification

D) All of the above

E) None of the above

.29. This Prolog fact produces a warning. What is the warning?:


foo([Head|Tail]) :- foo(Tail).

A) Singleton variable

B) Anonymous variable

C) Unbound variable

D) Ground variable

E) None of the above

.30. In Prolog, the term, _ (underscore):

A) Denotes a named variable

B) Does not represent the same value everywhere it occurs within a predicate definition

C) Can only be used in query terms

D) All of the above

E) None of the above

.31. A Prolog list

A) May be an atom, []

B) May be a compound term with functor . (dot) and arity 2

C) May be written with elements separated by , (comma) and surrounded by square brackets [ and ]

D) All of the above

E) None of the above

.32. What unifies with the following Prolog term?:

3 + 4

A) +(_, _)

B) 4 + 3

C) 7

D) All of the above

E) None of the above

.33. What unifies with the following Prolog term?:

foo(X, X, X)

A) foo(bar, baz, quux)

B) foo(_)

C) foo(_, bar(_), bar(_,_))

D) All of the above

E) None of the above

.34. What unifies with the following Prolog term?:

foo(X, Y, Z)

A) foo(foo(A, B, C), foo(A, B, C), foo(A, B, C)).

B) foo(A, B, C)

C) foo(_, bar(_), bar(_,_))

D) All of the above

E) None of the above

.35. What unifies with the following Prolog term?:

[A,B|C]

A) [1,2]

B) [1,2|3]

C) [1,2,3]

D) All of the above

E) None of the above

.36. What unifies with the following Prolog term?:

.(A, .(B, C))

A) [1,2]

B) [1,2|3]

C) [1,2,3]

D) All of the above

E) None of the above

.37. Consider the following Prolog program:


foo([X,X]).
foo([0,_]).
foo([X,Y]) :- foo([Y,X]).

Which of the following queries succeed?

A) ?- foo([1,0]).

B) ?- foo([2,2]).

C) ?- foo([0,2]).

D) All of the above

E) None of the above

.38. Consider the following Prolog program:


bar(X,[X]).
bar(X,[X|Rest]) :- bar(X,Rest).

Which of the following queries succeed?

A) ?- bar(1,[0,1]).

B) ?- bar(1,[1,1]).

C) ?- bar(1,[]).

D) All of the above

E) None of the above

.39. Consider the following Prolog program:


baz([]).
baz([[_,_]|Rest]) :- baz(Rest).

Which of the following queries succeed?

A) ?- baz([[1,2],[3,4]]).

B) ?- baz([X|Y]).

C) ?- baz([[X|Y]]).

D) All of the above

E) None of the above

.40. Consider the following Prolog program:


quux([[0,0]|_]).
quux([_|Rest]) :- quux(Rest).

Which of the following queries succeed?

A) ?- quux([[1,2],[0,0],[3,4]]).

B) ?- quux([[0,0]]).

C) ?- quux([[0,0],[0,0]]).

D) All of the above

E) None of the above

.41. Consider the following Prolog program:


goo(0).
goo(A) :- B = A-1, goo(B).

Which of the following queries succeed?

A) ?- goo(1).

B) ?- goo(2).

C) ?- goo(0-1).

D) All of the above

E) None of the above

.42. The compilation phases in order are:

A) Tokenizing, Semantic Analysis, Parsing, Code Generation

B) Tokenizing, Parsing, Semantic Analysis, Code Generation

C) Parsing, Tokenizing, Code Generation, Semantic Analysis

D) Tokenizing, Parsing, Code Generation, Semantic Analysis

E) Semantic Analysis, Tokenizing, Parsing, Code Generation

.43. Implementing a recursive descent parser is best done using:

A) Right-recursive grammar rules defining an LL(k) language

B) Right-recursive grammar rules defining an LR(k) language

C) Left-recursive grammar rules defining an LL(k) language

D) Left-recursive grammar rules defining an LR(k) language

E) None of the above

.44. What is the weakest precondition? Fill in the assert expression.


assert(fill this in...);
y = x * y;
assert(y == 0);

A) assert(false);

B) assert(y == 0);

C) assert(x == 0);

D) assert(x*y == 0);

E) assert(true);

.45. What is the weakest precondition? Fill in the assert expression.


assert(fill this in...);
x = x * y;
assert(y == 0);

A) assert(false);

B) assert(y == 0);

C) assert(x == 0);

D) assert(x*y == 0);

E) assert(true);

.46. What is the weakest precondition? Fill in the assert expression.


assert(fill this in...);
x = x * 2;
y = x * y;
assert(y == 0);

A) assert(false);

B) assert(x == 0);

C) assert(y == 0);

D) assert(x*y == 0);

E) assert(true);

.47. What is the weakest precondition? Fill in the assert expression.


assert(fill this in...);
t = x
x = y
y = t
assert((y == 5) or (x == 3));

A) assert(false);

B) assert((t == 3) or (t == 5));

C) assert((y == 5) or (x == 3));

D) assert((x == 5) or (y == 3));

E) assert(true);

.48. What is the weakest precondition? Fill in the assert expression.


assert(fill this in...);
i = 2;
s = 3;
assert(s == 0 + 1 + 2 + ... + i);

A) assert(false);

B) assert(i == 2);

C) assert(s == 3);

D) assert((i == 2) and (s == 3))

E) assert(true);

.49. What is the weakest precondition? Fill in the assert expression.


assert(fill this in...);
if (x == 0) then
  y = 0
else
  y = x * y
end
assert(y == 0);

A) assert(false);

B) assert(x == 0);

C) assert(y == 0);

D) assert((x == 0) or (y == 0));

E) assert(true);

.50. Given the following invariant and postcondition, what is the best guard?


assert(n > 1);   // PRECONDITION
...
assert(sum == A[0] + A[1] + ... + A[i]);  // INVARIANT
while(fill this in...) {
...
}
assert(sum == A[0] + A[1] + ... + A[n]);  // POSTCONDITION

A) assert(i == n);

B) assert(i != n);

C) assert(i >= n);

D) assert(i <= n);

E) assert(true);

.51. Given the following invariant, which code fragment will re-establish the invariant?


while(...) do
  assert(sum == A[0] + A[1] + ... + A[i]);  // INVARIANT
  fill in this code...
  assert(sum == A[0] + A[1] + ... + A[i]);  // INVARIANT
end

A) i = i + 1; sum = sum + A[i];

B) sum = sum + A[i]; i = i + 1;

C) sum = sum + A[i-1]; i = i + 1;

D) i = i + 1; sum = sum + A[i+1]

E) None of the above

.52. Given the following while loop and its invariant, choose a viable POSTCONDITION.


while(i != 100) do
  assert(forall x in (0..i), A[x] == x);  // INVARIANT
  ...
  ...
end
assert(Fill this in...);  // POSTCONDITION

A) assert(false);

B) assert(forall x in (0..i), A[x] == x);

C) assert(forall x in (100..i), A[x] == x);

D) assert(forall x in (0..100), A[x] == x);

E) assert(true);

.53. Given the following postcondition, choose the best invariant.


forall x in (0..n), A[j] >= A[x]);

A) assert(false);

B) assert(forall x in (0..i), A[j] >= x);

C) assert(forall x in (i..n), A[j] == A[x]);

D) assert(forall x in (0..i), j >= x);

E) assert(true);

.54. What is a property of reference counting garbage collection?:

A) Cannot handle cycles

B) Runs in O(n) time, where n is the total memory size

C) Each object must be equipped with a "mark" bit

D) All of the above

E) None of the above