Paniere completo Algoritmi e strutture dati

LIFO.

La funzione push in una pila:

inserisce un elemento in testa.

La funzione pop in una pila:

elimina l'elemento in testa.

La scelta della struttura dati per implementare una pila:

ricade negli array o nei puntatori a seconda dello scenario.

Una pila:

può essere usata per la valutazione di una espressione.

L'implementazione di una pila tramite array prevede:

la conoscenza del numero massimo di elementi che la pila può contenere.

Non è possibile accedere direttamente agli elementi all'interno della pila senza

rimuoverli:

è un'affermazione vera.

Le operazioni di base su una pila hanno complessità:

O(1).

L'operazione di push in una pila ha complessità:

O(1).

L'operazione di pop in una pila ha complessità:

O(1).

La coda è un sistema:

FIFO.

La funzione EnQueue in una coda:

inserisce un elemento in coda.

La funzione DeQueue in una coda:

elimina l'elemento in testa.

La scelta della struttura dati per implementare una coda:

ricade negli array o nei puntatori a seconda dello scenario.

Una coda circolare:

supera il problema dello shift dei valori in un array quando c'è una DeQueue.

L'implementazione di una coda circolare:

può avvenire tramite array con 2 variabili che mantengono i valori di head e tail.

L'implementazione di una coda in C++ può avvenire tramite:

la classe queue.

Le operazioni di base su una coda circolare hanno complessità:

O(1).

Le operazioni di base su una coda non circolare hanno complessità:

O(n).

L'operazione di EnQueue in una coda circolare ha complessità:

O(1).

Un albero di ricerca:

è una struttura ordinata.

Un albero può essere:

decisionale.

In un albero:

esiste un cammino unico dalla radice ad ogni nodo.

Cosa si intende per "albero connesso":

per ogni coppia di nodi x, y, esiste un cammino da x ad y.

Un albero di ricerca:

è un albero binario in cui i valori di ogni nodo sono maggiori dei valori dei nodi figlio a

sinistra e minori dei valori dei nodi figlio a destra.

Ogni nodo che non presenta archi uscenti è detto:

foglia.

A parte la radice:

ogni nodo ha esattamente un arco entrante.

La profondità di un nodo:

è la lunghezza del cammino semplice dalla radice al nodo.

Il grado di un nodo in un albero:

è il numero di sotto alberi del nodo.

Il livello di un nodo:

è il numero di livelli tra la radice dell'albero e il nodo stesso.

Nel seguente albero indicare qual è il livello dei nodi B e C: 1

Nel seguente albero indicare qual è il livello dei nodi B e C: 1

Indicare quali alberi in figura sono binari: sono tutti binari

Nell’albero in figura le foglie sono : D, E , F , G

La seguente funzione: crea un nodo con un dato ed un genitore assegnato

Questo codice: consente di gestire un nodo di un albero binario

Tale funzione può essere correttamente definita come: insertLeft

Tale funzione può essere correttamente definita come: inserRight

Nello schema in figura: è rappresentato un albero binario

Tale classe Node è definita in linguaggio: Python

Un albero binario è un albero radicato in cui ogni nodo ha: esattamente due figli,

identificati come figlio sinistro e figlio destro.

Per tenere traccia dei nodi da visitare, la DFS usa: uno stack

Per tenere traccia dei nodi da visitare, la BFS usa: una coda

La DFS esplora prima: i nodi più profondi dell'albero

Dato il seguente albero binario, indicare l’ordine di visita in pre-order: A B C D E F G

Dato il seguente albero binario, indicare l’ordine di visita in-order: C B D A F E G

Dato il seguente albero binario, indicare l’ordine di visita post-order: C D B F G E A

Nell’immagine, le etichette degli archi indicano: il totale dei nodi che provengono dal

sottoalbero

Tale codice rappresenta una visita in pre-order: iterativa

La complessità delle visite DFS in un albero binario è: lineare

Qualora la DFS in modalità ricorsiva sia troppo memory-consuming si può adottare come

strategia: la versione iterativa

La visita in ampiezza: può far uso di una coda

La specifica insertSibling(Node t) può essere usata: per inserire il sottoalbero radicato in

t come prossimo fratello nodo di questo nodo

Il riferimento all'array contenente i figli: è tipico di un nodo di un albero generico

In un albero generico: non vi sono vincoli sul grado di un nodo

La visita in ampiezza: può essere usata su alberi generici

Tale rappresentazione può essere usata per: rappresentare il nodo di un albero generico

Tale struttura di nodo: può essere usata per un albero generico

Tale funzione: è corretta

Il nome di questa funzione è: bfs

In nome di questa funzione è: bfs

In un albero binario di ricerca: due elementi non possono avere la stessa chiave

Un dizionario: è un tipo di insieme dinamico che associa ad ogni elemento una coppia

chiave-valore

L'operazione di lookup in un albero binario di ricerca bilanciato ha complessità:

logaritmica

In un albero binario di ricerca, per ogni nodo N dell'albero: l'informazione associata ad

ogni nodo nel sottoalbero sinistro di N è strettamente minore dell'informazione associata ad

N

Il seguente albero: è un ABR

Il seguente albero: non è un ABR

Il nome di questa funzione è: is_bst

Il nome di questa funzione è: is_bst

Il nome di questa funzione è: bfs

Questo albero: è bilanciato

Il nome di questa funzione è: insert_bst

