Esercizi sulle liste

Lunghezza di una lista
Definire una funzione llength che data una lista restituisca il numero dei suoi elementi
(llength '(a b c d e)) --> 5
(llength '()) -->0
Ricerca di un elemento in una lista
Definire una funzione lsearch che data una lista L e un atomo X restituisca T se X appartiene a L, Nil altrimenti.
(lsearch '(2 4 a 7) 4) --> T
(lsearch '(2 4 a 7) b) --> NIL
Somma degli elementi di una lista
Definire una funzione lsum che data una lista L di numeri, restituisca la somma dei suoi elementi.
(lsum '(1 2 38 21)) -->62
(lsum '()) --> 0
Lista con i primi n numeri naturali
Definire una funzione lnum che dato un numero n restituire la lista con i primi n naturali:
(lnum 5) --> (1 2 3 4 5)
Appendere un elemento in fondo ad una lista
Definire una funzione lappend che data una lista L e un oggetto X, restituisca una lista avente gli elementi di L con X aggiunto in fondo.
(lappend '(a bc d e) 'f) -->(a bc d e f)
(lappend '(a bc d e) '(f g)) -->(a bc d e (f g))
(lappend '() 5) -->(5)
Restituzione dell'ultimo elemento di una lista
Definire una funzione llast che data una lista L restituisca l'ultimo elemento di L.
(llast '(a bc d e)) --> e
(llast '(a bc d (e f))) --> (e f)
Concatenazione di due liste
Definire una funzione lcat che date due liste L1 e L2 restituisca una lista con gli elementi di L1 e L2 concatenati fra loro.
(lcat '(a b c) '(d e f g)) -->(A B C D E F G)
(lcat nil '(a bc d)) -->(A BC D)
(lcat '(a bc d) nil) -->(A BC D)
Reverse di una lista
Definire una funzione lrev che data una lista L restituisca una lista con gli elementi di L invertiti.
(lrev '(a bc d e f)) -->(F E D BC A)
(lrev '(a)) -->(A)
(lrev nil) -->NIL
Inserimento ordinato in una lista ordinata (di numeri)
Definire una funzione linsord che data una lista L di interi e un intero N restituisca una lista in cui N è inserito ordinatamente in L.
(linsord '(12 23 45 67 80) 30) -->(12 23 30 45 67 80)
(linsord '(12 23 45 67 80) 10) -->(10 12 23 45 67 80)
(linsord '(12 23 45 67 80) 300) -->(12 23 45 67 80 300)
Eliminazione di un elemento da una lista
Definire una funzione ldel che data una lista L di interi e un intero N restituisca una lista in cui la prima occorrenza di N è stata eliminata.
(ldel '(12 23 45 67 80) 300) -->(12 23 45 67 80)
(ldel '(12 23 45 67 80) 12) -->(23 45 67 80)
(ldel '(12 23 45 67 80) 80) -->(12 23 45 67)
(ldel '(12 23 45 67 80) 23) -->(12 45 67 80)
(ldel '(45 12 23 45 23 67 80) 23) -->(45 12 45 23 67 80)
Lista degli elementi di posto pari
Definire una funzione lpp che data una lista L restituisca la lista con gli elementi di posto pari di L (gli elementi sono numerati da 1)
(lpp '(a b c d e f)) -->(B D F)
(lpp '(a b)) -->(B)
(lpp '(a)) -->NIL
(lpp '()) -->NIL
Lista degli elementi di posto dispari
Definire una funzione lpd che data una lista L restituisca la lista con gli elementi di posto dispari di L (gli elementi sono numerati da 1)
(lpd '(a b c d e f)) -->(A C E)
(lpd '(a b)) -->(A)
(lpd '(a)) -->(A)
(lpd '()) -->NIL
Insertion sort
Definire una funzione linsort che data una lista L restituisca una lista ordinata con gli stessi elementi di L utilizzando l'algoritmo dell'insertion sort.
(linsort '(84 3 8 1 0 9)) -->(0 1 3 8 9 84)
(linsort '(84)) -->(84)
(linsort '()) -->NIL
Merge di due liste ordinate
Definire una funzione lmerge che date due liste ordinate L1 e L2 restituisca lista ordinata ottenuta dalla fusione di L1 e L2
(lmerge '(1 3 5 7 8 10) '(2 3 6 9 12 14)) -->(1 2 3 3 5 6 7 8 9 10 12 14)
Break 1 [17]> (lmerge '(1) '(2 3 6 9 12 14)) -->(1 2 3 6 9 12 14)
Break 1 [17]> (lmerge '(2 3 6 9 12 14) '(1)) -->(1 2 3 6 9 12 14)
Mergesort
Definire una funzione lmergesort che data una lista L restituisca una lista ordinata con gli stessi elementi di L utilizzando l'algoritmo del mergesort.
(lmergesort '(3 2 9 8 5 2 19)) -->(2 2 3 5 8 9 19)
L2 prefisso di L1
date due liste L1 ed L2 verificare se L2 è un prefisso di L1.
(lprefix '( 1 2 3 5 67 8 ) '(1 2 3)) -->T
(lprefix '( 1 2 ) '(1 2 3)) -->NIL
(lprefix '( 0 1 2 3 5 67 8 ) '(1 2 3)) -->NIL
L2 sottolista di L1
date due liste L1 ed L2 verificare se L2 è sottolista di L1
(lsublist '( 1 2 3 5 67 8 ) '(1 2 3)) -->T
(lsublist '( 1 2 ) '(1 2 3)) -->NIL
(lsublist '( 0 1 2 3 5 67 8 ) '(1 2 3)) -->T
Estrazione di una sottolista
Estrazione dalla lista L della sottolista che inizia dalla posizione in ed è lunga lun; se in è maggiore della lunghezza di L restituire la lista vuota; se in + lun è maggiore della lunghezza di L restituire la sottolista da in al termine di L.
(lslist '(a b c d e f g) 1 9) -->(A B C D E F G)
(lslist '(a b c d e f g) 3 2) -->(C D)
(lslist '(a b c d e f g) 12 9) -->NIL
Numero di atomi in una multilista
(lml '(1 (2 3) 4 (5) (6 (7 8 9) 10))) -->10
Lista degli atomi di una multilista
(ml2l '(1 (2 3) 4 (5) (6 (7 8 9) 10))) -->(1 2 3 4 5 6 7 8 9 10)
Profondità massima di una multilista
(La lista vuota ha profondità 0; un atomo ha profondità 1)
(mllev '()) -->0
(mllev 'a) -->1
(mllev '(a)) -->2
(mllev '(a b c d)) -->5
(mllev '(1 (2 3) 4 (5) (6 (7 8 9) 10))) -->11
(mllev '((a . b) . (c . (d . e)))) -->4

Soluzioni

Soluzioni proposte e qualche esempio su altre caratteristiche del linguaggio (notazione lambda, APPLY, FUNCALL, MAPCAR, SETQ etc.)

Esercizi sugli alberi binari

Un albero binario può essere rappresentato nel seguente modo:
albero binario vuoto
NIL
albero binario di radice x e sottoalberi left e right
(x left right)
Risolvere i seguenti esercizi:

Ulteriori esercizi

Alcuni esercizi d'esame

16/07/2009 - 16/07/2010 - 22/06/2011