Quiz su Algoritmi e Strutture Dati

Il termine "algoritmo"
1. è sinonimo di "programma"
2. designa una procedura che esegue una sequenza finita di operazioni
3. designa una procedura che non termina necessariamente
4. indica una formula di calcolo
L’algoritmo di ordinamento per inserimento (insertion sort)
1. è particolarmente veloce quando l’array è quasi ordinato
2. è particolarmente lento quando l’array è quasi ordinato
3. ha prestazioni indipendenti dall’ordine
4. ha complessità quadratica nel caso migliore
La somma di tutti gli interi compresi tra 1 e n
1. vale
2. vale
3. vale (n^2)/2
4. è un numero di Fibonacci
* La somma degli inversi dei primi n interi positivi, per n tendente a infinito,
1. tende a una costante.
2. diverge come log n.
3. diverge molto rapidamente.
4. non è né convergente né divergente.
* Un generatore pseudo-casuale lineare congruente
1. fornisce numeri realmente casuali
2. fornisce una lista lineare
3. fornisce una sequenza periodica
4. fornisce infiniti valori tutti differenti
Qualche calcolo! La relazione di ricorrenza f(n) = f(n – 1) + 2 f(n – 2) con f(0) = f(1) = 1 fornisce come valore di f(5)
1. 8
2. 21
3. 43
4. non si può calcolare f(5) se non viene specificato il valore di f(2)
* Un ladro cerca di aprire una cassaforte che ha un milione di possibili combinazioni numeriche. La sua particolare tecnica gli consente di stabilire se la combinazione che sta provando precede o segue, nell'ordine numerico, quella corretta. Per aprire la cassaforte avrà bisogno di provare al più circa
1. un milione di combinazioni
2. mezzo milione di combinazioni
3. 100 combinazioni
4. 20 combinazioni
I numeri di Fibonacci crescono in maniera
1. lineare
2. quadratica
3. esponenziale
4. doppiamente esponenziale
Un albero libero può essere definito come
1. un grafo aciclico
2. un grafo connesso
3. un grafo non orientato, connesso e aciclico
4. un grafo orientato aciclico
* Un albero binario con n nodi aventi 2 figli
1. ha altezza log n
2. ha altezza √n
3. ha n + 1 nodi senza figli (foglie o nodi esterni)
4. è completo
Uno heap
1. è un albero binario di ricerca
2. è un albero binario completo in cui ogni nodo (tranne la radice) ha chiave non maggiore del padre
3. è un albero binario in cui tutti i percorsi dalla radice alle foglie hanno esattamente la stessa lunghezza
4. è un array in cui ogni elemento è non minore del successivo
Uno heap
1. può essere gestito con un array
2. è un albero binario in cui ogni nodo è maggiore del figlio sinistro e minore del destro
3. ha la proprietà LIFO (Last In First Out)
4. richiede necessariamente due puntatori per ogni nodo
HeapSort è asintoticamente ottimo?
1. No, perché QuickSort è più veloce.
2. No, perché non esistono algoritmi ottimi.
3. Sì, perché ha complessità
  Theta(n lg n) nel caso migliore.
4. Sì, perché ha complessità
  O(n lg n) nel caso peggiore.
Uno heap con n elementi
1. può essere costruito in tempo logaritmico
2. può essere costruito in tempo lineare
3. richiede tempo Theta(n log n) per la costruzione
4. richiede tempo almeno quadratico per la costruzione
Una coda a priorità
1. non è altro che uno stack
2. richiede necessariamente una lista
3. ha la proprietà FIFO (First In First Out)
4. può essere realizzata con uno heap
E’ corretto dire che la complessità in tempo di Quicksort è O(n^2)?
1. sì, perché O fornisce un estremo superiore
2. no, perché la complessità nel caso medio è O(n log n)
3. no, perché la complessità è
  O(n log n)
4. occorre valutare diversi casi
Per Quicksort
1. il caso peggiore è comunque quadratico
2. la versione randomizzata ha complessità O(n log n) anche nel caso peggiore
3. la complessità è lineare se i dati sono ordinati
4. il caso medio ha complessità quadratica
Per gestire la ricorsione in quicksort
1. basta una pila di dimensione lg n.
2. occorre una pila di dimensione n.
3. occorre una pila di dimensione n^2.
4. basta l'array di input e una quantità costante di memoria aggiuntiva.
Quale delle seguenti affermazioni è vera?
1. non esistono algoritmi di ordinamento in tempo lineare
2. non esistono algoritmi di ordinamento in tempo O(n log n) nel caso peggiore
3. ogni algoritmo di ordinamento richiede almeno tempo O(n log n)
4. non esistono algoritmi di ordinamento con tempo inferiore a O(n)
Tutti gli algoritmi di ordinamento basati sui confronti
1. sono asintoticamente ottimi.
2. hanno complessità
  Omega(n lg n) nel caso peggiore.
