• Non ci sono risultati.

Analizzare la complessit`a dell’algoritmo proposto

N/A
N/A
Info
Scarica
Protected

Academic year: 2021

Condividi "Analizzare la complessit`a dell’algoritmo proposto"

Copied!
1
0
0

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

Scarica adesso ( 1 pagine )

Testo completo

(1)

008AA – ALGORITMICA E LABORATORIO Appello del 23 Gennaio 2016

Cognome Nome: N. Matricola: Corso: A B

Esercizio 1. (9 punti)

Sia A un array di n interi tale che, ∀ i, 1 ≤ i ≤ n, A[i] = O(n).

1. Progettare e descrivere in pseudocodice un algoritmo che ordini A.

2. Analizzare la complessit`a in tempo e in spazio dell’algoritmo proposto.

Esercizio 2. (9 punti)

Dato un albero binario T , progettare e descrivere in pseudocodice un algoritmo che, per ogni chiave dell’albero, stampi la sua altezza. Analizzare la complessit`a dell’algoritmo proposto.

Esercizio 3. (9 punti)

Descrivere in pseudocodice l’algoritmo di visita DFS di un grafo orientato G(V, E) facendo l’ipotesi che G sia rappresentato con matrice di adiacenza.

Esercizio 4. (3 punti)

Risolvere la seguente equazione di ricorrenza:

T (n) =

 8T (n/2) + 2n2 n > 1

1 n = 1

Riferimenti

Scarica adesso ( PDF - 1 pagine - 73.73 KB )

Documenti correlati

visita di un albero binario

costruire un albero binario di ricerca Marco Lapegna – Laboratorio di Programmazione 2 Cenni agli alberi. procedura ricerca(in: radice, e;

ESERCIZI (da temi d’esame)

Dato un albero binario, progettare un algoritmo efficiente per determinare il minimo valore di ∆ per cui l’albero risulti ∆-bilanciato. Analizzare la complessit` a

008AA – ALGORITMICA E LABORATORIO

Dato un array a di n interi, progettare un algoritmo efficiente che costruisca ricorsivamente un albero binario bilanciato tale che a[i] sia l(i+1)-esimo campo u.dato in ordine

ESERCIZI (alberi binari, alberi binari di ricerca, dizionari)

Dato un albero binario i cui nodi sono colorati di rosso o di nero, progettare un algoritmo efficiente che calcoli il numero di nodi aventi lo stesso numero di discendenti rossi

AEREO ALBERO

[r]

a come albero A come… A a

[r]

A a come albero A a

[r]

Un albero nella casadi

Sembravano tutti aspettare qualcosa e visto che tutti erano tranquilli Il cerbiatto pensò che fosse normale per gli esseri umani avere gli alberi dentro casa!. Così pensando