Tentamenvoorbeeld III

Vraag 1

Welke van de volgende procedures dwingt Scheme ertoe een combinatie als ``special form'' te behandelen?

a.

cond

b.

*

c.

>

d.

cons

Vraag 2

Gegeven onderstaand Scheme programma:

               
(define (test x)               
  (cond ((= x 0) (= x 0))                                               
        ((= x 1) (= x 1))                                               
        ((= x 2) (= x 2))                                               
        ((= x 3) (= x 3))                                               
        (else (test (- x 3)))))

Wat is het resultaat van de volgende Scheme expressie: (test 5)

a.

5

b.

2

c.

#T

d.

#F

Vraag 3

Gegeven onderstaand programma:

(define (test x)
  (cond ((= x 0) (= x 0))
        ((= x 1) (= x 1))
        ((= x 2) (= x 2))
        ((= x 3) (= x 3))
        (else (test (- x 3)))))

Hoe vaak wordt tijdens de evaluatie van (test 5) de primitieve procedure '=' uitgevoerd?

a.

14

b.

7

c.

9

d.

8

Vraag 4

De volgende Scheme code wordt uitgevoerd:

(define counter 0)
(sequence
  (set! counter (+ 1 counter))
  (+ 1 counter))

Welke van de volgende uitspraken is het meest correct:

a.

Counter wordt 1 en de sequence expressie heeft als resultaat 1.

b.

Counter wordt 1 en de sequence expressie heeft als resultaat 2.

c.

Counter wordt 2 en de sequence expressie heeft als resultaat 2.

d.

Counter wordt 1 en de sequence expressie heeft een ongedefinieerd resultaat.

Vraag 5

Theo wil zien hoe vaak tijdens evaluatie van een Scheme programma de primitieve procedure '=' wordt uitgevoerd. Daartoe definieert hij een counter en herdefinieert '=' als volgt:

(define counter 0)
(define =
  (sequence 
    (set! counter (+ 1 counter))
    =))

Vervolgens executeert hij een Scheme programma; tijdens de executie wordt de procedure '=' 3 keer aangeroepen. Wat is de waarde van 'counter' na executie van dit programma?

a.

0

b.

1

c.

3

d.

4

Vraag 6

Gegeven de volgende procedure:

(define (a b c d)
   (if (= c 0)
       d
       (a b (- c 1) (* d (b c)))))

Wat zal het resultaat zijn van de volgende combinatie?

(a (lambda (x) (+ x 2)) 3 1)

a.

20.

b.

120.

c.

60.

d.

Geen van de antwoorden a, b en c.

Vraag 7

Wat zal de waarde van 'r' zijn na evaluatie van de volgende Scheme code?

(define x 2)
(define (proc)
    (set! x (+ x 1))
    x )
(define r (+ (proc) (proc)))

a.

4.

b.

5.

c.

6.

d.

7.

Vraag 8

Wat zal de waarde van 'r' zijn na evaluatie van de volgende Scheme code?

(define x 2)
(define (proc)
    (set! x (+ x 1))
    x)
(define r (+ x (proc) ))

a.

4.

b.

5.

c.

6.

d.

De waarde van 'r' is implementatie afhankelijk.

Vraag 9

Het volgende stuk Scheme code wordt uitgevoerd:

(define (proc a)
  (cond ((= a 0) 1)
        ((= a 1) 2)
        ((= a 2) 3)
        (else (list (proc (- a 1))
                    (proc (- a 2))
                    (proc (- a 3)) ))))
(proc 5)

Hoe vaak wordt de body van procedure 'proc' geëvalueerd?

a.

15.

b.

14.

c.

13.

d.

12.

Vraag 10

Wat zal na evaluatie van de volgende Scheme code de waarde van 'r' zijn?

(define (proc) 1)

(define (test)
  (define (proc)
    2)
  (+ (proc) (proc)) )

(define r (* (test) (proc) ))

a.

8.

b.

6.

c.

4.

d.

2.

Vraag 11

Gegeven de volgende Scheme procedure:

(define proc
  (lambda (a b)
    (if (= b 0)
        0
        (+ a (proc a (- b 1))))))

Welke van de volgende namen correspondeert het beste met de definitie van proc?

a.

gcd

b.

max

c.

mul

d.

exp

Vraag 12

Gegeven de volgende Scheme procedure:

(define (proc a b)
  (if (= a 0)
      b
      (+ b (proc (- a 1) (* a b)))))

Geef aan wat de ruimte en tijd complexiteiten zijn wanneer we (proc n m) evalueren; n en m zijn positieve gehele getallen.

ruimte tijd

complexiteit complexiteit

a. 0(1) 0(n)

b. 0(n) 0(n)

c. 0(m) 0(n)

d. 0(1) 0(m)

Vraag 13

