Laboratorio di Algoritmi e Strutture Dati ESAME FINALE 12/12/2001
(Compito B – seconda parte)
PRIMA PARTE
B.A.1 Si descriva il funzionamento dell’algoritmo di ordinamento heap_sort applicando l’algoritmo alla sequenza:
<5, 11, 3, 6, 2, 7, 9>
B.A.2 Si descriva il funzionamento dell’algoritmo di ordinamento insertion_sort applicando l’algoritmo alla sequenza:
<5, 11, 3, 6, 2, 7, 9>
B.A.3 Si descriva una procedura iterativa per la visita in profondità di un albero binario.
B.A.4 Sia dato un array di 100 interi per realizzare una tabella hash, e siano definite le seguenti funzioni:
int h1(char* s) = cat(cod(s[0]), cod(s[1]), …, cod(s[n-1]))%100 int h2(char* s) = (cod(s[0]) + cod(s[1]) + … + cod(s[n-1]))%100
dove cod è la funzione che codifica come un intero un carattere come segue:
cod(A) = 01, cod(B) = 02, …, cod(M) = 11, cod(N) = 12, … e cat ottiene un intero mediante concatenazione di altri interi, nel seguente modo:
cat(01, 02, 14) = 010214
Ad esempio, h1(ABCD) = cat(01,02,03,04)%100 = 1020304%100 = 4 e h2(ABCD) = (01+02+03+04) %100 = 10%100 = 10 Dire quale delle due funzioni è migliore e giustificarne i motivi.
B.B.1 Si scriva un programma per la gestione degli ambulatori di un pronto soccorso, assumendo che:
1) Il numero di ambulatori non è un parametro del problema, ma è fissato.
2) Ogni persona in attesa è identificata da una struttura che contiene il nome, il numero di tesserino sanitario, la patologia e la priorità associata a tale patologia.
3) La persona con più alta priorità è la prossima ad accedere a un ambulatorio.
4) Ogni persona viene fatta accomodare nell’ambulatorio che si libera prima.
[Bisogna realizzare le funzioni di inserimento nella coda di attesa e di estrazione di un elemento. Il programma deve controllare continuamente lo stato – libero/occupato – degli ambulatori. Solo quando uno di essi è trovato libero, si procede con l’estrazione dalla coda del prossimo paziente, e la sua assegnazione all’ambulatorio libero].
B.C.1 Si discutano i principali vantaggi nella realizzazione di un dizionario tramite tabelle hash.
