Esercizi utili per la preparazione all'esame - collezione 6
Scrivere un metodo
Nodo<Integer> merge(Nodo<Integer> a, Nodo<Integer> b) che, date due SCL di interi ordinate, le fonde creando una nuova SCL ordinata contenente tutti gli elementi delle SCL di ingresso (realizzazione funzionale con condivisione di memoria). La soluzione del problema deve essere ricorsiva, eventualmente usando metodi privati ausiliari, senza usare alcuna istruzione di ciclo.
Ad esempio, se
a=<2,3,5,5,6> e
b=<1,3,4>, la SCL prodotta deve essere
<1,2,3,3,4,5,5,6>.
Scrivere un programma di prova per verificare la correttezza del metodo scritto.
[
Soluzione ]
Scrivere un metodo
List<Integer> merge(Iterator<Integer> a, Iterator<Integer> b) che, dati due iteratori di interi ordinati, ne fonde gli elementi creando una lista ordinata contenente tutti gli elementi degli iteratori di ingresso. La soluzione del problema deve essere ricorsiva, eventualmente usando metodi privati ausiliari, senza usare alcuna istruzione di ciclo.
Ad esempio, se
a=<2,3,5,5,6> e
b=<1,3,4>, la lista prodotta deve essere
<1,2,3,3,4,5,5,6>.
Scrivere un programma di prova per verificare la correttezza del metodo scritto.
[
Soluzione ]
Si scriva un'interfaccia pubblica
MiaLista che consenta di mantenere una sequenza di elementi mediante le seguenti operazioni con side-effect:
- size(): restituisce in numero di elementi nella lista;
- add(Object x, int k): inserisce l'elemento x in posizione size()-k se size()-k>=0 e in posizione 0 altrimenti. Se k è negativo, lancia un'eccezione di una nuova classe EccezioneIndiceErrato con il messaggio "errore in add: indice errato".
- get(int i): restituisce l'elemento i-esimo della lista, con i>=0 e i<size(). Se l'indice i è errato, lancia un'eccezione di una nuova classe EccezioneIndiceErrato con il messaggio "errore in get: indice errato".
Implementare l'interfaccia
MiaLista scrivendo una classe pubblica
MiaListaArray con i seguenti vincoli:
- la classe deve utilizzare un array per memorizzare gli elementi (non è possibile fare uso del Java Collections Framework, di strutture collegate, ecc.);
- la classe deve fornire inoltre un metodo int capacity() che restituisce la dimensione corrente dell'array (deve essere sempre capacity()>=size());
- la dimensione dell'array deve essere inizialmente 2 e aumentare del 50% ogni volta che si chiama il metodo add() su una lista con size()==capacity() (le dimensioni successive dell'array devono essere pertanto: 2=dimensione iniziale, 3=2+2/2, 4=3+3/2, 6=4+4/2, 9=6+6/2, 13=9+9/2, ecc.).
Scrivere un programma di prova per verificare la correttezza del metodo scritto usando
k=15 in
add. Il programma deve inserire i numeri da 1 a 30 e stampare dopo ogni inserimento il valore restituito dal metodo
capacity().
Si implementi l'interfaccia pubblica
MiaLista dell'esercizio 090609a scrivendo una classe pubblica
MiaListaCollegata con i seguenti vincoli:
- la classe deve utilizzare una struttura collegata lineare per memorizzare gli elementi (non è possibile fare uso del Java Collections Framework, di array, ecc.): a questo scopo, scrivere una classe pubblica Nodo<E> con due campi protetti next (di tipo Nodo<E>) ed elem (di tipo E) per rappresentare i nodi di una SCL con elementi di tipo <E>;
- la classe deve fornire un ulteriore metodo protected Nodo<E> getSCL() che restituisce il nodo di testa della SCL usata per mantenere gli elementi.
Scrivere un programma di prova per verificare la correttezza del metodo scritto usando
k=15 in
add. Il programma deve inserire i numeri da 1 a 30 e stampare dopo ogni inserimento il contenuto complessivo della lista usando il metodo
getSCL().
Scrivere un metodo
void appendi(Nodo a, Nodo b) che, date due SCL
a e
b di elementi
Object, con
a non vuota, attacca
b in coda ad
a (realizzazione con side-effect). La soluzione del problema deve essere ricorsiva, eventualmente usando metodi privati ausiliari, senza usare alcuna istruzione di ciclo.
Ad esempio, se
a=<6,3,5,9,5,6> e
b=<4,3,4>, la SCL prodotta deve essere
<6,3,5,9,5,6,4,3,4>.
Scrivere un programma di prova per verificare la correttezza del metodo scritto.
Scrivere un metodo
List<Object> concatenaFiltrando(Iterator<Object> a, Iterator<Object> b, Class c) che, dati due iteratori
a e
b e una classe
c, restituisce una nuova lista ottenuta prendendo prima tutti gli elementi di
a di tipo
c e poi tutti gli elementi di
b di tipo
c. La soluzione del problema deve essere ricorsiva, eventualmente usando metodi privati ausiliari, senza usare alcuna istruzione di ciclo.
Ad esempio, se
a=<"6",6,3,"1",5,9,"3",5,6>,
b=<4,"9",3,4> e
c=Integer.class, la lista prodotta deve essere
<6,3,5,9,5,6,4,3,4>.
Scrivere un programma di prova per verificare la correttezza del metodo scritto.
Scrivere un metodo
boolean uguali(Iterator<Object> a , Iterator<Object> b, Iterator<Object> c) che restituisce
true se le sequenze rappresentate dai tre iteratori sono uguali, e
false altrimenti. La soluzione del problema deve essere ricorsiva, eventualmente usando metodi privati ausiliari, senza usare alcuna istruzione di ciclo.
Scrivere un programma di prova per verificare la correttezza del metodo scritto.
Scrivere un metodo
boolean uguali(Nodo a , Nodo b, Nodo c) che restituisce
true se le tre SCL sono uguali, e
false altrimenti. La soluzione del problema deve essere ricorsiva, eventualmente usando metodi privati ausiliari, senza usare alcuna istruzione di ciclo.
Scrivere un programma di prova per verificare la correttezza del metodo scritto.
Scrivere un metodo
Nodo converti(Iterator i) che restituisce una SCL con tutti gli elementi di
i (
null se
i non contiene elementi). La soluzione del problema deve essere ricorsiva, eventualmente usando metodi privati ausiliari, senza usare alcuna istruzione di ciclo.
Scrivere un programma di prova per verificare la correttezza del metodo scritto.
Scrivere un metodo
Nodo convertiRovesciato(Iterator i) che restituisce una SCL con tutti gli elementi di
i in ordine rovesciato (
null se
i non contiene elementi). La soluzione del problema deve essere ricorsiva, eventualmente usando metodi privati ausiliari, senza usare alcuna istruzione di ciclo.
Scrivere un programma di prova per verificare la correttezza del metodo scritto.
Scrivere un metodo
Object[] converti(Iterator i) che restituisce un array con tutti gli elementi di
i (un array con zero elementi se
i non contiene elementi). La soluzione del problema deve essere ricorsiva,
senza fare uso di liste di appoggio e senza usare alcuna istruzione di ciclo.
Scrivere un programma di prova per verificare la correttezza del metodo scritto.
Scrivere un metodo statico
void moltiplica(Nodo<Integer> l) che, dato un riferimento
l al primo nodo di una SCL di interi non negativi, la modifica (con side effect) in modo che subito dopo ogni elemento
x vengano aggiunte
x-1 copie dell'elemento stesso. Ad esempio, data la lista
[1,0,3,4,2,0,1], dopo l'applicazione del metodo la lista deve diventare
[1,0,3,3,3,4,4,4,4,2,2,0,1].
Scrivere un programma di prova per verificare la correttezza del metodo scritto.
Scrivere un metodo statico
Nodo<Integer> moltiplicaF(Nodo<Integer> l) che, dato un riferimento
l al primo nodo di una SCL di interi non negativi, ne restituisce una nuova (realizzazione funzionale) ottenuta a partire da
l aggiungengo subito dopo ogni elemento
x,
x-1 copie dell'elemento stesso. Ad esempio, data la lista
[1,0,3,4,2,0,1], il metodo deve restituire la nuova lista
[1,0,3,3,3,4,4,4,4,2,2,0,1]. La realizzazione deve essere senza condivisione di memoria (non ci devono essere nodi in comune fra la vecchia e la nuova lista).
Scrivere un programma di prova per verificare la correttezza del metodo scritto.
Fornire una soluzione
ricorsiva degli esercizi 090709a e 090709b, eventualmente usando metodi privati ausiliari, senza usare istruzioni di ciclo.
Scrivere un metodo statico
Nodo<Integer> converti(String s) che, data una stringa
s, restituisce una SCL di interi contenente i codici ASCII di tutti i caratteri di
s, nello stesso ordine in cui appaiono. Il metodo deve essere ricorsivo,
senza usare metodi ausiliari e senza usare cicli.