Wat is het resultaat bij evaluatie van de volgende Scheme expressie in een environment, waarin x is gekoppeld (bound) aan 8, en y aan 4?

(let ((x  y)
      (y  x))
   (list x y) )

a.

(4 4)

b.

(4 8)

c.

(8 4)

d.

(8 8)

Vraag 14

Gegeven de volgende lijst definities:

(define lijst-1 '((a (b)) (c (d))))
(define lijst-2 (cadr lijst-1))
(define lijst-3 (cdar lijst-1))

Wat zal na invoer van deze definities de waarden van lijst-2 en lijst-3 zijn?

lijst-2 lijst-3

a. c (b)

b. (c (d)) ((b))

c. ((b)) (c (d))

d. (b) c

Vraag 15

Gegeven de volgende Scheme code:

(define lijst-1 '(((a) b) c) )
(define lijst-2 (car lijst-1))
(set-cdr! lijst-2 '(d))

Wat zal na evaluatie van deze code de waarden van lijst-1 en lijst-2 zijn:

lijst-1 lijst-2

a. (((a) b) c) ((a) d)

b. (((a) b) c) ((a) (d))

c. (((a) d) c) ((a) d)

d. (((a) (d)) c) ((a) (d))

Vraag 16

Gegeven de volgende procedure om het aantal elementen in een een lijst te bepalen:

( define  (length x )
    ( if  (null? x)
          0
          ....... ???? ...... ))

Wat moet er in de plaats van de vraagtekens komen?

a.

(length (+ (cdr x) 1))

b.

(+ (length (car x)) (length (cdr x)))

c.

(+ 1 (length (car x)))

d.

(+ 1 (length (cdr x)))

Vraag 17

Gegeven de volgende procedure welke test of een element 'el' in in lijst 'lst' voorkomt, en zo ja, dit element als resultaat geeft.

 
(define (test el lst)
  (cond ((null? lst) '())
        ..... ????? ......
        (else (test el (cdr lst))) ))

Wat moet er in de plaats van de vraagtekens komen?

a.

((atom? el) (car lst))

b.

((eq? el (car lst)) (cadr lst))

c.

((eq? el (car lst)) el)

d.

niets

Vraag 18

Gegeven dat de variabele 'x' is gedefinieerd als:

( define  x  '( a  b  (c)  d  ))

Hoeveel pairs zal Scheme gebruiken om de waarde van 'x' te representeren?

a.

4.

b.

5.

c.

6.

d.

7.

Vraag 19

Gegeven de procedure 'mapcar' die als volgt gebruikt kan worden:

==> (mapcar (lambda (x) (* x x)) '(1 2 3 4))
(1 4 9 16)

Welke van onderstaande procedures I, II, en III implementeren 'mapcar'? Geef het meest correcte antwoord.

I:   (define (mapcar p lst)  
       (if (null? lst)     
           '()
           (cons (p (car lst))
                 (mapcar p (cdr lst)))))  

II:  (define (mapcar p lst)              
       (define (mapiter lst r)   
         (if (null? lst) 
             r
             (mapiter (cdr lst)
                      (cons (p (car lst))
                            r))))
       (mapiter lst '()))
                          
III: (define (mapcar p lst)                       
       (define (mapiter lst r)     
         (if (null? lst) 
             r
             (mapiter (cdr lst)
                      (append r (list (p (car lst) ))) )))
       (mapiter lst '()))

a.

I

b.

II en III

c.

III

d.

I en III

Vraag 20

Wat is het resultaat na evaluatie van de volgende Scheme code?

(define (test x)
  (cond ((null? x) '())         
        ((atom? x) (list x))
        (else (append (test (cdr x))
                      (test (car x)) ))))
(test '(1 (2 3) ((4 5))) )

a.

(1 2 3 4 5)

b.

(5 4 3 2 1)

c.

(() () () 5 4 () 3 2 1)

d.

Geen van de antwoorden a, b en c.

Vraag 21

Wat is het resultaat na de evaluatie van de volgende Scheme expressies?

(define a 1)
(define b a)
(list   a b)

a.

(1 1)

b.

(1 a)

c.

(a . b)

d.

(1 . 1)

Vraag 22

Wat is het resultaat na evaluatie van de volgende Scheme expressie?

(list (quote quote))

a.

((quote))

b.

(quote)

c.

(quote quote)

d.

Syntax fout.

Vraag 23 Iemand gebruikt de volgende constructor voor het representeren van (x y) coördinaten:

(define (make-coord x y)
  (define (dispatch m)
    (cond ((eq? m 'x-part) x)
          ((eq? m 'y-part) y) ))
  dispatch)

Nu kan als volgt de coordinaat z = (3 4) gecreëerd worden d.m.v.:

(define z (make-coord 3 4))

Wat is een correcte definitie van 'x-coord' welke van een coordinaat de x-waarde retourneert:

a.

(define (x-coord z) (z x-part))

b.

(define (x-coord z) (z 'x-part))

c.

(define (x-coord z) (car z))

d.

(define (x-coord z) (x-part z))

Vraag 24

Iemand gebruikt de volgende constructor voor het representeren van (x y) coördinaten:

(define (make-coord x y)  
  (lambda (m) (m x y)) )

Nu kan als volgt de coordinaat z = (3 4) gecreëerd worden d.m.v.:

(define z (make-coord 3 4))

Wat is een correcte definitie van 'x-coord' welke van een coordinaat de x-waarde retourneert:

a.

(define (x-coord z) (z (lambda (x y) (cadr x))))

b.

(define (x-coord z) (cadr z))

c.

(define (x-coord z) (z (lambda (x y) x)))

d.

Geen van de antwoorden a, b en c.

Vraag 25

Gegeven het volgende stukje Scheme code:

( define p1  '(( 1  2 )  3  4 ))
( define p2  '(( 5  6 )  7  8 ))
( set-car!     ( car  p2 ) ( car  p1 ))

Wat zal na uitvoer van deze code de waarde van p2 zijn?

a.

(( 1 2 ) 7 8 )

b.

( 1 2 7 8 )

c.

((( 1 2 ) 6 ) 7 8 )

d.

(( 5 6 ) 7 8 )

Vraag 26

Gegeven de volgende voorbeeld data structuur om een tabel te representeren:

De tabel bestaat uit records met 2 velden: 'key' en 'value'. Voor dit soort tabellen wordt de volgende procedure 'zoek' geschreven welke bij gegeven 'key' het bijbehorende record zoekt. Wordt dit niet gevonden dan wordt '() geretourneerd. Bijvoorbeeld:

(zoek 2 tabel)
==> (2 . 6)

(define (zoek key tabel)
  (cond ((null? tabel) '())
        ((eq? key (caar tabel)) (cdar tabel))
        (else (zoek key (cdr tabel))) ))

M.b.v. deze procedure zoek wordt 'vervang' gedefinieerd, welke een record met een bepaalde 'key' zoekt en, indien gevonden, de bijbehoren 'value' wijzigt. Bijvoorbeeld (vervang 2 10 tabel) vervangt in het record met key 2 de value in 10. Deze procedure is alsvolgt in Scheme gecodeerd:

(define (vervang x y tabel)
  (let ((t (zoek x tabel)))
    (if (null? t)
        'niet-aanwezig
        ...?????... )))

Wat moet er op de vraagtekens worden ingevuld?

a.

(set-car! t y)

b.

(set! (cdr t) y)

c.

(set-cdr! t y)

d.

(set-cdr! (cdr t) y)

Vraag 27

De volgende Scheme code wordt uitgevoerd:

(define p1 '(1 2))
(define p2 '(1 2))
(define p3 p2))

Welke van de volgende expressies geeft bij evaluatie als resultaat #T ?

a.

(eq? p1 p2)

b.

(and (eq? p1 p2) (eq? p2 p3))

c.

(and (= p1 p2) (eq? p2 p3))

d.

(eq? p2 p3)

Vraag 28

De volgende Scheme code wordt uitgevoerd:

      
(define (make-proc x)
  (lambda (y)
    (let ((temp x))
      (set! x y)
      temp) )) 

(define proc (make-proc 1))

Wat is nu de uitvoer van (+ (proc 2) (proc 3))

a.

2

b.

3

c.

4

d.

5

Vraag 29

Gegeven de volgende Scheme code voor de faculteitsfunctie:

(define (fact n)
  (fact-iter 1 1 n) )

(define (fact-iter p c max)
  (if (> c max)
      p
      (fact-iter (* c p)
                 (+ c 1)
                 max )))

De environment die ontstaat tijdens evaluatie van de expressie (fact 3) staat voor een deel getekend in onderstaande figuur:

Welke van onderstaande uitspraken over pointers I en II is het meest correct:

a.

I wijst naar E1; II wijst naar E1.

b.

I wijst naar E1; II wijst naar E2.

c.

I wijst naar E2; II wijst naar E1.

d.

I wijst naar E2; II wijst naar E2.

Vraag 30

Gegeven onderstaande Scheme code voor de faculteitsfunctie:

(define (fact n)
  (define (fact-iter p c)
    (if (> c n)
        p
        (fact-iter (* c p)
              (+ c 1) )))
  (fact-iter 1 1) )

De environment die ontstaat tijdens evaluatie van de expressie (fact 3) staat voor een deel getekend in onderstaande figuur:

Welke van onderstaande uitspraken over pointers I, II en III is het meest correct:

a.

I wijst naar E2; II wijst naar E1.

b.

I wijst naar E1; II wijst naar E2.

c.

I wijst naar E2; II wijst naar E2 en III wijst naar E3.

d.

I wijst naar E2; II wijst naar E2.