• Non ci sono risultati.

008AA – ALGORITMICA E LABORATORIO

N/A
N/A
Info
Scarica
Protected

Academic year: 2021

Condividi "008AA – ALGORITMICA E LABORATORIO"

Copied!
1
0
0

Caricamento.... (Visualizza il testo completo ora)

Scarica adesso ( 1 pagine )

Testo completo

(1)

008AA – ALGORITMICA E LABORATORIO Appello del 5 Settembre 2016

Cognome Nome: N. Matricola: Corso: A B

Esercizio 1. (10 punti)

Si progetti e si descriva in pseudocodice una variante del QuickSort che selezioni come pivot il mediano della porzione di array da ordinare invocando l’algoritmo Quickselect.

Analizzare la complessit`a dell’algoritmo al caso medio e al caso pessimo, indicando e risolvendo le corrispon- denti relazioni di ricorrenza.

Esercizio 2. (8 punti)

Sviluppare e descrivere in pseudocodice un algoritmo efficiente che verifichi se un albero binario `e 1-bilanciato.

Esercizio 3. (8 punti)

E dato il seguente grafo orientato, rappresentato con liste di adiacenza ordinate alfabeticamente:`

h b

c

d e

g

f a

1. Indicare l’ordine di visita BFS e DFS dei vertici del grafo, partendo dal vertice a.

2. Disegnare gli alberi BFS e DFS ottenuti con le visite.

3. Indicare la classificazione degli archi indotta dalla visita DFS.

Esercizio 4. (4 punti)

Dimostrare che un albero binario completo (ogni nodo interno ha esattamente due figli) di 2 n−1 nodi contiene esattamente n foglie.

Riferimenti

Scarica adesso ( PDF - 1 pagine - 68.46 KB )

Documenti correlati

008AA – ALGORITMICA E LABORATORIO

Calcolare la visita DFS su G e si mostri l’albero DFS specificando anche il tipo di archi individuati dalla visita (ossia dell’albero, indietro, in avanti, attraversamento – o

008AA – ALGORITMICA E LABORATORIO

(4+3+3 punti) Si progetti un algoritmo ricorsivo basato sulla tecnica Divide et Impera che calcola il secondo elemento pi` u grande di un vettore A di n interi, senza modificarlo..

008AA – ALGORITMICA E LABORATORIO

(4+4) Si definisca la relazione che consente di calcolare mediante Programmazione Dinamica la Edit Distance di due stringhe S1 e S2, nell’ipotesi che l’errore di mismatch abbia costo

008AA – ALGORITMICA E LABORATORIO

• Si diano le regole per navigare sull’heap ternario, cio` e le regole per cui, dato il nodo i, si possa accedere direttamente ai 3 figli o al padre.. • Si fornisca l’algoritmo

008AA – ALGORITMICA E LABORATORIO

Dato un albero binario T in cui ogni nodo contiene un intero positivo, diciamo che la media di un sottoalbero non vuoto ` e la somma degli interi contenuti nei suoi nodi diviso

008AA – ALGORITMICA E LABORATORIO

Dato un albero binario T di n nodi, scrivere lo pseudocodice di un algoritmo efficiente che restituisce TRUE se per ogni nodo u di T vale la seguente propriet` a: il

008AA – ALGORITMICA E LABORATORIO

Lo pseudocodice della procedura split , richiamata su un nodo con ⇣ figli, `e inoltre mostrato in Figu- ra 6.23 (lo pseudocodice non mostra come aggiornare i campi ed ⇥ di ciascun

008AA – ALGORITMICA E LABORATORIO

In caso di risposta affermativa al punto 2, disegnare l’albero di decisione corrispondente all’algoritmo trovato che risolve il problema con due