Algoritmi e strutture dati - vari esercizi

Algoritmi e Strutture Dati

&

Laboratorio di Algoritmi e Programmazione

— Appello del 8 Giugno 2009 —

Esercizio 1 - ASD

• Giustificando la risposta, si risolva la seguente ricorrenza:

√

n 3

) + 3 n

T (n) = 2T ( 3

• Giustificando la risposta, si dica se la seguente affermazione è corretta. √

√ 3 3

n + f (n)) = Ω( n )

Per ogni funzione f (n) asintoticamente positiva si ha Θ(

Esercizio 2 - ASD

Chiamiamo BST-foresta una lista F = T , T , ..., T di BST non vuoti a chiavi intere che soddisfa la seguente proprietà:

1 2 n

≤

per ogni i, 1 i < n, la chiave più grande memorizzata in T è minore o uguale alla chiave più piccola memorizzata

i

in T .

i+1

Specificare la struttura dati BST-foresta (strutture dati usate, attributi dei nodi, operazioni, ....) e proporre un algo-

ritmo per l’operazione di inserimento di una chiave k in una BST-foresta.

Esercizio 3 - ASD

Si descriva l’algoritmo per l’inserimento di un nuovo elemento in una coda di priorità Q, realizzata con un array che

rappresenta un max-heap.

Esercizio 4 - ASD

1) Dire se il seguente albero binario gode della proprietà R/B. (Chiaramente si suppone che tutte le foglie-NIL lasciate

implicite siano nere). 15 B

/ \

10 B 23R

\ / \

13 R 22 B 30 B

/ \

28 R 50 R

2) In caso di risposta positiva, disegnare l’albero che si ottiene dopo aver simulato l’inserimento della chiave 35.