 | |
Il progetto dsy.it è l'unofficial support site dei corsi di laurea del Dipartimento di Scienze dell'Informazione e del Dipartimento di Informatica e Comunicazione della Statale di Milano. E' un servizio degli studenti per gli studenti, curato in modo no-profit da un gruppo di essi. I nostri servizi comprendono aree di discussione per ogni Corso di Laurea, un'area download per lo scambio file, una raccolta di link e un motore di ricerca, il supporto agli studenti lavoratori, il forum hosting per Professori e studenti, i blog, e molto altro...
In questa sezione è indicizzato in textonly il contenuto del nostro forum |
Soluzione esercizi: richiesta urgente!!!
Clicca QUI per vedere il messaggio nel forum |
| javaprogrammer |
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!!! |
|
|
|
|
