08: Pile e Code
47 Questions
0 Views

Choose a study mode

Play Quiz
Study Flashcards
Spaced Repetition
Chat to lesson

Podcast

Play an AI-generated podcast conversation about this lesson

Questions and Answers

Qual è il risultato della funzione E MPTY(S) quando S.N è uguale a 0?

  • Ritorna false
  • Ritorna true (correct)
  • Genera un errore
  • Non restituisce nulla
  • La funzione TOP(S) restituisce un valore corretto anche se la struttura S è vuota.

    False

    Cosa restituisce la funzione POP(S) quando la lista è vuota?

    Genera un errore di underflow

    La complessità temporale delle operazioni è __________.

    <p>O(1)</p> Signup and view all the answers

    Abbina le seguenti funzioni con il loro comportamento:

    <p>E MPTY(S) = Controlla se la lista è vuota TOP(S) = Restituisce l'elemento in cima alla lista POP(S) = Rimuove e restituisce l'elemento in cima alla lista</p> Signup and view all the answers

    Quale operazione modifica il numero di elementi nella lista?

    <p>POP(S)</p> Signup and view all the answers

    Il comando S.N ← S.N − 1 viene usato esclusivamente in E MPTY(S).

    <p>False</p> Signup and view all the answers

    Quale struttura dati utilizza l'implementazione descritta?

    <p>Una lista</p> Signup and view all the answers

    Quale delle seguenti affermazioni descrive meglio un Tipo di Dato Astratto (ADT)?

    <p>Una struttura dati e una collezione di procedure designate per operare su di essa.</p> Signup and view all the answers

    In una pila, i dati vengono estratti nello stesso ordine in cui sono stati inseriti.

    <p>False</p> Signup and view all the answers

    Quale nome viene dato all'operazione per inserire un elemento in una pila?

    <p>push</p> Signup and view all the answers

    L'operazione di estrazione di un elemento dalla pila è chiamata ______.

    <p>pop</p> Signup and view all the answers

    Abbina i termini con le loro definizioni:

    <p>push = Inserire un elemento nella pila pop = Estrarre un elemento dalla pila pila = Struttura dati LIFO ADT = Tipo di dato astratto</p> Signup and view all the answers

    Quale struttura dati segue il principio LIFO (Last In, First Out)?

    <p>Pila</p> Signup and view all the answers

    Un'implementazione concreta di un ADT richiede sempre una collezione di dati.

    <p>True</p> Signup and view all the answers

    Qual è la relazione tra un tipo astratto e una struttura concreta?

    <p>Analoga a quella fra problema algoritmico e algoritmo</p> Signup and view all the answers

    Quale operazione estrarrà il numero 9 dalla coda?

    <p>dequeue() (prima volta)</p> Signup and view all the answers

    L'operazione 'dequeue()' restituisce il primo elemento inserito nella coda.

    <p>True</p> Signup and view all the answers

    Quali sono i primi tre numeri nella coda dopo l'esecuzione delle operazioni?

    <p>9, 5, 3</p> Signup and view all the answers

    L'operazione di inserimento in una coda è chiamata ______.

    <p>enqueue</p> Signup and view all the answers

    Dopo l'operazione 'dequeue(), dequeue(), queue(1)', qual è il primo elemento nella coda?

    <p>1</p> Signup and view all the answers

    L'operazione 'enqueue(2)' inserisce il numero 2 come ultimo nella coda.

    <p>True</p> Signup and view all the answers

    Quanti elementi rimangono nella coda alla fine delle operazioni?

    <p>2</p> Signup and view all the answers

    Abbina le operazioni alle loro descrizioni:

    <p>enqueue() = Inserisce un elemento nella coda dequeue() = Estrae un elemento dalla coda front() = Restituisce il primo elemento della coda queue() = Aggiunge un elemento alla coda</p> Signup and view all the answers

    Le pile e le code sono esempi di tipi di dato astratti.

    <p>True</p> Signup and view all the answers

    Nome di un operatore booleano.

    <p>¬ (negazione)</p> Signup and view all the answers

    Un tipo di dato __________ è rappresentato dai valori 0, 1, 2, ...

    <p>unsigned int</p> Signup and view all the answers

    Abbina i seguenti tipi di dato con le loro descrizioni:

    <p>unsigned int = Valori 0, 1, 2, ... boolean = Valori T, F float = Numeri con parte decimale char = Un singolo carattere</p> Signup and view all the answers

    Quale operazione è associata al tipo booleano?

    <p>Negazione</p> Signup and view all the answers

    Il tipo di dato astratto (ADT) è sempre associato a un linguaggio di programmazione tipato.

    <p>False</p> Signup and view all the answers

    Cosa significa ADT?

    <p>Tipo di dato astratto</p> Signup and view all the answers

    Quale operazione richiede di spostare gli elementi rimanenti quando si estrae un elemento dalla coda?

    <p>Dequeue() nell'ultima posizione</p> Signup and view all the answers

    La struttura dati coda richiede sempre operazioni di spostamento in O(1).

    <p>False</p> Signup and view all the answers

    Qual è la funzione di 'head' in una coda implementata tramite array?

    <p>Indica l'inizio della coda.</p> Signup and view all the answers

    Quando si implementa una coda usando un array, si utilizza un array in modo ______.

    <p>circolare</p> Signup and view all the answers

    Abbina le operazioni di coda con il loro effetto:

    <p>Queue(3) = Aggiungi 3 alla coda Dequeue() = Rimuovi elemento dalla coda Queue(5) = Aggiungi 5 alla coda Queue(9) = Aggiungi 9 alla coda</p> Signup and view all the answers

    Quale delle seguenti operazioni di coda è corretta secondo l'implementazione data?

    <p>Dequeue() rimuove il primo elemento presente</p> Signup and view all the answers

    L'array utilizzato per la coda non necessita di tenere traccia delle posizioni di head e tail.

    <p>False</p> Signup and view all the answers

    Dopo le operazioni queue(3), queue(5), dequeue(), che elemento rimane in testa alla coda?

    <p>5</p> Signup and view all the answers

    Qual è la condizione per determinare se una coda è piena durante l'operazione E NQUEUE?

    <p>Se S IZE(Q) è uguale a Q.M - 1</p> Signup and view all the answers

    L'operazione F RONT restituisce il valore in testa alla coda senza alcuna verifica.

    <p>False</p> Signup and view all the answers

    Cosa restituisce la funzione S IZE(Q) quando Q.tail è maggiore o Uguale a Q.head?

    <p>Q.tail - Q.head</p> Signup and view all the answers

    La funzione D EQUEUE restituisce ___ dalla coda e avanza il puntatore in testa.

    <p>un elemento</p> Signup and view all the answers

    Abbina le operazioni di coda con la loro descrizione:

    <p>E NQUEUE = Aggiungere un elemento alla coda D EQUEUE = Rimuovere un elemento dalla coda F RONT = Restituisce l'elemento in testa alla coda S IZE = Restituisce il numero di elementi nella coda</p> Signup and view all the answers

    Cosa succede se si tenta di fare D EQUEUE su una coda vuota?

    <p>Genera un errore di underflow</p> Signup and view all the answers

    Il metodo N EXT C ELL aumenta l'indice di un elemento nella coda.

    <p>True</p> Signup and view all the answers

    Quale errore può verificarsi durante l'operazione E NQUEUE?

    <p>erroroverflow</p> Signup and view all the answers

    Study Notes

    Introduzione

    • Il corso si intitola "Algoritmi e strutture dati" e fa parte del corso di Laurea in Informatica.
    • I docenti sono Ugo de'Liguoro e András Horváth.

    Indice

    • Tipo di dato astratto (ADT)
    • Pile (stack)
    • Code (queue)

    Sommario

    • Obiettivo: introdurre il concetto di tipo di dato astratto (ADT), specificare pile e code come ADT e definire diverse implementazioni.

    1. Tipi di dati

    • I linguaggi di programmazione tipati forniscono tipi predefiniti.
    • Ogni tipo di dato è associato a un insieme di valori e operatori.
    • Esempi: unsigned int (0, 1, 2, ... con operazioni +, -, ...) e boolean (T, F con operazioni ¬, ^, ...).
    • Ogni operatore funziona secondo certe regole.
    • Quando si usano tipi predefiniti del linguaggio, non si considera come vengono effettuate le operazioni.
    • Si possono introdurre nuovi tipi di dati e implementare operazioni per i nuovi tipi.

    1. Tipo di dato astratto (ADT)

    • Un tipo di dato è astratto se è descritto prescindendo dalla sua concreta implementazione.
    • La descrizione riguarda:
      • La collezione di dati: da quali tipi di dati si costruisce la struttura del nuovo tipo (senza specificare la costruzione).
      • Le operazioni: che cosa devono fare le operazioni definite sul nuovo tipo (senza indicare come lo devono fare).
      • La complessità: eventuali vincoli sulla complessità delle operazioni.
      • Una descrizione delle operazioni con le pre e post-condizioni che costituisce una sorta di assiomatizzazione del tipo.
    • Un'implementazione concreta di un ADT è una struttura dati per memorizzare la collezione di dati e una collezione di procedure per realizzare le operazioni.
    • La relazione tra tipo astratto e struttura concreta è analoga a quella tra problema algoritmico e algoritmo.

    2. Pile (stack)

    • I dati vengono estratti in ordine inverso rispetto all'inserimento.
    • Terminologia:
      • push: inserire un elemento nella pila.
      • pop: estrarre un elemento dalla pila.
      • top: restituisce l'elemento in cima alla pila.
    • Esempio di operazioni: push(3), push(5), push(9), pop(), pop(), push(1), push(8), push(2), pop(), push(6).
      • Pila risultante (dall'alto): 6, 8, 1, 3

    2. Pila come ADT

    • Collezione dati: elementi di qualunque tipo T di dati.
    • Operazioni:
      • void PUSH(Stack S, T t): inserisce l'elemento t nella pila S.
      • T POP(Stack S): estrae l'elemento in cima alla pila S e lo restituisce.
      • T TOP(Stack S): restituisce l'elemento in cima alla pila S senza rimuoverlo.
      • bool EMPTY(Stack S): restituisce true se la pila S è vuota, false altrimenti.
      • int SIZE(Stack S): restituisce il numero di elementi nella pila S.
    • Assiomi:
      • SIZE(S), EMPTY(S), PUSH(S, t) sono sempre definiti.
      • POP(S), TOP(S) sono definiti se e solo se EMPTY(S) restituisce falso.
      • EMPTY(S), SIZE(S) e TOP(S) non modificano la pila S.
      • EMPTY(S) restituisce Vero se e solo se SIZE(S) restituisce 0.
      • La sequenza PUSH(S, t), POP(S) restituisce t e non modifica la pila S.
      • La sequenza PUSH(S, t), TOP(S) restituisce t.
      • PUSH(S, t) incrementa SIZE(S) di 1.
      • POP(S) decrementa SIZE(S) di 1.

    2. Implementazione concreta con array

    • Utilizzo di un array statico di M celle per implementare la pila.
    • Grazie al meccanismo LIFO (Last In, First Out), gli elementi occupano le prime posizioni dell'array.
    • Quando ci sono N elementi, il prossimo elemento da estrarre è nella posizione N.
    • PUSH(S, t) è definito se SIZE(S) < M.

    2. Implementazione concreta con lista

    • Utilizzo di una lista semplice con sentinella per evitare controlli.
    • Q.head indica l'elemento da estrarre.
    • Q.tail indica l'ultimo elemento inserito.
    • Q.head == nil rappresenta una coda vuota.
    • Operazioni:
    • ENQUEUE(Q, t): inserisce l'elemento t in coda.
    • SIZE(Q): restituisce il numero di elementi presenti nella coda.
    • EMPTY(Q): restituisce Vero se la coda è vuota, Falso altrimenti.
    • FRONT(Q): restituisce l'elemento in testa alla coda (senza rimuoverlo).
    • DEQUEUE(Q): estrae l'elemento in testa alla coda e lo restituisce.

    3. Code (queue)

    • I dati vengono estratti nello stesso ordine in cui sono stati inseriti.
    • Terminologia: - enqueue: inserire un elemento nella coda. - dequeue: estrarre un elemento dalla coda. - front: restituisce il primo elemento nella coda.
    • Esempio di operazioni: queue(3), queue(5), queue(9), dequeue(), dequeue(), queue(1), queue(8), queue(2), dequeue(), queue(7), queue(4).

    3. Coda come ADT

    • Collezione Dati: Elementi di qualunque tipo (T) di dati.
    • Operazioni: void ENQUEUE(Queue Q, T t), T DEQUEUE(Queue Q), T FRONT(Queue Q), bool EMPTY(Queue Q), int SIZE(Queue Q).
    • Assiomi:
    • SIZE(Q), EMPTY(Q), ENQUEUE(Q, t) sono sempre definiti.
    • DEQUEUE(Q) e FRONT(Q) sono definiti se e solo se EMPTY(Q) restituisce falso.
    • EMPTY(Q), SIZE(Q), FRONT(Q) non modificano la coda Q.
    • Se SIZE(Q) = N e viene effettuata ENQUEUE(Q, t), allora dopo N esecuzioni di DEQUEUE(Q) si ottiene FRONT(Q)=t.
    • Se FRONT(Q) = t, allora DEQUEUE (Q) estrae t dalla coda.
    • ENQUEUE(Q, t) incrementa SIZE(Q) di 1.
    • DEQUEUE(Q) decrementa SIZE(Q) di 1.

    3. Implementazione concreta con array

    • Utilizzo di un array statico di M celle.
    • Implementazione circolare di head e tail per evitare lo spostamento di elementi.
    • SIZE(Q): restituisce il numero di elementi in coda.
    • EMPTY(Q): restituisce True se la coda è vuota, False altrimenti (Q.head == Q.tail).

    3. Implementazione concreta con lista

    • Utilizzo di una lista semplice con un puntatore all'ultimo elemento per ottimizzare ENQUEUE.
    • Q.head indica l'elemento da estrarre.
    • Q.tail indica l'ultimo elemento inserito.
    • Come si controlla se la coda è vuota?
      • Q.head == nil (o null).
    • ENQUEUE(Q, t): inserisce un elemento in testa.
    • DEQUEUE(Q): estrae un elemento da coda.

    3. Confronto delle implementazioni

    • La complessità temporale di tutte le operazioni è O(1) in entrambe le implementazioni (array circolare e lista).
    • La complessità spaziale dell'array è O(M), proporzionale al numero massimo di elementi. La complessità spaziale della lista è O(N) dove N è il numero attuale di elementi (c'è l'overhead dovuto ai puntatori).
    • Nell'array, si deve stabilire in anticipo la dimensione massima M, mentre nelle liste non c'è questo vincolo.

    3. Utilizzo della struttura dati coda

    • Buffer
    • Visita in ampiezza di grafi
    • Simulazione

    Studying That Suits You

    Use AI to generate personalized quizzes and flashcards to suit your learning preferences.

    Quiz Team

    Related Documents

    Pile e code PDF

    Description

    Metti alla prova le tue conoscenze sulle strutture dati, in particolare sulle pile e i tipi di dato astratti. Rispondi a domande riguardanti le funzioni E MPTY, TOP e POP, e comprendi il comportamento delle operazioni su una pila. Scopri quanto sei esperto su questo argomento fondamentale in informatica.

    More Like This

    Data Structure: Stacks as Abstract Data Type (ADT)
    10 questions
    Stack Data Structure Overview
    15 questions
    Data Structures: Stacks Quiz
    5 questions
    Use Quizgecko on...
    Browser
    Browser