Algoritmi e strutture dati: esercizi e domande d’esame

Notazione O grande, tempo di esecuzione degli algoritmi più comuni e compromessi tra array, liste concatenate, alberi, tabelle hash e grafi.

Esercitati gratis su questo corsoEsercitati su questo corsoFai una simulazione d’esame5 esercizi gratuiti ogni giorno. Nessuna carta richiesta.

Pacchetto last-minute (PDF)Formulari, passaggi del metodo ed esercizi con soluzioni complete, pronti da stampare.

Argomenti di questo corso

  1. Algoritmi e complessitàtermini e fatti chiave · applicare i concetti · casi e analisirisposta multipla
  2. Strutture datitermini e fatti chiave · applicare i concetti · casi e analisirisposta multipla
  3. Teoria dei grafigradi e lati · cammini euleriani e alberi · cammini minimi e alberi di coperturacalcoli

Consigli per l’esame di Algoritmi e strutture dati

  • Per i cicli annidati, moltiplica il numero di iterazioni; per i cicli in sequenza, tieni il termine maggiore.
  • Conosci il costo di ricerca, inserimento e cancellazione per ogni struttura dati.
  • Dimezzare l’input a ogni passo dà un tempo logaritmico.

Esempi svolti

Algoritmi e complessitàFacile

Quale notazione descrive un limite superiore della crescita?

  1. AOmega grande (Big Omega)
  2. BOmega piccolo (little omega)
  3. CO grande (Big O)
  4. DTheta grande (Big Theta)
Mostra i suggerimenti
  1. «Al massimo».
  2. Ora due risposte sbagliate sono barrate. Una delle due rimaste è giusta.
Mostra la risposta e la spiegazione

Perché è questa la risposta

O fornisce un limite superiore, Ω un limite inferiore e Θ un limite stretto.

Risposta

C · O grande (Big O)
Strutture datiMedia

Come funziona extract-min in un min-heap binario?

  1. ASi rimuove l'ultimo elemento dell'array
  2. BSi sposta l'ultimo elemento nella radice e lo si fa scendere
  3. CSi rimuove la radice e si spostano tutti gli elementi di una posizione a sinistra
  4. DSi cercano in tutte le foglie il nuovo minimo
Mostra i suggerimenti
  1. Mantieni l'albero completo, poi sistema l'ordine.
  2. Ora due risposte sbagliate sono barrate. Una delle due rimaste è giusta.
Mostra la risposta e la spiegazione

Perché è questa la risposta

L'ultimo elemento riempie il vuoto nella radice e viene scambiato con il figlio minore finché la proprietà di heap non è soddisfatta, in O(log n).

Risposta

B · Si sposta l'ultimo elemento nella radice e lo si fa scendere

Come funziona l’esercitazione

  • “Esercitati su questo corso” mescola esercizi di tutti i suoi argomenti, come in un vero esame.
  • Ogni esercizio ha valori nuovi, così impari il metodo invece di una risposta.
  • Bloccato? Apri prima un piccolo suggerimento e la spiegazione completa solo quando ti serve.
  • Le simulazioni d’esame sono a tempo e senza suggerimenti; alla fine ricevi il punteggio e una revisione completa.

Corsi correlati

Fondamenti di informaticaMatematica discretaReti di calcolatori
Esercitati gratis su questo corsoEsercitati su questo corsoFai una simulazione d’esame5 esercizi gratuiti ogni giorno. Nessuna carta richiesta.