FP Alg. Ing. Inf.

Con riferimento all’operazione di “inserzione” degli alberi binari di ricerca (BST), quale delle seguenti affermazioni è vera?. Il caso peggiore si verifica quando l’albero è completamente sbilanciato. Il caso migliore si verifica quando l’albero è completamente bilanciato. Il caso peggiore si verifica quando la chiave da inserire già esiste nell’albero. Il caso peggiore si verifica quando la chiave da inserire non esiste nell’albero.

Con riferimento agli alberi binari di ricerca (BST) quale delle seguenti affermazioni è vera?. Senza meccanismi aggiuntivi, un albero inizialmente bilanciato può anche sbilanciarsi a seguito di inserzioni e cancellazioni di chiavi. Un albero, una volta bilanciato, non andrebbe più modificato. Un albero inizialmente bilanciato rimane tale a prescindere da inserzioni e cancellazioni di chiavi successive. Un albero non può essere bilanciato, dipendendo il bilanciamento solo dall’ordine di inserimento delle chiavi.

Con riferimento all’operazione di “ricerca del massimo” degli alberi binari di ricerca (BST), quale delle seguenti affermazioni è vera?. Tale operazione viene effettuata percorrendo tutti i sottoalberi destri. Tale operazione viene effettuata accedendo in maniera randomica alla struttura, a partire da una foglia. Tale operazione viene effettuata percorrendo alternativamente i sottoalberi sinistri per le istanze pari (zero escluso), e destri per istanze dispari (2*n+1 escluso). Tale operazione viene effettuata percorrendo tutti i sottoalberi sinistri.

Con riferimento agli alberi binari di ricerca (BST), quale delle seguenti affermazioni è vera?. Per ottenere l’ordinamento crescente delle chiavi basta visitare l’albero con visita anticipata (detta anche visita pre-order). Per ottenere l’ordinamento crescente delle chiavi basta visitare l’albero con visita posticipata (detta anche visita post-order). Per ottenere l’ordinamento crescente delle chiavi basta visitare l’albero con visita simmetrica (detta anche visita in-order). Per ottenere l’ordinamento crescente delle chiavi basta visitare l’albero con visita per livelli (detta anche visita in ampiezza).

Con riferimento all’operazione di “visita” degli alberi binari di ricerca (BST), quale delle seguenti affermazioni è vera?. Ha una complessità lineare rispetto al numero dei nodi dell’albero. Ha una complessità lineare rispetto all’altezza dell’albero. Ha una complessità logaritmica rispetto all’altezza dell’albero. Ha una complessità logaritmica rispetto al numero dei nodi dell’albero.

Dato il grafo connesso, pesato e non orientato in figura: La lista di adiacenza corrispondente può essere antisimmetrica. La matrice di adiacenza corrispondente è simmetrica. La lista di adiacenza corrispondente può coincidere con la matrice di adiacenza. E’ sempre più efficiente calcolare la matrice di adiacenza rispetto alla lista di adiacenza.

Dato il grafo connesso, pesato e non orientato in figura, il costo totale del minimo albero ricoprente. Può assumere un solo valore, indipendentemente dal nodo di partenza. Non è calcolabile perché il grafo non è strettamente connesso. Può assumere valori diversi, a seconda dell’algoritmo usato per calcolarlo. Può assumere diversi valori, a seconda del nodo di partenza.

Dato il grafo connesso, pesato e non orientato in figura, partendo dal nodo C il minimo albero ricoprente. Non è calcolabile perché il grafo non è strettamente connesso. Può essere composto solo dagli archi: AC-AE-BC-CD. E’ unico, ma il suo valore dipende dall’algoritmo di calcolo utilizzato (per esempio Prim o Kruskal-Wallis). Non è unico, indipendentemente dall’algoritmo di calcolo (per esempio Prim o Kruskal-Wallis).

Con riferimento all’operazione di “ricerca” degli alberi binari di ricerca (BST), quale delle seguenti affermazioni è vera?. Il caso migliore si verifica quando l’albero è completamente bilanciato. Il caso migliore si verifica quando si fa partire la ricerca da un nodo foglia. Il caso migliore si verifica quando si fa partire la ricerca nel nodo radice. Il caso peggiore si verifica quando l’albero è completamente bilanciato.

In quanto tempo è possibile ricercare una chiave in un albero binario di ricerca di n elementi nel caso peggiore?. O(n^2). O(n). O(log n). O(sqrt(n)).

Dato il grafo connesso, pesato e non orientato in figura, qual è il costo totale del minimo albero ricoprente (MST)?. 7 (perché AE=1, AC=2, BC=1, CD o BD=3). 11.

Quanti modificatori di accesso conosci in java? Quali?.

quanti tipi di dato primitivi conosci in java? Quali?.

che differenza c'è tra un linguaggio di programmazione interpretato e uno compilato?.

Che strategia algoritmica adotta l'algoritmo di Huffman?.

Quale situazione rappresenta il caso medio dell'operazione di ricerca in albero binario di ricerca?.

Quale situazione rappresenta il caso peggiore dell'operazione di ricerca in un albero binario di ricerca?.

Quale situazione rappresenta il caso migliore dell'operazione di ricerca in un albero binario di ricerca?.

cosa è una espressione regolare?.