Podcast
Questions and Answers
Qual è il costo per accedere a un elemento in un array?
Qual è il costo per accedere a un elemento in un array?
L'inserimento di un elemento in un array statico ha un costo lineare.
L'inserimento di un elemento in un array statico ha un costo lineare.
False
Qual è il costo per rimuovere un elemento da un array?
Qual è il costo per rimuovere un elemento da un array?
O(N)
Un array in cui il numero massimo di elementi è fissato è chiamato array ____.
Un array in cui il numero massimo di elementi è fissato è chiamato array ____.
Signup and view all the answers
Abbina le operazioni agli aspetti dei costi:
Abbina le operazioni agli aspetti dei costi:
Signup and view all the answers
Cosa significa la notazione O(1) nel contesto degli array?
Cosa significa la notazione O(1) nel contesto degli array?
Signup and view all the answers
In un array statico, gli elementi vengono sempre inseriti nelle prime N celle.
In un array statico, gli elementi vengono sempre inseriti nelle prime N celle.
Signup and view all the answers
Nel caso di un inserimento di un elemento, se A.N è uguale a A.M, l'operazione restituisce ____.
Nel caso di un inserimento di un elemento, se A.N è uguale a A.M, l'operazione restituisce ____.
Signup and view all the answers
Qual è il costo di un inserimento se M è sufficientemente grande e si sfora poche volte?
Qual è il costo di un inserimento se M è sufficientemente grande e si sfora poche volte?
Signup and view all the answers
Se N è uguale a M, i successivi inserimenti richiedono riallocazioni.
Se N è uguale a M, i successivi inserimenti richiedono riallocazioni.
Signup and view all the answers
Cosa si fa quando l'array è pieno durante un inserimento?
Cosa si fa quando l'array è pieno durante un inserimento?
Signup and view all the answers
Quando il numero di elementi si riduce ad ______ della dimensione, dimezziamo la dimensione dell'array.
Quando il numero di elementi si riduce ad ______ della dimensione, dimezziamo la dimensione dell'array.
Signup and view all the answers
Qual è la principale differenza tra la prima e la seconda idea per l'implementazione di un ADT?
Qual è la principale differenza tra la prima e la seconda idea per l'implementazione di un ADT?
Signup and view all the answers
La cancellazione di un elemento comporta sempre una riallocazione dell’array.
La cancellazione di un elemento comporta sempre una riallocazione dell’array.
Signup and view all the answers
Abbina le seguenti operazioni con la loro descrizione:
Abbina le seguenti operazioni con la loro descrizione:
Signup and view all the answers
Il costo totale di una serie di operazioni può essere rappresentato come ______.
Il costo totale di una serie di operazioni può essere rappresentato come ______.
Signup and view all the answers
Qual è la complessità temporale per svolgere una ricerca in un array non ordinato?
Qual è la complessità temporale per svolgere una ricerca in un array non ordinato?
Signup and view all the answers
L'inserimento di un elemento in un array ordinato è sempre O(1).
L'inserimento di un elemento in un array ordinato è sempre O(1).
Signup and view all the answers
Qual è l'algoritmo utilizzato per inserire un elemento mantenendo un array ordinato?
Qual è l'algoritmo utilizzato per inserire un elemento mantenendo un array ordinato?
Signup and view all the answers
Espandere un array richiede un costo di _____ perché è necessario allocare memoria e copiare gli elementi.
Espandere un array richiede un costo di _____ perché è necessario allocare memoria e copiare gli elementi.
Signup and view all the answers
Abbina le operazioni agli array con la loro complessità:
Abbina le operazioni agli array con la loro complessità:
Signup and view all the answers
Quale delle seguenti affermazioni è vera riguardo all'algoritmo ArrayExtend?
Quale delle seguenti affermazioni è vera riguardo all'algoritmo ArrayExtend?
Signup and view all the answers
Qual è il tempo di inserimento di un elemento nella tabella hash utilizzando concatenamento?
Qual è il tempo di inserimento di un elemento nella tabella hash utilizzando concatenamento?
Signup and view all the answers
La complessità per la cancellazione in un array è O(1).
La complessità per la cancellazione in un array è O(1).
Signup and view all the answers
Qual è la complessità per cercare il massimo in un array ordinato?
Qual è la complessità per cercare il massimo in un array ordinato?
Signup and view all the answers
Nel caso peggiore, la ricerca in una lista con indice hash può richiedere Θ(N).
Nel caso peggiore, la ricerca in una lista con indice hash può richiedere Θ(N).
Signup and view all the answers
Qual è il costo della cancellazione di un elemento in una lista hash?
Qual è il costo della cancellazione di un elemento in una lista hash?
Signup and view all the answers
Il valore hash di una chiave si calcola in tempo __________.
Il valore hash di una chiave si calcola in tempo __________.
Signup and view all the answers
Qual è il fattore di carico α nella definizione della tabella hash?
Qual è il fattore di carico α nella definizione della tabella hash?
Signup and view all the answers
La funzione hash deve sempre distribuire uniformemente le chiavi fra le celle.
La funzione hash deve sempre distribuire uniformemente le chiavi fra le celle.
Signup and view all the answers
Abbina le seguenti operazioni con i loro tempi di esecuzione:
Abbina le seguenti operazioni con i loro tempi di esecuzione:
Signup and view all the answers
Quando la lista T[h(k)] è vuota oppure contiene solo un elemento, la ricerca costa __________.
Quando la lista T[h(k)] è vuota oppure contiene solo un elemento, la ricerca costa __________.
Signup and view all the answers
Qual è la complessità ammortizzata di un inserimento utilizzando la prima idea con n inserimenti?
Qual è la complessità ammortizzata di un inserimento utilizzando la prima idea con n inserimenti?
Signup and view all the answers
La complessità ammortizzata di un inserimento può essere O(1) utilizzando la seconda idea.
La complessità ammortizzata di un inserimento può essere O(1) utilizzando la seconda idea.
Signup and view all the answers
Quale è il costo totale (in senso ammortizzato) della rimozione degli elementi con la seconda idea considerando DELETE che rimuove l'ultimo elemento?
Quale è il costo totale (in senso ammortizzato) della rimozione degli elementi con la seconda idea considerando DELETE che rimuove l'ultimo elemento?
Signup and view all the answers
La complessità ammortizzata di K inserimenti semplici utilizzando la seconda idea è __________.
La complessità ammortizzata di K inserimenti semplici utilizzando la seconda idea è __________.
Signup and view all the answers
Abbina il tipo di operazione al suo costo ammortizzato:
Abbina il tipo di operazione al suo costo ammortizzato:
Signup and view all the answers
Qual è il valore di N se si effettuano 2K inserimenti?
Qual è il valore di N se si effettuano 2K inserimenti?
Signup and view all the answers
Espandere l'array di un numero costante di elementi comporta una complessità ammortizzata di O(n).
Espandere l'array di un numero costante di elementi comporta una complessità ammortizzata di O(n).
Signup and view all the answers
Riporta il nome della struttura dati in cui l'ordine degli elementi è determinato dai puntatori.
Riporta il nome della struttura dati in cui l'ordine degli elementi è determinato dai puntatori.
Signup and view all the answers
Qual è il costo medio per percorrere una lista in una tabella hash, secondo la descrizione data?
Qual è il costo medio per percorrere una lista in una tabella hash, secondo la descrizione data?
Signup and view all the answers
Il tempo medio richiesto per trovare un elemento in una tabella hash è sempre costante.
Il tempo medio richiesto per trovare un elemento in una tabella hash è sempre costante.
Signup and view all the answers
Cosa rappresenta α nella descrizione della tabella hash?
Cosa rappresenta α nella descrizione della tabella hash?
Signup and view all the answers
Il tempo richiesto per cercare un elemento scelto a caso in una tabella hash è proporzionale a _____.
Il tempo richiesto per cercare un elemento scelto a caso in una tabella hash è proporzionale a _____.
Signup and view all the answers
Abbina i seguenti termini ai loro significati:
Abbina i seguenti termini ai loro significati:
Signup and view all the answers
Qual è l'effetto dell'uniformità semplice nella risoluzione delle collisioni nelle tabelle hash?
Qual è l'effetto dell'uniformità semplice nella risoluzione delle collisioni nelle tabelle hash?
Signup and view all the answers
L'inserimento in testa nella lista significa che gli elementi più recenti sono sempre in cima.
L'inserimento in testa nella lista significa che gli elementi più recenti sono sempre in cima.
Signup and view all the answers
Qual è la formula per il tempo medio di ricerca di un elemento nella lista?
Qual è la formula per il tempo medio di ricerca di un elemento nella lista?
Signup and view all the answers
Per trovare l'elemento _____, si deve esaminare anche gli elementi che sono stati inseriti dopo di esso.
Per trovare l'elemento _____, si deve esaminare anche gli elementi che sono stati inseriti dopo di esso.
Signup and view all the answers
In media, quanti elementi precedono l'elemento xi nella lista?
In media, quanti elementi precedono l'elemento xi nella lista?
Signup and view all the answers
Study Notes
Array, Liste e Tabelle Hash
- Obiettivi: Capire come la scelta delle strutture dati per rappresentare insiemi dinamici influenzi il tempo di accesso ai dati. Argomenti: array (statici e ridimensionabili), liste, hash, costo ammortizzato.
Insiemi Dinamici (Dizionari)
- Strutture: Rappresentano insiemi dinamici con un numero finito di elementi, modificabili e con numero variabile di elementi.
- Attributi: Ogni elemento ha una chiave univoca.
- Tipi di Operazioni: Interrogazione (query) e modifiche (insert, search, delete). Operazioni specifiche se le chiavi sono ordinate (minimum, maximum, successor, predecessor)
Array
- Struttura: Sequenza di caselle con dimensione fissa (statico) o ridimensionabile. Le caselle hanno dimensioni e posizioni fisse nella memoria.
- Adozione Iniziale (Indirizzo base): L'indirizzo del primo elemento è costante.
- Accesso: L'accesso ad un elemento specifico avviene in tempo costante (O(1)), perché l'indirizzo dell'elemento è calcolabile direttamente.
- Inserimento (ARRAYINSERT): Se l'array non è pieno, l'inserimento ha costo costante (O(1)). Altrimenti, se l'array è pieno, l'inserimento richiede prima di ridimensionare l'array (O(N)).
- Cancellazione (ARRAYDELETE): Ha una complessità di O(N), poiché richiede di spostare gli elementi successivi per occupare la posizione cancellata.
- Ricerca (ARRAYSEARCH): Ha complessità O(N), perché si deve scorrere linearmente l'array.
Array Ridimensionabili
- Necessità: Per gestire casi in cui il numero di elementi non è noto in anticipo.
- Espansione: L'array viene espanso quando è pieno (operazione O(N)), il che implica copiare tutti gli elementi nell'array nuovo.
- Approcci: Due approcci sono presentati per l'array ridimensionabile. Il primo richiede un nuovo array (ed espande e copia) ogni volta che si raggiunge la capacità massima. Il secondo approccio (più efficiente) raddoppia la dimensione dell'array quando è pieno e dimezza quando è meno di ¼ pieno.
Liste
- Struttura: Struttura dati lineare dove l'ordine degli elementi è determinato da puntatori (che indicano l'elemento successivo).
- Operazioni: Ricerca (O(N)), Inserimento in testa (O(1)), Rimozione di un elemento (O(1)).
- Concatenamento Doppio: Liste che memorizzano sia il puntatore al successivo elemento che al precedente elemento.
Hashing
- Tabelle Hash: Strutture dati che consentono operazioni di inserimento, ricerca e cancellazione con un tempo medio costante (O(1)).
- Funzione Hash: Mappa le chiavi nell'universo delle chiavi a posizioni di un array (tabella hash). Una buona funzione hash distribuisce le chiavi uniformemente nella tabella hash riducendo il numero di collisioni.
- Collisioni: Quando due o più chiavi vengono mappate alla stessa posizione nella tabella hash.
- Risoluzione delle Collisioni: Due tecniche principali: concatenamento e indirizzamento aperto.
Tavole a Indirizzamento Diretto
- Idea: Ogni chiave ha una posizione specifica nella tabella e l'accesso ad un elemento ha un costo costante (O(1)).
- Limiti: Strutturamolto spaziale perché richiede una memorizzazione per ogni possibile chiave negli insiemi.
Studying That Suits You
Use AI to generate personalized quizzes and flashcards to suit your learning preferences.
Related Documents
Description
Scopri come le strutture dati come array e tabelle hash influenzano l'efficienza nel tempo di accesso ai dati. Il quiz approfondisce le operationi su insiemi dinamici e le differenze tra strutture statiche e dinamiche. Un'opportunità per mettere alla prova la tua comprensione di questi concetti fondamentali.
