Int. Sia Coda il costruttore (crea una coda vuota) e siano int dequeue



Scaricare 32.5 Kb.
29.03.2019
Dimensione del file32.5 Kb.

Esame del corso di ALGORITMI E STRUTTURE DATI - Appello del 28/6/2002
Tempo a disposizione: 120 minuti
1. Si abbia a disposizione una classe Coda che implementi il tipo astratto coda su elementi di tipo int. Sia Coda() il costruttore (crea una coda vuota) e siano int dequeue(), int firstEl(), boolean isEmpty() e void enqueue(int el) i metodi che implementano le operazioni corrispondenti del tipo astratto. In particolare, a differenza di dequeue, firstEl restituisce l’ elemento in testa senza estrarlo. Si scriva un metodo Coda inverti(Coda q) che restituisca una nuova coda con gli elementi in posizioni invertite rispetto a q (ad esempio, l’elemento in coda diventa quello in testa e così via). Si osservi che il metodo deve lasciare inalterato il contenuto di q alla fine dell’esecuzione (lo può modificare durante). Si possono usare al più altre due code per risolvere il problema.
2. Calcolare le complessità nel caso peggiore del metodo proposto per risolvere il punto precedente. Qual è la complessità ottenibile qualora si possano usare un’altra coda e una pila per risolvere il problema? Motivare succintamente la risposta.
3. Considerare la seguente versione modificata dell’ Insertion Sort, che usa la ricerca binaria per calcolare la posizione in cui collocare il prossimo elemento da ordinare:
public void modifiedInsertionSort(int[] data) {

int i, j, k;


for (i=1; i /* Calcola la posizione in cui inserire data[i] */

j=binarySearch(data, 0, i);

/* Colloca data[i] nella posizione calcolata sopra */

for (k=i; k>j; k--)

swap(data, k, k-1);

}

}
binarySearch(data, 0, i) calcola (eseguendo una ricerca binaria) l’indice all’interno del sottoarray data[0,..., i-1] (già ordinato) nel quale collocare data[i] (ovviamente il metodo restituisce i qualora data[i] sia più grande di ogni elemento in data[0,..., i-1]). swap(data, i, j) scambia gli elementi nelle posizioni i e j di data.



Tale modifica abbassa la complessità asintotica dell’ Insertion Sort (O(n2) nel caso peggiore)? Motivare la risposta.
4. Si consideri una classe BinTree che implementi il tipo albero binario. La classe è costruita a partire dalla classe BinNode, che implementa il generico nodo dell’albero binario. Si supponga che le due classi abbiano già, tra gli altri, i seguenti campi e metodi:

  • BinNode BinNode.father  riferimento al padre del nodo in considerazione.

  • boolean BinTree.isRoot(BinNode v)restituisce true se v è radice, false altrimenti.

Scrivere un metodo boolean isAncestor(BinNode v1, BinNode v2) della classe BinTree che restituisca true qualora v1 sia antenato di v2, false altrimenti. Dire quale sia la complessità del metodo proposto nel caso peggiore, motivando la risposta.


5. Si definisca la struttura dati heap e se ne illustrino succintamente le proprietà fondamentali. Non bisogna descrivere gli algoritmi per la creazione e la modifica degli heap.

Possibile soluzione es. 1. Si osservi che una soluzione più efficiente (a meno di costanti) è possibile. Questa dovrebbe essere più leggibile.
/* Si può risolvere anche usando una sola coda ausiliaria (oltre a q) */
Coda inverti (Coda q) {

int size = 0;

Coda tmp = new Coda();

Coda inv = new Coda();

/* Conta gli elementi nella pila */

while(!q.isEmpty()) {

size++;

tmp.enqueue(q.dequeue());

}

/* Li rimette a posto - non è necessario ma così il

programma dovrebbe risultare più leggibile */

while(!tmp.isEmpty())

q.enqueue(tmp.dequeue());

/* i indica l'elemento da spostare nella coda finale */

for(int i=size; i>0; i--) {

/* Mette i primi i-1 elementi in tmp */

for(int j=0; j

tmp.enqueue(q.dequeue());

/* Copia l'elemento i-esimo in inv */

inv.enqueue(q.firstEl());

/* Finisce di trasferire gli elementi di q in tmp */

while (!q.isEmpty())

tmp.enqueue(q.dequeue());

/* Ora ripristina q */

while (!tmp.isEmpty())

q.enqueue(tmp.dequeue());

} /* End for */

return inv;

}


Condividi con i tuoi amici:


©astratto.info 2019
invia messaggio

    Pagina principale