Göm menyn

Exempel på duggafrågor

Första duggan

Information uppdaterad 2010-09-03.

Den första duggan testar att du har koll på de Lisp-funktioner som vi har använt i första labbomgången. Detta innefattar i princip kapitel 1-5 i läroboken. (Utgå gärna från sammanfattningen på sid. 18 i labbhäftet.)

Duggan består av ett trettiotal uppgifter som ska lösas skriftligen på plats i labbsalen. Du har 30 minuter på dig och måste få minst 75% rätt för att bli godkänd. Om du inte blir godkänd får du en ny dugga vid ditt nästa labbtillfälle.

Här är exempel på typer av frågor som kommer på första duggan.

Du kan testa dig genom att köra uppgifterna i Lisp-systemet

Infix och prefix-notation

Gör om följande matematiska uttryck till prefix-notation, som Lisp använder!

15*x - 4
x+sin(y/2)/(x+y)
Aritmetiska uttruyck och datatyper

Vad blir resultatet av nedanstående uttryck? Vilken datatyp har resultatet?

(+ 3 4)
(+ 3 4.0)
(/ 15.0 3)
(/ 3 15)
Elementära operationer på listor och quote

Antag att vi har en variabel s som har listan (a b (c d)) som värde. Vad blir då resultaten av följande uttryck?

(first s)
(first (first (rest (rest s))))
(cons 's s)
(append (rest s) (first (rest (rest s))))
(list (first (rest s)) 's s)
(list '(+ 1 2) (+ 3 4))
Villkorliga uttryck

Kunna skriva villkorliga uttryck med if och cond, samt översätta if-uttryck till cond-uttryck och vice versa.

Skriv om följande cond-uttryck till ett if-uttryck:

(cond ((< x 10) x)
      ((< x 20) (* x x))
      (t 0))
Rekursiva funktioner

Skriva elementära rekursiva funktioner och förstå skillnaden mellan rekursiv och iterativ processlösning.

Skriv en funktion som räknar ut längden av en rak lista.

Givet en funktion. Kan du avgöra om funktionen nedan gör en rekursiv eller iterativ processlösning. Kan du motivera med att visa hur beräkningen går till via substitutionsmodellen eller ungefär hur en trace av funktionen ser ut.

(defun fak (n)
   (fak-help n 1))

(defun fak-help (n i)
   (if (> i n)
       1
       (* i (fak-help n (+ i 1)))))
Begrepp

Första duggan kommer dessutom att innehålla frågor om några grundläggande programmeringsbegrepp (t.ex. variabel, funktion, formell parameter, argument, sanningsvärde, predikatuttryck). Se begreppslistor, som fanns på oh-bilerna efter de två första föreläsningarna.

Andra duggan

Information uppdaterad 2009-09-16.

Den andra duggan fungerar på samma sätt som den första, men tar främst upp funktioner från den andra labbomgången (motsvarande kapitel 5-7 i läroboken). För att klara av duggan ska man kunna:

Skapa listor, tolka och rita cons-celler

Förstå och kunna använda cons, list och append, lite samma typ av frågor som kom upp på dugga 1. Nu har dessutom det punkterade paret tillkommit. Dessutom kunna rita upp cons-celler givet ett parentesuttryck, eller som det resultat vi får av ett Lisp-uttryck som skapar en lista. Kunna tolka cons-celler och skriva motsvarande parentesuttryck.

Rita upp listan (a (b (c d)) e) som cons-celler.
Uttrycket (a . ((b . nil) . nil)) kan förenklas till en lista utan punkter.
Vad blit värdet av följande uttryck i parentesformat och rita upp värdet med cons-celler.

(list (cons 'a '(b c)) 'd)
(cons (list 'a 'b) '(c d))
(list (cons 'a 1) (cons 'b 2))

Lokala variabler med let och let*

Förstå användning av let, dess syntax och skillanden mellan let och let*.

Skriv om följande uttryck med let, så att inte det kostsamma anropet till funktionen sök görs 2 gånger.

(if (eq (sök x (rest l)) 'inget-hittat) (sök-vidare x l) (sök x (rest l)))

Vad blir värdet av följande let-uttryck:

(setq temp 10)
(let ((temp 20) (value (+ temp 1))) (+ temp value))
(let* ((temp 20) (value (+ temp 1))) (+ temp value))
Dubbelrekursion

Bearbetning enligt sekvensmodell (listor i listor) och binär träd-modell.

Skriv en dubbelrekursiv funktion summera-sekv, som summerar alla talen i en lista enligt sekvensmodellen. Bara tal finns som element i listan.

(summera-sekv '((1 2) (3 (4)) 5)) = 15

Skriv en dubbelrekursiv funktion summera-bt, som summerar alla talen enligt binär träd-modellen. Bara tal finns som löv.

(summera-bt '((1 . 2) . ((3 . 4) . 5))) = 15

Lambda-uttryck och dess användning i traverse

Kunna skriva lambda-utryck, som anonyma funktioner. Kunna tillämpa dessa i traverse-uppgiften från laboration 2D.

Vad blir resultatet av:

(traverse '(1 . (2 . 3)) #'(lambda (löv) (+ löv 2)) #'cons)
Vilken lövfunktion och vilken nodfunktion skall du ge till traverse om du vill räkna alla löv större än 10. Vi antager att alla löven är tal.

Svar:

(traverse #'(lambda (löv) (if (> löv 10) 1 0)) #'+)

Sidansvarig: Peter Dalenius
Senast uppdaterad: 2010-09-20