3. hanno complessità
  O(n lg n) nel caso peggiore.
4. hanno complessità
  O(n^2) nel caso peggiore.
L'ordinamento per conteggio (counting sort) ordina in tempo lineare
1. sempre e comunque.
2. se il file è già ordinato.
3. se il valore k della chiave massima da ordinare cresce al più come n, ossia k=O(n).
4. solo se le chiavi sono in numero finito.
Radix sort ordina in tempo lineare
1. se il valore k della chiave massima da ordinare cresce al più come n, ossia k=O(n).
2. se la lunghezza delle chiavi da ordinare resta costante al crescere di n.
3. se si procede da destra a sinistra.
4. se si usa counting sort per ordinare le cifre.
L'ordinamento "a secchi" (bucket sort) ordina in tempo lineare
1. anche nel caso peggiore, se le chiavi sono ben distribuite.
2. in media.
3. solo se si crea un numero di secchi dell'ordine di n.
4. ma non si può usare se le chiavi non sono nell'intervallo [0, 1).
La determinazione del massimo in un file di n elementi
1. richiede n - 1 confronti.
2. richiede Theta(n^2) confronti.
3. richiede l'ordinamento del file.
4. richiede lo stesso numero di confronti che per determinare simultaneamente massimo e minimo.
La determinazione di una qualsiasi statistica d'ordine
1. richiede l'ordinamento del file.
2. può essere ottenuta in tempo lineare.
3. può essere ottenuta in tempo lineare soltanto in media, perché il caso peggiore è quadratico.
4. richiede il corso di CPSM, che non ho ancora seguito.
La struttura di dati "pila" (o "stack")
1. può essere realizzata facilmente con un array.
2. realizza una politica FIFO.
3. serve per gestire le chiamate non ricorsive.
4. realizza un heap.
L'uso di sentinelle
1. è altrettanto pericoloso quanto l'uso del costrutto "go to".
2. appesantisce inutilmente il codice.
3. è utile per semplificare la gestione dei casi limite.
4. rende più sicuro il codice.
La ricerca in una lista
1. richiede in ogni caso tempo lineare
2. richiede in ogni caso tempo costante
3. richiede in media tempo logaritmico
4. richiede in media tempo lineare
Per rappresentare alberi in cui ogni nodo ha un numero arbitrario di figli
1. si possono usare opportuni alberi binari
2. non si possono usare alberi binari
3. occorre usare i B-alberi
4. si possono usare solo le liste di adiacenza
Le tecniche hash
1. richiedono grandi quantità di memoria
2. hanno prestazioni che dipendono dal rapporto tra numero di scambi e numero di confronti
3. hanno prestazioni che dipendono dal rapporto tra numero delle posizioni occupate e numero delle posizioni disponibili
4. hanno prestazioni che dipendono solo dalla quantità di memoria allocata
L'indirizzamento aperto (open addressing)
1. è una tecnica di gestione della RAM
2. è una tecnica di gestione delle tabelle hash
3. è una tecnica di scansione delle liste
4. indica che un indirizzo di memoria contiene un indirizzo
Una ricerca senza successo in una tabella hash a indirizzamento aperto richiede in media 1/(1 - alfa) confronti, con alfa=n/m.
1. E' vero, nell'ipotesi di uniformità della funzione hash.
2. Impossibile: 1/(1 - alfa) tende all'infinito per alfa tendente a 1!
3. Quello è il numero di confronti nel caso peggiore.
4. Quello è il numero medio di confronti per una ricerca con successo.
La visita di un albero per livelli
1. è impossibile per ragioni di adiacenza
2. fornisce l'ordinamento dei nodi
3. fornisce un algoritmo di visita sistematica
4. è un'efficiente tecnica di ricerca
Un albero binario di ricerca con n nodi
1. ha altezza lg n
2. è un albero binario in cui ogni nodo è maggiore del figlio sinistro e minore del destro
3. può avere altezza n – 1
4. può avere altezza n lg n
L’altezza media di un albero binario di ricerca con n nodi, costruito in modo casuale, è dell’ordine di
1. log n
2. n
3. n log n
4. una costante
Nel caso peggiore, la ricerca su un albero binario di ricerca con n nodi può richiedere un numero di confronti dell’ordine di
1. log n
2. n
3. n log n
4. una costante
Le tecniche di bilanciamento degli alberi di ricerca hanno come scopo di
1. ottenere un tempo di ricerca costante
2. ottenere un tempo di ricerca al più logaritmico
3. ottenere un tempo di ricerca lineare
4. avere esattamente lo stesso numero di nodi a destra e a sinistra della radice
L'altezza di un RB-albero con n nodi interni
1. è lg n.
2. è al più 2 lg n.
3. è pari alla b-altezza.
4. è al più n/2.
Dopo l'inserimento di un nodo in un RB-albero
1. possono essere necessarie fino a 2 rotazioni.
2. possono essere necessarie anche più di 2 rotazioni.
3. basta al più una rotazione.
4. se lo zio è nero, basta ricolorare.
Le tecniche di programmazione dinamica
1. sono molto faticose per il programmatore.
2. sono più efficienti delle tecniche greedy.
3. consentono, in generale, di risolvere problemi di ottimizzazione.
4. richiedono tempo Omega(n^3).
Le tecniche greedy
1. consentono sempre di trovare una soluzione ottima.
2. trovano sempre una soluzione, che però può non essere affatto ottima.
3. servono a risolvere problemi ricorsivi.
4. come dice il nome, richiedono troppe risorse, in generale più della programmazione dinamica.
Perché far studiare i matroidi agli informatici?
1. Non l'ho mai capito.
2. Perché sono strutture matematiche eleganti e ricche.
3. Perché un problema di ottimizzazione che si possa descrivere mediante un matroide pesato ammette una soluzione greedy.
4. Perché nei problemi di ottimizzazione che si possono descrivere mediante un matroide pesato le tecniche greedy falliscono.
Il metodo degli accantonamenti per l'analisi ammortizzata
1. usa spesso il trucco di attribuire costo ammortizzato nullo alle operazioni il cui costo effettivo è di difficile determinazione.
2. determina il costo di n operazioni e poi divide per n.
3. prevede l'uso di un contatore binario.
4. accantona un potenziale per il costo effettivo.
I B-alberi
1. servono a gestire gli alberi in cui il numero dei figli non è determinato.
2. consentono di minimizzare il numero degli accessi.
3. hanno nodi in cui il numero minimo e massimo dei figli è rigorosamente fissato.
4. sono gli alberi di ricerca binaria.
L'altezza di un B-albero contenente n chiavi
1. non supera 2 lg n.
2. non supera il logaritmo in base t di n.
3. è almeno pari al logaritmo in base t di (n+1)/2.
4. non supera 3, perché il libro fa vedere che con altezza 2 già ci sono un miliardo di chiavi.
Come conseguenza di una applicazione dell'euristica della compressione dei cammini, per gestire insiemi disgiunti,
1. tutto l'albero considerato viene ridotto ad altezza 1.
2. il cammino d'accesso viene compresso e quindi occorre determinare la nuova altezza dell'albero.
3. l'altezza può ridursi, ma il rango non viene modificato: ecco perché il rango può non coincidere con l'altezza, ma essere più grande.
4. gli insiemi disgiunti vengono uniti per rango.
m operazioni su foreste di insiemi disgiunti con le euristiche di unione per rango e compressione dei cammini
1. richiedono tempo O(log m)
2. richiedono tempo lineare in m
3. richiedono tempo O(m α(m, n)), dove α(m, n) è una funzione che cresce molto lentamente con m
4. richiedono tempo quadratico in m
* La visita in ampiezza di un grafo qualsiasi, a partire da un nodo s,
1. genera un albero di visita, ma, se il grafo non è connesso, non tutti i nodi del grafo saranno nell'albero.
2. genera sempre un albero di visita ricoprente il grafo, senza escluderne alcun vertice.
3. cerca di allontanarsi prima possibile dal nodo s.
4. determina l'ordinamento topologico del grafo.
Le chiamate ricorsive di procedure
1. non possono essere eliminate
2. possono essere eliminate soltanto usando go to
3. in generale possono essere eliminate usando uno stack
4. vanno evitate a ogni costo
* Quale delle seguenti affermazioni è vera?
1. non è mai possibile accedere ai bit di un byte
2. i bit sono unità puramente concettuali
3. con il linguaggio C è facile accedere a singoli bit
4. per modificare un bit occorre usare l'Assembler

Quiz su Algoritmi e Strutture Dati

Una sola fra le risposte proposte è corretta