• 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;

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

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