WorksheetsASD - Strutture dati
Total questions: 20
Worksheet time: 10mins
Name
Class
Date
1.
Una foglia di un albero e' un nodo che
a)
non ha figli
b)
non ha padre
c)
ha piu' figli di tutti gli altri nodi
d)
ha piu' fratelli di tutti gli altri nodi
2.
L'altezza h(a) di un nodo a e' data
a)
dal numero di figli del nodo a
b)
dalla distanza tra il nodo a e la radice
c)
dalla distanza massima tra il nodo a ed una foglia
d)
nessuna delle precedenti
3.
Un albero si dice binario quando
a)
non ha piu' di due nodi
b)
ogni nodo non ha piu' di due figli
c)
l'altezza dell'albero e' sempre multipla di due
d)
il numero di nodi dell'albero e' potenza di due
4.
In una coda gli elementi vengono estratti utilizzando una politica
a)
LIFO
b)
FIFO
c)
TIFO
d)
SCHIFO
5.
Ricercare un elemento in una doubly linked list ordinata costa
a)
O(n)
b)
O(log(n))
c)
O(1)
d)
O(n log(n))
6.
Perche' si implementano le liste usando le sentinelle ?
a)
perche' cosi' facendo si diminuisce il costo computazionale
b)
perche' il codice risulta piu' semplice e pulito
c)
perche' e' necessario farlo
d)
per controllare il comportamento del codice
7.
Quando si genera una collisione in una tabella hash ?
a)
quando la memoria della tabella viene esaurita
b)
quando si associa la stessa posizione nella tabella a due chiavi distinte
c)
quando due chiavi distinte hanno molti bit in comune
d)
quando la funzione hash non e' suriettiva
8.
Il load factor in una hash table e'
a)
il rapporto tra dimensione della tabella e numero di elementi contenuti nella tabella
b)
dimensione della tabella
c)
numero di elementi massimo che puo' contenere la tabella
d)
il rapporto tra il numero di elementi nella tabella e la dimensione della tabella
9.
Il costo computazionale medio per la ricerca di un elemento in una tabella hash dove le collisioni vengono gestite col chaining e'
a)
O(1 + load factor)
b)
O(1 + load factor) ma solo nel caso di simple uniform hashing
c)
O(load factor + dimensione della tabella)
d)
O(load factor + numero di elementi presenti nella tabella)
10.
Il costo computazionale per la ricerca di un elemento in una tabella hash dove le collisioni vengono gestite col chaining nel caso pessimo e'
a)
O(numero di elementi presenti nella tabella)
b)
O(1 + load factor)
c)
O(load factor + dimensione della tabella)
d)
O(load factor + numero di elementi presenti nella tabella)
11.
In una hash table con gestione delle collisioni tramite open addressing
a)
il load factor non puo' mai essere maggiore di 1
b)
il load factor non puo' mai essere minore di 1
c)
il load factor puo' anche essere maggiore di 1
d)
il load factor deve essere 1
12.
In una hash table (uniform hashing) con gestione delle collisioni tramite open addressing la lunghezza media di una probe e'
a)
1/(1 - load factor)
b)
1 + load factor
c)
load factor
d)
dimensione della tabella + 1
13.
Sia x un nodo di un albero binario di ricerca
a)
la chiave del figlio sinistro di x e' minore o uguale della chiave di x
b)
la chiave del figlio destro di x e' minore o uguale della chiave di x
c)
la chiave di x e' maggiore o uguale della chiave dei figli di x
d)
la chiave di x e' minore o uguale della chiave dei figli di x
14.
l'inserimento di un elemento in un albero binario di ricerca con n nodi di altezza h ha un costo computazionale
a)
O(n)
b)
O(log(n))
c)
O(h)
d)
O(log(h))
15.
Sia x un nodo di un albero binario di ricerca. Il successore di x e'
a)
il figlio destro di x
b)
il minimo nel sottoalbero sinistro di x
c)
il minimo nel sottoalbero destro di x
d)
il massimo del sottoalbero sinistro di x
16.
Il successore di un nodo in un albero di ricerca viene usato quando
a)
si inserisce un nodo piu' grande del massimo
b)
si cerca un nodo
c)
si cancella un nodo senza figli
d)
si cancella un nodo con due figli
17.
La funzione Find-Set(x) per insiemi disgiunti
a)
trova l'insieme x fra tutti gli insiemi disgiunti
b)
trova l'insieme x e verifica che sia disgiunto dagli altri
c)
trova l'insieme a cui appartiene l'elemento x
d)
trova l'insieme di cui x e' la radice
18.
Il rango (rank) associato ad ogni nodo x di un up-tree rappresenta
a)
il numero di figli di x
b)
il limite superiore all'altezza di x
c)
il numero complessivo di discendenti di x
d)
il numero di antenati di x
19.
Se i=log*(n)
a)
i e' tale per cui F(i) = n
b)
i e' il piu' piccolo intero tale che F(i)>= n
c)
i e' il piu' piccolo intero tale che log log ... log(n)>= 1: log ripetuto i volte
d)
i e' il piu' piccolo intero tale che log log ... log(i)<= 1: log ripetuto n volte
20.
Per un insieme di up-tree vale che
a)
per tutte le radici x di alberi: size[x] >= 2rank[x]
b)
per tutte le radici x di alberi: size[x] >= rank[x]
c)
per tutte le radici x di alberi: size[x] <= rank[x]
d)
per tutte le radici x di alberi: size[x] = rank[x]
100 %