In un albero binario di ricerca totalmente bilanciato, l'operazione di lookup: ha

complessità logaritmica

In un albero binario di ricerca perfettamente sbilanciato, l'operazione di lookup: ha

complessità lineare

L'inserimento di un elemento in un ABR già popolato, prevede 2 fasi; nella prima si

cerca il nodo genitore X e nella seconda: il nodo è inserito come foglia

L'inserimento di un elemento in un ABR, nel caso peggiore ha complessità: lineare

L'inserimento di un elemento in un ABR, nel caso medio ha complessità: logaritmica

Nel caso di eliminazione di una foglia da un ABR: si elimina semplicemente il nodo

Nel caso di eliminazione di un nodo con figlio in un ABR: si elimina semplicemente il

nodo

Nel caso di eliminazione di un nodo con 2 figli in un ABR: si deve trovare il successore

o il predecessore e sostituire il suo valore con quello del successore/predecessore

La cancellazione in un ABR equilibrato ha complessità: logaritmica

Un albero è perfettamente bilanciato (APB) se, per ogni nodo: il numero di nodi del suo

sottoalbero sinistro e il numero di nodi del suo sottoalbero destro differiscono al più di 1

In un albero rosso-nero: le foglie sono costituite da nodi speciali Nil

In un albero rosso-nero: la radice è nera

In un albero rosso-nero: entrambi i figli di un nodo rosso sono neri

In un albero rosso-nero: ogni cammino semplice da un nodo ad una delle foglie contenute

nel suo sottoalbero ha lo stesso numero di nodi neri

Un ABR è AVL-bilanciato: se, per ogni nodo, l'altezza del suo sottoalbero sinistro e

l'altezza del suo sottoalbero destro differiscono al più di 1

L'altezza di un nodo X: è pari a Altezza(X) = max(Altezza(sinistro(X)), Altezza(destro(X))) +

1

Considerando il seguente ABR, eseguiamo la sostituzione del nodo 46 con il 52:

l’albero non è più ABR

Il seguente albero: è un AVL

Il seguente albero: non è un AVL

Il seguente albero: è rosso-nero

Il seguente albero: è rosso-nero

Cos'è un albero rosso-nero?

Un albero rosso-nero è un tipo di albero binario di ricerca bilanciato in cui ogni nodo ha un

colore (rosso o nero) e segue specifiche regole per mantenere l'equilibrio durante le

operazioni di inserimento e cancellazione.

Qual è la regola riguardante il colore della radice in un albero rosso-nero?

La radice di un albero rosso-nero è sempre nera.

Cosa succede alle foglie in un albero rosso-nero?

Le foglie in un albero rosso-nero sono nodi speciali (NIL) e sono sempre nere.

Qual è la restrizione sul colore dei nodi rossi in un albero rosso-nero?

Se un nodo è rosso, entrambi i suoi figli devono essere neri. Non possono esserci due nodi

rossi consecutivi lungo un cammino.

Cosa garantisce la regola dei nodi neri su ogni cammino in un albero rosso-nero?

Ogni cammino semplice da un nodo a una foglia contiene lo stesso numero di nodi neri,

garantendo che l'albero non diventi sbilanciato.

Come si mantiene l'equilibrio nell'albero rosso-nero?

Le cinque proprietà dell'albero rosso-nero assicurano che l'albero rimanga bilanciato, con

un tempo di ricerca, inserimento e cancellazione logaritmico, evitando che l'albero diventi

troppo sbilanciato o degeneri in una lista.

Il seguente albero: è rosso-nero

Il seguente albero: è rosso-nero

Nel seguente albero volendo costruirlo come rosso-nero: il 30 può essere configurato

come B

Nel seguente albero: 60 è R

Il seguente albero: è rosso-nero

Il seguente albero: non è rosso-nero

Il seguente albero: non è rosso-nero

Una rotazione a destra consiste nel prendere il nodo figlio sinistro del nodo da

ruotare e:

e promuoverlo a nodo padre, spostando il nodo padre corrente come suo figlio destro.

Una rotazione a destra è utile:

quando il figlio sinistro del nodo da ruotare ha un'altezza maggiore rispetto al figlio destro.

In una rotazione a sinistra:

il figlio destro del nodo da ruotare viene promosso a nodo padre, spostando il nodo padre

corrente come suo figlio sinistro.

Una rotazione a sinistra è utile:

quando il figlio destro del nodo da ruotare ha un'altezza maggiore rispetto al figlio sinistro.

Definiamo altezza nera di x:

il numero di nodi neri lungo ogni percorso da un nodo x (incluso) ad una foglia (nodo NIL).

Se il nuovo nodo inserito in un albero rosso nero, ha un padre nero:

non si devono fare modifiche.

La complessità dell'inserimento in un albero rosso nero è:

logaritmica.

Nel seguente albero, occorre ruotare il seguente nodo per renderlo rosso-nero: 60

Tale albero: è rosso-nero

Il seguente albero: è rosso-nero

Nello schema, se si elimina il nodo 1 ci ritroviamo nella casistica: caso3 (fratello nero, nipote

sinistro rosso e destro nero)

Nello schema, se si elimina il nodo 3 ci ritroviamo nella casistica: caso2 (fratello nero e nipoti

neri)

La seguente funzione ha nome: rotate_left

In un grafo G=(V,E), V ed E rappresentano:

vertici ed archi.

Un arco è