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-FALL-2007 for TEST NO. |
A) Require indefinite extent
B) Optimizing implementations replace with iteration
C) Requires backtracking
D) Uses an A-List implementation
E) (A) and (C)
(define (mc91 n)
(cond ((<= n 100) (mc91 (mc91 (+ n 11))))
(#t (- n 10))))
What is the result of evaluating this expression:
(mc91 100)
A) 110
B) 91
C) 1
D) Infinite recursion
E) None of the above
(1 2)
A) '(1 2)
B) (quote 1 2)
C) (quote (1 2))
D) (A) and (B)
E) (A) and (C)
(1 2)
A) (list (quote 1) (quote 2))
B) (quote (list 1 2))
C) (list 1 2)
D) (A) and (B)
E) (A) and (C)
(1 2)
A) (1 2)
B) (cons 1 2)
C) (list 1 2)
D) (list (1 2))
E) None of the above
(1 2)
A) (cons 1 2)
B) (cons 1 (cons 2 ())
C) (1 (cons 2 ()))
D) (cons 1 (cons 2))
E) None of the above
()
A) null
B) ()
C) (quote ())
D) (A) and (C)
E) All of the above
()
A) null
B) ()
C) (quote ())
D) (A) and (C)
E) All of the above
#t
A) (not 0)
B) (not ())
C) (not 1)
D) (not null)
E) None of the above
15
A) (if #t (+ 5 10) 10)
B) (cond ((< 5 10) 15) (#t 10))
C) (+ 1 2 3 4 5)
D) (A) and (C)
E) All of the above
15
A) (cdar '(20 15 10 5))
B) (cadr '(20 15 10 5))
C) (car (cdr '(20 15 10 5)))
D) (A) and (C)
E) (B) and (C)
15
A) ((lambda (x) 77) 15)
B) ((lambda (x) 15) 77)
C) (lambda (x) 15)
D) (A) and (C)
E) (B) and (C)
f(1, 2)
A) f(_, _)
B) f(X, X)
C) f(X, Y)
D) All of the above
E) (A) and (C)
?- 2 = X, 3 = X.
A) Succeeds in assigning the variable X with 2, then assigning the variable X with 3, so the final value of X is 3.
B) Fails with an error, because X is not on the left hand side of the assignment.
C) Fails because X cannot be unified to both 2 and 3.
D) Succeeds because X is a variable and variables can be unified with anything.
E) None of the above
f(1, X)
A) f(1, 1)
B) X
C) f(X, 1)
D) All of the above
E) (A) and (C)
f(f(1),g(2))
A) f(X, Y)
B) f(f(X), g(X))
C) X
D) All of the above
E) (A) and (C)
.(a, .(b, []))
A) [a, b]
B) [a | [b | []]]
C) [a | [b]]
D) All of the above
E) (A) and (C)
[]
A) [Head | Tail]
B) .(Head, Tail)
C) .(Head | Tail)
D) All of the above
E) None of the above
34 - 11
A) -(34, 11)
B) 23
C) X - Y
D) All of the above
E) (A) and (C)
"abc"
A) ["a", "b", "c"]
B) ['a', 'b', 'c']
C) [97,98,99]
D) All of the above
E) None of the above
foo(1).
foo(2).
foo(3).
bar(X) :- foo(X).
?- bar(X).
A) Produces no solutions and answers "no"
B) Produces one solution
C) Produces more than one solution
D) Goes into infinite recursion, resulting in global stack overflow
E) There is some other error
member(X,[X|R]).
member(X,[Y|R]) :- member(X,R).
A) ?- member(2, [1, 2]).
B) ?- member(X, [1, 2]).
C) ?- member(2, [1, X]).
D) All of the above
E) None of the above
baz([X], X).
baz([_ | Tail], X) :- baz(Tail, X).
?- baz([aaa, bbb, ccc], Result).
A) Produces no solutions and answers "no"
B) Produces one solution, with Result = ccc
C) Produces one solution, with Result = [ccc]
D) Goes into infinite recursion, resulting in global stack overflow
E) There is some other error
quux([X], X).
quux([Head | Tail], X) :- quux([Head | Tail], Head).
?- quux([aaa, bbb, ccc], Result).
A) Produces no solutions and answers "no"
B) Produces one solution, with Result = ccc
C) Produces one solution, with Result = [ccc]
D) Goes into infinite recursion, resulting in global stack overflow
E) There is some other error
A) Tokenizing
B) Semantic Analysis
C) Code Generation
D) Garbage Collecting
E) Parsing
(a | b)*b*
A) (a | b)*
B) b*(a* | b*)*
C) (ab)*
D) All of the above
E) (A) and (C)
S --> a | Sa
S --> b
A) aa*b
B) a* | b
C) (ab)*
D) All of the above
E) (A) and (C)
E --> F || E
E --> E
F --> T && F
F --> F
A) Bottom-up parsing
B) Recursive descent parsing
C) LR(k) parser generators such as YACC, Bison, JJTree
D) All of the above
E) (A) and (C)
assert(fill this in...);
i = i - 2;
j = i - 2;
assert(j > 0);
A) assert(false);
B) assert(i > 2);
C) assert(i > 4);
D) assert(j == i-2);
E) assert(true);
assert(fill this in...);
if (x == 0) then {
y = 1
} else {
y = x + 1
}
assert(y == x + 1);
A) assert(false);
B) assert(y > x);
C) assert(x > y);
D) assert(y == x + 1);
E) assert(true);
assert(n > 1); // PRECONDITION
fill in this code...
assert(sum == A[i] + A[i+1] + ... + A[n]); // INVARIANT
while( ... ) {
...
}
assert(sum == A[0] + A[1] + ... + A[n]); // POSTCONDITION
A) i = n-1; sum = 0;
B) i = n+1; sum = 0;
C) i = n; sum = 0;
D) All of the above
E) None of the above
assert(n > 1); // PRECONDITION
...
assert(sum == A[i] + A[i+1] + ... + A[n]); // INVARIANT
while(fill this in...) {
...
}
assert(sum == A[0] + A[1] + ... + A[n]); // POSTCONDITION
A) i == 0
B) i != 0
C) i >= 0
D) i <= n
E) true
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 scope
E) None of the above
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 scope
E) None of the above
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 scope
E) None of the above
A) Are not supported by C, C++, Java
B) Are returnable as the result of a procedure/function
C) Are supported by Scheme, JavaScript
D) All of the above
E) None of the above
A) Are not supported by C, C++, Java
B) Are definable by lambda expressions
C) Are supported by Scheme, JavaScript
D) All of the above
E) None of the above
A) A Stack of Activation Records
B) An A-list (Association List)
C) A Hash Table
D) Closures
E) None of the Above
int x = 0;
int f () { return x; }
int g () { int x = 1; return f(); }
Consider what g() returns under 2 situations:
A) g() returns 0 regardless of scoping semantics
B) g() returns 1 regardless of scoping semantics
C) g() returns 0 using lexical scope (and dynamic extent) semantics
D) g() returns 1 using lexical scope (and dynamic extent) semantics
E) None of the above
A) Lexical scope and indefinite extent with closures
B) Lexical scope and dynamic extent with closures
C) Lexical scope and indefinite extent with no support for closures
D) Lexical scope and dynamic extent with no support for closures
E) Indefinite scope
A) Lexical scope and indefinite extent with closures
B) Lexical scope and dynamic extent with closures
C) Lexical scope and indefinite extent with no support for closures
D) Lexical scope and dynamic extent with no support for closures
E) Indefinite scope
A) Lexical scope and indefinite extent with closures
B) Lexical scope and dynamic extent with closures
C) Lexical scope and indefinite extent with no support for closures
D) Lexical scope and dynamic extent with no support for closures
E) Indefinite scope
A lazy method of storage reclamation that puts off reclamation until the allocator runs out of space. Uses two halves of memory storage and allocates new blocks only in one half. Then during the marking pass, all reached blocks are copied to the other (unused) storage half. Performs compaction automatically.
A) Generation Scavenging
B) Stop and Copy
C) Reference Counting
D) Mark and Sweep
E) None of the above
A lazy method of storage reclamation that puts off reclamation until the allocator runs out of space. The first pass follows all reachable pointers (perform a transitive closure computation). The second pass scans linearly through memory returning unmarked blocks to the free list.
A) Generation Scavenging
B) Stop and Copy
C) Reference Counting
D) Mark and Sweep
E) None of the above
An "eager" method of storage reclamation that tries to reclaim space as soon as it is no longer referenced. Each storage block contains an extra count field, which stores the number of pointers to this block from other blocks. When the count drops to zero, the block is returned to the free list.
A) Generation Scavenging
B) Stop and Copy
C) Reference Counting
D) Mark and Sweep
E) None of the above
Let n be the size of total space. Let k be the size of non-garbage nodes.
A) O(n)
B) O(k)
C) O(n - k)
D) O(n * k)
E) O(n + k)
Let n be the size of total space. Let k be the size of non-garbage nodes.
A) O(n)
B) O(k)
C) O(n - k)
D) O(n * k)
E) O(n + k)
Consider the following Java code.
class Bar {
static int x = 1; // a field that is a class variable
public static void main(String[] args) {
int x = 0; // a local variable
System.out.println("x = " + x);
System.out.println("Bar.x = " + Bar.x)
}
}
This program prints:
x = 0 Bar.x = 1
This is an example of (circle one):
A) Hiding
B) Inheritance
C) Overloading
D) Shadowing
E) None of the above
bar = function (x) {
innerfunc = function (y) {
x = x + y;
return x;
};
return innerfunc;
};
afunc = bar(5);
afunc(3);
afunc(2);
The last call, afunc(2), returns 10 because JavaScript uses:
A) A-Lists
B) Continuations
C) Closures
D) Prototype inheritance
E) Private inheritance