Laboratorio di Algoritmi e Strutture Dati ESAME del 29/07/2002
(compito B)
PRIMA PARTE
B.1
Si ordini la seguente sequenza con gli algoritmi heap_sort e insertion_sort:<11, 1, 5, 4, 8, 13, 2>
B.2
Si illustrino con un esempio le funzioni di fusione, determinazione dell’insieme di appartenenza e creazione di un insieme per il tipo di dato astratto “insiemi disgiunti” con implementazione a foreste, discutendo le relative complessità computazionali.B.3
Si implementi in linguaggio C una funzione di ricerca di un elemento in un un albero binario di ricerca.B.4
In un sistema di elaborazione, l’algoritmo di scheduling “round robin” assegna nel tempo il processore a uno tra i diversi processi che ne fanno richiesta. L’algoritmo effettua una divisione del tempo in intevalli di uguale ampiezza, e verifica in ogni intervallo la priorità associata a ogni processo, quindi sceglie quello più prioritario. Ogni volta che un processo rilascia il processore, la sua priorità viene decrementata di una unità. Scrivere un programma C che implementi l’algoritmo in modo che l’assegnamento di un processo avvenga in tempo costante (non dipendente dal numero di processi presenti), e che fornisca le seguenti funzionalità aggiuntive all’amministratore:1) Modifica della priorità del processo X.
2) Aggiunta di un processo.
3) Eliminazione di un processo.
