Font size
S
M
L
XL
WorksheetsASD - Fondamenti e ordinamenti
Total questions: 15
Worksheet time: 12mins
Name
Class
Date
1.
Supponiamo che f(n) sia O(g(n)). Allora:
a)
g(n) non puo' essere Ω(f(n))
b)
g(n) e' O(f(n))
c)
g(n) puo' essere O(f(n))
d)
g(n) puo' essere Ω(f(n))
2.
20n + 36 nlogn e'
a)
Θ(n2)
b)
O(n)
c)
Θ(nlog(n))
d)
o(n)
3.
Se f(n) e' Θ(g(n)) allora possiamo dire che il limite per n che va all'infinito di f(n)/g(n) =
a)
costante maggiore di 0
b)
non si puo' dire a priori
c)
piu' infinito
d)
zero
4.
Insertion-sort nel caso ottimo ha un costo computazionale
a)
O(n)
b)
O(n2)
c)
O(n log(n))
d)
o(n2)
5.
L'approccio divide et impera ha il seguente costo computazionale:
a)
sempre polinomiale
b)
sempre esponenziale
c)
dipende dal problema
d)
non si puo' dire in anticipo
6.
Quick-sort nel caso pessimo ha costo computazionale
a)
O(n log(n))
b)
O(n2)
c)
o(n2)
d)
o(n log(n))
7.
Heap-sort nel caso pessimo ha costo computazionale
a)
O(n log(n))
b)
O(n2)
c)
o(n2)
d)
o(n log(n))
8.
T(n) = 2T(n/2) + n ha soluzione
a)
T(n) = Θ(n3/2)
b)
T(n) = Θ(n log(n))
c)
T(n) = Θ(n)
d)
T(n) = Θ(log(n))
9.
T(n) = T(n/2) + 1 ha soluzione
a)
T(n) = Θ(n2)
b)
T(n) = Θ(n log(n))
c)
T(n) = Θ(n)
d)
T(n) = Θ(log(n))
10.
Che costo computazionale ha la procedura Partition usata da Quick-sort?
a)
Θ(n)
b)
Θ(1)
c)
Θ(n log(n))
d)
Θ(n2)
11.
Ricercare un numero in un vettore generico ha complessita' computazionale
a)
Θ(log(n))
b)
O(n log(n))
c)
Θ(n)
d)
Ω(n log(n))
12.
Ricercare un numero in un vettore ordinato ha complessita' computazionale
a)
Θ(log(n))
b)
O(n log(n))
c)
Θ(n)
d)
Ω(n log(n))
13.
Dato un vettore di n elementi nel quale se ne devono cercare k < log(n), conviene:
a)
fare le ricerche senza ordinare il vettore
b)
ordinare il vettore prima di fare le ricerche
c)
ordinare il vettore dopo aver fatto le ricerche
d)
ordinare il vettore mentre si fanno le ricerche
14.
Che costo computazionale ha estrarre il massimo in una priority queue implementata con una max-heap?
a)
Θ(n)
b)
Θ(1)
c)
Θ(log(n))
d)
Θ(n log(n))
15.
Che costo computazionale ha la procedura Build-heap?
a)
Θ(n)
b)
Θ(n log(n))
c)
Altro
d)
Θ(n2)
Reset
