Fac-Simile

  1. Si discuta la complessità dell’algoritmo QuickSort(A, 1, 8) in funzione della procedure Partition. Dato la seguente sequenza di valori $A = \{1, 7, 6, 0, 2, 4, 5, 3\}$, si scelga una procedura Partition e si determini il numero di chiamate ricorsive necessarie ad ordinare la sequenza A.
  1. Definire un algoritmo ricorsivo per la visita in profondità di un Albero binario a partire dal nodo radice r.
  1. Qual è il numero di foglie di un Albero binario completo di altezza h. Fornire una dimostrazione per induzione su h del valore proposto.
  1. Qual è il tempo massimo per trovare la chiave massima in un Albero binario di ricerca di n elementi?
  1. In quanto tempo è possibile trovare il minimo in un Min-heap? Fare un esempio di Min-heap
  1. Considerare la seguente sequenza di numeri: 1-3-20-32-80-15-22-40-60-93-81-42 Assumendo che siano memorizzati in un array secondo la rappresentazione posizionale, discutere, motivando la risposta, se la sequenza rappresenta un Heap.
  1. Considerare la seguente sequenza di numeri: 42-20-80-33-77-23-67-88-99-15-7 Assumendo che siano memorizzati in un array secondo la rappresentazione posizionale, discutere, motivando la risposta, se la sequenza rappresenta un Heap. Se non è un heap sia applichi la procedure Heapify e si ottenga un heap.
  1. Si consideri l’array di numeri $A = \{3, 9, 8, 2, 4, 6, 7, 5\}$, si scelga una procedura Partition e si discuta la complessità dell’algoritmo QuickSort(A, 1, 8) rispetto alla sequenza di input A. Si risolva il problema e si determini il numero di chiamate ricorsive.
  1. Confrontare la complessità computazionale, nei casi ottimo, peggiore e medio, degli algoritmi InsertionSort, HeapSort e Mergesort. Ordinare la sequenza di numeri $A = \{57, 46, 35, 24, 13, 12, 1\}$ con i tre algoritmi e stabilire il numero di confronti necessari a ciascun algoritmo.