javaprogrammer

User info:

Registered: Sep 2009
Posts: 1 (0.00 al dì)
Location:
Corso:
Anno:
Time Online: 0:03:06: [...]
Status: Offline

Post actions:

Ciao Ragazzi,
io non ho molto tempo per rispolverare algoritmi e strutture dati dopotutto ho 2 esami nello stesso giorno il mercoledì questo. Praticamente basi di dati alla mattina e algoritmi e strutture dati al pomeriggio.
Gradirei di passarli tutti e due e praticamente sono venuto a conoscenza grazie ad un'amico che gli esercizi dell'esame potrebbero essere questi:

1) Scrivere un algoritmo che ordina n numeri compresi tra 0 e n^2 -1 in tempo
O(n). Suggerimento combinare counting-sort e radix-sort. Motivare le risposte.

2) Un grafo 2-colorabile se è possibile assegnare ad ogni nodo il colore rosso o nero in modo tale che tutte le coppie di nodi adiacenti non abbiano lo stesso colore. Trovare un algoritmo efficente per dire se un grafo è 2-colorabile oppure no. Discutere il costo computazionale dell'algoritmo fornito. (suggerimento: usare una BFS modificata).

3) Sia e l'arco di peso minimo in un grafo G. Dimostreare che esiste un MST per G che contiene e. (Suggerimento: procedere per assurdo. Se l'arco di peso minimo non stesse in nessun MST allora .... )

4) Scrivere una procedura RICORSIVA che prenda in input un albero A ( non necessariamente binario! ogni nodo può avere un numero qualsiasi di figli) e restituisca in output un albero B ottenuto da A guardandolo allo specchio. Per la soluzione dell'esercizio è possibile usare senza implementrare una funzione INVERTI che prende una lista e la inverte.

5) Dare la procedura con il costo computazionale minore possibile per ordinare lessicograficamente n stringhe di k caratteri ( k costante indipendente da n). Cosa succede se k non è costante?

6) Scrivere una FUNZIONE RICORSIVA che prende in input il puntatore alla radice di un albero binario e restituisce il numero di nodi dell'albero che si trovano a distanza pari dalla radice. Argomentare la sua correttezza e analizzare il suo costo computazioneale. Vietato usare variabili globali!!!!

Grazie a chi mi svolgerà i seguenti esercizio e lo pagherò con le mie capacità di altre materie come soprattutto il JAVA, C, C++, C#, e altre cose chiedetemi pure e vi sarà fornito tutto il mio materiale necessario!!!!

Grazie
Ciao Ciao!!!